google logo
Google· SDE II

Google L4 Phone Screen

Posted
12 Apr 2025
324 reads

Summary

I had a phone screen for an L4 role at Google where I was asked to find indices of ranges where a number lies. I was only able to provide an O(n*maxRange) approach and believe I will be rejected.

How it went

Find indices of ranges where a number lies.

ranges = {3 , 9} , {2 , 8} , {5 , 10} f(3) should return { 0 , 1} f(9) should return {0 , 2}

Bummed out because I was only able to give O(n*maxRange) approach. O(n * maxRange) for building the ArrayList[] array during the initialization and doing each query in O(1) time

maxRange being the maximum value of right - left in a range {left , right}

After the interview was able to figure out it would probably be solved by Segment Tree, which I did not study :(

I think I'll be rejected.

Questions asked (1)

  1. 01

    Find Indices of Ranges Where a Number Lies

    Data Structures & Algorithms

    Given a list of ranges, for example ranges = {{3, 9}, {2, 8}, {5, 10}}, and a query number x, return the indices of all ranges i such that ranges[i][0] <= x <= ranges[i][1].

    Example: f(3) should return {0, 1} (since 3 is in {3,9} and {2,8}) f(9) should return {0, 2} (since 9 is in {3,9} and {5,10})

How they prepared

I realized after the interview that the problem could likely be solved with a Segment Tree, which I had not studied.

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!