Coding interview

Hi, I'm Alex. Thanks for making the time. This is the coding round, about forty-five minutes, and we'll try to get through two problems: roughly twenty minutes each, then a few minutes at the end for your questions. There's an editor on the right, and you can run your code against the examples as often as you like. Any standard library is fine. If you get stuck, say what you're thinking; silence is harder for me to work with than a wrong idea. I'll mostly stay quiet while you code. Before we start, what are you working on these days?

Hi, thanks. Um, so I'm in the last year of my computer science degree. Most of my time right now goes into my thesis project, which is a booking system for shared lab equipment, like microscopes and a couple of really expensive centrifuges. So, funnily enough, a lot of time slots and overlapping reservations. It's a Python backend with Postgres and a small web front end. And in the evenings I do practice problems, mostly to get used to talking while I code, which I'm, uh, still working on. I tend to go quiet when I'm concentrating, so feel free to poke me.

Okay. Lab equipment, so people fight over the same slots. What's been the hardest part of that project so far?

Honestly, two people booking the same slot at the same moment. The first version checked for a conflict and then inserted, and of course two requests could both pass the check. I ended up using an exclusion constraint in Postgres on the time range, so the database rejects the second one. It took me a while to even reproduce the bug, I had to write a little script that fires requests in parallel.

How do you know the constraint actually fixed it, and not just made it rarer?

Uh, fair question. I ran the same parallel script a few thousand times before and after. Before, it produced a double booking every few hundred runs, after, never, and the second request gets a clean error that the API turns into a conflict response. That's not a proof, but the database enforcing it is the part I trust, rather than my code checking first.

Okay. Let's start. First problem. Given a list of intervals with start and end times, merge all overlapping intervals and return the result. Input is on standard input: the first number is n, then n pairs of start and end. Print the merged intervals one per line, start and end separated by a space. For example, 1 3, 2 6, 8 10 and 15 18 become 1 6, 8 10 and 15 18, because the first two overlap. The other examples are on the right.

Okay. A couple of questions first. Are the intervals sorted when they come in? And if one ends at 3 and the next one starts at 3, do they count as overlapping? Because in my booking system they don't, a slot ending at three and one starting at three is fine, but here it might be different.

Here they do. Touching intervals merge: 1 to 3 and 3 to 5 become 1 to 5. The input is not sorted, and the list may be empty, in which case you print nothing. A start is never bigger than its end, and both ends are integers.

Okay, good to know. And how big can n get? Just so I know if something quadratic is even on the table. And the output, sorted by start, I assume, like in the examples?

Assume up to a hundred thousand intervals, and values that fit in a normal integer. Output sorted by start, yes. Before you write anything, I'd like to hear the approach and roughly what it costs.

Okay. So, um, my first thought is the naive one, just to have something. Compare every pair, and whenever two overlap, merge them into one, remove the two originals, and start over from the beginning, until a full pass finds nothing to merge. That definitely works, it's correct by construction because it only stops when nothing overlaps, it's just slow.

How slow, roughly?

One pass over all pairs is n squared. And every merge can trigger another full pass, and there can be up to n minus one merges, so worst case it's, um, n cubed. With a hundred thousand intervals that's ten to the fifteen, so, no. Even n squared is ten to the ten, which in Python is way too slow.

Okay. Can you do better? Think about what forces you to compare every pair.

Hmm. The expensive part is that an interval could overlap anything anywhere in the list. If I put them in some order first, then maybe only neighbours matter. Sort by end time? Then, um, no, wait. If I sort by end, an interval with a very early start could still come late and swallow several earlier ones, like 1 to 10 would come after 2 to 3 and 5 to 6. Sorting by start is better: once they're sorted by start, the next interval can only overlap the last block I've merged, because everything before that block already ended earlier, or got absorbed into it.

Why can't the next interval overlap something before the last block? Convince me.

Because the merged list is disjoint and sorted. Say the new interval reached back into an earlier block. Its start is at least the start of the last block, since we're going in order of start. So if it overlapped an earlier block it would have to start before that block ends, which is before the last block starts. Contradiction. So checking only the last one is enough. Then it's one pass: extend the last block, or start a new one. Sorting is n log n, the pass is linear.

Okay. Walk me through the first example with that rule, before you code.

Sorted by start it's 1 3, 2 6, 8 10, 15 18, already in order. Start the merged list with 1 3. Then 2 6: 2 is less than or equal to 3, so they overlap, the block becomes 1 6. Then 8 10: 8 is bigger than 6, so a new block. 15 18, bigger than 10, new block. So 1 6, 8 10, 15 18, which matches the expected output.

Okay. Go ahead and code it. Talk me through it as you go; I'll mostly stay quiet until you run it.

Sure. I'll read the input in main and keep merge as its own function, so I can test it separately. I'll read all of standard input at once and split, so I don't care how the pairs are laid out on the lines.

So, merge. Sort by start, with a key on the first element. Then the merged list. For each start and end: if merged is non-empty and the start is less than or equal to the last block's end, I extend it, otherwise I append a new pair. Less than or equal, not strictly less, because touching intervals merge. And I store lists, not tuples, so I can update the end in place. Then main: n, then two n numbers, pair them up, print each block.

Okay, I think that's it. Let me run the first example.

The first example passes. Let me run all of them.

Three pass, the third one fails. That's the unsorted one where one interval contains the others. I print 1 3 and then 5 6, and it expects just 1 10. Hmm.

Before you change anything: what's happening on that input? Walk me through it.

Um, let me trace it. After sorting it's 1 10, then 2 3, then 5 6. Merged starts as 1 10. Then 2 3 starts inside 1 10, so I merge, but I set- I set the end to 3. I overwrite the end and, uh, lose the 10. Then, um, 5 6 doesn't overlap 1 3 anymore, so it becomes its own block. Um, so when I merge I need the max of the two ends, not just the new end. I, uh, wrote it as if the new interval always ends later, which is, I mean, exactly the contained case I mentioned five minutes ago.

Now all four pass, including the touching one and the single point, seven seven.

Mm-hm. The four examples are the ones I gave you. What else would you test?

The empty input, n is zero, so it should print nothing. I also want to check that n zero doesn't crash in the parsing, since I slice the data. And completely empty standard input, which I handle with the early return. Let me run the zero one.

Yes, it prints nothing and exits cleanly. Other cases I'd want: all intervals identical, they should collapse to one. One interval that contains everything, which is the case that just failed. A chain where each one touches the next, like 1 2, 2 3, 3 4, which should become 1 4. And negative times would work too, since I only compare numbers.

Think about the upper end of the input size. Anything in the parsing or the output that hurts at a hundred thousand intervals?

Not really. Reading everything at once is two hundred thousand numbers, a few megabytes at most. The one thing I'd change for really big inputs is printing: a print per line is slow in Python, so I'd join the lines and write once. At a hundred thousand it's fine.

Okay. Time and space complexity of the final version?

Sorting is O(n log n) and the sweep is O(n), so O(n log n) overall, the sort dominates. Space is O(n) for the merged list in the worst case, when nothing overlaps. And Python's sort, which is Timsort, can use up to n over two extra on top of that.

Is n log n the best possible here?

Hmm. In general, I think so, but I'm not sure how to prove it. Intuitively, if the intervals are tiny and don't overlap, the output is just the input in sorted order, so merging is at least as hard as sorting, and comparison sorting is n log n. If the coordinates were small integers you could do better with counting, but I wouldn't bet on that being allowed.

Here's a follow-up, closer to your booking system. What if intervals arrive one at a time and you must keep the merged set up to date? Say a few hundred per second, and someone can ask for the merged set at any time.

Um, so I'd keep the merged blocks sorted by start, all the time. For a new interval I binary search where its start goes, with bisect, and then I have to merge it with the blocks it overlaps, which is the one just before it, maybe, and then however many after it, I walk right while the next block starts before my end, and the—

Sorry, before you go on. Why only the one just before it?

Because the blocks before that one end before the previous block starts, they're disjoint. Same argument as before. So at most one block to the left can be touched. To the right, it can swallow several. Then the cost: finding the spot is log n, but inserting into or deleting from a Python list is O(n), because it shifts elements. A balanced tree or a sorted container would make it log n per block touched.

One insertion can swallow many blocks. What's the cost amortized over many insertions?

Hmm. Each block can be swallowed at most once, after that it's gone. So over m insertions the total swallowing work is at most m. So amortized it's O(log n) per insert with the tree. With the plain list it's still the shifting that hurts, that stays linear per insert.

Python has no balanced tree built in. What would you actually use?

There's the sortedcontainers package, which is a third-party library, but it's very widely used. If I couldn't add a dependency, honestly, I'd keep the plain list. At a hundred thousand blocks the shift is a memmove of under a megabyte, that's microseconds, and a few hundred inserts a second is nothing. I'd measure before writing a tree by hand.

Now suppose bookings can also be cancelled, so an interval can be removed again after it was merged. What changes?

Oh, that's much harder. Once two intervals are merged into one block I've lost the information about where each of them was, so I can't undo it. I'd have to keep the original intervals, not just the blocks. Um, then a removal could split a block into several pieces, and to find them I'd basically re-merge the originals that were inside that block. That's linear in the size of the block. For something better I think you'd want an interval tree or a segment tree with counts over the coordinates, but I haven't implemented one of those in a long time.

Last one on this problem. How would you find the free gaps between merged intervals?

That's easy once they're merged: walk the merged list and every pair of neighbours gives a gap from the previous end to the next start. If the ends are inclusive, uh, then for integers the gap is previous end plus one to next start minus one, and if they're touching there's no gap at all. Linear after the merge. That's basically the free-slot view in my booking system.

Okay. Let's leave that one there. We're a bit over twenty minutes in, so let's move on.

Second problem. Given an array of integers and an integer k, return the k most frequent elements. Input: n, then the n numbers, then k. Print the k values on one line. For example, 1 1 1 2 2 3 with k equal to 2 gives 1 and 2.

Can there be ties at the boundary? Like if the k-th and the k-plus-first value have the same count, which one do I return?

The answer is guaranteed to be unique, so you won't get a tie at the boundary. k is between 1 and the number of distinct values, so it's always possible to return k values.

Okay. And the output order? And can the numbers be negative?

Order doesn't matter for the answer, but the examples print them ascending. Yes, negatives are possible.

Okay. So the first step is clearly counting: a dictionary from value to frequency, one pass, O(n). Negatives don't matter for a dictionary. Then the simple version is to sort the distinct values by count, descending, and take the first k. If m is the number of distinct values, that's O(n plus m log m). I'll write that first, so I have something that works, and then see if I can do better.

Okay. Go ahead and write the simple version.

Same reading as before. Counter from collections for the counting. Then sorted over the keys, with the count as the key, reversed, and slice the first k.

All four pass, including the negative one.

What's the complexity of that, with n numbers and m distinct values?

Counting is O(n), sorting the distinct values is O(m log m), so O(n plus m log m), and m can be as big as n, so O(n log n) worst case. Space O(m) for the counts.

Think about what you're sorting. You only need the top k, not a full ordering. What structure exploits that?

A heap. A min-heap of size k, keyed on frequency. I push every value with its count, and when the heap gets bigger than k I pop the smallest, so what's left at the end is the k biggest. Each push and pop is log of the heap size, so it's O(n plus m log n)... no, sorry, m log k, the heap never has more than k plus one items.

When does the difference between log m and log k actually matter?

When k is much smaller than m. Like the top ten out of a million distinct values: log ten instead of log a million, and the heap is tiny in memory. If k is close to m it's basically the same as sorting. Python also has heapq dot nlargest, which does exactly this, but I'll write it out.

Walk me through the heap on the first example before you write it.

Counts are 1 three times, 2 twice, 3 once, k is 2. Push three-comma-one, heap has one item. Push two-comma-two, two items, fine. Push one-comma-three, three items, more than k, so pop the smallest, which is the count one, value 3. Left with value 2 and value 1. Which is the answer.

Huh. Two fail now, the first one and the last one. Example 1 prints 2 1 instead of 1 2. And the last one prints 9 8 instead of 8 9.

The set of values looks the same. And the first version passed all four. Why?

Because, um, the first version printed in order of frequency, highest first, and in these examples that happens to be ascending by value too. That was, uh, luck, I never actually sorted by value. The heap gives them back in heap order, smallest frequency first. The set of values is right, it's just the order. I'll sort the output, that's k log k, which doesn't change the bound. I should have sorted in the first version too.

All four pass again.

Okay. Can you get it linear in n, without the log factor?

Linear... Quickselect on the counts would be linear on average: partition the distinct values around the k-th largest frequency, like the partition step in quicksort, and recurse into one side only. But worst case it's quadratic, unless I do the median-of-medians thing, and it's fiddly to write in an interview. Um, is there something simpler...

Think about the values you're ordering by. What's the largest a frequency can be?

At most n. Oh, so the frequencies are small integers, I can bucket by frequency: an array of n plus one lists, put each value in the bucket of its count, then walk from the top bucket down until I have k values. That's O(n) time and O(n) space, no comparisons at all. Let me write that.

All pass. The final sort is only over k values, so it's still linear apart from that. In practice I'd probably still pick the heap, though. The buckets array is size n even when there are only a few distinct values, so it's mostly empty lists, and the heap version is easier to read.

Different setting now. Say the numbers are product IDs from a click stream, billions a day, and you have one machine with a fixed amount of memory. What if the data is a huge stream and memory is limited?

So I can't keep a count for every value. Honestly, I don't know the standard answer here. I think there's a probabilistic structure, a sketch of some kind, that keeps approximate counts in fixed memory, with hashing, but I couldn't explain how it works or what error it gives. What I can reason about is that you'd have to give up exact answers.

Okay. Say you can keep only a fixed number of counters, a few thousand. A value with no counter arrives and every counter is taken. What do you do?

Then, um, when a value comes that has a counter, increment it. If it doesn't and there's a free counter, take it. If they're all full... maybe decrement all of them, and drop the ones that hit zero? Then something really frequent can't be pushed out for long, because it gets incremented more often than everything gets decremented. So the heavy values survive. But the counts are only lower bounds, and I'm not sure about the exact guarantee, like how frequent something has to be to be safe.

Mm-hm. You said frequent values survive. Try to work out how frequent a value must be to be safe.

Okay. Say c counters and n items in the stream. Every time I decrement, I decrement c counters plus the new item I'm throwing away, so c plus one units of count disappear together. That can happen at most n over c plus one times in total. So a value's counter is at most n over c plus one below its true count. So anything that appears more than n over c plus one times must still have a counter at the end. I think that's right, but I'd want to check it on a small example.

Okay. One more variation. What if frequencies change over time and you need the current top k? Say the top products in the last hour, refreshed every few seconds.

Then I'd count over a window, like the last hour, with a count per value per minute, and drop the oldest minute as time moves. The totals change by small steps. Recomputing the heap on every query is m log k, so if queries are frequent I'd keep a sorted structure keyed on count that I update whenever a count changes, and read the top k off the end.

Before we finish, back to the first problem. You said the sort can use extra memory. Would you change the merge if memory were tight?

I could write the merged blocks back into the same list with a write index, and truncate at the end. The sort is already in place, intervals dot sort. Then it's O(1) extra apart from what the sort itself needs. It does modify the caller's list, though, so I'd say so in the docstring or name it something like merge in place.

Okay. That's both problems. We have a few minutes left. Do you have any questions for me?

Yes, um. What does a good first few months look like for someone joining as a new grad? Like, what would you want to see from them?

It depends on the team. Usually a small, well-scoped project first, so you learn the codebase and the deploy process end to end. Asking questions early matters more than shipping fast, and there's a lot of code review in both directions. The hiring team can give you the specifics for this role, including who you'd work with and what the first project would likely be.

Okay. And is this kind of problem close to the day-to-day work, or more of a filter?

Some of both. Nobody merges intervals all day, but reading a problem carefully, testing your own code and reasoning about cost come up constantly. The reasoning and the testing matter more than the exact problem.

Okay. And what happens after this round? How soon would I hear back?

The report from this round is ready in a few minutes. The hiring team handles the next steps and the timing; they'll be in touch about that.

Okay. That's all from me, thank you.

Thanks, that's time. The report covers both problems and will be ready in a few minutes.