Google Machine Learning Engineer Interview Experience — Piano Fingering Greedy Coding Question

Sharing a Google coding question that is "wrapped in a real-life scenario": you are given a sequence of notes, you split the consecutive notes into groups, each group is one hand position, and then you work out which finger plays each note. The setup feels new, but underneath it is a very typical "scan left to right + track the min and max of the current window" greedy. Below is how I laid it out when explaining it in the interview.

The problem

Given a list of notes, split the consecutive notes into groups so that in each group the difference between the largest and smallest note is at most 4. Every time the hand has to move to a new position, moves goes up by one. Also, assign each note a finger number based on its difference from the smallest note in its group: 0 is the thumb, 4 is the pinky.

What the problem really means: one hand's five fingers cover exactly 5 adjacent notes, so within one hand position the span of the notes (max minus min) cannot exceed 4. Once it does, you have to change hand position.

Approach

Go through the notes from left to right and keep the min and max of the current group:

• if after adding the new note the max minus min is still at most 4, put it into the current group;
• if it goes over 4, start a new group and add one to moves;
• once a group is settled, compute each finger number from "note minus the group's min".

Two key points in this approach:

• Each group should take in as many notes as possible (greedy): as long as a note still fits in the current hand position, do not move. That gives the fewest groups, so the fewest hand moves.
• Compute the finger numbers only after a group is settled, because the group's min may show up late in the group, and computing while scanning gives wrong answers.

Edge cases

• An empty array returns right away (moves is 0, the fingering list is empty);
• A single note needs no move;
• The range check must use "max minus min", not just a comparison of adjacent notes.

That last one is the easiest place to go wrong on this problem. For example, every adjacent difference is only 1, but after six consecutive ascending notes the difference between max and min is already 5 and one hand cannot reach. If you only look at the difference between two neighboring notes, you miss this case.

Complexity

Time is O(n) and space is O(n), where n is the number of notes. The space is mostly the output fingering list; if you only need moves, the extra space can go down to O(1).

Test case

The input is ten notes going down one at a time from 10 to 1. Output: moves is 1, fingering is 4, 3, 2, 1, 0, 4, 3, 2, 1, 0.

Walking through it by hand shows why:

• For the first five notes 10, 9, 8, 7, 6, the max is 10 and the min is 6, the difference is 4, which is just allowed. The group min is 6, so the fingering is 10-6=4, 9-6=3, 8-6=2, 7-6=1, 6-6=0;
• When the sixth note 5 is added, the max is 10 and the min is 5, the difference is 5, which is over 4, so a new group starts from 5 and moves goes up by one;
• In the second group 5, 4, 3, 2, 1 the group min is 1, so the fingering is 4, 3, 2, 1, 0.

Across the two groups the hand position changed once (the starting position of the first group does not count as a move), which matches moves equal to 1 in the example.

Some thoughts after the fact

These are things I added myself while reviewing afterwards, not follow-up questions from the interviewer.

• Why the greedy is correct: if some group does not extend as far as it can, the notes after it just get pushed into the next group, and the next group's start can only be later, never fewer. So taking as many notes as possible per group means the number of groups can never be more than with any other split. This can be explained to the interviewer in two sentences.
• Finger numbers cannot go out of range: the max minus min inside a group is at most 4, so "note minus group min" is always between 0 and 4, and no extra check is needed.
• Variations you could run into: notes that are not integers (such as black keys), handling the left and right hands separately, and charging a move cost based on the distance between adjacent hand positions. In the interview you can first confirm the scope of the problem, then describe how you would extend it.
• Suggested test cases: besides the example in the problem, add an empty array, a single note, all notes equal, adjacent differences all small but the cumulative span over 4 (for example 1, 2, 3, 4, 5, 6), and ascending and descending alternating.

Takeaways

• Translate the real-life problem into algorithm language first. Turn "one hand has five fingers" into "max minus min inside a group is at most 4", and the problem no longer feels unfamiliar.
• Use "max minus min" and not "adjacent difference". This is the biggest trap of the problem, and pointing it out yourself earns bonus points.
• Split grouping and fingering. Decide the boundaries of a group first, then compute the fingering together. The logic is clear and it is harder to get wrong.
• Walk through the example by hand. The example going from 10 down to 1 happens to verify both "when to start a new group" and "how the fingering is computed".
• Say why the greedy is optimal. Explaining in two sentences why taking as many notes as possible per group is optimal is more convincing than just writing the code.