/Projects

List diffing for animated UI updates

Turn old and new lists into deletes, inserts, moves and reloads, in O(n log n).

PracticeMachine codingTier 3 · Edge casesCreate40 minMobile systems

You will be able to: build list diffing for animated UI updates in 40 minutes, edge cases included.

Source: Tested in tests/mobile/MobileTests.kt

Mobile engineeringAll mobile pages

When 140 pulled changes land at once, this redraws only the rows that changed, with no flash. Start from the basics in Day 9 →

Study with AI

40-minute round · HardKotlin · coroutines · tested Watch as reels
Part 1 of 5

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.

01Why diff at all

Replacing the whole list makes it flash and loses the scroll position. Telling the list exactly what changed lets it animate only those rows.

02Identity vs content

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.

03Moves and the longest increasing subsequence

Among items present in both lists, the largest group still in the same relative order can stay put. Everything else counts as moved.

04Patience sorting

A way to find that longest increasing subsequence in O(n log n), using a binary search over the smallest tail of each length.

Part 2 of 5

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.

Interviewer

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 askInterviewer answers
Are ids unique?Yes, within one list.
Do moves matter?Yes: moving every row looks broken. Keep the most rows still.
Part 3 of 5

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.

Identity map

Old id → index makes every lookup O(1). The caller passes idOf, so any type works.

LIS keeps rows still

Among surviving items, the longest increasing run of old indices is the largest set that keeps order; everything else moved.

Patience sorting

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.

ListDiff.ktKotlin
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}
65 linesUTF-8Kotlin

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.

1

Index the old list

Map old ids to positions; anything whose id is not in the new list is a delete.

ListDiff.ktKotlin
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 }
lines 21–24UTF-8Kotlin
2

Walk the new list

Unknown ids are inserts; known ids are survivors, and changed content (data class equality) means a reload.

ListDiff.ktKotlin
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  }
lines 26–37UTF-8Kotlin
3

Moves are what LIS leaves out

Survivors on the longest increasing run of old indices stay; the rest are moves.

ListDiff.ktKotlin
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)
lines 39–41UTF-8Kotlin
4

Patience sorting

Binary search the first tail ≥ value; track predecessors to rebuild the sequence.

ListDiff.ktKotlin
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  }
lines 46–57UTF-8Kotlin
5

Rebuild the sequence

Follow predecessors back from the last tail, adding to the front of an ArrayDeque.

ListDiff.ktKotlin
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 out
lines 58–64UTF-8Kotlin

Complexity: O(n log n) time, O(n) space

Part 4 of 5

Q&A

The questions interviewers ask after the code works. Answer out loud, then open.

4.1Follow-up questions

Why not Myers' diff?
Myers minimises edits for sequences without identity; with stable ids, the map plus LIS is simpler and faster. DiffUtil uses Myers plus move detection.
What does the platform give you?
DiffUtil / ListAdapter on Android and diffable data sources on iOS do this for you; this is how they work underneath.
Part 5 of 5

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
ApproachSwift / iOS
Diffable data sourcesApply an NSDiffableDataSourceSnapshot of item identifiers; reconfigureItems for content changes.
SwiftUIForEach over Identifiable items animates inserts, deletes and moves by id.
AI Engineer · List diffing for animated UI updates