🎓 A1Learner
🔍

DSA The Interview Loop

The interview loop is a fixed order for solving a problem aloud in an interview. Its six stages are clarify, brute force, optimise, code, test, and state the complexity.

Clarify, then brute force

The problem asks for the longest run of days whose total bookings stay within a limit. Clarifying settles that bookings are never negative and the limit is given.

def longest_brute(days, limit):
    best = 0
    checks = 0
    for start in range(len(days)):
        total = 0
        for end in range(start, len(days)):
            total += days[end]
            checks += 1
            if total <= limit:
                best = max(best, end - start + 1)
    return best, checks

print("days:", [2, 1, 3, 1, 2], "limit:", 5)
print("brute force answer and checks:", longest_brute([2, 1, 3, 1, 2], 5))

Optimise with a sliding window

A sliding window is a range that grows at the right and shrinks at the left. Each day enters and leaves once, so the step count stays small.

def longest_fast(days, limit):
    best = 0
    left = 0
    total = 0
    steps = 0
    for right in range(len(days)):
        total += days[right]
        steps += 1
        while total > limit:
            total -= days[left]
            left += 1
            steps += 1
        best = max(best, right - left + 1)
    return best, steps

print("fast answer and steps:", longest_fast([2, 1, 3, 1, 2], 5))

Test the edges before finishing

The fast version runs on an empty list, one heavy day, one exact day, and one full run. Every answer matches what the rules demand.

def longest_fast(days, limit):
    best = 0
    left = 0
    total = 0
    for right in range(len(days)):
        total += days[right]
        while total > limit:
            total -= days[left]
            left += 1
        best = max(best, right - left + 1)
    return best

cases = [([], 5), ([7], 5), ([5], 5), ([2, 2, 2], 6)]
for days, limit in cases:
    print(days, "limit", limit, "->", longest_fast(days, limit))

Example

def longest_brute(days, limit):
    best = 0
    checks = 0
    for start in range(len(days)):
        total = 0
        for end in range(start, len(days)):
            total += days[end]
            checks += 1
            if total <= limit:
                best = max(best, end - start + 1)
    return best, checks

def longest_fast(days, limit):
    best = 0
    left = 0
    total = 0
    steps = 0
    for right in range(len(days)):
        total += days[right]
        steps += 1
        while total > limit:
            total -= days[left]
            left += 1
            steps += 1
        best = max(best, right - left + 1)
    return best, steps

cases = [
    ([2, 1, 3, 1, 2], 5, 3),
    ([], 5, 0),
    ([4, 4, 4], 8, 2),
    ([1, 1, 1, 1], 10, 4),
    ([9, 1, 1], 5, 2),
]
for days, limit, expected in cases:
    brute, checks = longest_brute(days, limit)
    fast, steps = longest_fast(days, limit)
    verdict = "PASS" if brute == expected and fast == expected else "FAIL"
    print("case", days, "limit", limit, "| expected", expected,
          "| brute", brute, "in", checks, "checks",
          "| fast", fast, "in", steps, "steps", "|", verdict)

Key points

  • The interview loop is a fixed order for solving a problem aloud.
  • Clarifying comes first because the answer depends on the exact rules.
  • A brute force solution proves the problem was understood.
  • Optimising replaces the slow part instead of rewriting everything.
  • Testing runs chosen cases before the interviewer finds a failure.
  • The complexity statement closes the problem with its real cost.

In this example, one fresh problem runs through all six stages in order. The clarify stage fixed the rules. Bookings are never negative, and the answer is a length, not the days themselves. The brute force stage checked every start and end pair. It answered 3 with 15 checks on the main case. The optimise stage replaced the inner loop with a sliding window. The window answered the same 3 in 8 steps. The code stage is the two functions printed above. The test stage ran five cases, including an empty list and a first day over the limit. Every case passed for both versions. The complexity stage reads the counts. Brute force costs O(n^2) checks, and the window costs O(n) steps because each day enters and leaves once. The window also holds O(1) extra space.

Note

Each stage is spoken aloud, not only typed.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A candidate writes polished code, then finds it fails on an empty input. Which stage would have caught this in the loop?