Running a coding round out loud

In a coding round the interviewer scores how you think, not only the code. They cannot see your thoughts, so they score what they hear. Two candidates can write the same working code. The one who explained each step scores higher.

A weak candidate reads the problem and starts to type at once, or goes silent for ten minutes. A strong candidate follows a fixed order. They ask, give an example, say the simple way, improve it, agree the plan, code, test and say the cost. Every step is spoken.

Tradeoff's coding mock works in a similar order. The interviewer gives a problem with examples. You ask questions. You give your approach and its time and space cost before you write code. Then you write the code in the editor. Run is private: use it to test yourself. When you are ready, press Submit. The interviewer then reads your code, the real run result and the results of hidden tests. You have up to 8 Submits. A follow-up comes next, and the round ends with three short questions about your own code. They are not scored. The report scores problem solving, communication, technical knowledge and coding skills. It notes the hints you used. You can ask for up to 3 hints, and a strict round has none.

Think of a pilot before take-off. The pilot follows a checklist and says each item aloud. A fixed order lets you stay calm, and it lets the interviewer follow you. This lesson is that checklist for a 45-minute round. It uses the spoken phrases of lesson 6, the small checks of lesson 16, and the maps and heaps of lessons 17 and 18.

The order and the clock

These minutes are our suggestion. Real rounds differ. Use the minutes to know when you are late. Two words first. An edge case is an input at the limit, such as an empty list. A dry run is tracing your code by hand. The table uses plain words for ideas explained below.

The first nine steps add up to 43 minutes: 2 + 3 + 3 + 3 + 5 + 2 + 15 + 5 + 5. So about 2 minutes are left for the follow-up. The mock's last three questions about your code come after this. The clock is tight on purpose. It shows which steps must stay short.

Clarify

Ask questions before you think about the answer. Ask only what the problem statement does not already say. Seven questions fit most problems:

1. How big can the input be?
2. Are there duplicates?
3. Can the input be empty?
4. Can numbers be negative?
5. Is the input in order?
6. What do I return: indexes (positions) or values, one answer or all?
7. What do I return when there is no answer?

The answers change the method. If the input is sorted, you can use a faster idea. If it can be empty, your code needs a check.

Examples

Take one normal example and one edge example. An edge example is an input at the limit, such as an empty list or one item. Solve the normal one by hand and watch what you do. The rule you follow in your head is your algorithm. Say it aloud.

Brute force first

The brute force is the simple, slow method that checks everything. Say it with its cost in Big-O: a way to say how the work grows when the input grows. Let n be the number of items. O(n) means the work grows in step with n. O(n x n) means that doubling n makes the work four times bigger. O(1) means the work does not grow. O(log n) means the work grows very slowly: for 1,000,000 items it is about 20 steps.

Then say why it is too slow, with a number. Assumption: n is 100,000 and the computer does 10 million simple steps a second. n x n = 10,000,000,000 steps. 10,000,000,000 / 10,000,000 = 1,000 seconds. That is far too slow.

Improve with an idea chosen from the slow part

Find the slow part first, then choose the idea.

Agree the plan, then code in small steps

Say the plan and its cost, and ask: "Shall I start?" The interviewer can correct you now, before 15 minutes of code. Then write the code in small, named steps. Say what the next line is for: "This line saves the number, so that a later number can find it." Do not go silent for a long time.

Dry run, edge cases and cost

A dry run means you trace the code by hand with your example, line by line, and write down the variables. Then try the edge cases. Use the small check helper and the boundary thinking of lesson 16. Press Run (it is private) and compare the printed values with what you expect. A run that does not crash is not proof that the answer is right. Press Submit when you believe it works: the interviewer reads the real result and the hidden tests.

Say the cost as a sentence: "Time is O(n) because it is one pass. Space is O(n) because the map can hold n items."

When you are stuck

1. Say what you know: "I know the answer must use two numbers that add to the target."
2. Simplify the problem: "What if the list is sorted?" Solve that first.
3. Try a small example by hand, and look for the rule.
4. Ask for a hint. The mock allows up to 3, and none in a strict round. Say it back in your own words, then try it. A hint used well is better than silence.

When the code is wrong

Trace, do not guess. Take the failing input and follow the code line by line until the value is not what you expect. Fix one thing at a time and run again. Changing three things at once hides which one worked.

Two Sum. The problem: given a list of integers and a target, return the indexes of two numbers that add to the target. Here is the full spoken round.

1. Read and repeat. "I get a list and a target. I return the positions of two numbers that add to the target."

2. Clarify. "Is there exactly one answer? Indexes, not values? May I use one element twice? Can numbers be negative? Is the list sorted? What if there is no answer?" The interviewer says:

• at most one answer, and it is indexes,
• no reuse of one element,
• negatives are allowed, and the list is not sorted,
• return an empty list when there is no answer,
• the size is up to 100,000.

3. Examples. "With [2, 7, 11, 15] and target 9, the answer is [0, 1], because 2 + 7 = 9. Another example is [3, 3] and target 6. Here the answer is [0, 1]. These are two different positions with the same value."

4. Brute force. "I check every pair with two loops. That is n x n steps. For 100,000 items it is 10,000,000,000 steps, about 1,000 seconds at 10 million steps a second. That is too slow."

5. Improve. "The slow part is the search for the partner. For each number I need the partner, which is target minus the number. A map finds it in one step. So I walk the list once. I look for the partner in the map, and then I save the current number."

6. Plan. "One pass, a map from value to index. Time is O(n). Space is O(n). Shall I start?"

7. Code.

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        need = target - num
        if need in seen:
            return [seen[need], i]
        seen[num] = i
    return []

8. Dry run on [2, 7, 11, 15], target 9. "i = 0, num = 2, need = 7. The map is empty, so I save 2 at position 0. i = 1, num = 7, need = 2. The map has 2 at position 0, so I return [0, 1]."

9. Edge cases and cost. "[3, 3] with target 6: i = 0, need = 3, the map is empty, save 3. i = 1, need = 3, found at 0, return [0, 1]. A one-item list [3] with target 6 returns an empty list. I check the partner before I save the number, so one item is never used twice. Time is O(n), because there is one pass. Space is O(n), because the map can hold n items."

10. Follow-up: a sorted list. "Use two pointers, one at each end. If the sum is too small, move the left pointer right. If too big, move the right pointer left. Time is O(n) and space is O(1)."

This answers the predict box. The candidate skipped steps such as clarify, examples, the brute force, the plan and the cost. Any two of them is a correct answer.

A shorter round: Valid Parentheses. The problem: a string of ( ) [ ] { }. Say whether every bracket closes in the right order.

• Clarify: "Only those six characters? Is the empty string valid?" Yes, and yes.
• Examples: "{[]}" is valid. "([)]" is not.
• Brute force: "Keep removing the pairs (), [] and {} until nothing changes. If the string is empty, it is valid. Each pass reads the string and removes at least one pair, so there can be n / 2 passes. That is O(n x n)."
• Improve: "The slow part is searching again and again for a pair that touches. A stack remembers the latest open bracket."

def is_valid(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif not stack or stack.pop() != pairs[ch]:
            return False
    return not stack

• Dry run: "{[]}": push {, push [, then ] removes [ and matches, then } removes { and matches. The stack is empty, so True. "([)]": push (, push [, then ) removes [, which is not (, so False."
• Edge cases: "The empty string gives True. '(' leaves the stack full, so False. ')' finds an empty stack, so False."
• Cost: "Time is O(n), one pass. Space is O(n), when the stack holds many open brackets."

• Saying the brute force first solves the risk of solving the wrong problem. It gives you a working base and it shows you where the slow part is. It costs about 3 minutes. I would shorten it to one sentence when the interviewer says to go straight to my best idea.
• Talking all the time solves the problem that the interviewer cannot see your thinking. It costs focus. I would ask for 30 seconds of quiet when I need it.

"I should start coding quickly to show that I am fast." The first minutes decide if you solve the right problem. The mock itself asks for the approach and the cost before code. A wrong plan that is coded quickly only wastes the 15 minutes.

"The brute force is a waste of time. I should say only the best answer." The brute force proves you understand the problem and shows the slow part. It also gives you a safe answer if you get stuck.

"Silence while I think shows deep thought." The interviewer cannot score silence. Say what you know, or ask for 30 seconds of quiet.

1. List the first five steps of the round in order.
2. n is 200,000. Assumption: 10 million simple steps a second. How long does an n x n method take? How long does a method with n steps take?
3. Your Two Sum code returns [0, 0] for [3, 3] with target 6. What do you do?