iprakhar22's blog

CodeNation Hiring Test Problems
By iprakhar22, history, 5 years ago, In English

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.

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (17)
| Write comment?
»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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) and Answer is (a[1]+...a[n])/n ???

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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??

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Is there any chances of getting a call after solving only 2 problems ?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :)

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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 :)

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you. I believe some people did submit the brute force solution and got it right without any optimizations even.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yup, bruteforce solution was passing all the test cases without any optimization.

      → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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!

→ Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Did anyone receive a call for an interview?
If yes then how many did they solve?

→ Reply