Merge intervals in a mobile coding interview: the calendar version

The textbook version: given a list of intervals, merge every pair that overlaps and return the set that covers the same points. The mobile version: a day view shades the time the user is busy. Given the day's events, return the blocks to shade. Same problem, and the calendar version hands you better questions.

For the whiteboard, represent time as minutes since midnight, so 9:00 is 540. In the real app the times are Date values on iOS and epoch milliseconds or Instant on Android. Say that sentence, then keep the integers. It shows you know the difference without spending ten minutes on time zones.

Three or four questions, each one able to change the code. Ask them, then state your assumptions out loud so the interviewer can correct them now instead of in minute 30.

The second question is the one that earns the point. In a calendar, events are naturally half-open: a meeting from 9:00 to 10:00 ends at the moment the next one starts. Whether those two are one block depends on what the result is for. For shading busy time, merge them. For a double-booking warning, they are not a conflict. The data is the same; the product question decides the operator.

Say it, cost it, and move on. Compare every pair of events; when two overlap, replace them with one block; repeat until a full pass merges nothing. It is correct, and it is O(n²) per pass. If you restart the scan after every merge, there can be up to n passes, so the worst case is O(n³).

You do not write it. You say it in two sentences so the interviewer hears that you can see a correct answer before you look for a fast one, and so the optimisation has something to be measured against.

The enabling move is sorting by start time. Once the events are sorted, a new event can only overlap the block you are currently building, never an earlier one.

The reason fits in one sentence, and saying it is what turns a memorised answer into a reasoned one: if the next event starts after the current block ends, every event after it starts even later, so nothing can reach back into that block. It is final. So one left-to-right pass is enough: either extend the current block, or close it and start the next.

One detail inside the extension: the new end is the larger of the two ends, not the incoming one. An event from 8:00 to 12:00 followed by one from 9:00 to 10:00 must stay a block until 12:00. Assigning the incoming end shrinks it to 10:00.

struct Busy: Equatable {
    var start: Int   // minutes since midnight
    var end: Int
}

func mergeBusy(_ events: [Busy]) -> [Busy] {
    let sorted = events.sorted { $0.start < $1.start }    // the enabling move
    var merged: [Busy] = []
    for event in sorted {
        if let last = merged.last, event.start <= last.end {  // overlap or touch
            merged[merged.count - 1].end = max(last.end, event.end)
        } else {
            merged.append(event)                             // a gap: start a new block
        }
    }
    return merged
}

Two Swift details worth saying while you type. Busy is a struct, so merged.last hands you a copy; mutating that copy would change nothing, which is why the update writes through the index. And sorted returns a new array, leaving the caller's events untouched, which is what a function called from a view model should do.

data class Busy(val start: Int, val end: Int)

fun mergeBusy(events: List<Busy>): List<Busy> {
    val merged = ArrayList<Busy>(events.size)
    for (event in events.sortedBy { it.start }) {           // the enabling move
        val last = merged.lastOrNull()
        if (last != null && event.start <= last.end) {      // overlap or touch
            merged[merged.lastIndex] = last.copy(end = maxOf(last.end, event.end))
        } else {
            merged.add(event)                               // a gap: start a new block
        }
    }
    return merged
}

The Kotlin version makes the same choices with immutable values: Busy has val fields, so extending a block means replacing the last element with a copy. sortedBy returns a new list, and the function accepts a read-only List, so it never mutates what the caller passed in.

Both versions pass the same cases: [1, 3], [2, 6], [8, 10], [15, 18] gives [1, 6], [8, 10], [15, 18]; touching [1, 4] and [4, 5] gives [1, 5]; an unsorted day where 8:00 to 12:00 contains 9:00 to 10:00 gives one block until 12:00; empty input gives empty output; three identical events give one.

Say it as part of the plan, not when the interviewer prompts you: O(n log n) time, dominated by the sort; the sweep itself is linear. O(n) extra space, for the sorted copy and the output.

Then add the sentence that shows judgment: for one day view, n is a few dozen events and any of these answers is instant. The complexity starts to matter when the same function merges months of a shared calendar, and there the next question is whether to merge only the visible range instead of the whole history.

• Empty and single: the loop handles both; no special case is needed, and saying so is better than adding a guard you cannot justify.
• Contained event: the reason for max, covered above.
• Touching events: the reason for <=, decided by the product question.
• Duplicates: three copies of the same event collapse into one block.
• Zero-length events: a 12:00 reminder merges into a block that covers 12:00 and stands alone otherwise.
• Invalid events: start after end is a data problem; validate before merging rather than letting the sweep produce a nonsense block.

Then trace one concrete input out loud before you call it done. Take 9:00 to 10:00, 9:30 to 12:00, 13:00 to 13:30 and 13:30 to 14:00, already sorted.

Result: 9:00 to 12:00 and 13:00 to 14:00. A trace like this is the test when the editor cannot run code, and it is the habit that catches the < versus <= bug before the interviewer does.

• Not sorting first. The linear sweep then misses overlaps between events that are not neighbours in the input.
• Using < when touching should merge. It fails the 10:00 case, and it is the bug the clarifying question exists to prevent.
• Setting the end to the incoming end instead of the max. It shrinks a block that fully contains the next event.
• Comparing against the original interval instead of the block being built. After two merges, the original end is stale.

All four produce code that passes the first example the interviewer gives. That is why the trace and the edge-case list matter more here than on problems that fail loudly.

An algorithm round looks like a solo puzzle and is scored as a conversation. What interviewers score while you share your screen covers the general rubric; on this problem the signals land at predictable moments.

Silence is the expensive part. A candidate who writes the correct twelve lines without a word gives the interviewer nothing to score between the prompt and the final code.

Once the merge works, the interviewer pushes. These are the ones the calendar framing invites, roughly in the order they come.

"Now find the free slots of at least 30 minutes in a 9:00 to 17:00 working day." This is the complement of the merge: walk the merged blocks with a cursor and collect the gaps. It tests whether you reuse the function you just wrote and clip to the day's bounds.

func freeSlots(in day: Busy, busy: [Busy], minimum: Int) -> [Busy] {
    precondition(minimum > 0)
    var slots: [Busy] = []
    var cursor = day.start
    for block in mergeBusy(busy) {
        let gapEnd = min(block.start, day.end)
        if gapEnd - cursor >= minimum {
            slots.append(Busy(start: cursor, end: gapEnd))
        }
        cursor = max(cursor, block.end)
    }
    if day.end - cursor >= minimum {
        slots.append(Busy(start: cursor, end: day.end))
    }
    return slots
}

With a day from 9:00 to 17:00 and events that include one starting before 9:00 and one running past 17:00, it returns only the gaps inside the working day that are 30 minutes or longer.

"Warn the user when they are double-booked." Now touching is not a conflict, so the comparison flips to <. And you do not need the merge at all: after sorting by start, if any two events overlap, some adjacent pair overlaps too, so checking neighbours is enough.

// Touching is not a conflict here, so the comparison is strict.
fun hasConflict(events: List<Busy>): Boolean =
    events.sortedBy { it.start }.zipWithNext().any { (a, b) -> b.start < a.end }

• "Insert one new event into an already merged, sorted list without re-sorting." Find where it lands, merge it with the neighbours it overlaps, copy the rest. Linear time. Tests whether you use the invariant the list already has.
• "How much of the day is busy?" Sum the lengths of the merged blocks. Tests whether you see that the merge does the hard part.
• "Lay overlapping events out side by side. How many columns does the day view need?" That is the maximum number of events in progress at once: sort the starts and the ends and sweep, or keep a min-heap of end times. O(n log n). Tests whether you recognise a neighbouring problem instead of forcing the merge onto it.
• "The times are real dates in the user's time zone." Compare instants, never wall-clock strings, and remember that in zones with daylight saving a day can be 23 or 25 hours long, so minutes since midnight stop being safe. Tests whether you have shipped date code.

Prepare one sentence for each. A follow-up you can answer by pointing at code you already wrote is the conversation going well.

The staff column does not contain cleverer code. It contains the same twelve lines with the product question answered and the edges named.

• Open an empty file. Set a 25-minute timer and record yourself.
• Ask your clarifying questions out loud, to the recording, and write your assumptions as a comment.
• Say the brute force and its cost in under a minute.
• Write the merge in the language of your role, narrating the sort and the max.
• Trace four events by hand, including one touch and one containment.
• Answer two follow-ups: free slots, and the double-booking warning.
• A week later, do it again from the empty file. Speed is not the point; the second run shows what you retrieved rather than recognised.

If the second run stalls on the empty file, you watched the solution, then opened an empty editor explains why reading answers does not transfer, and what does.

How do you solve merge intervals in a coding interview?

Sort the intervals by start time, then sweep once from left to right. Keep the block you are building; if the next interval starts at or before its end, extend the end to the larger of the two ends, otherwise close the block and start a new one. That is O(n log n) time, dominated by the sort, and O(n) space for the sorted copy and the output.

Should touching intervals like 9:00 to 10:00 and 10:00 to 11:00 merge?

It depends on what the result is for, which is why you ask. For shading busy time in a calendar, yes: the user sees one busy block. For a double-booking warning, no: back-to-back meetings are not a conflict. In code the whole difference is <= versus <.

Do mobile interviews still ask algorithm questions?

Some do, mostly at the largest companies, and usually at the level of a hash map, a stack, a binary search or an intervals sweep rather than hard puzzles. Product companies lean toward practical app tasks. Ask the recruiter which format your loop uses before you decide how much to drill.

Should I answer in Swift or Kotlin if the interviewer allows any language?

Use the language of the role. The algorithm is the same, and the platform details are free signal: sorted(by:) copying the array in Swift, sortedBy returning a new list in Kotlin, value types versus data class copies. Naming those while you type shows you write the language every day.