I interviewed for Google L4 a few months ago and got rejected after the onsite coding rounds. Sharing it here as a reference for anyone coming after me.
R1: Merge two nodes (each node has three fields: name, value, children). The core rule is to use t1's node order but t2's node values. 1. In the merged node, name comes from t1 and value comes from t2. 2. Children with the same name are matched one-to-one in order of appearance and merged. 3. All of t1's children keep their original order. 4. Children of t1 that have no match stay unchanged. 5. Children of t2 that have no match are appended at the end in their original order.
The problem statement was really long and the example format was a bit odd, so my understanding was slightly off at the start. Halfway through writing, the interviewer pointed out a detail I had misunderstood and I had to change my algorithm on the spot. In the end I left one small bug, but they still let me pass this round.
R2.1: This is the same problem as R2.2 in another thread here. I didn't know the segment tree approach during the interview. I first came up with an approach close to the optimal one, but when I started writing it I hadn't figured out how to store the intermediate state of the modifications, so I ended up degrading to a brute-force solution, and that got me failed. Also, a complaint: the computer at the Google onsite was really hard to use, and they didn't prepare any scratch paper or pens in advance for drafting and thinking things through. I only remembered this when half the time was already gone, because I was so nervous.
R2.2: This was the Employee Shift Timeline Table problem from Hack2Hire. I think I passed this one.
Discussion
Loading comments…