Google | Phone Screen | L4 | Reject
Summary
I had a phone screen with Google for an L4 position and unfortunately, I was rejected. The interview focused on designing a custom data structure for a string-based binary tree and a follow-up to find the Nth character.
Full Experience
I recently had a phone screen interview with Google for an L4 position. The interviewer presented a rather unique problem involving a string broken into multiple substrings, represented as a binary tree. Each external node contained a string and a data field, while internal nodes held a numerical value which was the sum of its children's data fields. For instance, if the left child had a data field of 5 and the right child 7, the internal node would show 12. There was an example provided, showing how 'APPLEPIEBANANA' could be structured this way. My primary task was to design a data structure to represent this tree. I opted to create a base Node class, with InternalNode and ExternalNode inheriting from it. The interviewer seemed content with my approach. As a follow-up, I was asked to find the Nth character in the complete string. For this, I implemented a recursive function that navigated through the tree, using a count variable, allowing me to solve it in O(height of tree) time. Despite my efforts, I received a rejection.
Interview Questions (2)
A string can be broken into multiple strings and represented as a binary tree where each external node contains a string and a data field and each internal node in the tree contains a numerical value that is the sum of the data fields of its left and right child nodes. For example, if the left child has a data field of 5 and the right child has a data field of 7, the internal node would contain the sum of these values, 12.
Example: 
So, here the complete string would be APPLEPIEBANANA
Question: Design a data structure that could represent the above tree.
Follow up: Find the Nth character in the string represented by the tree.