I have questions about the following problems from one of the hiring tests of CodeNation:
Problem 1 : Given a tree, find number of subgraphs of the tree which have diameter equal to x. Print answer for all x. 1 <= x <= N. Constraints : 2 <= N <= 20
My question : Since N <= 20, can't we just try all possible sub graphs and find their diameters? I was thinking O(2^N * N) complexity should work with such small N? I also thought of some kind of a solution for a little larger N though.
Problem 2 : N men pick elements from a bag of N distinct elements. Each man pick a element one by one. If a man picks an element that is greater than all the previous picked element, then we say that this man is promoted. Each element is equi-probable to be picked. Find the expected value of promoted men. Print answer in pq^-1 mod M form. 1 <= N <= 1e5. N is the only given input.
For Example : if N = 2, then bag can contain (1, 2). All combinations are (1, 2) and (2, 1). In (1, 2) , 1 and 2 both get promoted. In (2, 1) , only 2 get promoted. Answer for N = 2 is hence 1*(1/2) + 2*(1/2) = 3/2
My question : How to approach and solve this problem? I feel like there are many ways to approach expected value problems and I got confused as to which direction to think in.
For problem 2 :
https://math.stackexchange.com/questions/3374946/expected-number-of-balls-chosen-from-bag-i-throw-out-everything-in-the-bag-with
E(n) = 1 + (sum of E(k) for k = 1 to n-1)/n
Will this be right :-
Let a[x] : summation of (n-1)Cr * (r+1) where r is from 0 to n-1 (n>=2 and a[1]=1)andAnswer is (a[1]+...a[n])/n???It'll be good if you could explain why you feel this is the correct answer.
It's hard for anyone to help you without knowing the intuition behind your recurrence.
Thank you.
I don't understand how in the discussion forum at stackexchange they arrived at the recursion though. It would be of great help if someone is able to explain that a little clearer.
Sure, no problem.
Initially you have N balls in the bag.
With 1/N probability I can pick the smallest ball. Similarly for the 2nd smallest ball there is 1/N chance and so on.
E(N) = 1/N*(1 + E(N-1)) + 1/N*(1 + E(N-2)) + .. + 1/N*(1+E(0))
If Initially I picked the smallest ball I'll be left with N-1 useful balls same way if I picked the largest , I'll be left with 0 useful balls.
That +1 everywhere is because of the person getting promoted because of the current ball draw.
x1/N represents the chance of a particular outcome i.e. chance of picking a particular ball.
Hope this helps.
Thank you
can u share link to similiar problem they had asked about the string problem,where we had to find longest even palindromic subsequence i guess,i need to practice that kind of problem??
Link 1
And
Link 2
Is there any chances of getting a call after solving only 2 problems ?
Not to break your hopes but I'm guessing a lot of people solved all 4 problems. Still, I'd be happy if you get selected :)
Haha !! Never mind. I know that I haven't performed well this time but have certainly improved a lot from the last Hiring Contest(Codeagon). Will expect to improve afterwards. Thanks anyways :)
That's the spirit brother!
For problem 1: I think it should work, but you have to drop cases which would compose disconnected tree graph, by this you will reduce runtime a lot.
Thank you. I believe some people did submit the brute force solution and got it right without any optimizations even.
Yup, bruteforce solution was passing all the test cases without any optimization.
For the second problem formula for promoted men is f(n)=n!/2+n*(f(n-1)), where n>1,f(1)=1; so p=f(n) && q=n!
Did anyone receive a call for an interview?
If yes then how many did they solve?