Expression and Simulation

What is this?

Neither of these is a bracket-matching problem, and that is the point. In one, the "stack" is the recursion itself, carrying enough state that a multiplication arriving later can reach back and correct an addition already made. In the other, a genuine stack of call frames answers a question no single frame can: how much time a function spent excluding everything it called.

💡 Fun fact: the multiplication trick in Expression Add Operators is a small piece of algebra doing the work of a parser. Having built 1 + 2 you hold total = 3 and prev = 2. A * 3 must not give 9 — precedence says the 2 binds to the 3 first. So you undo the previous operand and re-apply it multiplied: total − prev + prev × num = 3 − 2 + 6 = 7. Two extra terms carried through the recursion replace an entire precedence-climbing parser.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: carry exactly the state a later decision will need — the previous operand so multiplication can correct itself, or the currently running function so elapsed time is credited to the right owner.

1. Carry the previous operand

def dfs(index, expr, total, prev):
    if index == len(num):
        if total == target: results.append(expr)
        return
    for end in range(index, len(num)):
        if end > index and num[index] == '0':
            break                                  # no leading zeros
        s = num[index:end + 1]
        val = int(s)
        if index == 0:
            dfs(end + 1, s, val, val)              # first operand: no operator
        else:
            dfs(end + 1, expr + '+' + s, total + val,  val)
            dfs(end + 1, expr + '-' + s, total - val, -val)
            dfs(end + 1, expr + '*' + s, total - prev + prev * val, prev * val)

Three things are doing real work. prev is signed — after a -, the previous operand is negative, and multiplication must use that sign or the correction is wrong. The leading-zero guard breaks rather than continues, because once a multi-digit number starts with 0 every longer extension is also invalid. And the first operand takes no operator, which is why it is a separate branch rather than a special case inside the loop.

2. Credit time to whoever is on top

res = [0] * n
stack, prev = [], 0
for log in logs:
    fid, typ, ts = parse(log)
    if typ == 'start':
        if stack: res[stack[-1]] += ts - prev      # credit the caller up to now
        stack.append(fid); prev = ts
    else:
        res[stack.pop()] += ts - prev + 1          # inclusive end timestamp
        prev = ts + 1

The + 1 on an end event and the prev = ts + 1 that follows are the whole difficulty: end timestamps are inclusive, so a function that starts and ends at the same timestamp ran for one unit, not zero. Every off-by-one in this problem lives in those two lines.

The credit-on-start line is what makes the time exclusive: the moment a child begins, the parent stops accruing, and it resumes only when the child returns.

3. A 30-second worked example (the multiplication correction)

num = "123", target = 6. Following the branch that builds 1 + 2 * 3:

"1"        total = 1    prev = 1
"+2"       total = 3    prev = 2
"*3"       total = 3 - 2 + (2 x 3) = 7    prev = 6      ✗ not the target

and the branch that builds 1 * 2 * 3:
"1"        total = 1    prev = 1
"*2"       total = 1 - 1 + (1 x 2) = 2    prev = 2
"*3"       total = 2 - 2 + (2 x 3) = 6    prev = 6      ✓ target reached

Note the second line of the second branch: 1 * 2 correctly gives 2, because the correction subtracts the standalone 1 before multiplying it. Naive left-to-right accumulation would give the same answer here but diverges the moment an addition precedes the multiplication — which is exactly what the first branch shows.

4. Where you'll actually meet this

• Profilers. Self time versus total time per function is computed from a call log exactly as here; every flame graph depends on it.
• Distributed tracing. Span accounting in Jaeger or OpenTelemetry subtracts child spans from parents the same way.
• Billing and metering. Attributing elapsed time to the correct owner when work nests.
• Spreadsheet and rule engines. Evaluating user-supplied expressions with precedence, without writing a full parser.
• Puzzle and constraint tooling. Inserting operators to reach a target is the shape of countdown-style solvers.

5. Problems in this chapter

▶ Expression Add Operators

Insert +, -, * between digits so the expression equals a target. Backtracking that carries the running total and the signed previous operand so multiplication can correct the last term.
Pattern: backtracking with carried evaluation state. Target: O(4ⁿ) with pruning, O(n) depth.

▶ Exclusive Time of Functions

Compute each function's self time from a log of start and end events. A stack of running call ids, crediting elapsed time to whatever is on top.
Pattern: call-stack accounting. Target: O(n) time, O(depth) space.

6. Common pitfalls 🚫

• Forgetting prev is signed. After a subtraction it must be negative, or the multiplication correction produces the wrong total.
• Allowing leading zeros. "05" is not a valid operand, and the guard must break, not continue.
• Giving the first operand an operator. It has none; handle it as its own branch.
• Treating end timestamps as exclusive. They are inclusive — hence the + 1 and the prev = ts + 1.
• Crediting a child's time to its parent. The parent stops accruing the instant the child starts.
• Assuming single-digit function ids when parsing the log.
• Integer overflow in other languages: concatenated operands can exceed 32 bits before the target comparison.

7. Key takeaways

1. Carry the state a later decision needs. prev exists solely so multiplication can undo an addition.
2. total − prev + prev × num is precedence handled by algebra rather than by a parser.
3. Sign travels with the operand, not with the operator.
4. Inclusive timestamps mean + 1 — and that single convention is where every bug in the timing problem lives.
5. Exclusive time means the parent pauses while a child runs.
6. Break on leading zeros, because every longer extension is invalid too.
7. Why interviewers like it: both look like parsing exercises and are really tests of whether you carry precisely the right state — too little and the answer is wrong, too much and the recursion is unmanageable.

Order: Expression Add Operators → Exclusive Time of Functions.