Google L3 onsite experience
Summary
I recently completed an onsite interview at Google for an L3 position. The experience involved three distinct technical rounds, each presenting a challenging coding problem focused on data structures and string manipulation.
Full Experience
I had an insightful onsite interview experience with Google for an L3 position, which was structured into three main coding rounds.
First onsite:
This round focused on data structure design. I was tasked with implementing a restaurant waitlist. The key requirements were to allow parties to join, leave, and to serve the first suitable party based on available table size. This required careful consideration of efficient insertion, deletion, and search operations, likely involving a combination of data structures like a min-heap or priority queue along with a hash map for quick lookups.
Second onsite:
The second challenge involved string manipulation and parsing. I was given a formula of letters with parentheses and asked to simplify it by removing the parentheses, ensuring correct sign propagation and handling nested structures. This problem tested my ability to manage state during string traversal, possibly using a stack-based approach to keep track of current signs and parenthesis levels. Examples like a-(b+c) -> a-b-c and a-(a-b) -> b were provided to clarify the expected behavior.
Third Onsite:
The final coding round was another complex string parsing problem: decompressing an encoded string. The encoding involved repeating groups of characters within parentheses, with the repetition count specified in curly braces, and supporting nested parentheses. For instance, a(bcd){3}e should become abcdbcdbcde, and a(bc(d){4}e){3}f should expand to abcddddebcddddebcddddef. This was a classic stack-based string decoding problem, demanding careful handling of nested structures and repetition counts.
Interview Questions (3)
Implement a restaurant waitlist data structure. It should support the following features:
1. A party of customers can join the waitlist.
2. A previously joined party can leave the waitlist at any time.
3. The restaurant serves the first party whose size fits the empty table size at a time (a table size is given as an argument).
Given a formula of letters with parentheses, return a simplified equivalent version of the formula without parentheses. Also handle nested parentheses.
Examples:a-(b+c) -> a-b-ca-(a-b) -> b
Write a function to decompress a string from an encoded format. A group of characters surrounded by parentheses should be repeated by the number in the following curly braces. Note that the parentheses can be nested.
For example:"a(bcd){3}e" -> "abcdbcdbcde""a(bc(d){4}e){3}f"-> "abcddddebcddddebcddddef"