Confluent·Software Engineer·Technical Phone Screen
- You have a directed graph of n rooms, each with a monster that costs hp[i] energy to pass. Starting at room s with energy E, can you reach room t without your energy going negative? Return true/false and a valid path if one exists. Implement with DFS and pruning, and justify correctness and complexity.
- Extend the graph problem: now m potions are scattered across rooms, each granting a one-time energy boost on first visit. Find a path from s to t that maximizes rooms visited while keeping energy nonnegative, or report t is unreachable. The graph can have up to 200k nodes and 500k edges. Discuss your approach, correctness, and how you'd optimize it.
“Part A felt manageable once I framed it as a constrained path search.”