How should I practice Knight Dialer Sequences?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Confluent onsite interview problems in FastPrep.

Is Knight Dialer Sequences associated with Confluent?

FastPrep tags this as a Confluent onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Dynamic Programming

Knight Dialer Sequences

Learn this problem

● Medium

ConfluentFULLTIMEONSITE INTERVIEW

Problem statement

A chess knight is dialing numbers on the standard telephone keypad:

A 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) → int

Examples

Example 1

n = 1return = 10

Every one-digit sequence is valid.

Example 2

n = 2return = 20

There are twenty directed knight moves between keypad digits.

Example 3

n = 3return = 46

Extending 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 5 has no legal outgoing knight move.