How to insert into sorted list of intervals?

Question

Sigiloso · 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

Pergunta de entrevista da empresa X

Respostas da entrevista

Empresas seguidas

Buscas de vagas