How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Confluent.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Confluent during technical interviews.

Solve constrained monster traversal | Confluent Coding Question

Quick Overview

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.

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.

Input: (1, [], [0], 0, 0, 0)

Expected Output: (True, [0])

Explanation: s == t == 0, entering it costs 0 with energy 0; the trivial single-room path is valid.

Input: (1, [], [3], 0, 0, 2)

Expected Output: (False, [])

Explanation: Entering the start room itself costs 3 but energy is only 2, so you die on entry; no path.

Input: (5, [[0,1],[0,2],[1,4],[2,3],[3,4]], [0,10,1,1,0], 0, 4, 5)

Expected Output: (True, [0, 2, 3, 4])

Explanation: Branch 0->1 is pruned (cost 10 > energy 5). The survivable route is 0->2->3->4.

Input: (3, [[0,1]], [0,0,0], 0, 2, 100)

Expected Output: (False, [])

Explanation: Target room 2 has no incoming edge and is unreachable regardless of energy.

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).

Input: (3, [[0,1],[1,2]], [0,5,0], [], 0, 2, 4)

Expected Output: -1

Explanation: Room 1 costs 5 with energy 4 and there is no potion; t=2 is unreachable survivably, so -1.

Input: (3, [[0,1],[1,2]], [0,5,0], [[1,3]], 0, 2, 4)

Expected Output: 3

Explanation: Potion +3 in room 1 makes entry net -2 (4 -> 2), so 0->1->2 survives and visits 3 rooms.

Input: (1, [], [0], [], 0, 0, 0)

Expected Output: 1

Explanation: s == t == 0; the single-room path is trivially survivable, count = 1.

Input: (1, [], [3], [], 0, 0, 2)

Expected Output: -1

Explanation: Entering the only room (which is also t) costs 3 but energy is 2, so you die on entry; -1.

Input: (5, [[0,1],[0,2],[1,4],[2,3],[3,4]], [0,10,1,1,0], [[1,12]], 0, 4, 5)

Expected Output: 4

Explanation: Path 0->1->4 with the +12 potion survives but visits only 3 rooms; the longer survivable path 0->2->3->4 visits 4 rooms, which is the maximum.

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.

Quick Overview