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 Onsite rounds at Mithril.

What role is this question designed for?

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

Determine Safe Bomb Defusal | Mithril Coding Question

Quick Overview

This question evaluates competency in graph traversal, state-space search, reachability analysis, and handling safety constraints within finite state machines. It is commonly asked in Coding & Algorithms interviews to test practical application of algorithmic reasoning—especially constrained pathfinding, cycle handling, and edge-case analysis—rather than purely theoretical understanding.

Determine Safe Bomb Defusal

Company: Mithril

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a finite state machine representing a bomb defusal process. - Each state is represented by a string. - `initialState` is the starting state. - `goalStates` is the set of states where the bomb is safely defused. - `unsafeStates` is the set of states that immediately fail the defusal. - `transitions` is a list of directed transitions. Each transition has a source state, an action name, and a destination state. At each step, you may choose one outgoing transition from the current state. You must never enter an unsafe state. The transition graph may contain cycles. Implement a function that determines whether there exists a sequence of legal actions that takes the bomb from `initialState` to any state in `goalStates` without ever entering an unsafe state. If a safe sequence exists, return it; otherwise return that no safe defusal is possible. Clarify edge cases such as: - The initial state is already a goal state. - The initial state is unsafe. - Multiple actions lead to the same state. - The graph contains cycles. - A state has no outgoing transitions.

Quick Answer: This question evaluates competency in graph traversal, state-space search, reachability analysis, and handling safety constraints within finite state machines. It is commonly asked in Coding & Algorithms interviews to test practical application of algorithmic reasoning—especially constrained pathfinding, cycle handling, and edge-case analysis—rather than purely theoretical understanding.

You are given a finite state machine for a bomb defusal process. Each state is a string. You start at `initialState`. Some states in `goalStates` represent a safely defused bomb, while any state in `unsafeStates` causes immediate failure. Each transition is a directed edge of the form `(sourceState, actionName, destinationState)`. At each step, you may choose one outgoing transition from the current state. You must never be in an unsafe state, including the starting state and every destination you enter. Return `(True, actions)` if there exists a safe sequence of actions that reaches any goal state without ever entering an unsafe state. `actions` must be the shortest such sequence by number of transitions. If multiple shortest safe sequences exist, return the one found by exploring outgoing transitions in the same order they appear in `transitions`. Return `(False, [])` if no safe defusal is possible. Edge cases: - If `initialState` is already a goal state and is not unsafe, return `(True, [])`. - If `initialState` is unsafe, return `(False, [])` even if it is also listed as a goal state. - Multiple actions may lead to the same state. - The graph may contain cycles. - A state with no outgoing transitions is a dead end unless it is already a goal state.

Constraints

0 <= len(transitions) <= 200000
The number of distinct states is finite and can be up to 100000
State names and action names are case-sensitive strings
goalStates and unsafeStates may be empty

Examples

Input: ('armed', {'done'}, {'boom'}, [('armed', 'cut_red', 'w1'), ('w1', 'press_button', 'done'), ('armed', 'cut_blue', 'boom')])

Expected Output: (True, ['cut_red', 'press_button'])

Explanation: The safe path is armed -> w1 -> done using actions cut_red, press_button. The cut_blue transition is illegal because it enters an unsafe state.

Input: ('safe', {'safe', 'done'}, {'boom'}, [('safe', 'wait', 'boom')])

Expected Output: (True, [])

Explanation: The initial state is already a goal state and is not unsafe, so no actions are needed.

Input: ('done', {'done'}, {'done'}, [('done', 'wait', 'other')])

Expected Output: (False, [])

Explanation: Unsafe states fail immediately. Since the initial state is unsafe, there is no legal safe sequence.

Input: ('s', {'g'}, {'x'}, [('s', 'to_a', 'a'), ('a', 'loop', 's'), ('a', 'trap', 'x'), ('a', 'to_b', 'b'), ('b', 'finish', 'g')])

Expected Output: (True, ['to_a', 'to_b', 'finish'])

Explanation: There is a cycle between s and a, but the safe route is s -> a -> b -> g. The transition to x is illegal because x is unsafe.

Input: ('start', {'done'}, {'fail'}, [('start', 'left', 'mid'), ('start', 'right', 'mid'), ('mid', 'finish', 'done')])

Expected Output: (True, ['left', 'finish'])

Explanation: Both left and right reach the same state in one step. Since transitions are explored in input order, the shortest returned path uses left first.

Input: ('start', {'done'}, {'fail'}, [('start', 'step', 'mid')])

Expected Output: (False, [])

Explanation: The state mid is a dead end and is not a goal state, so no safe defusal path exists.

Input: ('start', set(), {'fail'}, [('start', 'go', 'mid'), ('mid', 'finish', 'done')])

Expected Output: (False, [])

Explanation: There are no goal states at all, so reaching a safe defused state is impossible.

Hints

Model the states as graph nodes and the transitions as directed edges.
Because cycles are allowed and you need the shortest safe action sequence, think about BFS plus storing parent information to rebuild the path.

Last updated: Jun 6, 2026

Loading coding console...

Quick Overview

Determine Safe Bomb Defusal

Company: Mithril

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Constraints

0 <= len(transitions) <= 200000
The number of distinct states is finite and can be up to 100000
State names and action names are case-sensitive strings
goalStates and unsafeStates may be empty

Examples

Input: ('armed', {'done'}, {'boom'}, [('armed', 'cut_red', 'w1'), ('w1', 'press_button', 'done'), ('armed', 'cut_blue', 'boom')])

Expected Output: (True, ['cut_red', 'press_button'])

Explanation: The safe path is armed -> w1 -> done using actions cut_red, press_button. The cut_blue transition is illegal because it enters an unsafe state.

Input: ('safe', {'safe', 'done'}, {'boom'}, [('safe', 'wait', 'boom')])

Expected Output: (True, [])

Explanation: The initial state is already a goal state and is not unsafe, so no actions are needed.

Input: ('done', {'done'}, {'done'}, [('done', 'wait', 'other')])

Expected Output: (False, [])

Explanation: Unsafe states fail immediately. Since the initial state is unsafe, there is no legal safe sequence.

Input: ('s', {'g'}, {'x'}, [('s', 'to_a', 'a'), ('a', 'loop', 's'), ('a', 'trap', 'x'), ('a', 'to_b', 'b'), ('b', 'finish', 'g')])

Expected Output: (True, ['to_a', 'to_b', 'finish'])

Explanation: There is a cycle between s and a, but the safe route is s -> a -> b -> g. The transition to x is illegal because x is unsafe.

Input: ('start', {'done'}, {'fail'}, [('start', 'left', 'mid'), ('start', 'right', 'mid'), ('mid', 'finish', 'done')])

Expected Output: (True, ['left', 'finish'])

Explanation: Both left and right reach the same state in one step. Since transitions are explored in input order, the shortest returned path uses left first.

Input: ('start', {'done'}, {'fail'}, [('start', 'step', 'mid')])

Expected Output: (False, [])

Explanation: The state mid is a dead end and is not a goal state, so no safe defusal path exists.

Input: ('start', set(), {'fail'}, [('start', 'go', 'mid'), ('mid', 'finish', 'done')])

Expected Output: (False, [])

Explanation: There are no goal states at all, so reaching a safe defused state is impossible.

Hints

Model the states as graph nodes and the transitions as directed edges.
Because cycles are allowed and you need the shortest safe action sequence, think about BFS plus storing parent information to rebuild the path.

Last updated: Jun 6, 2026

Loading coding console...