google logo
Google· SDE II

Google L4 Phone Screen Round (US)

Location
US
Posted
22 May 2025
340 reads

Summary

I had a phone screen round for Google L4 in the US, where I solved a binary tree pathfinding problem, and I cleared the round.

How it went

Given 2 numbers and an unsorted binary tree, find the path between them and return it as a string with the words "up", "right" and "left"

       1
     /  \
    2    7 
   / \
  8   6
 /
5

Path(root, 6, 7) -> "up, up, right"
Path(root, 7, 8) -> "up, left, left"
Path(root, 5, 6) -> "up, up, left"

I asked the following questions:

  • are the node values unique? Yes
  • Will both nodes be always present in tree? Yes

Solved it using the following approach:

  1. Find LCA node between the two nodes.
  2. A path function that will record L/R from LCA node to first node.
  3. Same path function that will record L/R from LCA node to second node.
  4. Form the answer string a. place all "up" strings for path from LCA to start node b. append the recorded path from LCA to end node

Interviewer asked if I can optimise and decrease the traversals, as I was traversing the tree thrice. But couldn't think well in that interview setting.

EDIT: Cleared the phone screen round. Moving Onward

Questions asked (1)

  1. 01

    Find Path Between Two Nodes in Binary Tree

    Data Structures & Algorithms · Medium

    Given 2 numbers and an unsorted binary tree, find the path between them and return it as a string with the words "up", "right" and "left"

           1
         /  \
        2    7 
       / \
      8   6
     /
    5
    
    Path(root, 6, 7) -> "up, up, right"
    Path(root, 7, 8) -> "up, left, left"
    Path(root, 5, 6) -> "up, up, left"
    

    I asked the following questions:

    • are the node values unique? Yes
    • Will both nodes be always present in tree? Yes

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!