Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Introduction to Ordered Set Pattern

You are booking meeting rooms. Bookings arrive one at a time, and each one must not clash with any booking already accepted.

booked:  [10, 20)  [30, 40)
new:     [15, 25)   clashes with [10, 20)
new:     [25, 30)   fits

Checking a new booking against every accepted one costs O(N). After N bookings that is O(N²).

A hash set does not help. It answers "is this exact value present" and nothing more. The question here is different. It asks which booking starts just before the new one, and which starts just after. Only those two can clash.

.....

.....

.....

Like the course? Get enrolled and start learning!
L

Lee

· 2 years ago

Yes, it is "ordered" but the time complexities are N or NlogN. Not correct at all. Does not employ a tree.

Show 1 reply
Spencer Lan

Spencer Lan

· 7 months ago

Am I wrong or does the code not utilize a TreeSet or Tree structure at all?

Show 1 reply
M

mailman14736

· a month ago

Hilariously bad implementation, use AI or something to generate better code - this implementation does not have the time/space complexity that you describe below it.....