Generate Tower of Hanoi moves
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given **n** disks of different sizes stacked on peg **A** (largest at bottom). You have two other pegs, **B** and **C**. You may move one disk at a time, and you may never place a larger disk on top of a smaller disk.
Write a program that outputs a valid sequence of moves to transfer all disks from **A** to **C**. Define the move format (e.g., "A -> C"). Analyze the time complexity.
Quick Answer: This question evaluates understanding of recursion, algorithmic problem decomposition, and analysis of time complexity when generating constrained move sequences.
You are given n disks of different sizes stacked on peg A, with the largest disk at the bottom and the smallest at the top. You also have two other pegs, B and C.
You may move only one disk at a time, and you may never place a larger disk on top of a smaller disk.
Write a function that returns the minimum-length valid sequence of moves needed to transfer all disks from peg A to peg C, using peg B as the auxiliary peg.
Represent each move as a string in the format "X -> Y", where X is the source peg and Y is the destination peg.
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.
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.