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…