Simulate Android Pattern Locking
Filed under Amazon
Free read 1 of 3Create a map of invalid moves (e.g., 1 to 3 requires 2 to be visited).
The question
Given an N x N grid (e.g., 3x3), find all valid Android lock patterns of a specific length starting from a given point, respecting jump-over rules.
Constraints
- N is typically 3
- Cannot reuse visited nodes
- Must jump over intermediate nodes if moving across them
Examples
- Input
- length 2, start 1
- Output
- 1-2, 1-4, 1-5, 1-6, 1-8, 1-9
- Why
- 1-3 is invalid because 2 must be visited first.
Approach
Create a map of invalid moves (e.g., 1 to 3 requires 2 to be visited).
Use DFS to explore all paths of the given length, maintaining a 'visited' set.
At each step, check if the move is valid based on the jump map and visited status.
Tips
- What they are testing: Verify that the 'jump' rule is correctly implemented for diagonal and knight-move jumps.
- Common mistake: Forgetting to mark nodes as visited during the backtracking recursion.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.