NextBeing blog · the coding round, as a show

Coding interview example: one round, solved out loud

A coding interview round has a shape: restate the problem, ask two or three questions, name the slow way, explain a faster plan on the example, write it while talking, test it, fix what fails, and state the cost. This six-minute episode plays one whole round on the most-asked question, the longest stretch without a repeat, with every step drawn.

One problem, two people, a pad. Press play: she sets the problem, he answers the way a strong candidate does, and the picture acts out every step. Click any line of code for what it does. Space pauses; the arrows step a line.

Live interview
    M

    Python 3▶ Runclick a line to see what it does
    OutputNothing run yet.
    D

    This part, three ways

    What does a coding interview round look like?

    Eight parts, in this order: the problem, saying it back with questions, the slow way, the plan, writing it, testing it, the cost, and a changed requirement. In recorded rounds, candidates ask two or three clarifying questions before they code, and about half of first runs fail; what is judged is what you do next.

    What is the question in this episode?

    The longest stretch without a repeat, known as the longest substring without repeating characters. Here the letters are gems in a museum corridor. The fast answer is one walk with two markers and a dictionary, a method called a sliding window: linear time, and one dictionary entry per kind of gem.

    Read the whole episode: every line and every version of the code

    The problem

    Mara: So. You think you can code.

    Dex: I do. You look like you've heard that before.

    Mara: Every day. I'm Mara. One problem, forty minutes. Talk while you work, or I'll assume you're guessing.

    Dex: Dex. Talking is the easy part.

    Mara: Here is the problem. A museum, after hours. One corridor, with a row of display cases, one gem in each. Ruby, emerald, ruby, sapphire, opal.

    Mara: You walk along and take gems into your bag. In a row. No skipping.

    Mara: The alarm trips the moment your bag holds two of the same gem.

    Mara: You may start at any case. I want the longest haul: the most cases you can take in one go.

    Say it back

    Dex: Let me say it back. I pick a case, walk right, and take every gem. I stop before I'd hold two of the same.

    Dex: From the first case, that is a haul of two.

    Dex: From the emerald, I get four: emerald, ruby, sapphire, opal. So here, the answer is four?

    Mara: Four.

    Dex: Can the corridor be empty?

    Mara: It can.

    Dex: Then the answer is zero. How long can it get?

    Mara: Millions of cases.

    Dex: So speed matters. And you want the number, not the gems?

    Mara: The number. Are you planning to write any code today?

    Dex: Starting now. Your corridor, as a list: the gems, in order. Code counts from zero, so the first ruby is case zero.

    corridor = ["ruby", "emerald", "ruby", "sapphire", "opal"]

    The slow way

    Mara: Then solve it.

    Dex: The obvious way first, because it is certainly right. Try every starting case, and walk right from each.

    Dex: It is right, and it is slow. Every start walks the same cases again. With millions of cases, that is far too many steps.

    Mara: Then don't show me that one.

    The plan

    Dex: I won't. One walk. Two markers. Start, where my haul begins. Here, where I am. What is between them is in my bag.

    Mara: And how do you spot a repeat? You dig through the bag every time?

    Dex: No. I keep a notebook. For each gem, the case where I last saw it. One look, however long it gets. In code, that is called a dictionary.

    Dex: Two rules. A new gem: I take it, and I note it.

    Dex: Emerald is new too. Taken, and noted.

    Dex: Now a ruby again. The notebook says where the old one is. I let go of everything up to it, and my start moves just past it.

    Mara: No alarm.

    Dex: No alarm. The old ruby left the bag before the new one went in.

    Dex: Sapphire and opal are new. I take them. Four in the bag: my best haul.

    Mara: Hm. Fine. Write it.

    Writing it

    Dex: A function is a named recipe. This one is longest haul. It takes the cases, and gives back a number.

    corridor = ["ruby", "emerald", "ruby", "sapphire", "opal"]
    
    def longest_haul(cases):

    Dex: last_seen is the notebook. start is my start marker. best is my best haul so far.

    corridor = ["ruby", "emerald", "ruby", "sapphire", "opal"]
    
    def longest_haul(cases):
        last_seen = {}
        start = best = 0

    Dex: Now the walk. enumerate counts for me. here is the case number. gem is what is in it.

    corridor = ["ruby", "emerald", "ruby", "sapphire", "opal"]
    
    def longest_haul(cases):
        last_seen = {}
        start = best = 0
        for here, gem in enumerate(cases):

    Dex: Rule two. If the gem is in the notebook, the start moves just past the old one.

    corridor = ["ruby", "emerald", "ruby", "sapphire", "opal"]
    
    def longest_haul(cases):
        last_seen = {}
        start = best = 0
        for here, gem in enumerate(cases):
            if gem in last_seen:
                start = last_seen[gem] + 1

    Dex: Rule one. Note where this gem is.

    corridor = ["ruby", "emerald", "ruby", "sapphire", "opal"]
    
    def longest_haul(cases):
        last_seen = {}
        start = best = 0
        for here, gem in enumerate(cases):
            if gem in last_seen:
                start = last_seen[gem] + 1
            last_seen[gem] = here

    Dex: The haul runs from start to here. Its length is here, minus start, plus one.

    corridor = ["ruby", "emerald", "ruby", "sapphire", "opal"]
    
    def longest_haul(cases):
        last_seen = {}
        start = best = 0
        for here, gem in enumerate(cases):
            if gem in last_seen:
                start = last_seen[gem] + 1
            last_seen[gem] = here
            best = max(best, here - start + 1)

    Mara: Why plus one?

    Dex: Cases one to four are four cases, not three. And max keeps the larger: this haul, or my best.

    Dex: Last line: return best. That hands the answer back.

    corridor = ["ruby", "emerald", "ruby", "sapphire", "opal"]
    
    def longest_haul(cases):
        last_seen = {}
        start = best = 0
        for here, gem in enumerate(cases):
            if gem in last_seen:
                start = last_seen[gem] + 1
            last_seen[gem] = here
            best = max(best, here - start + 1)
        return best

    Mara: You're sure about that?

    Dex: Sure enough to test it.

    Testing it

    Dex: Two checks. Your corridor should give four. An empty one should give zero. The word assert means: this must be true, or stop.

    corridor = ["ruby", "emerald", "ruby", "sapphire", "opal"]
    
    def longest_haul(cases):
        last_seen = {}
        start = best = 0
        for here, gem in enumerate(cases):
            if gem in last_seen:
                start = last_seen[gem] + 1
            last_seen[gem] = here
            best = max(best, here - start + 1)
        return best
    
    assert longest_haul(corridor) == 4
    assert longest_haul([]) == 0
    print("all checks pass")

    Dex: Now I run it.

    The run printed: all checks pass

    Dex: Green.

    Mara: You chose those yourself. Try mine. Ruby, opal, opal, ruby.

    Dex: By hand first. The two opals sit side by side, so the best I can take is two. It should say two.

    corridor = ["ruby", "emerald", "ruby", "sapphire", "opal"]
    
    def longest_haul(cases):
        last_seen = {}
        start = best = 0
        for here, gem in enumerate(cases):
            if gem in last_seen:
                start = last_seen[gem] + 1
            last_seen[gem] = here
            best = max(best, here - start + 1)
        return best
    
    assert longest_haul(corridor) == 4
    assert longest_haul([]) == 0
    assert longest_haul(["ruby", "opal", "opal", "ruby"]) == 2
    print("all checks pass")

    Dex: Running it.

    The run printed: assert longest_haul(["ruby", "opal", "opal", "ruby"]) == 2 / AssertionError

    Mara: Red.

    Dex: Red. So my code is wrong, not your corridor. I won't guess. I'll walk it, line by line.

    Dex: Ruby is new. Opal is new. Then opal again: the old one goes, and the start moves to case two. All correct.

    Dex: Now the last ruby. The notebook says: case zero. So my start jumps to case one. Backwards.

    Mara: Your thief went back for a gem he had already left.

    Dex: Yes. The notebook never forgets, but my bag does. That old ruby is not in my bag. So rule two needs a condition: only if the old one is still in the bag.

    Dex: In code: last seen at, or after, start.

    corridor = ["ruby", "emerald", "ruby", "sapphire", "opal"]
    
    def longest_haul(cases):
        last_seen = {}
        start = best = 0
        for here, gem in enumerate(cases):
            if gem in last_seen and last_seen[gem] >= start:
                start = last_seen[gem] + 1
            last_seen[gem] = here
            best = max(best, here - start + 1)
        return best
    
    assert longest_haul(corridor) == 4
    assert longest_haul([]) == 0
    assert longest_haul(["ruby", "opal", "opal", "ruby"]) == 2
    print("all checks pass")

    Dex: Running it.

    The run printed: all checks pass

    Mara: Green.

    Dex: Green. My bug. Your check.

    Mara: It was.

    Dex: I should have tested a repeat myself. One more: three opals should give one.

    corridor = ["ruby", "emerald", "ruby", "sapphire", "opal"]
    
    def longest_haul(cases):
        last_seen = {}
        start = best = 0
        for here, gem in enumerate(cases):
            if gem in last_seen and last_seen[gem] >= start:
                start = last_seen[gem] + 1
            last_seen[gem] = here
            best = max(best, here - start + 1)
        return best
    
    assert longest_haul(corridor) == 4
    assert longest_haul([]) == 0
    assert longest_haul(["ruby", "opal", "opal", "ruby"]) == 2
    assert longest_haul(["opal", "opal", "opal"]) == 1
    print("all checks pass")

    Dex: Running it.

    The run printed: all checks pass

    The cost

    Dex: The cost, before you ask. One walk. Each case once, and each look in the notebook is one step. A million cases, about a million steps.

    Mara: And the notebook?

    Dex: One line for each kind of gem. Four kinds, four lines.

    The verdict

    Mara: New rule. The alarm allows two of each gem. The third one trips it. What breaks?

    Dex: The notebook. A place is not enough now. It has to count. On a third ruby, I let gems go from the left, until I am back to two.

    Mara: That is the next round.

    Dex: Then I'm through this one?

    Mara: All right. Fine.

    Mara: Whatever. You're through.

    Every run shown was really run when the page was built. Want to say your own answers out loud and have them graded? NextBeing has a Practice mode with an interviewer that knows the job. Published .