Блог пользователя priyanshu-panwar

Автор priyanshu-panwar, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How did you solve the xor one?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 .

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

      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]

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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 ?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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
»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!"

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      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.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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!!!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Are these questions from CodeNation CodeAgon?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится