priyanshu-panwar's blog

By priyanshu-panwar, history, 3 months ago, In English

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

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

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did you solve the xor one?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 .

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      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]

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Auto comment: 3rd question has been updated by priyanshu-panwar (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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 ?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

»
3 months ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

The questions are really good, these are my solutions:

Beautiful tree: The first question have two parts, first one is to find the ith 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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot man for giving the solutions.

    Big Help for us.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We are generating 105 values which can be easily generated in the time limit.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your code for Beautiful tree may give wrong output as it is not mentioned in the ques that the tree is a binary tree

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it +13 Vote: I do not like it

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

$$${5 \choose 0},{5 \choose 1},{5 \choose 2},{5 \choose 3},{5 \choose 4},{5 \choose 5}$$$

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.

Spoiler
»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For 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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

"Here is my O(N) solution to ZaurXOR: https://youtu.be/lccWXAd7enI
I 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!"

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 code
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Yes 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.

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like 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!!!

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 months ago, # |
  Vote: I like it -8 Vote: I do not like it

For Problem 3 — Zaurxor we 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 is xored 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???

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

1st : Beautiful Trees

My 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/02yxKnyS

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Are these questions from CodeNation CodeAgon?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?