dunjen_master's blog

Codenation Hiring Test 2020
By dunjen_master, history, 5 years ago, In English

Can somebody explain their solutions to problems-

1) Promotion Game 2) Count Diameters

  • Vote: I like it
  • -8
  • Vote: I do not like it

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

2)Count Diameters

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

    Oh shit !!

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

    Did you submit and get the testcases right?

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

    Suppose the graph looks like this

    5 3 1 3 5 5 4 5 2

    • $$$k=1$$$ There are $$$4$$$ diameters
    • $$$k=2$$$ There are $$$4$$$ diameters
    • $$$k=3$$$ There are $$$2$$$ diameters
    • $$$k=4$$$ There are $$$0$$$ diameters

    Can someone please explain why this is wrong ?

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

      I also had a stupid bug. After fixing my code gives these graphs

      • k=1 There are 4 diameters (1,3), (3,5), (4,5), (2,5)
      • k=2 There are 5 diameters (1,3,5), (3,5,4), (3,5,4,1), (3,5,2), (2,5,4)
      • k=3 There are 3 diameters (1,2,3,4,5), (1,3,5,4), (1,3,5,2)
      • k=4 There are 0 diameters
      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh thanks ! I understand my mistake. I was counting diameters but we should be counting subgraphs !

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

Promotion Game — Stirling numbers of the first kind (https://oeis.org/A000254). This gives p. q is n!

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

    And is $$$summation(1/i)$$$ for all i from 1 to n . Can anyone prove????

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

How did you get to know about the test through some website or anything..?

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

How did you solve the string question?

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

    Dp with states (i,j,k) representing answer for substring from l to r with k being the last taken alphabet, as there are 26n² states and each state can be computed in constant time, the overall run time was 26n².

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

      what is wrong in it?

      static int f(int left,int right,int last,char a[]){
        if(dp[left][right][last]!=null)return dp[left][right][last];
        if(left>=right)return dp[left][right][last]=0;
        if(a[left]!=a[right]){
            return dp[left][right][last]=Math.max(f(left+1,right,last,a),f(left,right-1,last,a));
        }
        else{
            if(last!=a[left]-'a'){
                int temp=2+f(left+1,right-1,a[left]-'a',a);
                temp=Math.max(temp,Math.max(f(left+1,right,last,a),f(left,right-1,last,a)));
                return dp[left][right][last]=temp;
            }
            else{
                return dp[left][right][last]=Math.max(f(left+1,right,last,a),f(left,right-1,last,a));
            }
        }
    }
      → Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Had you written a brute force and searched oeis, the solution of promotion game was <10 Lines of code

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

For string question- Take two pointers let's say i and j representing the points in the string where i<=j Now if s[i] is equal to s[j] we can take them only if the last character we took is not equal to s[i], this is because of the condition that Xi =/= Xi+1. Thus along with i and j we need to remember the last character we took. Thus in this case ans= 2+ f(i+1,j-1,s[i]) If s[i] =/= s[j] we need to take maximum by increasing i or decreasing j that is, ans=max( f(i+1,j,last_ch) , f(i,j-1,last_ch) )

ans=f(0,n-1,26) , ['a'-'z']=[0-25]

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

Any idea when they call for further rounds and what will the cutoff in this test?

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

How many questions did you solved? I was able to solve 1st, promotion game and partial for count diameters.

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

The content was great.

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

Hey, how come some of the comments mention "googling" the problems? Isn't it forbidden to use Internet resources in this?

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

    Nope it wasn't this time.

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

      I remember there was a check box before starting the test on HackerRank that said only language reference and IDE with auto-completion are allowed?

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

Can You please Provide the question statements for the same...

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

did anyone give today's hiring test?

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

    Yes, did war one. What about you?

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

      I did the cubes one, and I passed 12 test cases/15 in the metrices problem. What was your approach for War?

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

        I was only shown 1 sample test and 4 hidden tests which my solution passed for B. How were you able to see the 12/15 thing? Btw I used binary search to find the answer in B and used prefix array in the check function. What should be the cutoff according to you?

        → Reply