Group Consecutive Piano Notes into Hand Positions and Assign Fingers
Company: Google
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
A pianist plays a melody with one hand. Notes are integers, where consecutive integers are adjacent keys. The hand's five fingers cover five adjacent keys, so one hand position can play a group of notes only if the highest and lowest notes in the group differ by at most 4. Split the melody into groups of consecutive notes played from one hand position, count how many times the hand has to move, and assign each note a finger.
### Function Signature
```python
def assign_fingers(notes: list[int]) -> tuple[int, list[int]]:
```
### Rules
- The notes are played in the given order. The first note starts the first group.
- The hand stays in its position as long as it can: a note joins the current group if, with that note included, the largest and smallest notes of the group differ by at most 4. Otherwise the hand moves, the note starts a new group, and the move count increases by 1.
- The first hand position is not a move, so `moves` equals the number of groups minus one.
- The finger for a note is the note minus the smallest note of its whole group, including notes of the group that are played after it. Finger 0 is the thumb and finger 4 the little finger.
- Return `(moves, fingers)`, where `fingers[i]` is the finger for `notes[i]`. For an empty melody return `(0, [])`.
### Constraints
- `0 <= len(notes) <= 10^5`
- `0 <= notes[i] <= 10^9`; notes may repeat.
- All values and differences fit in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: notes = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Output: (1, [4, 3, 2, 1, 0, 4, 3, 2, 1, 0])
```
The first five notes span `10 - 6 = 4`, so they share one position whose smallest note is 6, giving fingers 4, 3, 2, 1, 0. Adding 5 would make the span `10 - 5 = 5`, so the hand moves once, and 5 through 1 form the second group with smallest note 1.
**Example 2**
```text
Input: notes = [5, 3, 7, 2, 9]
Output: (2, [2, 0, 4, 0, 0])
```
5, 3 and 7 span `7 - 3 = 4` and share one position whose smallest note is 3, so note 5 gets finger 2 even though 3 is played after it. Adding 2 would make the span `7 - 2 = 5`, so the hand moves and 2 starts a new group; 9 is 7 above 2, so the hand moves again.
**Example 3**
```text
Input: notes = [1, 2, 3, 4, 5, 6]
Output: (1, [0, 1, 2, 3, 4, 0])
```
Each step between neighbours is only 1, but 1 through 6 spans 5, so 6 starts a new group.
Overview: A coding question that splits a melody's consecutive notes into five-key hand positions whose highest and lowest notes differ by at most four. It asks for the number of hand moves and each note's finger number, testing careful range tracking, correct finger assignment and edge cases such as an empty melody.
Read the full Google Machine Learning Engineer interview experience this question came from