Reconcile a keyed list
Implement reconcileKeys(oldKeys, newKeys), a small model of how React updates a keyed list. Both are arrays of unique strings. Return operations in this order. First a { type: 'remove', key } for every old key that is gone, in old order. Then walk newKeys from left to right with lastIndex = -1: a key that was not in oldKeys gives { type: 'insert', key, index }; for a key that existed, let oldIndex be its old position: when oldIndex < lastIndex it gives { type: 'move', key, index }, otherwise it gives nothing and lastIndex becomes oldIndex. index is the position in newKeys.
Start from
function reconcileKeys(oldKeys, newKeys) {
// Return the remove, insert and move operations.
}Hints
Each hint gives away a little more. Open one only when you need it.
Hint 1
Build a Map from each old key to its index, and a Set of the new keys.
Hint 2
The removals come from filtering oldKeys. The rest is one loop over newKeys that follows the lastIndex rule in the task.
Solution
From here on the page gives the method away. If you are still solving, go back to the hints.
JavaScript
function reconcileKeys(oldKeys, newKeys) {
const oldIndex = new Map(oldKeys.map((key, index) => [key, index]));
const kept = new Set(newKeys);
const ops = oldKeys
.filter((key) => !kept.has(key))
.map((key) => ({ type: "remove", key }));
let lastIndex = -1;
newKeys.forEach((key, index) => {
if (!oldIndex.has(key)) ops.push({ type: "insert", key, index });
else if (oldIndex.get(key) < lastIndex) ops.push({ type: "move", key, index });
else lastIndex = oldIndex.get(key);
});
return ops;
}What an interviewer looks for
It makes the keys answer concrete. With stable keys, adding an item at the top is one insert. With index keys every item looks changed, and state sticks to the wrong row.