How to insert into sorted list of intervals?

Question

Anonymous · Accepted Answer

I failed in the details of the implementation. Provided a working O(n) solution after most of the 45 minutes elapsed. Interviewer made it clear from the beginning he wanted O(lg n), though. It's a tough thing to implement -- especially on the spot.

Mi nombre es Cristiano Ronaldo · Answer

Honestly, I'd have done a binary search tree since insertion is O(log n). But then I need more details about the problem

hivehive · Answer

The question is unclear. If the interval is already list of interval there is no way to get O(log N), because it need to scan from start to end to find the insertion point.

X

X Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches