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.
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.
Thanks for putting the question!!
I solved it using matrix exponentiation.
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
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…