# Mobstack internship test

Recently gave the mobstack internship test, wasnt able to solve both the questions. Anyone has the solutions or approach for those questions? If yes, please mention them.

1 Like

No I could not solve a single questionâ€¦
Itâ€™s better to post the questions here and ask for helpâ€¦

First Question was based on LCA of the tree using binary lifting.

1 Like

Thanks for putting the question!!

I solved it using matrix exponentiation.

@vamshikrishna7 Have you solved both the qns ??

No I solved only first one

Not sure but I got the answer : (M-1)^{N-1} - (-1)^N*(M-1). Could you confirm this?

I think rooting the tree at X and finding LCA of Y_i and Z_i should work.

First one was simple, if X lies between Y and Z, then answer is X, else answer is LCA of Y and Z.
I couldnâ€™t think of second one.

For the question related to counting arrays:
I figured out something like this:

If N is odd (say N = 7) : a possible answer is 1 2 1 2 1 2 1.
So we are requiring any two numbers from 1 to M. So the number of possible arrays will be mC2.

If N is even(say N = 8) then, 1 2 3 2 3 2 3 1.
We require any three numbers from 1 to M. So the number of possible arrays will be mC3.

Plz correct me if I am wrong.

``````F(0,0)= 1
F(0,1) = 0
F(i,0) = (m-2)*F(i-1,0)+F(i-1,1)
F(i,1) = (m-1)*F(i-1,0)
ans  = m*F(n-2,1)
``````

What do u guys think about the cut off of this test ?? @invincibel , @narlax @ashish_kaur @samarth2017 and @vamshikrishna7.
I think most of the people solved only one problem so it should be 150 - 200 , tell me what do u guys think

1 Like

Yeah, it works

There were 5 openings only, canâ€™t really predict cutoff i think

Matrix Exponentiation, LCA, Binary lifting etc. I donâ€™t know any of these. @samarth2017 @predicate007 @invincibel could you please link some good online materials here (preferably YT videos)â€¦

Thank you

considering the stipend, JD and also the company nameâ€¦ these questions were overkill in my opinion (or maybe they just want to hire folks strictly on the basis of CP knowledge)â€¦

and also 25K per month for in office internship at Bangalore is a bit limited in my opinionâ€¦