Adjacent-Key Lock Patterns
Updated
Problem statement
An Android-style lock screen has nine keys in a 3 by 3 grid:
1 2 3
4 5 6
7 8 9A lock pattern is a sequence of keys that follows two rules:
- Each key touches the key before it. Two keys touch when they are next to each other in the same row, in the same column, or on a diagonal. For example,
5touches every other key, while1touches only2,4and5. - No key appears more than once in a pattern.
Given an integer length, return every lock pattern made of exactly length keys. Write each pattern as a string of its digits in the order they are pressed, such as "1254", and return the list sorted in increasing order.
Function
listLockPatterns(length: int) → List<String>Examples
Example 1
length = 1return = ["1","2","3","4","5","6","7","8","9"]A pattern of length 1 is a single key, so each of the nine keys is its own pattern.
Example 2
length = 2return = ["12","14","15","21","23","24","25","26","32","35","36","41","42","45","47","48","51","52","53","54","56","57","58","59","62","63","65","68","69","74","75","78","84","85","86","87","89","95","96","98"]Each pattern is one move to a touching key. Key 5 touches all eight other keys, so it starts 8 patterns. A corner such as 1 touches only 2, 4 and 5, so it starts 3. A side key such as 2 touches 1, 3, 4, 5 and 6, so it starts 5. That gives 4 * 3 + 4 * 5 + 8 = 40 patterns, listed in increasing order.
Constraints
1 <= length <= 5
More C3.ai interview questions
- Fewest Turns to Open a Wheel LockPHONE SCREEN · Seen Nov 2024
- Days Until a Warmer DayPHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022
- Longest Run of Ones After Flipping k ZerosPHONE SCREEN · Seen Mar 2022
- Top K Frequent ElementsPHONE SCREEN · Seen Feb 2021
- Item Prices From Material CostsPHONE SCREEN · Seen Dec 2020
- Drop Recent Duplicate MessagesOA · Seen Oct 2026
- Maximum K-Star SumOA · Seen Oct 2026
- Every Result of Grouping an ExpressionONSITE INTERVIEW · Seen Jan 2023
- Fewest Jumps to the Last IndexONSITE INTERVIEW · Seen Jan 2023
- Rotate a Square Grid ClockwiseONSITE INTERVIEW · Seen Jan 2023
Similar questions at other companies
- Word SearchBloomberg LP · OA · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Word SearchCognitiv · PHONE SCREEN
- Find a Word in a Letter GridAdobe · PHONE SCREENAdobe interview questions
- Word SearchWhatNot · PHONE SCREENWhatNot interview questions
- Word Search IIApple · PHONE SCREENApple interview questions
- Word SearchAmazon · ONSITE INTERVIEW
- Word SearchMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Enumerate Character Paths to a MarkerTesla · ONSITE INTERVIEWTesla interview questions
- Trace a Word Through a Letter GridExpedia · ONSITE INTERVIEWExpedia interview questions
- Rat in a Maze: All Simple PathsPeopleStrong · OAPeopleStrong interview questions