</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

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.

Two problems whose stacks carry evaluation state

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, because 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.


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 prev timestamp, 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 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.
  • Calling the backtracking O(4^n). Each leaf copies an expression string, so it is O(n * 4^n).
  • 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 most bugs in the timing problem live.
  5. Exclusive time means the parent pauses while a child runs, and one prev timestamp marks where the pause began.
  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.

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.