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.

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 ?

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

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

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.

int main()
{
    int parity[k + 1];

    //compute parity of (k)C(j)for j=0 to k

    int ans = 0;
    int j = 0;
    for (i = m; i <= k + m; i++)
    {
        //if (k)C(j) is odd then xor it with
        //answer othwerwise not
        if (parity[j] == 1)
            ans = ans ^ a[i];
        j++;
    }
}

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.

Sharing my previous comment from: https://codeforces.me/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!"

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

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

Are these questions from CodeNation CodeAgon?

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?

Here are some questions which are asked in CNIL 2020 https://codeforcompany.blogspot.com/2020/08/codenation-cnil-recruitment-test-2020.html