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.
last_seenWhat 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 .