Android Unlock Patterns

Android Unlock Patterns

What is this problem about?

The "Android Unlock Patterns interview question" is a backtracking problem based on the $3 imes 3$ grid used for phone security. You need to find the total number of valid unlock patterns that have a length between m and n. A pattern is valid if:

• All dots in the pattern are distinct.
• If a line between two dots passes through an intermediate dot, that intermediate dot must have already been visited. For example, moving from 1 to 3 is only allowed if 2 has already been used.

Why is this asked in interviews?

Google uses the "Android Unlock Patterns coding problem" to test a candidate's ability to implement recursive search with complex constraints. It evaluates "Backtracking interview pattern" skills and the ability to optimize using symmetry (since the pattern counts from corner 1 are the same as corner 3, 7, and 9).

Algorithmic pattern used

This problem is solved using Backtracking with Symmetry Optimization.

1. Jump Table: Pre-calculate a 2D array skip[10][10] where skip[i][j] stores the number that must be visited to jump from i to j. For example, skip[1][3] = 2 and skip[1][7] = 4.
2. Recursive DFS: For each starting number, explore all possible next numbers.
3. Validation: A move from current to next is valid if next is unvisited AND (skip[current][next] == 0 OR visited[skip[current][next]] == true).
4. Symmetry:
   • Patterns starting at 1, 3, 7, 9 are identical.
   • Patterns starting at 2, 4, 6, 8 are identical.
   • Pattern starting at 5 is unique. Calculate once for each group and multiply.

Example explanation

Starting at 1, wanting a pattern of length 2:

• Can go to 2, 4, 5, 6, 8. (5 valid moves).
• Cannot go to 3 (requires 2), 7 (requires 4), or 9 (requires 5). If we had already visited 2, then jumping from 1 to 3 would be allowed.

Common mistakes candidates make

• Missing symmetry: Calculating all 9 starting points separately, which is inefficient and more prone to errors.
• Wrong jump logic: Forgetting that "jumps" can also be diagonal (e.g., 1 to 9 requires 5).
• State Management: Not properly "un-visiting" a node during the backtracking step.

Interview preparation tip

Symmetry is your best friend in grid-based counting problems. Always ask yourself: "Is the top-left corner essentially the same as the top-right?" This can reduce your computation by 75% and impress your interviewer.