When you need order too

A hash map answers "is t a key" and nothing else about t. Ask it for the nearest key below t and it must look at every key it holds: hashing scatters keys to keep buckets evenly loaded, and the ordering is not hidden by that, it is gone.

That makes four common questions unanswerable in better than O(n):

• predecessor — the largest key ≤ t
• successor — the smallest key ≥ t
• range — the keys, or the sum of the values, in [lo, hi]
• rank and ordered iteration — the k-th smallest, or everything in order

Each costs a full scan. With 10⁵ keys and 10⁵ queries that is 10⁵ × 10⁵ = 10¹⁰ operations, about 100 seconds at 10⁸ operations per second — the same wall that complexity by counting puts on any quadratic solution at that size.

The booking calendar

One room. Each booking is a half-open interval [start, end). A new booking is accepted only if it overlaps nothing already on the calendar.

The naive check compares the newcomer against all n existing bookings. But overlap is a local property: sort by start and only two bookings can possibly conflict with [s, e) — the latest booking starting at or before s (does its end run past s?) and the earliest booking starting after s (does e run past its start?). Everything else is separated by one of those two.

So the operation the calendar actually needs is the predecessor query, and a dict keyed by start gives you O(1) answers to a question nobody asked: "is there a booking that starts at exactly 13:40."

A predecessor query answered by binary search over sorted starts, and unanswerable over the same keys in bucket order100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

Sorted list plus bisect

Keep the starts in a sorted list and a parallel list of ends.

import bisect

class Calendar:
    def __init__(self):
        self.starts = []          # kept sorted
        self.ends = []            # same order as starts

    def book(self, s, e):
        i = bisect.bisect_right(self.starts, s)   # first booking starting after s
        if i > 0 and self.ends[i - 1] > s:        # predecessor still running at s
            return False
        if i < len(self.starts) and e > self.starts[i]:   # successor starts before e
            return False
        self.starts.insert(i, s)
        self.ends.insert(i, e)
        return True

bisect_right returns the count of keys ≤ s, which makes it both queries at once: starts[i - 1] is the predecessor, the largest key ≤ s, and starts[i] is the first key strictly after s — which is what the overlap check wants, and not the ≥ successor defined above. When s is itself a key, the smallest key ≥ s is s, and landing on that takes bisect_left. That index is the same boundary discipline as binary search boundaries — i is a position between elements, not an element.

The search is 17 comparisons at n = 10⁵, since log₂(10⁵) ≈ 17. The insert is where the honesty is required.

Costing the insert

A Python list is a contiguous array of pointers, so insert in the middle memmoves the tail. Assume 8 bytes per slot and roughly 10 GB/s for a block move:

• an insert into a list already holding m entries moves m / 2 slots on average
• the calendar starts empty, so the run totals the sum of m / 2 over m = 1 … n, which is n² / 4, not n² / 2 — pricing every insert at the final size doubles the answer
• at n = 10⁵: 2.5 × 10⁹ slots × 8 bytes = 20 GB ÷ 10 GB/s ≈ 2 seconds

Survivable. At n = 10⁶ the average insert at full size moves 4 MB, the build moves about 2 TB, and you are at roughly 200 seconds. The crossover sits near 10⁵, which is why "bisect into a list" is the right answer more often than its O(n) insert suggests: memmove costs perhaps a hundredth of a Python-level loop step, so the quadratic term carries a tiny constant. Say it that way; do not call the whole thing O(log n).

When a tree is the real answer

A balanced binary search tree (red–black, AVL) or a skip list gives O(log n) insert, delete, predecessor, successor and in-order iteration, with no hidden block move. Python ships neither, so in an interview you have three honest moves, in the order you should consider them:

1. The keys are all known before the queries. Sort once, replace each key by its rank, and put a Fenwick tree or segment tree over the ranks. Everything becomes O(log n) with small constants and no insertion cost at all — the strongest answer whenever the problem is offline, and routinely missed.
2. You only ever need one end. The smallest, the largest, the k-th largest so far — that is a heap, O(log n) push and pop, O(1) peek, and it does not pretend to order anything in between. See the heap invariant before reaching past it.
3. Neither holds. Say "a balanced BST or an ordered container, O(log n) per operation", implement with bisect, and name the O(n) insert. That is accepted almost everywhere: the interviewer is testing whether you know what you pay.

The cost table

operation	hash map	sorted list + bisect	balanced tree / skip list	Fenwick over ranks
lookup by key	O(1) avg	O(log n)	O(log n)	O(log n)
insert	O(1) avg	O(log n) + O(n) shift	O(log n)	O(log n)
delete	O(1) avg	O(log n) + O(n) shift	O(log n)	O(log n)
predecessor / successor	O(n)	O(log n)	O(log n)	O(log n)
count in a range	O(n)	O(log n)	O(log n)	O(log n)
sum in a range	O(n)	O(n)	O(log n), with subtree sums	O(log n)
k-th smallest	O(n log n) sorting, O(n) expected quickselect	O(1)	O(log n), with subtree sizes	O(log n)
iterate in order	O(n log n)	O(n)	O(n)	O(n)

The hash-map column is what what a hash map buys you is about: it wins the first three rows, the ones that name a single key, and loses the five below them outright. The range rows split because a sorted list holds keys, not aggregates — a count is the gap between two bisects, but a sum must walk the k values in the range unless a prefix-sum array carries it, and that array costs O(n) to repair on every insert. That row is why the Fenwick column is here.

The rule for choosing

Choose by the question, not by the data.

• Only membership and counts → hash map. Nothing competes on constant factor.
• Neighbours or ranges, with fewer than about 10⁵ mutations → sorted list with bisect, and say the insert is O(n) and why that is still fine here.
• More mutations than that, or ordered iteration interleaved with updates → balanced tree or skip list.
• All keys known up front → ranks plus a Fenwick tree.
• Only the extreme → heap.

The case that catches people is needing two at once: "O(1) lookup by id, and always know the least recently used". One structure will not do it. You keep a dict from id to a node inside an ordered structure and pay to keep the two consistent. Say that rather than bending one container into both — the pairing is the answer.

In an interview

What is being tested is whether you notice that the question is about neighbourhood rather than membership. The tell is any of: "the nearest", "before", "after", "between", "the k-th", "in order".

The sentence: "Membership would be O(1) with a dict, but this asks for the latest start before t, which a hash map cannot answer without scanning all n. I want an ordered structure — bisect over a sorted list at this input size, a balanced BST if insertions dominate."

The mistake that loses points: claiming O(log n) for a solution that calls list.insert in the loop. Name the O(n) shift, bound it with the arithmetic, and conclude. A candidate who prices the term scores above one who omits it, and well above one caught by the follow-up.

Check yourself

10⁵ bookings arrive one at a time and each must be checked against the existing ones. dict, sorted list, or tree — and what does your pick cost?

Sorted list with bisect. Each check is about 17 comparisons; the list grows from empty, so the run moves n² / 4 slots × 8 bytes ≈ 20 GB, about 2 seconds at 10 GB/s. Acceptable. A dict cannot answer the predecessor query at all without an O(n) scan, which is 10¹⁰ operations over the whole run.

Queries and insertions are interleaved, you need the count of keys in [lo, hi], and n = 10⁶. What changes?

The sorted list's range count is still two bisects, O(log n) — the counting was never the problem. The inserts are: 10⁶ of them move about 2 TB, roughly 200 seconds. If every key is known in advance, compress to ranks and use a Fenwick tree; if they are not, you need a balanced tree.

Your dict happens to iterate in sorted order on your test input. Can you rely on it?

No. Python dicts iterate in insertion order, and it matched sorted order because you happened to insert in sorted order. Any other input silently returns a different order — a bug with no exception attached to it.