dunjen_master's blog

Codenation Hiring Test 2020
By dunjen_master, history, 6 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?
»
6 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

2)Count Diameters

Spoiler
→ Reply
»
6 years ago, hide # |
← 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
»
6 years ago, hide # |
 
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
»
6 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

How did you solve the string question?

→ Reply
  • »
    »
    6 years ago, hide # ^ |
     
    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
    • »
      »
      »
      6 years ago, hide # ^ |
      ← 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
»
6 years ago, hide # |
 
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
»
6 years ago, hide # |
 
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
»
6 years ago, hide # |
 
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
»
6 years ago, hide # |
 
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
»
6 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

The content was great.

→ Reply
»
6 years ago, hide # |
 
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
»
6 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

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

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

did anyone give today's hiring test?

→ Reply