Hi,
I received the following interview question in Phone screen of Uber for Senior Software Engineer position.
When Provided a list of intervals, return the list of intervals that occurs maximum number of times inside other intervals. The interval should be completely contained inside the other, (x,y)
Ex: Input -> [1,12],[2,6],[3,5], [4,4],[5,6]
Output -> [4,4] occurs in 3 times inside [1,12],[2,6],[3,5]
Ex: Input -> [1,12],[2,6],[3,5], [4,4],[5,6], [5,6]
Output -> [4,4] or [5,6] Both of them occurs three times inside others. There is a pair of [5,6], so each appear within the other
My solution:
Sort the inputs first by Y (Second element) and then by X (first element).
Then for each pair,
do binary search of the format [X, float('-inf')] -> Left index
Binary search on [Y, float('-inf')] -> Right index
Search all the intervals between the left and right index from Step 2, loop through them to see whether the interval is completely contained within them.
Compare the number of occurance to the exiting maximum occurance. If greater, replace maximum else discard.
To avoid N^2. When a single interval appearing N times, each time we can check whether the difference between left_index and right_index is greater than exiting maxiumum, else dont run the inner loop.
I was rejected. But, I would like to know what you folks think about my solution and your way of approach and your solution.
Thanks
For more interview experiences check the below link
https://interview.desiqna.in/