Google

## Online Assessment *Format:** 2 questions, not proctored. 1 hour in total. ### Questions: **Tree XOR Problem:** **Problem:** A tree is given and values are associated with each node. We are allowed to pick two nodes $x$ and $y$. The tree is to be rooted at $x$ and the node-values in the subtree of $y$ are to be XORed with a given constant $k$. Compute the maximum possible sum of all node values after picking $x, y$ and doing the XOR operation. **Solution:** Solved by precomputing the subtree sum and the XORed subtree sum with an arbitrary root and then checking all possible values of $y$. **AP Subsequence Problem:** **Problem:** We are first given $N$ queries of the type $(L, R, X)$ which means we are required to add $X$ to all array elements with indices in the range $[L, R]$. The array is of infinite length and the elements are all initially 0. We then need to compute the largest, lexicographically smallest subsequence which forms an AP (Arithmetic Progression). The common difference is given to us but the starting element can be anything. $N, D \sim 10^5$. **Solution:** Partially solved by pre-processing all the intervals to get a collection of disjoint intervals using line sweep. Then using DP on the newly obtained array to compute the largest AP. The solution failed on 2 test cases out of the roughly 10 test cases given. -- ## Interview Round A It started with the standard routine of the interviewer giving his introduction and I following with mine. He then pasted the question in the shared document: *Problem:** There are one-on-one games to be played among a group of $n$ people - each game having a clear winner and a loser. For each person, we are required to answer whether their rank within the group can be precisely determined or not. *Discussion:** I pointed out that the problem at hand can be reduced to a graph problem - more specifically a Hasse diagram. Eventually, I was able to formulate the following criterion for a node $u$ having a fixed rank: `nodes having a directed path to u + nodes reachable from u = total nodes - 1`. So the problem boiled down to computing the number of nodes reachable from a particular node and the other part would be the same quantity in the transposed graph. I mentioned this was easily doable in $O(n^2)$ using $n$ DFSes, but the interviewer didn’t seem interested in that. I tried to write a DP on the topologically sorted array, but it was counting paths and not nodes. The interviewer seemed to be convinced that a single DFS pass was all that was needed to compute the quantity for each node. I visibly struggled to wrap my head around whatever he touted as the solution and since we were out of time, the interview ended here. Later I found that counting the number of reachable nodes for every node in a DAG under quadratic time complexity is an open problem. There is an optimization using bitsets but I hadn’t mentioned it in the interview. There may be another way to solve the original problem but I haven’t been able to come up with anything yet. I had coded out the topologically sorted approach and I caught the error during a dry run. After having to pivot to a single DFS, I kept the count update logic blank as I couldn’t nail it down. -- ## Interview Round B The interviewer asked me to introduce myself and then jumped directly to the question: *Problem 1:** There are $n$ people and we are given logs of the form: "A is now friends with B". We are asked to report the first timestamp when all the $n$ people are friends with each other, either directly or through a chain of mutual friends. *Solution:** This clearly boiled down to a graph question and the connectivity check could be done using a DSU (Disjoint Set Union). I wrote out the code for the tree-based DSU and then added the path-compression trick. *Problem 2 (Follow-up):** He studied the code for a while and then modified the question. We are given a new kind of log: "A is no longer friends with B". How do we handle the same situation? He emphasized that the queries were strictly online. *Discussion:** I augmented the previous logic with a few heuristics and wrote some code to support rollbacks in the DSU, but couldn’t reduce the asymptotic complexity from $O(n^2)$.