Google Interview Question: Can You Make This Lookup O(1)?

Tiny interval problem, three working approaches, and the memory bill hiding behind constant time.

You have a correct solution. You can explain the loop, handle the endpoints, and tell the interviewer exactly why it works. Then comes the follow-up that makes an otherwise pleasant question feel personal: can the lookup be faster?

Of course we want to say yes. Ideally with a clever data structure and absolutely no awkward silence.

But this is where I prefer to slow down for one question of my own: faster at the expense of what?

This interval-membership problem was reported as a Google interview question. You can read the full prompt without an unlock. Here is how I would work through it, using our own example and implementation.

By the end, you will have a working binary-search version, an honest constant-time alternative, and a way to choose between them without treating Big O like a leaderboard.

Start with three intervals and one very ordinary question

Our class supports addNonOverlappingInterval(start, end) and contains(x). Insert a closed interval, then ask whether a number belongs to any stored interval.

Use these intervals: [2, 5], [9, 12], [20, 24]. Now contains(10) is true, contains(7) is false, and contains(5) is true because both endpoints count.

The prompt guarantees valid, non-overlapping insertions. Keep that guarantee visible. If we later remove it, part of our reasoning will stop working.

For the worked implementation, coordinates are integers, adjacent intervals stay separate, and calls happen one at a time. Intervals [2, 5] and [6, 8] may coexist. Intervals [2, 5] and [5, 8] overlap at 5 and violate our contract.

Before choosing a structure, ask how many queries happen between insertions and how large the coordinate domain can be. Those answers will do more useful work than reaching for the fanciest tree you remember.

Keep the boring solution long enough to understand it

An unsorted list is a perfectly good starting point. Append each interval. For a query, inspect every pair until start <= x <= end, or return false after checking them all.

With n intervals, that is an O(n) query, amortized O(1) append, and O(n) storage. Cheap insertion depends on trusting the non-overlap guarantee; validating arbitrary input would require additional work.

I like keeping this version on the page because it gives us a simple reference answer. Every clever version still has to agree with that plain membership rule. We are improving the way we find the answer, not negotiating a new definition of correct.

Binary search gets us down to one candidate

Sort the intervals by their start. For a query x, find the last interval whose start is less than or equal to x. Then check its end.

For 10, that candidate is [9, 12], and 10 fits. For 7, the candidate is [2, 5], and 7 is already past its end.

Here is the reason we can stop after that one check. Every later interval starts after our query. Every earlier interval ends before the candidate begins, because the intervals do not overlap. Neither group can rescue a failed candidate.

That explanation is worth practising aloud. Naming binary search is easy; explaining why one interval is enough is the part that shows you understand the problem.

This small Python class keeps matching arrays of starts and ends. Its insertion method trusts the prompt’s non-overlap guarantee.

from bisect import bisect_left, bisect_right
class IntervalIndex:
    def __init__(self):
        self.starts = []
        self.ends = []
    def addNonOverlappingInterval(self, start, end):
        if start > end:
            raise ValueError('start must not exceed end')
        i = bisect_left(self.starts, start)
        self.starts.insert(i, start)
        self.ends.insert(i, end)
    def contains(self, x):
        i = bisect_right(self.starts, x) - 1
        return i >= 0 and x <= self.ends[i]

bisect_right matters at an exact start: querying 9 must select the interval beginning at 9. Subtracting one gives its index. The i >= 0 guard handles an empty index or a query before the first interval.

Now for the detail that is easy to accidentally oversell: the query is O(log n), but insertion into these arrays is O(n) because elements may shift. Python's bisect documentation makes the same distinction between finding an insertion point and inserting into a list.

If frequent online insertions matter, a balanced search tree keyed by start can support both insertion and predecessor lookup in O(log n). If the intervals arrive as a batch, sorting once in O(n log n) and then serving queries may be simpler.

Yes, we can get O(1). Please read the receipt.

Suppose every possible coordinate is an integer in a known domain from lo through hi. Let U = hi - lo + 1. We can allocate one membership bit per possible position.

Adding [2, 5] marks positions 2, 3, 4, and 5. Querying 4 checks one bit. Check the domain bounds first, then use x - lo as the index; an out-of-domain query is false.

Under the usual machine-word indexing assumptions, that lookup is O(1). However, a packed bitset needs O(U) bits, and marking an interval of length L with a simple point-by-point loop takes O(L) work. Word-level operations can reduce the work in practice; they do not turn an arbitrarily long update into a free operation.

One million possible positions need about 125 KB of raw packed-bit storage. One trillion positions need about 125 GB, before overhead. These are decimal units and a packed representation, not the memory footprint of a Python list of booleans.

Notice what decides the size: the universe of possible coordinates, even if we store only three tiny intervals. Empty space has become part of our memory bill. Suddenly, the sorted arrays look rather lovely.

Initialization also costs work proportional to the representation’s size. With fixed-size machine words, zeroing the bitset is conventionally described as O(U); more explicitly, it touches about U / w words of w bits. In a fixed-width language, compute the domain size and interval lengths safely before allocating. A wrapped size calculation is not a clever memory optimization.

Two tempting shortcuts deserve a follow-up

What about a hash set? Storing every covered integer can give expected constant-time membership and use space proportional to the number of covered points. But a single enormous interval still means inserting an enormous number of integers. Storing only its endpoints does not answer whether an arbitrary point lies inside it.

What about coordinate compression? Mapping the starts 2, 9, and 20 to ranks 0, 1, and 2 makes the representation compact. A query for 10 still needs to discover that its relevant start is 9. That arbitrary-coordinate lookup has not disappeared just because our internal labels are smaller.

Compression becomes especially useful when the queries are known in advance or when we build a suitable search structure around the compressed boundaries. Say which version you mean. Otherwise, we have merely moved the difficult step into an unnamed helper.

There is another useful option for a fixed batch in a small integer domain: a difference array. Add a +1 at each interval’s start and a -1 just after its end, then take prefix sums to build membership. This gives O(n + U) batch construction and constant-time queries after construction, using O(U) counter storage. Handle the upper-bound sentinel safely.

A new insertion makes that materialized prefix result stale until it is updated or rebuilt. This is a good batch technique, not a promise of constant-time online inserts and queries together.

Choose the version you can defend for this workload

My starting recommendation is sorted arrays for a mostly-read workload with sparse coordinates. I can explain the candidate, account for storage, and keep the code small. Frequent inserts push the discussion toward a balanced tree. A genuinely small bounded domain makes direct addressing worth considering.

For a tiny workload with very few queries, the unsorted list may be enough. None of these choices needs an apology. What matters is connecting the cost to the operations the system actually performs.

If overlapping intervals become legal, revisit the proof before reusing the code. With [2, 100] and [9, 12], querying 50 selects the second interval and wrongly returns false. The earlier interval contains 50. We can merge coverage for membership-only semantics, or use a structure designed for overlap queries when interval identities matter.

Try the five-minute explanation before collecting another solution

Start with an empty index, add our three intervals out of order, and reason through queries 1, 2, 5, 7, 9, 12, 24, and 25. Expected results are false, true, true, false, true, true, true, and false. Add the single-point interval [30, 30] and check 30 as well.

Then ask a friend to change one condition: the universe grows to a trillion positions, insertions become frequent, or overlaps become legal. Explain which assumption broke and what you would change. You can practise the explanation on paper before running an implementation.

Here is the sentence I want to be able to finish comfortably: I can make this lookup constant time if we accept these costs and these constraints.

That is a much more useful answer than stopping at the complexity label. You have shown where the work went, what the representation buys, and when you would choose something else.

If you enjoy working through interview questions with one small example and a few increasingly interesting complications, follow me or subscribe for the next walkthrough. And tell me which version you would start with if this index received a million queries for every insertion.

~ Emily