Google | Phone Screen | L4 | Reject

Result
Rejected
Posted
6 Nov 2024
370 reads

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.

How it went

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.

Questions asked (2)

  1. 01

    Design String Binary Tree Data Structure

    Data Structures & Algorithms

    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: Tree Example
    So, here the complete string would be APPLEPIEBANANA

    Question: Design a data structure that could represent the above tree.

  2. 02

    Find Nth Character in String Binary Tree

    Data Structures & Algorithms

    Follow up: Find the Nth character in the string represented by the tree.

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Google recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!