Google L4 Phone Screen
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.
Full Experience
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.
Interview Questions (1)
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})
Preparation Tips
I realized after the interview that the problem could likely be solved with a Segment Tree, which I had not studied.