Solve constrained monster traversal
Company: Confluent
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a directed graph with n rooms labeled 0..n-1; each room i contains a monster with health hp[i] ≥ 0. You start at room s with energy E. Entering room i immediately reduces your energy by hp[i]; if energy ever becomes negative, you die. Part A: Determine whether there exists a path from s to target t such that energy never drops below 0 at any point; return true/false and one valid path if it exists. Implement using DFS with pruning and justify correctness and complexity. Part B: There are m potions; potion j sits in room pj and increases your energy by gain[j] the first time you enter pj. You may collect any potions along the way. Find a path from s to t that maximizes the number of rooms you can visit while keeping energy nonnegative, or report that t is unreachable. Discuss algorithmic approach (e.g., graph search with state, heuristics, or DP), correctness, and optimize for n up to 2e5 and edges up to 5e5.
Quick Answer: Solve constrained monster traversal evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Constrained Monster Traversal — Part A: Survivable Path Existence
You are given a directed graph with `n` rooms labeled `0..n-1`. Each room `i` contains a monster with health `hp[i] >= 0`. You start at room `s` with energy `E`. Entering a room (including the start room `s`) immediately reduces your energy by that room's `hp`; if your energy ever becomes negative, you die.
Determine whether there exists a path from `s` to target `t` such that your energy never drops below `0` at any point. Return a pair `(reachable, path)` where `reachable` is a boolean and `path` is one valid sequence of room labels from `s` to `t` (inclusive) if it exists, or an empty list otherwise.
The intended approach is DFS with energy-based pruning: prune any branch whose next entry would make energy negative. Because all `hp[i] >= 0`, revisiting a room can never increase your remaining energy, so it is sufficient (and optimal) to search over simple paths only.
Input: `n` (int), `edges` (list of `[u, v]` directed edges), `hp` (list of length `n`), `s` (start), `t` (target), `E` (initial energy).
Constraints
- 1 <= n <= 2*10^5 (challenge inputs are small)
- 0 <= edges.length <= 5*10^5
- hp[i] >= 0 for all i
- 0 <= s, t < n
- E >= 0
- Energy must remain >= 0 after entering every room on the path, including s.
Examples
Input: (4, [[0,1],[1,2],[0,2],[2,3]], [0,2,1,1], 0, 3, 4)
Expected Output: (True, [0, 1, 2, 3])
Explanation: Start energy 4, enter 0 (cost 0) -> 4, enter 1 (cost 2) -> 2, enter 2 (cost 1) -> 1, enter 3 (cost 1) -> 0. Energy never negative, reaches t=3.
Input: (3, [[0,1],[1,2]], [0,5,0], 0, 2, 4)
Expected Output: (False, [])
Explanation: Only path 0->1->2 requires surviving room 1 (cost 5) with energy 4, which goes negative. No survivable path exists.
Hints
- Entering the start room s also costs hp[s]; the path is impossible immediately if E - hp[s] < 0.
- Because every hp[i] >= 0, walking through extra rooms can only lower your energy — so a simple path (no repeated rooms) is always at least as good as any walk that revisits rooms.
- Prune before recursing: only descend into a neighbor w if (current_energy - hp[w]) >= 0. This bounds the search to survivable states.
Constrained Monster Traversal — Part B: Maximize Rooms Visited with Potions
Same setup as Part A: a directed graph of `n` rooms with monster health `hp[i] >= 0`, starting at room `s` with energy `E`, entering a room reduces energy by its `hp`, and energy must never go negative.
Now there are also potions. Each potion is given as `[room, gain]`: the first time you enter `room`, your energy increases by `gain`. The net energy change when entering a room `r` is `gain[r] - hp[r]` (potions and the monster both apply on entry).
Find a path from `s` to `t` that maximizes the number of distinct rooms visited while keeping energy nonnegative after every entry. Return that maximum count of rooms (the path length in rooms, inclusive of `s` and `t`), or `-1` if `t` is unreachable under the energy constraint.
Model the search as a state-space DFS over simple paths (each room visited at most once — potions are one-time, so revisiting a room is never beneficial). Among all survivable simple paths that end at `t`, return the largest room count.
Input: `n`, `edges` (list of `[u, v]`), `hp` (length `n`), `potions` (list of `[room, gain]`), `s`, `t`, `E`.
Constraints
- 1 <= n <= 2*10^5 (challenge inputs are small)
- 0 <= edges.length <= 5*10^5
- hp[i] >= 0; potion gain[j] >= 0
- Each potion [room, gain] applies once, on first entry to room
- Energy must remain >= 0 after entering every room, including s
- Return -1 if no survivable path reaches t
Examples
Input: (4, [[0,1],[1,2],[0,2],[2,3]], [0,2,1,1], [], 0, 3, 4)
Expected Output: 4
Explanation: No potions. The longest survivable path to t=3 is 0->1->2->3, visiting 4 rooms.
Input: (4, [[0,1],[1,2],[0,2],[2,3]], [0,5,1,1], [[1,5]], 0, 3, 4)
Expected Output: 4
Explanation: Room 1 costs 5 but holds a +5 potion (net 0 on entry), so 0->1->2->3 stays survivable and visits all 4 rooms; without the potion you'd be forced onto the shorter 0->2->3 (3 rooms).
Hints
- Precompute a per-room gain array from the potion list, then the energy delta on entering room r is simply gain[r] - hp[r].
- Potions are one-time and hp >= 0, so revisiting a room never helps. Restrict the search to simple paths (mark rooms on the current path).
- Track the running room count; whenever the DFS reaches t, update a global best. The answer is that best, or -1 if t is never reached survivably.