Google

## Round 0: Written Round (Online Assessment) ### DSA Questions: 1. **Tree String Concatenation** Given a tree description ($n$ nodes from 1 to $n$ and $n-1$ edges in $(u, v)$ format), every node has a character associated with it. The string for a node is defined as: `string(u) = (concatenation of strings of all children of u) + character of u` The children of a node need to be traversed in ascending order when concatenating their strings. Given $Q$ queries where each query is a node (value between 1 and $n$), the string for that node needs to be returned. 2. **Maximum Subtree Sum after XOR** Given a tree description ($n$ nodes from 1 to $n$ and $n-1$ edges in $(u, v)$ format) and an integer $k$, you can perform an operation at most once. The operation is: - You can make any node in the tree the new root of the tree. - You can then pick any node in the new tree. - In the subtree rooted at this node, XOR the value of every node in the subtree with $k$. - Return the sum of all values of this subtree after XORing. Return the maximum possible sum obtainable by performing this operation at most once. ## Round 1: Technical Interview ### DSA Question: Buddy Strings Grouping Two strings are called buddies if the distance between adjacent characters in the strings are the same. *Example:* `acb` and `bdc` are buddies because: - `a - c` = `b - d` = -2 - `c - b` = `d - c` = 1 Given a list of strings, return a list of the groups of buddies in the list (`vector>`). Note that each group of buddies can be more than length 2 (3 or more strings can all be buddies). **My Approach:** - Algorithm: $O(nK)$ Time and $O(n)$ Space, where $n$ is the number of strings in the list and $K$ is the length of the longest string. ## Round 2: Technical Interview ### DSA Question: Run-Length Iterator Given a list of numbers (0-indexed, even length), create an Iterator Class (`Constructor`, `next()`, and `hasNext()`) that for every even index ($i$) in the list, returns the number at $i+1$ index `arr[i]` times. *Example:* `Iterator([2,3,0,1,3,5])` - `next()` -> 3 - `next()` -> 3 - `next()` -> 5 - `next()` -> 5 - `next()` -> 5 - `hasNext()` -> false - `next()` -> throw error *Note:* Need to take care of all edge cases, mainly 0 coming at the beginning and the end. **Follow-up:** Given that there is at most one 0 at an even index, when that 0 is encountered, all the numbers from the beginning need to be printed again. *Example:* `Iterator([1,4,2,3,0,1,3,5])` - `next()` -> 4 - `next()` -> 3 - `next()` -> 3 - (Encounter 0 at index 4, restart from beginning) - `next()` -> 4 - `next()` -> 3 - `next()` -> 3 - `next()` -> 5 - `next()` -> 5 - `next()` -> 5 - `hasNext()` -> false ## Experience The experience was quite nice; both interviewers were friendly and approachable. Both of them gave me hints after I told them the brute-force technique and couldn’t immediately think of an optimized approach. I needed to code on a custom Google editor and not an IDE. Dealing with incorrect indentation and the editor not completing the `}` for every `{` was a little frustrating.