Lab 05 — Manual Testing

Goal

Train the discipline of manually walking through your code before claiming it’s done — and finding bugs before the interviewer does.

Background Concepts

Trace tables: writing variable state row-by-row through a loop
Edge cases as a reflex
The “rubber duck” verbalization while tracing
Pre-submission checklist

Strong candidates always test their code by walking through at least one example by hand, vocalizing variable state. The interviewer learns whether you can verify your own work — a critical engineering signal.

Weak candidates write the code and say “I think this works” without verification, then submit and the interviewer finds the bug. Even when the candidate would have caught the bug if they’d traced.

Problem Statement

You are given 4 small functions below, each with at least one bug. For each:

Construct a trace table for one input
Identify the bug
State a fix
Construct a test case that exposes the bug

Function 1 — is_palindrome(s: str) -> bool:

def is_palindrome(s):
    i, j = 0, len(s)
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

Function 2 — binary_search(a: list[int], target: int) -> int:

def binary_search(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        elif a[mid] < target:
            lo = mid
        else:
            hi = mid
    return -1

Function 3 — reverse_linked_list(head):

def reverse_linked_list(head):
    prev = None
    curr = head
    while curr.next is not None:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

Function 4 — max_subarray(a: list[int]) -> int:

def max_subarray(a):
    best = 0
    cur = 0
    for x in a:
        cur += x
        if cur < 0:
            cur = 0
        if cur > best:
            best = cur
    return best

Constraints

Standard.

Clarifying Questions

For palindrome: case-sensitive? Treat as is.
For binary search: input is sorted ascending, no duplicates.
For reverse linked list: input may be empty.
For max subarray: input may be all negative.

Examples

For each function, work a non-trivial input by trace table.

Initial Brute Force

N/A — debugging lab.

Brute Force Complexity

N/A.

Optimization Path

N/A.

Final Expected Approach

For each function, identify:

The bug
The minimal fix
The triggering input

Reference answers (DON’T peek until you’ve tried):

is_palindrome: j = len(s) should be len(s) - 1 (or change loop to i < j and use s[i] == s[j-1] style — but as written, immediate IndexError on non-empty input). Trigger: any non-empty string.
binary_search: lo = mid should be lo = mid + 1, otherwise infinite loop. Trigger: target larger than a[lo] but smaller than a[hi-1], e.g., a=[1,2,3], target=3. Actually wait — let’s check: lo=0, hi=3, mid=1, a[1]=2 < 3, lo=1 (correct in the buggy version; mid would still advance). Try a=[1,3], target=3: lo=0, hi=2, mid=1, a[1]=3 → return 1. OK that works. Try a=[1,2], target=2: lo=0, hi=2, mid=1, a[1]=2 → return 1. Try a=[1], target=2: lo=0, hi=1, mid=0, a[0]=1<2, lo=0 → infinite loop. Trigger: target greater than max element.
reverse_linked_list: loop condition while curr.next is not None skips reversing the last node. Should be while curr is not None. Also crashes on empty input (head = None).
max_subarray: initializing best = 0 fails on all-negative input — returns 0 instead of the largest (least negative) element. Should be best = -infinity or best = a[0].

Data Structures Used

Trace table: a small ASCII grid of variable values per loop iteration

Build a trace table on paper
Identify the bug
Write the fix
Write 4 unit tests covering the bug and adjacent cases

Tests

For function 1:

assert is_palindrome("") == True
assert is_palindrome("a") == True
assert is_palindrome("aa") == True
assert is_palindrome("ab") == False
assert is_palindrome("racecar") == True

For function 2:

assert binary_search([], 5) == -1
assert binary_search([5], 5) == 0
assert binary_search([1,2,3], 0) == -1
assert binary_search([1,2,3], 4) == -1   # the trigger
assert binary_search([1,3,5,7], 5) == 2

(Build similar for #3, #4.)

Follow-up Questions

“How would you find this bug in production?” — logs, test failure, customer report
“How would you prevent this class of bug?” — property-based testing, fuzz testing
“What’s your debugging strategy when you can’t reproduce locally?” — see phase-10-testing-debugging/

Product Extension

These four bugs are real bug archetypes:

Off-by-one (#1, #2)
Loop termination (#2, #3)
Initialization (#4)

In code review, scan specifically for: array bounds, loop conditions, accumulator initial values, null inputs.

Language/Runtime Follow-ups

Python: index s[len(s)] raises IndexError immediately — defensive crash
C/C++: would silently read garbage and possibly continue. Always be more defensive
Java: ArrayIndexOutOfBoundsException like Python
Go: panic with clear message

Common Bugs

The four bugs themselves are the common bugs:

Off-by-one in array bounds
Off-by-one in binary search update
Loop terminates one iteration early
Wrong initial accumulator value

Debugging Strategy

Trace table for the smallest failing input
Print state every iteration (the printf approach)
Verbalize the loop invariant — does the code uphold it?
Step through with a debugger (last resort, not first — debugger usage is slower than tracing for small problems)

Deliverable

Trace tables for all 4 functions (one per function)
Bug identification + fix + test suite for each
A “trace table template” you’ll reuse going forward

Mastery Criteria

Found all 4 bugs via tracing (without peeking at answers)
Wrote correct fixes
Wrote tests that exposed each bug
Can construct a trace table for an unseen function in <2 minutes
Adopted “always trace one example before submitting” as a permanent habit

LeetCode Interview — Extreme Coding