Three Questions were given Link CodeNation CNIL Recruitment test 2020
I was not able to solve any one, the second one was partially solved using LCS. Can anyone explain or give hints or solutions of these three problems. Especially the second one cause a similar question that was asked in Google FTE Hiring a few days back and I was able to partially solve it by LCS. Thanks for the help.
1.String Reduction - can be solved using stack Link
2.It can be solved using LCS [ When one array has distinct elements, you can consider index of each element as its value and find LIS in both arrays , LIS will be equal to LCS ] (nlogn)
3.Cumulative summation for 32 bits
can u plz explain the solution to 3rd question a bit more
make a (n+1)*32 table then table[a][i] - table[b-1][i] gives you the count of numbers in [a,b] which have ith bit set, if this is equal to b-a+1 then this bit will be set in the AND of the subarray [a,b] .
Everything else is bruteforce.
1 Like
can you elaborate on 2nd one.
The whole problem was based on finding LCS in O(nlogn)
Array1 : 5 6 4 2 15 (distinct elements)
Array2: 9 3 5 4 6 2 11 15
Use array 1 indexes as values
m[5] = 1
m[6] = 2
m[4] = 3
m[2] = 4
m[15] = 5
Now transform the second array, remove those which are not common in both arrays
Array2: 9 3 5 4 6 2 11 15
Tarr2 : _ _ 1 3 2 4 _ 5
Now find LIS of Tarr2 in nlogn that will LCS.
1 Like
Thanks a lot. Wow I didn’t know this approach
Where did you register for the contest?
3rd question can be done easily using sparse table
Did you get the final offer?
It was an on campus test.
Sometimes, I really regret two failures in JEE. Btw thanks for answering
Same here bro. I feel you.
It was on campus test. No one from my college was able to crack even first round.
Hey man you can have a look at this video , here he explained approach to all 3 questions…
1 Like
Yes but only after watching a YouTuber solve that problem 
I didn’t give the test.
Don’t need to dude, no one in our batch was able to perform good so they didn’t even selected anyone for interview, in the end what matters is your skills in cp.
2 Likes
Did you also have the test on 1st August?
Yes ,but i did poorly in it as it was my first experience giving such kind of test 