Knight Dialer Sequences
Updated
Problem statement
A chess knight is dialing numbers on the standard telephone keypad:
1 2 3
4 5 6
7 8 9
0A sequence may start on any digit. Each following digit must be reachable from the previous digit by one legal knight move. Given the sequence length n, return the number of valid digit sequences modulo 1000000007.
Function
countKnightDialerNumbers(n: int) → intExamples
Example 1
n = 1return = 10Every one-digit sequence is valid.
Example 2
n = 2return = 20There are twenty directed knight moves between keypad digits.
Example 3
n = 3return = 46Extending every valid two-digit sequence by one knight move produces forty-six sequences.
Constraints
1 <= n <= 5000.- A sequence may begin at any of the ten digits.
- Digit
5has no legal outgoing knight move.
More Confluent Onsite Interview questions
- Implement tail -nPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Sudoku Board ValidationPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Sudoku Puzzle SolverPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Sequential Phrase Search Across DocumentsPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Bounded Combination Sum with Signed CandidatesONSITE INTERVIEW · Seen Oct 2026
- Detect a Silent SensorONSITE INTERVIEW · Seen Sep 2026
- Build an Inverted Document IndexONSITE INTERVIEW · Seen Sep 2026
- Combination Sum with Unlimited ReuseONSITE INTERVIEW · Seen Sep 2026
- Word Search Across DocumentsPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Windowed Key-Value MapPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2025
Similar questions at other companies
- Knight Dialer SequencesBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Count Routes Through Four Shop TypesOpenAI · OAOpenAI interview questions
- Reach a Destination Through Scheduled FlightsGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Count Staircases with Strictly Increasing StepseBay · ONSITE INTERVIEWeBay interview questions
- Minimum Completion Time for DAG DependenciesAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Minimum Time to Complete Target CoursesMeta · ONSITE INTERVIEWMeta interview questions
- Cheapest Flights Within K StopsGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Critical Path Through Dependent TasksModular · PHONE SCREEN · ONSITE INTERVIEW
- Rocket Component CostSpaceX · ONSITE INTERVIEWSpaceX interview questions
- Coin Change IIApple · PHONE SCREEN · ONSITE INTERVIEWApple interview questions