Expression and Simulation
What is this?
Neither of these is a bracket-matching problem, and that is the point. In one, the recursion carries a running total and the last operand, so a multiplication arriving later can reach back and correct an addition already made. In the other, a real stack of open call ids answers a question no single call 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 + 2you holdtotal = 3andprev = 2. A* 3must not give9, because precedence says the2binds to the3first. 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.
Core idea: carry exactly the state a later decision will need. That is the previous operand, so multiplication can correct itself, or the stack of open calls plus a
prevtimestamp, 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.
The lesson frames this as an OCR'd register tape whose operators washed out, with total and prev as the two numbers you carry. Each leaf copies an expression string, so the cost is O(n * 4^n), not O(4^n).
2. Credit time to whoever is on top of the stack
res = [0] * n
stack, prev = [], 0 # open call ids; first uncredited time unit
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. Most off-by-one errors in this problem live 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. Recursion needs no special case, since the same id can appear on the stack more than once.
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 per function comes from a call log by crediting each interval to the call on top of the stack, and flame graphs are built from stacks of open calls like this.
- Expression evaluators. Handling precedence while generating or reading an expression, without a full parser, uses the same undo-and-reapply step.
- Interviews. Both are stack or recursion simulations where the test is a small convention: the sign of
prev, or the inclusive end stamp.
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(n * 4^n) time (each leaf copies an expression string), O(n) recursion depth.
Exclusive Time of Functions
Compute each function's self time from a log of start and end events. A stack of call ids plus one prev timestamp, crediting elapsed time to whatever is on top.
Pattern: call-stack accounting. Target: O(n) time, O(depth) space.
6. Common pitfalls
- Forgetting
previs 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 mustbreak, notcontinue. - 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
+ 1and theprev = 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.
- Calling the backtracking
O(4^n). Each leaf copies an expression string, so it isO(n * 4^n). - Integer overflow in other languages: concatenated operands can exceed 32 bits before the target comparison.
7. Key takeaways
- Carry the state a later decision needs.
prevexists solely so multiplication can undo an addition. total - prev + prev * numis precedence handled by algebra rather than by a parser.- Sign travels with the operand, not with the operator.
- Inclusive timestamps mean
+ 1, and that single convention is where most bugs in the timing problem live. - Exclusive time means the parent pauses while a child runs, and one
prevtimestamp marks where the pause began. - Break on leading zeros, because every longer extension is invalid too.
- 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.
Calculating Exclusive Execution Time for Function Calls
Core idea: Keep a stack of the calls that are open and one variable,
prev, the first time unit nobody has been credited for yet. On astart, the call on top of the stack has been running sinceprev, so credit itts - prev, push the new call and setprev = ts. On anend, credit the topts - prev + 1(an end stamp includes its own unit), pop, and setprev = ts + 1. Recursion needs no special case: the same id just appears on the stack more than once. O(n) time overnlog lines.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson