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
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. Implement `assign_fingers(notes)`.
### 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, [])`.
### Return value in each language
- Python: the tuple `(moves, fingers)`, with `fingers` a list of ints.
- JavaScript: the two-element array `[moves, fingers]`.
- Java: a `java.util.List<Object>` whose first element is `moves` (an `Integer`) and whose second element is `fingers` (a `java.util.List<Integer>`).
- C++: a `std::pair<int, std::vector<int>>` holding `moves` and `fingers`.
No value exceeds 2^31 - 1: every note, every difference between notes, `moves` and every finger fit in a 32-bit signed integer, so `int` is enough in Java and C++.
### 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.
### 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.
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
Input: ([],)
Expected Output: (0, [])
Explanation: Minimum valid: an empty melody returns (0, []).
Input: ([7],)
Expected Output: (0, [0])
Explanation: Minimum valid: a single note is one group, no move, finger 0.
Hints
- Whether a note fits depends on the whole current group, not only on the previous note: a group fits one hand position only while its largest and smallest notes differ by at most 4.
- A note's finger is measured from the smallest note of its entire group, and that note may be played later, so a finger is not always known at the moment its note is played.
- When a note does not fit, it begins the next group. Check the boundary: a span of exactly 4 still fits, a span of 5 does not.