Hello All:
In fact it has been a long time since we had posted any sort of interview questions or puzzles and so here we are with a very practical problem.
Let's see how many of you can crack it! The puzzle is stated below as it was first posted in 2008. The answer, with a full worked solution, now follows it, so stop reading at the question if you want to try it first.
The problem
The Sheel lock Company has recently received an order from Mr. Manmohan Singh for their all-digital Perfectly Perplexing Padlock (P3). The P3 has two buttons ("0" and "1") that when pressed cause the FSM controlling the lock to advance to a new state. In addition to advancing the FSM, each button press is encoded on the B signal (B=0 for button "0", B=1 for button "1").
The padlock unlocks when the FSM sets the UNLOCK output signal to 1, which it does whenever the last N button presses correspond to the N-digit combination. Unfortunately the design notes for the P3 are incomplete. Using the specification above and clues gleaned from the partially completed diagrams below fill in the information that is missing from the state transition diagram with its accompanying truth table.
When done
- each state in the transition diagram should be assigned a 2-bit state name S1S0 (note that in this design the state name is not derived from the combination that opens the lock),
- the arcs leaving each state should be mutually exclusive and collectively exhaustive,
- the value for UNLOCK should be specified for each state, and
- the truth table should be completed.

What is the combination for the lock?
The puzzle is adapted from a finite state machine tutorial problem used in MIT's digital design courses; the original version is Problem 2 in the MIT 6.111 (Fall 2005) FSM tutorial problems.
What the puzzle is really testing
The lock is a sequence detector: a finite state machine that watches a stream of bits and raises an output whenever the most recent bits match a pattern. Sequence detectors are among the most common FSM interview questions because they test three skills at once:
- Turning a word description into states that each mean something ("I have seen the first digit", "I have seen the first two digits").
- Handling overlap: when a wrong press arrives, the machine must not always go back to the start, because the wrong press may itself be the start of the combination.
- Writing the next-state and output logic as a truth table and then as equations or RTL.
The two-bit state name is a strong clue. Two bits give at most four states, and a detector for an N-digit combination needs N + 1 states (nothing matched, 1 digit matched, ..., all N matched). So the combination has at most three digits.
The answer
The combination is 100, as given in the MIT 6.111 answer set for this problem. The deep dive below builds a complete detector for 100 from scratch, so you can check it against the clues in the diagram.
Deep dive: the numbers and details
This part holds the state diagram in table form, the truth table, the logic equations and RTL for a "100" detector. Skip it if the answer is all you need.
States and their meaning
A Moore machine (output depends only on the state) with four states. The state names below are one valid assignment; the diagram in the puzzle uses its own names, which, as the problem says, are not derived from the combination.
| State | Meaning | UNLOCK |
|---|---|---|
| A | No useful progress | 0 |
| B | Last press was "1" | 0 |
| C | Last two presses were "1 0" | 0 |
| D | Last three presses were "1 0 0": open | 1 |
Transitions, including overlap
| Current state | B = 0 | B = 1 |
|---|---|---|
| A | A | B |
| B | C | B |
| C | D | B |
| D | A | B |
The overlap cases are the interesting ones. From B, another "1" keeps us in B, because the latest "1" is still a valid first digit. From C, a "1" breaks "1 0" but starts a new attempt, so we go to B, not A. From D (unlocked), a "0" leaves the last presses as "0 0", which matches no prefix of 100, so we go to A; a "1" starts a new attempt in B. Every state has exactly one arc for B = 0 and one for B = 1, so the arcs are mutually exclusive and collectively exhaustive, as the problem requires.
Truth table with a state encoding
Choose A = 00, B = 01, C = 10, D = 11 (any one-to-one assignment works; this one keeps the equations short).
| S1 | S0 | B | S1' | S0' | UNLOCK |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 |
Logic equations
Reading the table (with ~ for NOT, & for AND, | for OR):
S1' = ~B & (S1 ^ S0) // from B (01) or C (10) on a 0 S0' = B | (S1 & ~S0) // any 1, or C (10) on a 0 UNLOCK = S1 & S0 // state D
Check one row: state C (S1 = 1, S0 = 0) with B = 0 gives S1' = 1 & (1 ^ 0) = 1 and S0' = 0 | (1 & 1) = 1, so the next state is 11 = D. Correct.
The same machine in Verilog
module p3_lock (
input wire clk,
input wire rst_n,
input wire press, // one-cycle pulse per button press
input wire b, // 0 for button "0", 1 for button "1"
output wire unlock
);
reg [1:0] s;
always @(posedge clk or negedge rst_n)
if (!rst_n) s <= 2'b00;
else if (press) s <= { ~b & (s[1] ^ s[0]), b | (s[1] & ~s[0]) };
assign unlock = s[1] & s[0];
endmodule
The press input reflects the specification: the FSM advances only when a button is pressed, not on every clock.
Test sequence
Pressing 1, 1, 0, 0 walks A, B, B, C, D and opens on the fourth press, because the last three presses are 1 0 0. Pressing 1, 0, 1, 0, 0 walks A, B, C, B, C, D and opens on the fifth press. Pressing 1, 0, 0, 0 opens on the third press and locks again on the fourth.
Interview follow-ups
- Mealy version: a Mealy machine can raise UNLOCK on the arc from C with B = 0, needing only three states, at the cost of an output that depends directly on the input.
- Longer combinations: an N-digit combination needs N + 1 states in a Moore detector, so a 4-digit code would need a 3-bit state register.
- Security: because the lock checks only the last N presses, an attacker can try codes back to back without any reset, which is a good discussion point about real lock design.


Your comments will be moderated before it appears here.