Basics
The concepts this component is built on. With these in mind, every line of the solution has a reason.
1.1Key concepts
One idea per card, in the order the solution uses them.
Replacing the whole list makes it flash and loses the scroll position. Telling the list exactly what changed lets it animate only those rows.
The id says which item a row is; the fields say what it shows. The same id with new content is a reload, not a delete plus an insert.
Among items present in both lists, the largest group still in the same relative order can stay put. Everything else counts as moved.
A way to find that longest increasing subsequence in O(n log n), using a binary search over the smallest tail of each length.
Question
What exactly you are asked to build, what must be true when you are done, and what to ask before you start.
2.1Prompt
The question as the interviewer asks it, and the requirements to check your solution against.
When the feed refreshes, we reload the whole list and the UI flashes. Compute the minimal batch update between the old and new lists so the list can animate.
Requirements
- Match items by identity
- Report deletions by old index and insertions by new index
- Report moves, but as few as possible
- Report content changes as reloads
2.2Clarify first
Questions worth asking, and the answers this interviewer gives.
| You ask | Interviewer answers |
|---|---|
| Are ids unique? | Yes, within one list. |
| Do moves matter? | Yes: moving every row looks broken. Keep the most rows still. |
Detailed answer
The design decisions, the complete Kotlin solution, and a walk through it one block at a time.
3.1Design decisions
Settle these before writing code; each one shows up in the solution.
Old id → index makes every lookup O(1). The caller passes idOf, so any type works.
Among surviving items, the longest increasing run of old indices is the largest set that keeps order; everything else moved.
LIS in O(n log n) with a predecessor array to rebuild the sequence.
3.2Solution
Complete, compiling Kotlin with coroutines, built with warnings as errors and covered by tests/mobile/MobileTests.kt. The Java and TypeScript tabs do the same job with each language's own tools: Java compiled and run in our tests, TypeScript run in our tests.
1/**2 * The changes a list needs to animate from old to new: deletions (old indices),3 * insertions (new indices), moves and in-place reloads.4 */5data class ListDiff(6 val deletes: List<Int> = emptyList(),7 val inserts: List<Int> = emptyList(),8 val moves: List<Move> = emptyList(),9 val reloads: List<Int> = emptyList(), // new indices whose content changed10) {11 data class Move(val from: Int, val to: Int)12 13 val isEmpty: Boolean get() = deletes.isEmpty() && inserts.isEmpty() && moves.isEmpty() && reloads.isEmpty()14}15 16/**17 * O(n log n) diff keyed by identity. Items that keep their relative order stay put18 * (the longest increasing subsequence); only the others are reported as moves.19 */20fun <T, ID> diff(old: List<T>, new: List<T>, idOf: (T) -> ID): ListDiff {21 val oldIndex = HashMap<ID, Int>()22 old.forEachIndexed { i, item -> oldIndex[idOf(item)] = i }23 val newIds = new.mapTo(HashSet(), idOf)24 val deletes = old.indices.filter { idOf(old[it]) !in newIds }25 26 val inserts = mutableListOf<Int>()27 val reloads = mutableListOf<Int>()28 val survivors = mutableListOf<Pair<Int, Int>>() // (old index, new index) in new order29 new.forEachIndexed { j, item ->30 val i = oldIndex[idOf(item)]31 if (i == null) {32 inserts += j33 } else {34 survivors += i to j35 if (old[i] != item) reloads += j36 }37 }38 39 val stay = longestIncreasingSubsequence(survivors.map { it.first }).toHashSet()40 val moves = survivors.filterIndexed { k, _ -> k !in stay }.map { (from, to) -> ListDiff.Move(from, to) }41 return ListDiff(deletes, inserts, moves, reloads)42}43 44/** Indices (into [values]) of one longest strictly increasing subsequence. Patience sorting. */45fun longestIncreasingSubsequence(values: List<Int>): List<Int> {46 val tails = mutableListOf<Int>() // index of the smallest tail for each length47 val previous = IntArray(values.size) { -1 }48 values.forEachIndexed { i, v ->49 var lo = 050 var hi = tails.size51 while (lo < hi) { // first tail >= v52 val mid = (lo + hi) ushr 153 if (values[tails[mid]] < v) lo = mid + 1 else hi = mid54 }55 if (lo > 0) previous[i] = tails[lo - 1]56 if (lo == tails.size) tails += i else tails[lo] = i57 }58 val out = ArrayDeque<Int>()59 var k = tails.lastOrNull() ?: -160 while (k >= 0) {61 out.addFirst(k)62 k = previous[k]63 }64 return out65}1import java.util.ArrayDeque;2import java.util.ArrayList;3import java.util.Deque;4import java.util.HashMap;5import java.util.HashSet;6import java.util.List;7import java.util.Map;8import java.util.Set;9import java.util.function.Function;10 11/**12 * The changes a list needs to animate from old to new: deletions (old indices),13 * insertions (new indices), moves and in-place reloads.14 */15public record ListDiff(List<Integer> deletes, List<Integer> inserts, List<Move> moves, List<Integer> reloads) {16 public record Move(int from, int to) {}17 18 public boolean isEmpty() {19 return deletes.isEmpty() && inserts.isEmpty() && moves.isEmpty() && reloads.isEmpty();20 }21 22 /**23 * O(n log n) diff keyed by identity. Items that keep their relative order stay put24 * (the longest increasing subsequence); only the others are reported as moves.25 */26 public static <T, ID> ListDiff diff(List<T> old, List<T> next, Function<T, ID> idOf) {27 Map<ID, Integer> oldIndex = new HashMap<>();28 for (int i = 0; i < old.size(); i++) oldIndex.put(idOf.apply(old.get(i)), i);29 Set<ID> newIds = new HashSet<>();30 for (T item : next) newIds.add(idOf.apply(item));31 List<Integer> deletes = new ArrayList<>();32 for (int i = 0; i < old.size(); i++) if (!newIds.contains(idOf.apply(old.get(i)))) deletes.add(i);33 34 List<Integer> inserts = new ArrayList<>();35 List<Integer> reloads = new ArrayList<>();36 List<int[]> survivors = new ArrayList<>(); // {old index, new index} in new order37 for (int j = 0; j < next.size(); j++) {38 T item = next.get(j);39 Integer i = oldIndex.get(idOf.apply(item));40 if (i == null) {41 inserts.add(j);42 } else {43 survivors.add(new int[] {i, j});44 if (!old.get(i).equals(item)) reloads.add(j);45 }46 }47 48 List<Integer> oldIndices = new ArrayList<>();49 for (int[] s : survivors) oldIndices.add(s[0]);50 Set<Integer> stay = new HashSet<>(longestIncreasingSubsequence(oldIndices));51 List<Move> moves = new ArrayList<>();52 for (int k = 0; k < survivors.size(); k++) {53 if (!stay.contains(k)) moves.add(new Move(survivors.get(k)[0], survivors.get(k)[1]));54 }55 return new ListDiff(deletes, inserts, moves, reloads);56 }57 58 /** Indices (into [values]) of one longest strictly increasing subsequence. Patience sorting. */59 public static List<Integer> longestIncreasingSubsequence(List<Integer> values) {60 List<Integer> tails = new ArrayList<>(); // index of the smallest tail for each length61 int[] previous = new int[values.size()];62 java.util.Arrays.fill(previous, -1);63 for (int i = 0; i < values.size(); i++) {64 int v = values.get(i);65 int lo = 0, hi = tails.size();66 while (lo < hi) { // first tail >= v67 int mid = (lo + hi) >>> 1;68 if (values.get(tails.get(mid)) < v) lo = mid + 1;69 else hi = mid;70 }71 if (lo > 0) previous[i] = tails.get(lo - 1);72 if (lo == tails.size()) tails.add(i);73 else tails.set(lo, i);74 }75 Deque<Integer> out = new ArrayDeque<>();76 int k = tails.isEmpty() ? -1 : tails.get(tails.size() - 1);77 while (k >= 0) {78 out.addFirst(k);79 k = previous[k];80 }81 return new ArrayList<>(out);82 }83}1export interface Move {2 from: number;3 to: number;4}5 6/**7 * The changes a list needs to animate from old to new: deletions (old indices),8 * insertions (new indices), moves and in-place reloads.9 */10export interface ListDiff {11 deletes: number[];12 inserts: number[];13 moves: Move[];14 reloads: number[]; // new indices whose content changed15}16 17export const isEmpty = (d: ListDiff) => !d.deletes.length && !d.inserts.length && !d.moves.length && !d.reloads.length;18 19/**20 * O(n log n) diff keyed by identity. Items that keep their relative order stay put21 * (the longest increasing subsequence); only the others are reported as moves.22 */23export function diff<T, ID>(old: T[], next: T[], idOf: (t: T) => ID, same: (a: T, b: T) => boolean = (a, b) => JSON.stringify(a) === JSON.stringify(b)): ListDiff {24 const oldIndex = new Map<ID, number>();25 old.forEach((item, i) => oldIndex.set(idOf(item), i));26 const newIds = new Set(next.map(idOf));27 const deletes = old.map((_, i) => i).filter((i) => !newIds.has(idOf(old[i])));28 29 const inserts: number[] = [];30 const reloads: number[] = [];31 const survivors: [number, number][] = []; // (old index, new index) in new order32 next.forEach((item, j) => {33 const i = oldIndex.get(idOf(item));34 if (i === undefined) {35 inserts.push(j);36 } else {37 survivors.push([i, j]);38 if (!same(old[i], item)) reloads.push(j);39 }40 });41 42 const stay = new Set(longestIncreasingSubsequence(survivors.map((s) => s[0])));43 const moves = survivors.filter((_, k) => !stay.has(k)).map(([from, to]) => ({ from, to }));44 return { deletes, inserts, moves, reloads };45}46 47/** Indices (into [values]) of one longest strictly increasing subsequence. Patience sorting. */48export function longestIncreasingSubsequence(values: number[]): number[] {49 const tails: number[] = []; // index of the smallest tail for each length50 const previous = new Array<number>(values.length).fill(-1);51 values.forEach((v, i) => {52 let lo = 0;53 let hi = tails.length;54 while (lo < hi) { // first tail >= v55 const mid = (lo + hi) >>> 1;56 if (values[tails[mid]] < v) lo = mid + 1;57 else hi = mid;58 }59 if (lo > 0) previous[i] = tails[lo - 1];60 if (lo === tails.length) tails.push(i);61 else tails[lo] = i;62 });63 const out: number[] = [];64 let k = tails.length ? tails[tails.length - 1] : -1;65 while (k >= 0) {66 out.unshift(k);67 k = previous[k];68 }69 return out;70}3.3Line-by-line walkthrough
The same code in the order you would explain it in the room. The line numbers follow the Kotlin file; the Java and TypeScript tabs above have the same steps in the same order.
Index the old list
Map old ids to positions; anything whose id is not in the new list is a delete.
21 val oldIndex = HashMap<ID, Int>()22 old.forEachIndexed { i, item -> oldIndex[idOf(item)] = i }23 val newIds = new.mapTo(HashSet(), idOf)24 val deletes = old.indices.filter { idOf(old[it]) !in newIds }Walk the new list
Unknown ids are inserts; known ids are survivors, and changed content (data class equality) means a reload.
26 val inserts = mutableListOf<Int>()27 val reloads = mutableListOf<Int>()28 val survivors = mutableListOf<Pair<Int, Int>>() // (old index, new index) in new order29 new.forEachIndexed { j, item ->30 val i = oldIndex[idOf(item)]31 if (i == null) {32 inserts += j33 } else {34 survivors += i to j35 if (old[i] != item) reloads += j36 }37 }Moves are what LIS leaves out
Survivors on the longest increasing run of old indices stay; the rest are moves.
39 val stay = longestIncreasingSubsequence(survivors.map { it.first }).toHashSet()40 val moves = survivors.filterIndexed { k, _ -> k !in stay }.map { (from, to) -> ListDiff.Move(from, to) }41 return ListDiff(deletes, inserts, moves, reloads)Patience sorting
Binary search the first tail ≥ value; track predecessors to rebuild the sequence.
46 val tails = mutableListOf<Int>() // index of the smallest tail for each length47 val previous = IntArray(values.size) { -1 }48 values.forEachIndexed { i, v ->49 var lo = 050 var hi = tails.size51 while (lo < hi) { // first tail >= v52 val mid = (lo + hi) ushr 153 if (values[tails[mid]] < v) lo = mid + 1 else hi = mid54 }55 if (lo > 0) previous[i] = tails[lo - 1]56 if (lo == tails.size) tails += i else tails[lo] = i57 }Rebuild the sequence
Follow predecessors back from the last tail, adding to the front of an ArrayDeque.
58 val out = ArrayDeque<Int>()59 var k = tails.lastOrNull() ?: -160 while (k >= 0) {61 out.addFirst(k)62 k = previous[k]63 }64 return outComplexity: O(n log n) time, O(n) space
Q&A
The questions interviewers ask after the code works. Answer out loud, then open.
4.1Follow-up questions
Why not Myers' diff?
What does the platform give you?
Extra depth
The cases that break naive solutions, how the same design looks on iOS, and what to practise next.
5.1Edge cases
Say these before the interviewer does.
Show detailsHide details
- Identical lists produce an empty diff
- Everything replaced
- Pure reorder
- Duplicate ids (reject or dedupe first)
5.2On iOS
The same design in Swift and Apple's frameworks.
Show detailsHide details
| Approach | Swift / iOS |
|---|---|
| Diffable data sources | Apply an NSDiffableDataSourceSnapshot of item identifiers; reconfigureItems for content changes. |
| SwiftUI | ForEach over Identifiable items animates inserts, deletes and moves by id. |