Generate Tower of Hanoi moves
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Quick Answer: This question evaluates understanding of recursion, algorithmic problem decomposition, and analysis of time complexity when generating constrained move sequences.
Constraints
- 0 <= n <= 12
- The returned sequence must be a valid minimum-length solution
- Peg A starts with all n disks, peg C must contain all n disks at the end
Examples
Input: (0,)
Expected Output: []
Explanation: With no disks, no moves are needed.
Input: (1,)
Expected Output: ['A -> C']
Explanation: A single disk can be moved directly from A to C.
Input: (2,)
Expected Output: ['A -> B', 'A -> C', 'B -> C']
Explanation: Move the smaller disk to B, move the larger disk to C, then move the smaller disk from B to C.
Input: (3,)
Expected Output: ['A -> C', 'A -> B', 'C -> B', 'A -> C', 'B -> A', 'B -> C', 'A -> C']
Explanation: This is the classic minimum sequence of 7 moves for 3 disks.
Hints
- To move n disks, first think about what must happen to the top n-1 disks before the largest disk can move.
- This problem naturally breaks into smaller subproblems with the same structure.