Cracking the Safe

Cracking the Safe

What is this problem about?

The Cracking the Safe interview question is a mathematical puzzle involving combinations. You have a safe with an $n$-digit password, where each digit can be from $0$ to $k-1$. The safe opens if the last $n$ digits entered match the password. You want to find the shortest possible string that contains all possible $k^n$ passwords as substrings.

Why is this asked in interviews?

Google uses the Cracking the Safe coding problem to evaluate a candidate's knowledge of advanced graph theory, specifically De Bruijn sequences and Eulerian Circuits. It’s a "Hard" problem because it requires modeling passwords as edges in a directed graph and finding a path that visits every edge exactly once.

Algorithmic pattern used

This problem uses the Hierholzer’s Algorithm to find an Eulerian Circuit.

1. Each node in the graph represents a string of length $n-1$.
2. An edge exists from node $u$ to node $v$ if the last $n-2$ characters of $u$ plus a new digit $d$ form $v$.
3. The edge represents an $n$-digit password.
4. Since every node has an equal in-degree and out-degree (equal to $k$), an Eulerian circuit exists.
5. Use DFS to traverse the graph, adding the digit to the result string only after all edges from a node have been explored (post-order).

Example explanation

$n=2, k=2$ (Passwords: 00, 01, 10, 11)

1. Nodes are length $n-1=1$: "0" and "1".
2. From node "0", you can add digit '0' to get back to "0" (edge 00), or add digit '1' to go to "1" (edge 01).
3. From node "1", you can add '0' to go to "0" (edge 10), or add '1' to stay at "1" (edge 11).
4. A valid sequence could be "00110". Substrings: 00, 01, 11, 10. All 4 passwords are present.

Common mistakes candidates make

• Greedy Failure: Trying to build the string greedily without ensuring a path exists to visit the remaining combinations.
• Incorrect Graph Model: Representing passwords as nodes instead of edges, which makes finding the shortest path much harder.
• String Building: Forgetting to reverse the result if using a post-order DFS to build the circuit.

Interview preparation tip

This is a niche but classic problem. If you encounter it, mention "De Bruijn Sequences." Even if you don't remember the exact algorithm, identifying the graph theory category shows high-level expertise.