Google

## Round 0: Online Assessment *Type:** Online Assessment *Duration:** 1 hour *Format:** 2 questions, no individual time limit per question. ### Questions: **Tree Palindrome String:** A tree with $N$ nodes is given. A character array $C$ is provided, where $C[i]$ corresponds to node $i$ in the tree. For a given node, a string is generated as follows: ``` S = Empty string makeString(u) { For all v = child of u: makeString(v) S += C[u]; } ``` Find out whether the string generated for a given node is a palindrome or not. **Maximum Tree Sum with XOR Operation:** Given a tree with $N$ nodes, an array $A$ denoting the value of each node, and a non-negative integer $K$. You can do the following at most once: Pick a node $r$ and make it the root of the tree. Pick a new node $x$ in the new tree, and XOR each node in the subtree with $K$ (Note: A subtree of a node contains the descendants of that node and the node itself). Find the maximum sum of the values of all the nodes in the whole tree possible. -- ## Round 1: Technical Interview *Type:** Technical *Duration:** 45 minutes The session started with introductions. **DSA Question:** Given an array of integers, find indices $i$ and $j$ such that $i \le j$, $a[i] = a[j]$, and the sum of the elements between and including $i$ and $j$ is maximum. **Discussion:** Initially proposed a brute force approach in $O(n^3)$. Optimized it using prefix sums to $O(n^2)$. I was asked to code this approach. The interviewer provided a hint on how to optimize the solution to $O(n)$ (likely using a Hash Map to store the first occurrence/minimum prefix sum for each value). I explained the $O(n)$ approach based on the hint and was asked to code it. Discussed edge cases before the time concluded. -- ## Round 2: Technical Interview *Type:** Technical *Duration:** 45 minutes Started with introductions. **DSA Question:** You are given $N$ people and $M$ pairs of these people. These pairs of people meet each other every day. Person $X$ is said to know person $Y$ either if $X$ meets $Y$ every day, or there exists person $Z$ such that $X$ meets $Z$ every day and $Y$ meets $Z$ every day. Find the number of pairs of people who don’t know each other. **Discussion:** Clarified doubts regarding the definition of "knowing" (transitive relationship). Identified this as a "Number of Connected Components" problem (using BFS/DFS or Disjoint Set Union). Discussed time and space complexity and coded the solution. -- ## Overall Experience A lot of importance is given to the candidate’s thinking process and communication skills. It is highly recommended to think out loud and organically arrive at the solution. Interviewers value the readability of the code, so naming variables clearly is important. The interviewers were friendly and provided helpful hints when stuck.