Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
in Interview-Experiences by Expert (30,360 points) | 622 views

1 Answer

0 like 0 dislike

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.


For more interview experiences check the below link
by Expert (30,360 points)

Get best answers to any doubt/query/question related to programming , jobs, gate, internships and tech-companies. Feel free to ask a question and you will receive the best advice/suggestion related to anything you ask about software-engineering , development and programming problems .