Solve constrained monster traversal

Q: Solve constrained monster traversal

This is a Coding & Algorithms interview question from Confluent for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Solve constrained monster traversal

Comments (0)