Yesterday, there was a CodeNation Intern Hiring Test that got failed due to Hackerrank server down problem. But the questions are available, I snapped them in the mean time. If someone can please solve them:

**QUESTION — 1 Beautiful Tree** You are given a tree, rooted at 1, with N vertices (indexed from 1 to N). Each vertex has a value associated with it. The value of ith vertex is a[i]. Consider f[i] as the a[i]th beautiful number. A beautiful number is a positive number, whose sum of the square of its digits is less than or equal to X. You have to process M queries, where each query can be : **Query 1**- 1iy-Update a[i] = y. **Query 2**- 2i — Output the sum of for all the nodes in the sub-tree of node i (including node i), since the output can be very large, answer it modulo 998244353

**Input/Output Format** Input The first line contains N, M, and X, where N is the number of vertices, and M is the number of queries and X is the upper limit to check for a beautiful number. Each of the next N — 1 lines contains Pair of vertices representing a tree edge. i.e. Nth line having (u, v) implies u; is connected to v and vice-versa. Next Line contains N numbers denoting a[i] the value associated with ith node. Each of the next M lines will represent the query as explained above. Output For each query of type 2 answer, the sum of f[i]s in the sub-tree of node i (including node i) modulo 998244353.

**Sample Case** Input : 3 3 5 1 2 1 3 1 2 3 2 1 1 2 5 21 **Sample Output** 13 23

**Explanation** For X=5. Initial few f[i]'s are [1, 2, 10, 11, 12]

This problem went over my head. Didn't even understand it.

**Question — 2: Laser Tag!** CodeNation Fresher batch has a tradition of laser tag tournaments. In laser tag, two teams play against each other. A team can have any number of players >= 1. The two teams can have unequal team members. For successful completion of this tournament, Ipshita [our HR] wants that every person must have played against every other person, as part of different teams. Every Laser tag match takes 30 minutes to complete. Now the gaming arena has allowed Codenation to play for a maximum of X hours after which the arena closed. Given the number of folks in the batch as N, you will have to find out if Codenation will be able to finish the tournament before the complex closes? Note: Please return output as 0 or 1, 1 means tournament will successfully complete, 0 otherwise Note: Partial Points are present

**Input Format** The input contains 2 integers N and X, where N is the number of folks in the batch, and X is the number of hours they are allowed to play.

**Input** 2 1 **Sample Output** 1 **Explanation** For 2 players only 1 laser tag match is enough so 30 minutes (<= 1 hour) is enough for the tournament to end.

**Question -3 ZAURXOR**

You are given an array of integers A of size N. You perform a certain operation K times on the array A, modifying the array with every operation. The operation is to replace the array A with a new array, which is the XOR of the adjacent elements of A, and of length size(A)-1. You are given an index M, the value of this index in array A after K operations is to be found. Note: Partial points are present

**Sample Case** **Input** 4 (N) 2 (K) 1 (M) 1 2 3 4 (Array) **Sample Output** 6 **Explanation** Original Array => 1234 Operation 1 => 3 1 7 (1 XOR 2 = 3, 2 XOR 3 =1, 3 XOR 4 = 7) Operation 2 => 2 6 (3 XOR 1 = 2, 1 XOR 7 = 6) M is 1, so after 2 operations, A[1] = 6

For better visualisation of questions, I have posted article on LeetCode with better indentation, you can see the questions there: https://leetcode.com/discuss/interview-question/759851/CodeNation-Intern-Hiring-2021-Program-Questions

Please try to solve them and answer in the comment with the algo or something. THANK YOU

2nd one is quite easy . Just find ceil of log2(n) . This will be number of matches which has to be played . Multiply by 0.5 and check with the given time.

How did you solve the xor one?

Some people told me that Brute Force too worked . But if you want to go with the optimal one you have to use DP. While solving I found that one state is dependent on the other . For example 14th iteration of xor will be dependent on 6th iteration , 6th will be dependent on 2nd and 2nd is dependent on 1st . So we can solve it in klog(n) using bottom up dp easily . I have not participated in the contest as I am not the part of Munjal institute .

Brute Force didn't work out for me, it showed TLE on last few test cases. Can you draw the pattern somehow to show this up, or just write up the code once. Would be big help.

let's say a_k denotes our array after k operations

if k is a power of 2, then

mth element of a_k i.e. a_k[m]=a_0[m] ^ a_0[m+k]

else k will be equal to the sum of x and y where x is a power of 2

then a_k[m]=a_y[m] ^ a_y[m+x]

Hey how do you get to solve these type of questions so quickly. Am a noobie would be thankful for guidance.

I don't get it.. why shouldn't it be N-1 matches? I'd always break the team into 1 and N-1 no?

You have to find minimum number of matches to be played .

for n=8 , min matches should be 4 ,right?

Auto comment: 3rd question has been updated by priyanshu-panwar (previous revision, new revision, compare).Sorry for not related to the post , how to know about these contests well before ? Do we need to visit their website or we can know through hackerrank itself ?

actually, it was not an offcampus pool hiring, colleges had contacted them first, so ask your intern cell or placement cell to do it.

For third question answer: https://leetcode.com/discuss/interview-question/759687/CodeNation-Online-Coding-Assessment-Questions/633340

The questions are really good, these are my solutions:

Beautiful tree:The first question have two parts, first one is to find the i^{th}beautiful number we can use BFS, we can pre-process all the beautiful numbers in linear time. For the second part we can use the well known segtree and euler tour.code

Laser tag:It can be easily proved that making partitions of size/2 is ideal, and then we can solve it recursively, which is simply`ceil(log2(n))`

code

ZaurXOR:It can be observed that for powers of 2 solution are xor of m and m+k, therefore using it recursively, we can solve the questions.Code

Hope these help

Thanks a lot man for giving the solutions.

Big Help for us.

Sorry I might be wrong, if possible can u clear a doubt I have, as the constraints for X (for the first question) are almost 10^10 so won't doing BFS would lead to TLE?

We are generating 10

^{5}values which can be easily generated in the time limit.Your code for Beautiful tree may give wrong output as it is not mentioned in the ques that the tree is a binary tree

I haven't assumed it to be a binary tree, first I have flantend the graph using euler tour, storing in time and out time, then used this to make segment tree.

This is well known algorithm you can easily find it on web

Can you please share the code for first question again, the pastebin link above gives 404.

I have updated the links, you can check them now.

I think the Test was only for SDE-1 Role and not intern.

Are you sure ?

For Question 3

Simple/well known fact is that for any given number $$$x$$$ we know $$$xor(x,x)=0$$$,

so if we take xor of $$$x$$$ with itself an even number of times then $$$xor(x,x,x....)=0$$$,

but if we take xor of $$$x$$$ with itself odd times the result is $$$x$$$.

Notation Used- $$$xor(x,x,x...x)[k-times]=x^k$$$

Consider the simple array $$$a=1,2,3,4,5$$$

For observing the pattern assume $$$m=0$$$

So we will look only at the value $$$a[0]$$$

Performing the operation 1 time we get —

$$$a[0]=[1\cdot2]$$$

here $$$1\cdot2=xor(1,2)$$$ same notation is followed below

2nd time —

$$$a[0]=[1\cdot2^2\cdot3]$$$

3rd time —

$$$a[0]=[1\cdot2^3\cdot3^3\cdot4^1]$$$

4th time —

$$$a[0]=[1\cdot2^4\cdot3^6\cdot4^4\cdot5^1]$$$

5th time —

$$$a[0]=[1\cdot2^5\cdot 3^{10} \cdot4^{10}\cdot5^5\cdot6^1]$$$

Now observe the powers of $$$1,2,3,4,5,6$$$ which are respectively $$$1,5,10,10,5,1$$$ which helps us notice the pattern as we can now see that powers obtained after 5th time are nothing but

But how to find $$$4^{10}$$$ or $$$2^5$$$(xor-value) ? For finding the value we just need to know for any $$$k$$$, $$$i$$$ when $$${k \choose i}$$$ is even and when it is odd. or we just need to find $$${k \choose i} \% \space 2$$$ for doing this many methods are given on gfg you just need to select the appropriate method keeping in mind the time-complexity as here $$$k$$$ is the of the order of $$$10^5$$$. Some methods are given here, and here.

SpoilerFor the third question, I tried like this :

After the Kth operation, number of times we will have to xor every number of array from the Mth index will be equal to the (k+1)th row of pascal's triangle.

For example :

Let arr = [1,2,3,4,5]

k = 1 => [(1^2) , (2^3) , (3^4), (4^5)]

k = 2 => [(1^2^2^3), (2^3^3^4), (3^4^4^5)]

k = 3 => [(1^2^2^2^3^3^3^4), (2^3^3^3^4^4^4^5)]

k = 4 => [(1^2^2^2^2^3^3^3^3^3^3^4^4^4^4^5)]

Now if we observe the number of times we have to XOR every element of arr for m = 0:

row[1] = 1 0 0 0 0 (represents the array itself) (k=0)

row[2] = 1 1 0 0 0 (k=1)

row[3] = 1 2 1 0 0 (k=2)

row[4] = 1 3 3 1 0 (k=3)

row[5] = 1 4 6 4 1 (k=4)

Same pattern can be observed for all the m values.

Thus all remains is to find the (k+1)th row of pascals triangle which can be done in O(N) and if (row[k+1][i])%2 is 1 then we will take xor with the value of arr[i+m] because (a^a^a....odd number of times) = a, while (a^a^a...even number of times) = 0.

I was not able to submit the question due to server issues, so if you find anything wrong or confusing, feel free to reply.

I tried it but it will result in overflow since k can be quite large. So we need to just get the powers of 2 in the expression that will tell if it is odd or even. It worked for me.

Yes, I tried it by using lucas theorem to calculate nCr % p

Sharing my previous comment from: https://codeforces.com/blog/entry/80693?#comment-670270

"Here is my O(N) solution to ZaurXOR: https://youtu.be/lccWXAd7enII think the solution is very easy to comprehend and does not use any pattern observation etc. I have used number of paths in a graph to evaluate the answer. Basically I have developed a DP solution and optimized it using some very basic combinatorics!

"I don't think you should go that complex, Here's my approach -> we know that we are getting a pattern for the power of two, so we will find the greatest power of two that is less than k And using the pattern we will find the answer for this directly and from here we will go like brute force and find the answer. (Sorry for my bad English)

Sample codeYes Indeed this can be a much simpler way to find the answer however the real question is why does this pattern work, where does it come from ? what is the intuition ?, I have tried to answer some of them on this comment on codeforces[based on the above Youtube video], the real reason why the pattern you are using above works is related to Lucas theorem and the fact that we need $$${k \choose i} mod \space 2$$$ is why there exists a solution using bit-manipulation.

I got it

Hey... How do you get to know about these tests?? I missed Facebook HackerCup and now this. Can anyone please tell me how can I keep track of these interview tests or competitions? Plz, it would be a great help!!!

For the competitions like Facebook hackercup there are many resources. Usually someone will post a blog regarding their schedule on codeforces or codechef some days before the contest like this or you can use this website which has list of all running and future contests.

And for codenation test, most people got to know about it from their placement cell in college. So you might want to contact them for such info.

And also your friends are a great resource for these things.

For

Problem 3 — Zaurxorwe can generate the (k+1)th row/sequence in the pascal triangle which can be done in O(k) I suppose. Then slide this over the given array, for every window, the value in the sequence (for a corresponding index in array) gives the number of times the corresponding array value isxored to itself, so if it is even then xor is 0, if odd then xor is A[i] (for ith index in array).The number of elements in the final array will be n-k, obviously. Can this be done in the given time constraint???

Ohh I saw late that someone has already posted similar solution.

1st : Beautiful TreesMy approach :

(i) Push all beautiful numbers ( not more than 5x10^5 numbers, as per constraints ) in an array, generated using BFS.

(ii) Then, convert the tree to linear array, using DFS so that it's easy to access the subtree of a node, easily. If you don't know, this technique, view it here

(iii) Use a Fenwick tree (BIT) over this array for queries. View here for Fenwick tree, if you don't know about this data strcutre.

My code: https://pastebin.com/02yxKnySAre these questions from CodeNation CodeAgon?

No

For the 2nd one, shouldn't the number of matches be n-1? I proceeded by strong induction on n. For n=1 there are 0 matches which satisfies n-1=0. Let f(n)=number of matches for n players =n-1 for n<k. Now we prove it for n=k. Let in the first match, the 2 teams have x players and y players respectively, x<k and y<k and x+y=k. In this case, the total number of matches=f(x)+f(y)+1=x-1+y-1+1(by induction hypothesis)=x+y-1=k-1. So, no matter the choice of x and y, we end up with k-1 matches at best. What's wrong with this?