Getting unstuck: heuristics and using hints

Most coding rounds have a moment when the problem is clear, a brute force is on the screen and no better idea comes. What you do next is a skill you can practise. This lesson gives you six questions to ask a problem when no approach comes to mind and follows them through one problem as a conversation. Then it covers the other half of getting unstuck: thinking aloud so that a hint can help, and turning a hint into code without throwing away what already works.

Six heuristics for when nothing comes to mind

A heuristic is a question that often produces an idea, with no promise that it will. Each of these takes a few minutes with a pen and paper, so you can try several before you need a hint. Start with the first two: they cost the least, and what they show you makes the others easier.

1. Solve a smaller case by hand. What would you do with three items, or with one? This often shows the work that your brute force repeats, and the edge cases.
2. Draw the data. What does the input look like as a table, a timeline, a grid or a graph? Running totals, overlaps and neighbours show up, and sometimes a graph hiding in a list.
3. Work backwards from the answer. If you already had the answer, what would be true of it? This often gives a target value to look for, or the last step of a recursion.
4. Fix one variable, optimise the other. If this index or value were fixed, what would be the best choice for the rest? A nested loop often becomes one loop and a lookup.
5. Look for something monotonic. What only grows, or only shrinks, as you move through the input? That allows an early stop, two pointers or a binary search.
6. Relax a constraint, then add it back. Which rule makes the problem hard, and could you solve it without that rule? The simpler problem often has a solution that you can repair.

Asking yourself questions, rather than following recipes, is the approach of George Pólya’s How to Solve It, a classic book on solving problems. It was written about mathematics, and working backwards from the goal is one of its techniques. The habits carry over to algorithms, where the variable you fix, the quantity that only grows or the rule you drop often names the data structure that the fast solution needs.

Two habits make the list work. Try each heuristic on a concrete input small enough to finish by hand, because that is where patterns show. And say which one you are trying, which is what the second half of this lesson is about.

A worked example: side A and side B

Here is one way the conversation can go when the fast idea does not come at once. Where a step uses one of the six heuristics, a note in italics names it.

1. You: “Let me check the rules: one cut, the songs keep their order, each side gets at least one song, and every length is at least one minute?”

   Interviewer: “Yes. And there can be up to 100,000 songs.”

2. You: “The brute force tries every cut and adds up both sides. That’s about n additions for each of n cuts, so about ten billion for 100,000 songs: far too slow. I’ll write it anyway, because it’s correct and I can test a faster version against it.”

3. You: “I don’t see the faster version yet, so let me do a small case by hand: songs of 3, 1, 2, 4 and 2 minutes, every cut, as a table.”

   Heuristics: solve a smaller case by hand, and draw the data.

"""Every cut of a five-song playlist, with the totals of both sides."""

lengths = [3, 1, 2, 4, 2]  # song lengths in minutes
total = sum(lengths)
print(f"playlist {lengths}, total {total} minutes")
print("songs on side A   side A   side B")
for k in range(1, len(lengths)):  # side A gets the first k songs
    side_a, side_b = sum(lengths[:k]), sum(lengths[k:])
    note = "   equal" if side_a == side_b else ""
    print(f"{k:>15}   {side_a:>6}   {side_b:>6}{note}")

playlist [3, 1, 2, 4, 2], total 12 minutes
songs on side A   side A   side B
              1        3        9
              2        4        8
              3        6        6   equal
              4       10        2

4. You: “Side B is always 12 minus side A. So once the cut is fixed, I only need side A, and side B follows from the total.”

   Heuristic: fix one variable (the cut) and get the other from what you already know.

5. Interviewer: “If a cut works, what do you know about side A?”

6. You: “The two sides are equal, so side A is exactly half the total: 6 here. And an odd total can’t be halved, so then the answer is -1 straight away.”

   Heuristic: work backwards from the answer.

7. You: “Moving the cut one song to the right adds exactly that song to side A. So a running total gives me side A for every cut in one pass: O(n) time and O(1) extra memory.”

8. You: “And because every length is positive, the running total only grows. Once it passes half, no later cut can work, so I can stop there.”

   Heuristic: look for something monotonic.

Here are both versions in code. split_fast is the plan of steps 4 to 8: the check for an odd total, a running total and the early stop.

"""Cut a playlist into two sides that play for the same time."""


def split_brute(lengths):
    """Try every cut, adding up both sides from scratch: about n * n additions."""
    for k in range(1, len(lengths)):  # k songs on side A
        if sum(lengths[:k]) == sum(lengths[k:]):
            return k
    return -1


def split_fast(lengths):
    """Side A must be half the total, and each cut adds one song to it: O(n)."""
    total = sum(lengths)
    if total % 2 == 1:  # an odd total cannot be cut into equal halves
        return -1
    half = total // 2
    side_a = 0
    for k in range(1, len(lengths)):  # k songs on side A, at least one on B
        side_a += lengths[k - 1]
        if side_a == half:
            return k
        if side_a > half:  # lengths are positive: side A only grows
            return -1
    return -1


if __name__ == "__main__":
    playlists = [[3, 1, 2, 4, 2], [5, 5], [1, 2, 4], [2, 3], [7]]
    print([split_fast(p) for p in playlists])

[3, 1, -1, -1, -1]

The demo covers the edge cases too: [5, 5] has a cut after one song, [1, 2, 4] and [2, 3] have odd totals, and [7] has nowhere to cut. If you prefer a library call to the loop, itertools.accumulate gives the same running totals.

Notice what made the single hint in step 5 work. Because steps 2 to 4 were said aloud, the interviewer knew that a correct brute force existed and that you had already seen side B as the total minus side A. The question could aim at the next idea that was missing.

Keep the brute force and test against it

The brute force does exactly what the problem says, so it is easy to trust, and the fast version has to give the same answers. A stress test runs both on many small random inputs, where the brute force is quick, and stops at the first disagreement:

"""Compare split_fast with split_brute on 1,000 small random playlists."""
import random

from split import split_brute, split_fast

rng = random.Random(2)  # a fixed seed: the same playlists on every run
with_a_cut = 0
for case in range(1000):
    lengths = [rng.randint(1, 6) for _ in range(rng.randint(1, 8))]
    expected, got = split_brute(lengths), split_fast(lengths)
    if got != expected:
        print(f"case {case}: {lengths}: brute force {expected}, split_fast {got}")
        raise SystemExit(1)
    if expected != -1:
        with_a_cut += 1
print(f"1000 playlists, {with_a_cut} of them with a cut: no mismatches")

1000 playlists, 140 of them with a cut: no mismatches

The fixed seed makes every run test the same 1,000 playlists. The count in the output matters as well: 140 of them have a cut that works, so the test compared real answers and not only -1.

A common mistake: halving with //

This fast version looks right and gives the answer 3 for the playlist of the conversation. It halves the total with // and leaves out the check for an odd total. The same stress test finds the problem in the fifth playlist it tries:

"""The same stress test on a plausible bug: // and no check for an odd total."""
import random

from split import split_brute


def split_floor(lengths):
    """split_fast without its check for an odd total."""
    half = sum(lengths) // 2  # 7 // 2 is 3: an odd total is rounded down
    side_a = 0
    for k in range(1, len(lengths)):
        side_a += lengths[k - 1]
        if side_a == half:
            return k
        if side_a > half:
            return -1
    return -1


rng = random.Random(2)
for case in range(1000):
    lengths = [rng.randint(1, 6) for _ in range(rng.randint(1, 8))]
    expected, got = split_brute(lengths), split_floor(lengths)
    if got != expected:
        print(f"case {case}: {lengths}: brute force {expected}, split_floor {got}")
        a, b = sum(lengths[:got]), sum(lengths[got:])
        print(f"with {got} songs on side A, side A plays {a} and side B {b}")
        raise SystemExit(1)
print("1000 playlists: no mismatches")

case 4: [5, 4, 5, 3, 1, 1]: brute force -1, split_floor 2
with 2 songs on side A, side A plays 9 and side B 10

The total is 19, and 19 // 2 is 9, so the function reports the cut where side A reaches 9 minutes and leaves 10 on side B. A rounded-down half is not a half. The fix is the line that split_fast has and this version lacks: return -1 when the total is odd.

Keeping the brute force matters most when time is short. On some online-assessment platforms each hidden test case is worth its own points, and your score is the sum over the cases that pass: HackerRank’s documentation of its coding questions describes exactly this. A correct slow solution then scores on every case it finishes in time, while a fast one that is half written scores nothing. So submit the version that works first, then improve it in a new function beside it.

Think aloud so that a hint can help

An interviewer can only redirect what they can hear. While you think in silence, they cannot tell whether you are one step from the answer or heading into a dead end, so a hint comes late or aims at the wrong gap. Whenever your plan changes, say three things in a sentence or two: what you are trying, why it might work, and what would show you whether it does.

Thinking aloud does not mean talking without a break. It is fine to say “give me a minute to work this example” and write in silence, then say what the example showed. When you want a hint, ask a specific question: “Is a running total the right direction, or is there a better first step?” is easier to answer well than “Can you help me?”.

In an online assessment nobody hears you, but the habit still helps. A one-line comment with the idea you are trying keeps you from circling back to it, and the six heuristics are your hints. If none of them gives you a plan, move on to another question and come back to this one later.

Turn a hint into the next step

Hints usually arrive as questions, and a question is hard to code. Before you touch the code, restate the hint as an operation on the data, then try that operation on your small example.

A lookup in a Python set or dict takes constant time on average (the documentation’s table of time complexity gives O(1) for x in s), which is why replacing an inner loop with one can turn O(n²) into O(n).

Then change the plan, not the whole program. A hint that sounds like a new direction usually replaces one loop. Write the new idea as a new function next to the brute force, run both on the small example, then run the stress test. If the idea fails, you still have working code, and the interviewer has seen you test before you trust.

A hint ladder for the playlist problem

When you practise alone, a hint ladder plays the interviewer’s part: hints written in order, from the lightest nudge to an almost complete plan, and opened one at a time only when you are stuck. Here is one for the playlist problem, with what each rung changes in the plan.

How much work does each rung save? This program counts the additions made by the plan after each rung, on two playlists of 1,000 songs: one with an even total and no cut that works, and one with an odd total.

"""Count the additions each plan of the hint ladder makes on 1,000 songs."""

additions = 0


def add(a, b):
    """a + b, counted."""
    global additions
    additions += 1
    return a + b


def total_of(songs):
    total = 0
    for length in songs:
        total = add(total, length)
    return total


def plan0(lengths):
    """No hint yet: try every cut, adding up both sides from scratch."""
    for k in range(1, len(lengths)):
        if total_of(lengths[:k]) == total_of(lengths[k:]):
            return k
    return -1


def plan1(lengths):
    """Hint 1: side A must be half the total, so an odd total has no cut."""
    total = total_of(lengths)
    if total % 2 == 1:
        return -1
    for k in range(1, len(lengths)):
        if total_of(lengths[:k]) == total // 2:
            return k
    return -1


def plan2(lengths):
    """Hint 2: each cut adds one song to side A, so keep a running total."""
    total = total_of(lengths)
    if total % 2 == 1:
        return -1
    side_a = 0
    for k in range(1, len(lengths)):
        side_a = add(side_a, lengths[k - 1])
        if side_a == total // 2:
            return k
    return -1


def plan3(lengths):
    """Hint 3: the lengths are positive, so stop once side A is past half."""
    total = total_of(lengths)
    if total % 2 == 1:
        return -1
    side_a = 0
    for k in range(1, len(lengths)):
        side_a = add(side_a, lengths[k - 1])
        if side_a == total // 2:
            return k
        if side_a > total // 2:
            return -1
    return -1


playlists = {
    # Total 1998, so half is 999. Side A runs 2, 4, ..., 1000 and then
    # 1001, 1003, ...: it never equals 999.
    "even, no cut": [2] * 500 + [1] + [2] * 498 + [1],
    "odd total": [2] * 999 + [1],
}
print("additions" + "".join(f"{name:>16}" for name in playlists))
for plan in (plan0, plan1, plan2, plan3):
    counts = []
    for lengths in playlists.values():
        additions = 0
        assert plan(lengths) == -1  # no plan finds a cut in either playlist
        counts.append(additions)
    print(f"{plan.__name__:<9}" + "".join(f"{count:>16,}" for count in counts))

additions    even, no cut       odd total
plan0             999,000         999,000
plan1             500,500           1,000
plan2               1,999           1,000
plan3               1,500           1,000

The second rung is the big one: it turns about n²/2 additions into about 2n. The first pays off at once when the total is odd, and the third saves another quarter here by stopping halfway. Counts like these come out the same on every computer, which timings do not.

Practise with the exercise

The exercise below is a harder relative of the playlist problem, and it comes with a hint. Work it the way this lesson suggests: set a time limit, write a brute force and pass the sample tests with it, try the heuristics on a small playlist, and open the hint only when the time is up. Before you code the hint, write it down as an operation.

Key takeaways

• When no approach comes to mind, ask the problem questions: a smaller case by hand, the data drawn as a table, the answer worked backwards, one variable fixed, something monotonic, a constraint relaxed. Try the cheap ones first, on an input small enough to finish.
• Say what you are trying, why, and what would show that it works: an interviewer can only aim a hint at a gap they can hear.
• Restate each hint as an operation on the data and try it on your small case before you code it.
• Keep the brute force runnable. It earns the points of the test cases it passes, and it is the reference that your stress test compares the fast version with.
• When a stress test fails, print the failing input and keep it as a test case.