Hash Maps · Commitwise

If you remember one trick for coding interviews, make it this one: when your first idea is two nested loops, ask yourself “could a hash map remember what I’ve already seen?” Very often the answer turns an O(n²) solution into O(n), and that’s the difference between “OK” and “strong hire”.

New to some of these? Open what you need, or skip ahead.

Basics:What are lists, sets and maps?

Collections hold many values:

A list (Swift Array, Kotlin List, Java List) keeps items in order, and allows duplicates: ["Ana", "Ben", "Ana"].
A set holds each value at most once and answers “is this in it?” very quickly.
A map (Swift Dictionary, Kotlin, Java and TypeScript Map) stores values under keys: "Ana" → 30, looked up by the key.

Lists use indexes starting at 0: in ["a", "b", "c"], "a" is at index 0 and "c" at index 2.

Basics:What are arrays and indexes?

An array is a row of values stored one after another: [5, 8, 2, 9]. Each position has an index, starting at 0: here 5 is at index 0 and 9 at index 3. The last index is always count - 1 (Swift) or size - 1 / length - 1 (Kotlin, Java).

Reading nums[2] is instant, whatever the array’s size. Reading an index that doesn’t exist (like nums[4] here) crashes with an “index out of range” error, which is why loops usually go from 0 up to, but not including, the length.

Basics:What does O(n) mean?

Big-O describes how the amount of work grows with the size of the input n:

O(1): the same work whatever the size (reading array[5]).
O(log n): grows very slowly (about 20 steps for a million items).
O(n): grows in step with the input (one pass over the array).
O(n²): comparing every item with every other item, which gets slow fast.

You’ll see it next to every solution, for time and for extra space (memory). The Big-O tutorial explains it properly.

Basics:What is hashing?

A hash is a number computed from a value, like a fingerprint: the same value always gives the same hash, and different values usually give different ones. "Ana".hashCode() (Java, Kotlin) or Swift’s Hashable produce it; TypeScript’s Map computes it for you behind the scenes.

Hash maps and hash sets use the hash to decide where to store each key, so they can jump straight to it later instead of searching: that’s why looking up a key takes about one step. Two different keys can occasionally have the same hash (a collision); the map handles it, just a little slower.

Basics:What is boxing (int vs Integer)?

Java has fast primitive types like int, double and boolean, which aren’t objects. Collections and generics can only hold objects, so Java wraps primitives in objects: int → Integer, double → Double. That wrapping is called boxing; reading the number back out is unboxing.

Two things to know: an Integer can be null (and unboxing null crashes), and comparing two Integers with == compares the objects, not the numbers. Kotlin hides most of this (its Int becomes int or Integer as needed), and Swift has no boxing at all for its number types.

Part Not started

How a hash map works

Think of a coat check. You hand over your coat and get a ticket with a number. When you come back, the attendant doesn’t search every coat in the room: the number tells them exactly which hook to go to.

A hash map does the same with data. You store a value under a key (a word, a user ID, a number). The map turns the key into a number, called its hash, and uses that number to jump straight to the right spot. That’s why finding a value takes the same short time whether the map holds ten items or ten million. We call that O(1), read “constant time” (see Big-O notation).

Each key appears at most once. Writing to a key that is already there replaces its value instead of adding a second entry.

An array of buckets, a hash function that maps keys to bucket indexes, an equality check to resolve collisions, and a resize when the load factor gets too high. That gives average O(1) insert, lookup and delete, amortized over resizes. Worst case is O(n) when many keys collide (O(log n) for Java’s HashMap, which turns long chains into trees). The details, and how they differ between Swift, Kotlin and Java, are in the Detailed version.

Counting words

let words = ["swift", "kotlin", "swift", "java", "swift"]

var counts: [String: Int] = [:]
for word in words {
    counts[word, default: 0] += 1
}
// ["swift": 3, "kotlin": 1, "java": 1]

val words = listOf("swift", "kotlin", "swift", "java", "swift")

val counts = mutableMapOf<String, Int>()
for (word in words) {
    counts[word] = (counts[word] ?: 0) + 1
}
// {swift=3, kotlin=1, java=1}
// Shorter: words.groupingBy { it }.eachCount()

var words = List.of("swift", "kotlin", "swift", "java", "swift");

Map<String, Integer> counts = new HashMap<>();
for (String word : words) {
    counts.merge(word, 1, Integer::sum);
}
// {swift=3, kotlin=1, java=1} (in some order)

const words = ["swift", "kotlin", "swift", "java", "swift"];

const counts = new Map<string, number>();
for (const word of words) {
  counts.set(word, (counts.get(word) ?? 0) + 1);
}
// Map(3) { 'swift' => 3, 'kotlin' => 1, 'java' => 1 }

Operation	Average	Worst case
Insert, lookup, delete	O(1)	O(n)
Iterate all entries	O(n)	O(n)
Memory	O(n)	O(n)

Practice: counting, step by step

Counting is the hash map move you’ll use most, so let’s slow down and watch it happen. Here’s the map after each letter of "banana":

Letter	What the code does	Map afterwards
`b`	`b` isn’t there yet: start at 0, add 1	`b: 1`
`a`	`a` isn’t there yet: start at 0, add 1	`b: 1, a: 1`
`n`	`n` isn’t there yet: start at 0, add 1	`b: 1, a: 1, n: 1`
`a`	`a` is there: 1 + 1	`b: 1, a: 2, n: 1`
`n`	`n` is there: 1 + 1	`b: 1, a: 2, n: 2`
`a`	`a` is there: 2 + 1	`b: 1, a: 3, n: 2`

Every step is one lookup and one write, and both take about the same time whether the map holds 3 keys or 3 million. That’s why counting a whole book is still O(n).

The first row is where beginners trip: the key isn’t in the map yet. Which line crashes?

Spot the bugCounting letters

Tap the line with the bug.

func letterCounts(_ text: String) -> [Character: Int] {
    var counts: [Character: Int] = [:]
    for letter in text {
        counts[letter] = counts[letter]! + 1
    }
    return counts
}

fun letterCounts(text: String): Map<Char, Int> {
    val counts = mutableMapOf<Char, Int>()
    for (letter in text) {
        counts[letter] = counts[letter]!! + 1
    }
    return counts
}

static Map<Character, Integer> letterCounts(String text) {
    Map<Character, Integer> counts = new HashMap<>();
    for (char letter : text.toCharArray()) {
        counts.put(letter, counts.get(letter) + 1);
    }
    return counts;
}

function letterCounts(text: string): Map<string, number> {
  const counts = new Map<string, number>();
  for (const letter of text) {
    counts.set(letter, counts.get(letter)! + 1);
  }
  return counts;
}

On the very first letter, the map has no entry for it, so the lookup returns nil/null. Force-unwrapping it crashes (Java crashes too, when it unboxes null to add 1). The function fails on every input except the empty string.

TypeScript note

TypeScript doesn’t crash, which is worse: ! checks nothing, undefined + 1 is NaN, and every count in the map ends up NaN.

Each language has a way to say “start at 0 if it’s missing”:

counts[letter, default: 0] += 1

counts[letter] = (counts[letter] ?: 0) + 1
// or: counts.merge(letter, 1, Int::plus)

counts.merge(letter, 1, Integer::sum);
// or: counts.put(letter, counts.getOrDefault(letter, 0) + 1);

counts.set(letter, (counts.get(letter) ?? 0) + 1);

Predict the output

What gets printed?

var ages = ["Ana": 30]
ages["Ana"] = 31
ages["Marko"] = 25
print(ages.count)

val ages = mutableMapOf("Ana" to 30)
ages["Ana"] = 31
ages["Marko"] = 25
println(ages.size)

Map<String, Integer> ages = new HashMap<>(Map.of("Ana", 30));
ages.put("Ana", 31);
ages.put("Marko", 25);
System.out.println(ages.size());

const ages = new Map([["Ana", 30]]);
ages.set("Ana", 31);
ages.set("Marko", 25);
console.log(ages.size);

Exerciseeasy

First Unique Character

Given a string, return the index of the first character that appears exactly once. If there isn’t one, return -1.

"leetcode"     → 0   ('l' appears once)
"loveleetcode" → 2   ('v')
"aabb"         → -1

›

You can’t know whether a character is unique until you’ve seen the whole string. So walk it twice.

›

First pass: count every character, exactly like "banana" above. Second pass: go through the string again in order and return the first index whose count is 1. Don’t loop over the map instead: you need the string’s order, not the map’s.

SolutionTry it yourself firstTime O(n)Space O(1)

func firstUniqueChar(_ s: String) -> Int {
    var counts: [Character: Int] = [:]
    for c in s {
        counts[c, default: 0] += 1
    }
    for (index, c) in s.enumerated() where counts[c] == 1 {
        return index
    }
    return -1
}

fun firstUniqueChar(s: String): Int {
    val counts = mutableMapOf<Char, Int>()
    for (c in s) {
        counts[c] = (counts[c] ?: 0) + 1
    }
    return s.indexOfFirst { counts[it] == 1 }
}

static int firstUniqueChar(String s) {
    Map<Character, Integer> counts = new HashMap<>();
    for (char c : s.toCharArray()) {
        counts.merge(c, 1, Integer::sum);
    }
    for (int i = 0; i < s.length(); i++) {
        if (counts.get(s.charAt(i)) == 1) return i;
    }
    return -1;
}

function firstUniqueChar(s: string): number {
  const counts = new Map<string, number>();
  for (const c of s) {
    counts.set(c, (counts.get(c) ?? 0) + 1);
  }
  return [...s].findIndex((c) => counts.get(c) === 1);
}

Two passes of n steps is still O(n). The space is O(1) when the input is only lowercase letters, because the map can never hold more than 26 keys; for any characters at all, say O(k), where k is the number of different characters.

In an interview, mention the follow-up yourself: if the input is only a to z, an array of 26 counts (counts[c - 'a']) does the same job without hashing.

What happens inside

Every hash map turns a key into an array index: compute hashCode() / hash(into:), mix the bits, and keep the low bits (hash & (capacity - 1), because the capacity is a power of two). The designs differ in what they do when two keys want the same bucket:

Separate chaining (Java’s HashMap, so also Kotlin on the JVM, and V8’s Map in JavaScript and TypeScript): each bucket points to a small linked list of entries.
Open addressing (Swift’s Dictionary): every entry lives in the array itself; a taken bucket means “try the next one” (linear probing).

Insert the keys below and watch both layouts. "Aa" and "BB" have the same String.hashCode() (2112), and ana, eve and max land in the same bucket of the small table:

Inside a hash table

0 keys · 8 buckets · load 0.00

Insert keys one at a time. Each key's hash picks a bucket: index = hash & (capacity − 1).

Tap a key to look it up. Both layouts use Java's String.hashCode so you can compare them; Swift's real hashes are seeded randomly per process.

Chaining keeps a collision local to its bucket, at the cost of an object per entry. Open addressing keeps everything in contiguous arrays (cache-friendly, little overhead), but collisions spill into the neighbors and form clusters, which is why it must stay well below full.

Java

java.util.HashMap

Table: an array of Node<K,V> (hash, key, value, next), allocated lazily on the first put with 16 buckets.
Index: (n - 1) & (h ^ (h >>> 16)). The XOR spreads the high bits into the low bits that pick the bucket.
Lookup: compare the stored hash first, then ==, then equals. Equal keys must have equal hashes, or the lookup never reaches equals in the right bucket.
Tree bins: a bucket that reaches 8 entries becomes a red-black tree (O(log n)), but only once the table has at least 64 buckets; smaller tables resize instead. It turns back into a list at 6.
Resize: when size > capacity × 0.75, the table doubles. Each bucket splits into a “low” and a “high” list by one bit of the hash (hash & oldCap), so nothing is rehashed and relative order is kept.
Variants: LinkedHashMap threads a doubly linked list through the entries (insertion or access order, the basis of LRU caches). HashSet is a HashMap with a dummy value. ConcurrentHashMap locks per bucket and allows no null keys or values.

Kotlin

Kotlin collections

On the JVM there’s no separate implementation: HashMap is a type alias for java.util.HashMap, and mutableMapOf(), linkedMapOf() and mapOf(a to b, …) create a java.util.LinkedHashMap. Everything about Java’s buckets, tree bins and resizing applies.
Index: (n - 1) & (h ^ (h >>> 16)), chaining with linked nodes, a red-black tree for a bucket of 8+ entries once the table has 64+ buckets, and doubling at load factor 0.75.
data class keys get equals and hashCode generated from the constructor properties, which is why they make good keys as long as those properties are vals.
Boxing: a Map<Int, Int> stores java.lang.Integer objects. On Android, SparseArray / SparseIntArray (sorted primitive arrays, binary search) and ArrayMap (two arrays, binary search on the hash) use far less memory for maps up to a few hundred entries, at O(log n) per lookup.
Kotlin/Native (Kotlin Multiplatform on iOS) ships its own open-addressing HashMap, so don’t rely on JVM details like tree bins or iteration order in shared code.

TypeScript

Map and Set (V8, the engine in Chrome and Node.js)

Two arrays: an entries array that keeps every key and value in insertion order, and a bucket array whose slots point to the first entry with that hash; entries in the same bucket are chained. This “deterministic hash table” design is why iteration order is guaranteed.
Hashes: numbers are hashed by value, strings by content (computed once and cached in the string, with a seed chosen randomly per process), and objects by an identity hash: a random number stored on the object the first time it’s used as a key. That’s why object keys match only themselves.
Equality is SameValueZero: like ===, except NaN matches NaN. 1 and "1" are different keys.
Deleting leaves a hole in the entries array; the table is compacted when it’s rebuilt, which also happens when it grows.
Limits: a single Map in V8 holds at most about 16.7 million entries (2²⁴); beyond that, set throws RangeError.
Plain objects used as dictionaries are a different structure (hidden classes, switching to a slower “dictionary mode” as keys come and go), with string-only keys and inherited properties. Map is the hash map; objects are records.

Swift

Dictionary

Storage: a value type backed by one copy-on-write buffer: a bitmap of occupied buckets, plus contiguous arrays of keys and values. No object per entry.
Index: Hasher (SipHash-1-3) with a random seed per process, mixed with a per-storage seed, then masked to a power-of-two bucket count.
Collisions: linear probing, with a maximum load factor of 3/4; inserting beyond it allocates a bigger buffer and reinserts everything.
Removal: no tombstones. The entries after the hole in the same cluster are shifted back, so lookups never have to skip deleted slots.
Copy-on-write: var b = a shares the buffer, and the first mutation of a shared buffer copies the whole thing, O(n). Mutating a dictionary inside a class property or an array element while another reference holds it pays that copy every time.
Set is the same table without the values array. NSDictionary bridging is lazy and uses Objective-C hash / isEqual:.

Kotlin, Java

Deep diveWhy Java XORs the high bits into the low bitsInterview favorite

The bucket index uses only the low bits: with 16 buckets, hash & 15 keeps 4 bits. Keys whose hashes differ only in their high bits would all land in one bucket. That happens more than you’d think: Float keys like 1.0f, 2.0f, 4.0f differ mostly in their exponent bits, and hand-written hashCode()s often multiply by large numbers.

h ^ (h >>> 16) folds the top 16 bits into the bottom 16, so every bit of the hash influences the index. It costs one shift and one XOR, which is why Java does this instead of a full mixing function (tree bins take care of the really bad cases).

Deep diveTree bins need Comparable keysInterview favorite

A tree bin is ordered by hash first. Keys with equal hashes (like "Aa" and "BB") are ordered with compareTo when the key class implements Comparable, such as String. Then a lookup in a bucket of thousands of colliding strings is O(log n).

If the keys aren’t Comparable, the tree can only use a tie-breaker (class name, then identity hash) for insertion, and a lookup may have to search both subtrees, which is O(n) again. Tree bins were added in Java 8 as the answer to hash flooding (below); make your key types Comparable, or better, give them good hash codes.

TypeScript

Deep diveMap or plain object?Interview favorite

Before ES2015, JavaScript developers used plain objects as hash maps, and a lot of code still does. The differences come up in interviews and in production:

Keys: an object turns every key into a string (obj[1] and obj["1"] are the same entry, and an object key becomes "[object Object]"). A Map keeps keys as they are.
Inherited names: counts["constructor"] on a plain object finds Object.prototype.constructor, so a word counter breaks on the word “constructor”. Object.create(null) avoids it; a Map never has the problem.
Order: a Map iterates in insertion order; an object lists integer-like keys first, in numeric order, then the rest in insertion order.
Size and speed: map.size is O(1), Object.keys(obj).length builds an array. Engines optimize objects for a fixed shape; adding and deleting many keys pushes them into a slower dictionary mode, while Map is built for exactly that.

Use objects for records with known fields, Map for lookups with keys you don’t know in advance.

Swift

Deep diveWhy Swift seeds every dictionary differently

With linear probing, the order of insertion matters. Iterating a dictionary returns keys in bucket order. If a second, smaller dictionary used the same hash function, copying the first into it (for (k, v) in big { small[k] = v }) would insert keys in exactly the order that piles them into one growing cluster, and the copy becomes quadratic.

Swift therefore mixes a per-storage seed into every hash, so two dictionaries with the same keys usually iterate in different orders. The same idea explains why you can’t rely on order even between two dictionaries in one run. For reproducible tests, set the environment variable SWIFT_DETERMINISTIC_HASHING=1.

Where it goes wrong

Hash flooding. If an attacker chooses the keys (JSON field names, form parameters, HTTP headers), they can send thousands that collide and turn every insert into O(n): a few kilobytes of request burn seconds of CPU. In 2011 this hit Java, PHP, Python, Ruby and ASP.NET at once. Strings like "Aa" and "BB" can be combined into endless colliding keys ("AaAa", "AaBB", "BBAa", "BBBB", …). Defenses: tree bins (Java 8), randomly seeded hashing (Swift, Python, Rust), and limits on the number of parameters a server accepts.
Resizing spikes. Insert is O(1) amortized: the insert that crosses the load factor copies every entry. In a latency-sensitive loop, or when you know the size, presize the map. Note that Java’s new HashMap<>(1000) still resizes before 1,000 entries, because 1,000 × 0.75 < 1,000; Java 19 added HashMap.newHashMap(1000), which accounts for the load factor.
Concurrent writes. None of these maps is thread-safe. In Java 7, two threads resizing a HashMap at once could link a bucket into a cycle, and the next get looped forever at 100% CPU; Java 8 removed the cycle, but lost updates and corrupted state remain. Swift reports a data race on a Dictionary as undefined behavior (and Swift 6 strict concurrency refuses to compile the sharing).
Changing the map while iterating. Java and Kotlin iterators are fail-fast and throw ConcurrentModificationException (on a best-effort basis); use iterator.remove(), removeIf or entries.removeAll { … }. Swift iterates over a value, so mutating inside the loop is safe, but may copy the whole dictionary.
Memory. A HashMap<Integer, Integer> with a million entries holds three million objects (node, boxed key, boxed value). Primitive maps (Android’s SparseIntArray, fastutil on the server) or arrays indexed by key are often several times smaller.
Mutable keys and broken equals / hashCode are covered in Keys that behave.

Java

Pick the right map: ConcurrentHashMap for shared mutable state (and compute / merge for atomic updates), LinkedHashMap for predictable order or an LRU, EnumMap for enum keys (an array, no hashing), HashMap.newHashMap(n) when you know the size.

Kotlin

Pick the right map: ConcurrentHashMap (or a Mutex around a plain map in coroutines) for shared mutable state, HashMap(n) instead of mutableMapOf() when order doesn’t matter and memory does, EnumMap for enum keys, and SparseArray / ArrayMap for small maps on Android.

Swift

Pick the right map: an actor (or Mutex from the Synchronization module) around shared state, reserveCapacity(_:) or Dictionary(minimumCapacity:) when you know the size, and isKnownUniquelyReferenced / keeping one owner to avoid copy-on-write copies in hot paths.

TypeScript

Pick the right map: Map / Set for dynamic keys (not plain objects), string or number keys for compound values, and WeakMap for caching data about objects: its entries disappear when the key object is garbage collected, so the cache can’t leak.

Buckets, a hash function, equality inside a bucket, and a resize at a load factor: average O(1) insert, lookup and delete, O(n) iteration, and O(n) in the worst case when many keys collide.

Swift

Dictionary uses open addressing in one buffer and seeds hashing randomly per process (against hash flooding), so iteration order changes between runs.

Kotlin

HashMap() is Java’s: at a load factor of 0.75 it doubles, and a bucket of 8+ entries (in a table of 64+) becomes a red-black tree, so the worst case is O(log n). mutableMapOf() returns a LinkedHashMap, which keeps insertion order.

Java

At a load factor of 0.75 the table doubles, and a bucket of 8+ entries (in a table of 64+) becomes a red-black tree, so the worst case is O(log n). Iteration order is unspecified; LinkedHashMap keeps insertion order.

TypeScript

V8’s Map and Set are deterministic hash tables: buckets of chained entries, plus an entries array in insertion order, so iteration order is guaranteed. Objects and arrays are keys by identity (SameValueZero), never by contents. Use Map rather than a plain object for dynamic keys: object keys are always strings, and inherited names like "constructor" get in the way.

	Swift	Kotlin	Java	TypeScript
Create	`[String: Int]()`	`mutableMapOf<String, Int>()` (ordered), `HashMap()`	`new HashMap<>()`	`new Map<string, number>()` (ordered)
Get with default	`m[k, default: 0]`	`m.getOrDefault(k, 0)`, `m[k] ?: 0`	`m.getOrDefault(k, 0)`	`m.get(k) ?? 0`
Increment	`m[k, default: 0] += 1`	`m.merge(k, 1, Int::plus)`	`m.merge(k, 1, Integer::sum)`	`m.set(k, (m.get(k) ?? 0) + 1)`

Never let output or tests depend on the iteration order of an unordered map.

Refresher:Hash, bucket, collision

The hash is a number computed from the key; the map uses it to pick a bucket (an array slot). Two keys in the same bucket are a collision, resolved by comparing the keys for equality. That’s why equal keys must have equal hashes.

Check this part

What is the average time to look up a key in a hash map?
The hash points straight to the right spot, so the average lookup doesn't depend on the size of the map.
A map holds "Ana": 30. You write "Ana": 31, then add "Marko": 25. How many entries does it have?
Writing to a key that already exists replaces its value, so there is still one "Ana", plus "Marko".
You print the same Dictionary in two runs of your program. Is the order the same?What does mutableMapOf() give you, and in what order does it iterate?In what order does a HashMap iterate its entries?In what order does a Map iterate its entries?
Random seeding defends against hash flooding, and it means output and tests must never depend on dictionary order.mutableMapOf() keeps insertion order at a little extra memory per entry; HashMap() is the plain, unordered one. Never let tests depend on the order of an unordered map.Iteration order is unspecified and can change as the table resizes. Never let output or tests depend on it.Unlike most hash maps, a JavaScript Map (and Set) always iterates in insertion order. Plain objects don't quite: integer-like keys come first, in numeric order.
Many keys land in the same bucket of a Dictionary. What is the worst case for a lookup?Many keys land in the same bucket of a HashMap on the JVM. What is a lookup in that bucket?In Java 8+, many keys land in the same HashMap bucket. What is a lookup in that bucket?Many keys land in the same bucket of a V8 Map. What is the worst case for a lookup?
With many collisions the probe sequence grows to O(n). Swift defends with randomly seeded hashing instead of trees.Kotlin's HashMap on the JVM is Java's: buckets with 8 or more entries (in a table of at least 64) become red-black trees when keys are Comparable.Buckets with 8 or more entries (in a table of at least 64) are treeified, which bounds the damage of bad hashes or hash flooding when keys are Comparable.V8 chains colliding entries, so a crowded bucket is walked one by one: O(n). Its defense is a string hash seeded randomly per process, which makes collisions hard to plan.

A hash map stores values under keys and finds any key in O(1) on average, because the key's hash points straight to its spot.

Part Not started

The pattern: “have I seen this before?”

Many interview problems ask you to find a pair or a match in a list, like “which two numbers add up to 9?”. This is what almost everyone writes first:

Every pair, one by one

for i in nums.indices {
    for j in (i + 1)..<nums.count where nums[i] + nums[j] == target {
        return [i, j]
    }
}

for (i in nums.indices) {
    for (j in i + 1 until nums.size) {
        if (nums[i] + nums[j] == target) return intArrayOf(i, j)
    }
}

for (int i = 0; i < nums.length; i++) {
    for (int j = i + 1; j < nums.length; j++) {
        if (nums[i] + nums[j] == target) return new int[] { i, j };
    }
}

for (let i = 0; i < nums.length; i++) {
  for (let j = i + 1; j < nums.length; j++) {
    if (nums[i] + nums[j] === target) return [i, j];
  }
}

It’s correct, and it’s slow: it compares every number with every other one. For 1,000 numbers that’s about 500,000 checks; for 100,000 numbers, about 5 billion, which takes seconds. In an interview, this is where you hear “can you do better?”

The fast way walks through the list once and keeps a hash map of what it has already seen. For each new item, it asks the map: “is the partner I need already here?” Each question is O(1), so the whole thing is O(n). You pay with extra memory for the map, and that trade is almost always worth it.

One detail matters: for each item, look up its partner first, and only then store the item. Otherwise an item can find itself and be paired with itself.

Recognize the shapes: complement lookup (Two Sum, pairs with a difference), counting (anagrams, majority element, top-k with a heap), grouping by a canonical key (anagrams, isomorphic strings), index of last occurrence (longest substring without repeats, with a sliding window) and prefix sums (subarray sum equals k: store counts of prefix sums). State the trade-off out loud: “O(n) extra space for O(n) time”. For prefix sums, start the map with {0: 1}: a subarray that starts at index 0 needs the empty prefix before it.

Problemeasy

Two Sum

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Each input has exactly one solution, and you may not use the same element twice.

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]        because nums[0] + nums[1] = 2 + 7 = 9

›

The brute force checks every pair: O(n²). For each number, which one number would you need to find?

›

For num, the partner is target - num. Keep a map from value to index of everything you’ve passed. Look the partner up before you store the current number.

SolutionTry it yourself firstTime O(n)Space O(n)

Walk once. For each number, check whether its complement is already in the map; if so, you’re done. Otherwise remember the number and its index.

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var seen: [Int: Int] = [:]   // value → index
    for (i, num) in nums.enumerated() {
        if let j = seen[target - num] {
            return [j, i]
        }
        seen[num] = i
    }
    return []
}

fun twoSum(nums: IntArray, target: Int): IntArray {
    val seen = HashMap<Int, Int>()   // value → index
    for ((i, num) in nums.withIndex()) {
        seen[target - num]?.let { j -> return intArrayOf(j, i) }
        seen[num] = i
    }
    return intArrayOf()
}

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();   // value → index
    for (int i = 0; i < nums.length; i++) {
        Integer j = seen.get(target - nums[i]);
        if (j != null) return new int[] { j, i };
        seen.put(nums[i], i);
    }
    return new int[0];
}

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();   // value → index
  for (const [i, num] of nums.entries()) {
    const j = seen.get(target - num);
    if (j !== undefined) return [j, i];
    seen.set(num, i);
  }
  return [];
}

Spot the bugTwo Sum, almost

Tap the line with the bug.

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var seen: [Int: Int] = [:]
    for (i, num) in nums.enumerated() {
        seen[num] = i
        if let j = seen[target - num] {
            return [j, i]
        }
    }
    return []
}

fun twoSum(nums: IntArray, target: Int): IntArray {
    val seen = HashMap<Int, Int>()
    for ((i, num) in nums.withIndex()) {
        seen[num] = i
        seen[target - num]?.let { j -> return intArrayOf(j, i) }
    }
    return intArrayOf()
}

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        seen.put(nums[i], i);
        Integer j = seen.get(target - nums[i]);
        if (j != null) return new int[] { j, i };
    }
    return new int[0];
}

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();
  for (const [i, num] of nums.entries()) {
    seen.set(num, i);
    const j = seen.get(target - num);
    if (j !== undefined) return [j, i];
  }
  return [];
}

Shapes: complement lookup (Two Sum), counting (anagrams, majority element, top-k with a heap), grouping by a canonical key, last-seen index (with a sliding window), prefix-sum counts (subarray sum equals k: seed the map with {0: 1}). Say the trade-off: O(n) extra space for O(n) time.

The complement lookup (Two Sum)

var seen: [Int: Int] = [:]                  // value -> index
for (i, n) in nums.enumerated() {
    if let j = seen[target - n] { return [j, i] }
    seen[n] = i
}

val seen = HashMap<Int, Int>()              // value -> index
nums.forEachIndexed { i, n ->
    seen[target - n]?.let { j -> return intArrayOf(j, i) }
    seen[n] = i
}

Map<Integer, Integer> seen = new HashMap<>(); // value -> index
for (int i = 0; i < nums.length; i++) {
    Integer j = seen.get(target - nums[i]);
    if (j != null) return new int[] {j, i};
    seen.put(nums[i], i);
}

const seen = new Map<number, number>();     // value -> index
for (const [i, n] of nums.entries()) {
  const j = seen.get(target - n);
  if (j !== undefined) return [j, i];
  seen.set(n, i);
}

Look up before you store, or a number that is half the target pairs with itself.

Check this part

In Two Sum, why do you look up the complement before storing the current number?
If you store first, a number that is exactly half the target finds itself and you return the same index twice.
What do you trade to turn an O(n²) pair search into O(n) with a hash map?
The map holds up to n entries. Saying this trade-off out loud is part of a strong interview answer.
Counting subarrays that sum to k with prefix sums, why start the map with {0: 1}?
A subarray from the start has prefix sum exactly k, so it needs a previous prefix of 0: the empty prefix before the first element.

To find a pair or a match, walk the list once and ask a map of what you've seen: O(n) time for O(n) extra memory.

Part Not started

Grouping by a key

The second big hash map pattern: compute a key that is the same for everything that belongs together, and group by it. Anagrams (“eat”, “tea”, “ate”) are made of the same letters, so sorting their letters gives the same key, "aet":

Group words by their sorted letters

var groups: [String: [String]] = [:]
for word in words {
    groups[String(word.sorted()), default: []].append(word)   // a new key starts with []
}

val groups = words.groupBy { it.toCharArray().sorted().joinToString("") }

Map<String, List<String>> groups = new HashMap<>();
for (String word : words) {
    char[] letters = word.toCharArray();
    Arrays.sort(letters);
    groups.computeIfAbsent(new String(letters), k -> new ArrayList<>()).add(word);   // a new key starts with an empty list
}

const groups = new Map<string, string[]>();
for (const word of words) {
  const key = [...word].sort().join("");
  if (!groups.has(key)) groups.set(key, []);   // a new key starts with an empty list
  groups.get(key)!.push(word);
}

The map’s values are lists. The first time a key shows up there’s no list yet, so each language creates an empty one before adding the word: default: [] in Swift, computeIfAbsent in Java, a has check in TypeScript, and Kotlin’s groupBy does it all for you.

Sorting costs O(k log k) per word. With a fixed alphabet, a key of 26 letter counts brings the whole thing down to O(n · k): the usual follow-up.

Problemmedium

Group Anagrams

Given a list of words, group the anagrams together (words made of the same letters). The order of the groups doesn’t matter.

Input:  ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

›

What do “eat”, “tea” and “ate” have in common that “tan” doesn’t? Find a way to turn each word into the same key.

›

Sort the letters: “eat”, “tea” and “ate” all become “aet”. Use that as the key in a map from key to list of words.

SolutionTry it yourself firstTime O(n · k log k)Space O(n · k)

For each word (n words, up to k letters each), sort its letters to get the key, and append the word to that key’s list.

func groupAnagrams(_ words: [String]) -> [[String]] {
    var groups: [String: [String]] = [:]
    for word in words {
        let key = String(word.sorted())   // "eat" → "aet"
        groups[key, default: []].append(word)
    }
    return Array(groups.values)
}

fun groupAnagrams(words: List<String>): List<List<String>> =
    words.groupBy { it.toCharArray().sorted().joinToString("") }   // "eat" → "aet"
        .values
        .toList()

List<List<String>> groupAnagrams(String[] words) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String word : words) {
        char[] letters = word.toCharArray();
        Arrays.sort(letters);   // "eat" → "aet"
        groups.computeIfAbsent(new String(letters), k -> new ArrayList<>()).add(word);
    }
    return new ArrayList<>(groups.values());
}

function groupAnagrams(words: string[]): string[][] {
  const groups = new Map<string, string[]>();
  for (const word of words) {
    const key = [...word].sort().join("");   // "eat" → "aet"
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key)!.push(word);
  }
  return [...groups.values()];
}

Follow-up you may get: if the words only use a to z, a key of 26 letter counts avoids sorting and brings it down to O(n · k).

	Swift	Kotlin	Java	TypeScript
Group	`Dictionary(grouping:by:)`	`groupBy { }`	`Collectors.groupingBy(…)`	`Map.groupBy(xs, f)` (ES2024)
Append to list value	`m[k, default: []].append(x)`	`m.getOrPut(k) { mutableListOf() }.add(x)`	`m.computeIfAbsent(k, x -> new ArrayList<>()).add(v)`	`if (!m.has(k)) m.set(k, []); m.get(k)!.push(x)`

Group Anagrams: key = sorted letters, O(n · k log k). Follow-up: with only a to z, a key of 26 counts makes it O(n · k).

Check this part

What is a good key for grouping anagrams?
All anagrams share the same sorted letters ("eat", "tea" and "ate" all become "aet"), and nothing else does.
In groups[key, default: []].append(word), what happens the first time a key appears?What does words.groupBy { sortedLetters(it) } give you?In groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word), what happens the first time a key appears?In if (!groups.has(key)) groups.set(key, []); groups.get(key)!.push(word), what happens the first time a key appears?
The default gives a new key an empty list to start from.groupBy builds the map for you, creating a list the first time each key shows up.computeIfAbsent creates the list only when the key is missing, and returns the list either way.The has check creates the list only for a new key; after that, get returns the same list every time.
The words use only a to z. How do you avoid sorting each word?
Counts are O(k) per word and identify anagrams exactly. A set loses duplicates ("aab" vs "ab"), and a hash code can collide.

Compute a key that is the same for everything that belongs together, like a word's sorted letters, and group by it.

Part Not started

Using a set as a lookup table

Here’s a duplicate check that looks perfectly fine: keep a list of the numbers you’ve seen, and for each new number ask seen.contains(n). The catch is that contains on a list walks it from the start every time. By the end, each check walks up to 100,000 numbers, and the whole thing does billions of comparisons.

Sometimes you don’t need a value at all, only the answer to “is this in it?”. That’s a hash set: a hash map with keys and no values. Checking a set takes O(1) on average, while checking a list means walking it, O(n). Swap the list for a set, and the same code does 100,000 quick lookups instead. And adding the same value twice keeps only one copy.

A hash set is a hash map with no values (Java’s HashSet literally wraps a HashMap). Reach for it whenever the question is membership: visited nodes, seen values, allowed words. Building one costs O(n) time and memory; every lookup after that is O(1).

Does the list contain a duplicate?

func hasDuplicate(_ nums: [Int]) -> Bool {
    var seen = Set<Int>()
    for n in nums {
        if !seen.insert(n).inserted { return true }   // already there
    }
    return false
}

fun hasDuplicate(nums: IntArray): Boolean {
    val seen = HashSet<Int>()
    for (n in nums) {
        if (!seen.add(n)) return true   // add returns false when it was already there
    }
    return false
}

boolean hasDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int n : nums) {
        if (!seen.add(n)) return true;   // add returns false when it was already there
    }
    return false;
}

function hasDuplicate(nums: number[]): boolean {
  const seen = new Set<number>();
  for (const n of nums) {
    if (seen.has(n)) return true;
    seen.add(n);   // add returns the set itself, not true or false
  }
  return false;
}

Problemmedium

Longest Consecutive Sequence

Given an unsorted array of integers, return the length of the longest run of consecutive numbers. It must run in O(n), so sorting is not allowed.

Input:  [100, 4, 200, 1, 3, 2]
Output: 4             because 1, 2, 3, 4

›

Put everything in a set. A number starts a run only if number - 1 is not in the set.

SolutionTry it yourself firstTime O(n)Space O(n)

Only count upward from the start of each run. Every number is visited at most twice (once in the outer loop, once while counting), so the nested loop is still O(n) overall.

func longestConsecutive(_ nums: [Int]) -> Int {
    let set = Set(nums)
    var best = 0
    for n in set where !set.contains(n - 1) {
        var length = 1
        while set.contains(n + length) { length += 1 }
        best = max(best, length)
    }
    return best
}

fun longestConsecutive(nums: IntArray): Int {
    val set = nums.toHashSet()
    var best = 0
    for (n in set) {
        if (n - 1 in set) continue
        var length = 1
        while (n + length in set) length++
        best = maxOf(best, length)
    }
    return best
}

int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) set.add(n);
    int best = 0;
    for (int n : set) {
        if (set.contains(n - 1)) continue;
        int length = 1;
        while (set.contains(n + length)) length++;
        best = Math.max(best, length);
    }
    return best;
}

function longestConsecutive(nums: number[]): number {
  const set = new Set(nums);
  let best = 0;
  for (const n of set) {
    if (set.has(n - 1)) continue;
    let length = 1;
    while (set.has(n + length)) length++;
    best = Math.max(best, length);
  }
  return best;
}

	Swift	Kotlin	Java	TypeScript
Set	`Set(nums)`	`nums.toHashSet()`	`new HashSet<>(list)`	`new Set(nums)`
Add, report duplicate	`set.insert(x).inserted`	`set.add(x)`	`set.add(x)`	`set.has(x)`, then `set.add(x)`

Longest Consecutive Sequence in O(n): put everything in a set, and count upward only from numbers where n - 1 is not in the set. Each number is visited at most twice, so the nested loop is still O(n).

Check this part

You need to answer "have I seen this number?" thousands of times. Which is faster?
A set jumps to the value by its hash, O(1) on average. A list has to be walked, O(n).
You add the number 7 to a set twice. How many 7s does the set hold?
A set keeps each value at most once. The second insert reports inserted: false.A set keeps each value at most once. The second add simply returns false.A set keeps each value at most once. Careful: add returns the set itself, not true or false, so ask has first when you need to know.
Longest Consecutive Sequence in O(n): which numbers do you start counting from?
Starting only at the beginning of each run means every number is visited at most twice overall.

A set is a map without values: it tells you whether a value is in it in O(1), and keeps each value once.

Part Not started

Keys that behave

A map finds a key by the hash it had when it was stored. Watch what happens when a key changes after that:

Changing a key after storing it

var key = [0, 0]
var visited: Set<[Int]> = [key]
key[0] = 5
print(visited.contains([0, 0]))   // true: the set kept its own copy

val key = mutableListOf(0, 0)
val visited = hashSetOf(key)
key[0] = 5
println(key in visited)   // false: it's still filed under the hash of [0, 0]

List<Integer> key = new ArrayList<>(List.of(0, 0));
Set<List<Integer>> visited = new HashSet<>(Set.of(key));
key.set(0, 5);
System.out.println(visited.contains(key));   // false: still filed under the hash of [0, 0]

const key = [0, 0];
const visited = new Set([key]);
key[0] = 5;
console.log(visited.has(key));      // true: the same array object
console.log(visited.has([0, 0]));   // false: a different array

Kotlin, Java

The set holds the same list object you changed. It’s still sitting in the spot for [0, 0], but it now says [5, 0]: asking for [5, 0] looks in another spot, and asking for [0, 0] finds an object that isn’t equal anymore. The entry is lost, though it still takes up memory.

TypeScript

TypeScript’s Map and Set compare objects and arrays by identity, never by contents: they ask “is it the same object?”. So changing key doesn’t lose it, but a new array that looks the same, [0, 0], is never found. For a key made of several values, build a string or a number: `${row},${col}`.

Swift

Arrays and structs in Swift are values: inserting copied the key into the set, so changing your variable didn’t touch it. That’s one bug Swift’s value types prevent; a class used as a key would have the same problem as in Kotlin and Java.

So use keys that never change: strings, numbers, and structs, data classes or records with read-only properties (let, val).

One Java trap: map values like Integer are objects (see boxing in the basics above), and == on two objects asks “is it the same object?”, not “is it the same number?”. Compare them with equals (or Objects.equals).

The two contracts every key must keep: what equals / hashCode (or Hashable) use never changes while the key is in a map, and equal keys have equal hashes. Records, data classes and synthesized Hashable give you both; hand-written ones and var properties are where it breaks.

Bugs that only appear with real data

Mutable keys. Change a field that hashCode() uses after inserting the object, and the entry is still there but can never be found. Use immutable keys: Swift structs, Kotlin data class with vals, Java records.
equals without hashCode (Java): two equal objects land in different buckets. Records and data classes generate both.

Spot the bugComparing letter counts

Tap the line with the bug.

boolean sameCounts(Map<Character, Integer> a, Map<Character, Integer> b) {
    if (a.size() != b.size()) return false;
    for (char c : a.keySet()) {
        if (a.get(c) != b.get(c)) return false;
    }
    return true;
}

Keys that change

A hash set finds an element by the hash it had when it was inserted. Value types and reference types behave very differently here:

Predict the output

What gets printed?

struct Cell: Hashable {
    var row: Int
    var col: Int
}

var visited = Set<Cell>()
var cell = Cell(row: 0, col: 0)
visited.insert(cell)
cell.col += 1
visited.insert(cell)
print(visited.count)
print(visited.contains(Cell(row: 0, col: 0)))

data class Cell(var row: Int, var col: Int)

val visited = HashSet<Cell>()
val cell = Cell(0, 0)
visited.add(cell)
cell.col += 1
visited.add(cell)
println(visited.size)
println(Cell(0, 0) in visited)

final class Cell {
    int row, col;
    Cell(int row, int col) { this.row = row; this.col = col; }
    @Override public boolean equals(Object o) { return o instanceof Cell c && c.row == row && c.col == col; }
    @Override public int hashCode() { return Objects.hash(row, col); }
}

Set<Cell> visited = new HashSet<>();
Cell cell = new Cell(0, 0);
visited.add(cell);
cell.col += 1;
visited.add(cell);
System.out.println(visited.size());
System.out.println(visited.contains(new Cell(0, 0)));

const visited = new Set<{ row: number; col: number }>();
const cell = { row: 0, col: 0 };
visited.add(cell);
cell.col += 1;
visited.add(cell);
console.log(visited.size);
console.log(visited.has({ row: 0, col: 0 }));

Equality without a matching hash

Spot the bugThe newsletter that ignores unsubscribes

Tap the line with the bug.

struct Email: Hashable {
    let value: String

    static func == (a: Email, b: Email) -> Bool {
        a.value.lowercased() == b.value.lowercased()
    }
}

let unsubscribed: Set = [Email(value: "ana@example.com")]
print(unsubscribed.contains(Email(value: "Ana@Example.com")))

class Email(val value: String) {
    override fun equals(other: Any?) =
        other is Email && other.value.equals(value, ignoreCase = true)
}

val unsubscribed = hashSetOf(Email("ana@example.com"))
println(Email("Ana@Example.com") in unsubscribed)

final class Email {
    final String value;
    Email(String value) { this.value = value; }
    @Override public boolean equals(Object o) {
        return o instanceof Email e && e.value.equalsIgnoreCase(value);
    }
}

Set<Email> unsubscribed = new HashSet<>(Set.of(new Email("ana@example.com")));
System.out.println(unsubscribed.contains(new Email("Ana@Example.com")));

class Email {
  constructor(readonly value: string) {}
  equals(other: Email) { return other.value.toLowerCase() === this.value.toLowerCase(); }
}

const unsubscribed = new Set([new Email("ana@example.com")]);
console.log(unsubscribed.has(new Email("Ana@Example.com")));

Equal objects must have equal hashes, because the set compares with equals only inside one bucket. Here equality ignores case but the hash doesn’t:

Swift still synthesizes hash(into:) from value, case-sensitively, so the two emails land in different buckets.
Kotlin and Java inherit hashCode() from Object: an identity hash, different for every instance, so even two identical lowercase emails don’t match.
TypeScript has no equals / hashCode contract at all: a Set of objects compares by identity and never calls your equals, so no two Email objects ever match.

It prints false, and a user who unsubscribed keeps getting email: a support ticket at best, a legal problem at worst.

Normalize once, and let the language derive both from the same data:

struct Email: Hashable {
    let value: String
    init(_ raw: String) { value = raw.lowercased() }   // == and hash both use the normalized value
}

@JvmInline
value class Email private constructor(val value: String) {
    companion object {
        fun of(raw: String) = Email(raw.lowercase())   // equals and hashCode come from value
    }
}

record Email(String value) {
    Email {
        value = value.toLowerCase(Locale.ROOT);           // equals and hashCode come from value
    }
}

// Sets can't compare objects by value: store the normalized string itself.
const normalize = (raw: string) => raw.toLowerCase();
const unsubscribed = new Set([normalize("ana@example.com")]);
unsubscribed.has(normalize("Ana@Example.com"));   // true

Note Locale.ROOT: with the default locale, a Turkish server lowercases I to a dotless ı, and MAIL@... stops matching.

Exercise: an LRU cache

Exercisemedium

LRU Cache

Design a cache with a fixed capacity that supports get(key) and put(key, value) in O(1) time. When it’s full, put evicts the least recently used entry. Both get and put count as a use.

capacity 2
put(1, "a"), put(2, "b")
get(1)       → "a"     (1 is now the most recent)
put(3, "c")            (evicts 2, the least recent)
get(2)       → null

This is one of the most common senior coding questions, and a real building block (image caches, HTTP caches).

›

A hash map gives O(1) lookup but no order. A linked list gives O(1) move-to-front and remove-from-back, but no lookup. Combine them.

›

Map from key to list node, and use a doubly linked list so a node can unlink itself in O(1). Sentinel head and tail nodes remove all the edge cases. In an interview, mention that Java’s LinkedHashMap with accessOrder = true already is this structure, then build it yourself if they ask.

SolutionTry it yourself firstTime O(1) per operationSpace O(capacity)

final class LRUCache<Key: Hashable, Value> {
    private final class Node {
        let key: Key?
        var value: Value?
        var prev: Node?
        var next: Node?
        init(key: Key? = nil, value: Value? = nil) { self.key = key; self.value = value }
    }

    private let capacity: Int
    private var nodes: [Key: Node] = [:]
    private let head = Node(), tail = Node()   // head.next = most recent

    init(capacity: Int) {
        self.capacity = capacity
        head.next = tail
        tail.prev = head
    }

    func get(_ key: Key) -> Value? {
        guard let node = nodes[key] else { return nil }
        moveToFront(node)
        return node.value
    }

    func put(_ key: Key, _ value: Value) {
        if let node = nodes[key] {
            node.value = value
            moveToFront(node)
            return
        }
        if nodes.count == capacity, let lru = tail.prev, let lruKey = lru.key {
            unlink(lru)
            nodes[lruKey] = nil
        }
        let node = Node(key: key, value: value)
        nodes[key] = node
        insertAfterHead(node)
    }

    private func moveToFront(_ node: Node) { unlink(node); insertAfterHead(node) }

    private func unlink(_ node: Node) {
        node.prev?.next = node.next
        node.next?.prev = node.prev
    }

    private func insertAfterHead(_ node: Node) {
        node.next = head.next
        node.prev = head
        head.next?.prev = node
        head.next = node
    }
}

class LRUCache<K : Any, V : Any>(private val capacity: Int) {
    private class Node<K, V>(val key: K?, var value: V?) {
        var prev: Node<K, V>? = null
        var next: Node<K, V>? = null
    }

    private val nodes = HashMap<K, Node<K, V>>()
    private val head = Node<K, V>(null, null)   // head.next = most recent
    private val tail = Node<K, V>(null, null)

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: K): V? {
        val node = nodes[key] ?: return null
        moveToFront(node)
        return node.value
    }

    fun put(key: K, value: V) {
        nodes[key]?.let { node ->
            node.value = value
            moveToFront(node)
            return
        }
        if (nodes.size == capacity) {
            val lru = tail.prev!!
            unlink(lru)
            nodes.remove(lru.key!!)
        }
        val node = Node(key, value)
        nodes[key] = node
        insertAfterHead(node)
    }

    private fun moveToFront(node: Node<K, V>) { unlink(node); insertAfterHead(node) }

    private fun unlink(node: Node<K, V>) {
        node.prev?.next = node.next
        node.next?.prev = node.prev
    }

    private fun insertAfterHead(node: Node<K, V>) {
        node.next = head.next
        node.prev = head
        head.next?.prev = node
        head.next = node
    }
}

// The library answer: LinkedHashMap keeps access order and asks before each insert whether to evict.
class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    LRUCache(int capacity) {
        super(16, 0.75f, true);   // accessOrder = true: get() moves the entry to the end
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}
// If the interviewer wants it by hand, it's the same map + doubly linked list as the Swift and Kotlin versions.

// A Map remembers insertion order, so "move to the end" is delete + set,
// and the least recently used key is always the first one.
class LRUCache<K, V> {
  private readonly entries = new Map<K, V>();

  constructor(private readonly capacity: number) {}

  get(key: K): V | undefined {
    if (!this.entries.has(key)) return undefined;
    const value = this.entries.get(key)!;
    this.entries.delete(key);
    this.entries.set(key, value);
    return value;
  }

  put(key: K, value: V): void {
    this.entries.delete(key);
    this.entries.set(key, value);
    if (this.entries.size > this.capacity) {
      const oldest = this.entries.keys().next().value!;
      this.entries.delete(oldest);
    }
  }
}

Follow-ups to be ready for:

Thread safety. Every get mutates the list, so even reads need the lock (or an actor in Swift). Under contention, shard the cache by key hash, or switch to approximate recency like Caffeine’s W-TinyLFU, which also has a better hit rate than pure LRU.
Size by weight, not count: images of very different sizes need a byte budget (NSCache.totalCostLimit, Android’s LruCache.sizeOf).
Memory pressure on mobile: clear or shrink the cache on a memory warning or onTrimMemory.

Swift

Keys are safe by default: a struct is copied into the set or dictionary, so changing your variable afterwards doesn’t touch the stored key.
Equal values need equal hashes: a custom == that ignores case next to a synthesized, case-sensitive hash(into:) makes contains return false. Normalize once in init and let Swift synthesize both.
LRU cache in O(1): a dictionary from key to node of a doubly linked list, with sentinel head and tail.

Kotlin

Mutable keys: change a field used by hashCode after inserting, and the entry is stranded in the old bucket. Use val properties in a data class.
Equal objects need equal hashes: overriding equals (say, ignoring case) without hashCode keeps the identity hash, so contains returns false. Normalize once and let a data or value class derive both.
LRU cache in O(1): a HashMap from key to node of a doubly linked list, with sentinel head and tail.

Java

Mutable keys: change a field used by hashCode after inserting, and the entry is stranded in the old bucket. Use records.
Equal objects need equal hashes: overriding equals (say, ignoring case) without hashCode keeps the identity hash, so contains returns false. Normalize in a record’s compact constructor (with Locale.ROOT).
Integer with == compares references; it works only inside the -128..127 cache. Use equals, or Map.equals for whole maps.
LRU cache in O(1): LinkedHashMap with accessOrder = true and removeEldestEntry, or by hand, a map from key to node of a doubly linked list.

TypeScript

Keys are compared by identity: changing an object used as a key doesn’t lose it, but an equal-looking new object ({ row: 0, col: 0 }, [0, 0]) is never found. Encode compound keys as strings (`${row},${col}`) or numbers.
No equals / hashCode: a Set never calls your equals method. Store the normalized value (a lowercased email) instead of an object.
LRU cache in O(1): a Map already keeps insertion order, so delete + set moves a key to the end, and keys().next().value is the least recently used.

Check this part

You store an object as a key, then change a field used to compute its hash. What does a lookup with that object return?
The entry is still stored under the old hash. Use keys that never change.
Which of these is a safe key for a dictionary?Which of these is a safe key for a map?How should you compare two Integer counts taken from a map?You add [0, 0] to a Set, then ask has([0, 0]). What do you get?
Read-only properties mean the hash can never change after the key is stored.Read-only properties mean the hash can never change after the key is stored, and a data class generates equals and hashCode for you.== compares objects, not numbers. It happens to work for small numbers, which makes the bug hard to spot.Set and Map compare objects and arrays by identity. Use a string key like "0,0" for coordinates.
You insert a Cell struct into a Set, then change cell.col. What happens to the element in the set?You use a mutable object as a key, then change a field that hashCode uses. What does map[key] return?You use a mutable object as a key, then change a field that hashCode uses. What does get(key) return?You use an object as a Map key, then change one of its fields. Does map.get(sameObject) still find it?
Structs are values: insert stored a copy, and changing your variable doesn't touch it. That's why value types make safe keys.The set or map holds a reference to the same object, still filed under the old hash, so it's effectively lost. Use val properties for keys.The map holds a reference to the same object, still filed under the old hash, so it's effectively lost. Use records for keys.The hash of an object key is an identity hash, stored on the object and independent of its fields, so the entry is still found. The trap is the other way round: an equal-looking new object is never found.
A Hashable struct has a custom == that ignores case, and a synthesized hash. Does a Set find "Ana@Example.com" when it holds "ana@example.com"?A Kotlin class overrides equals (ignoring case) but not hashCode. Does a HashSet find an equal instance?A Java class overrides equals (ignoring case) but not hashCode. Does a HashSet find an equal instance?A Set holds { email: "ana@example.com" }. Does has({ email: "ana@example.com" }) find it?
The set only compares for equality inside one bucket. Equal values must have equal hashes: normalize once in the initializer and let the language derive both.

Use keys that never change, and make sure equal keys have equal hashes; in Java, compare Integer values with equals, not ==.

Key takeaways

A hash map stores values under keys and finds them in O(1) on average.
When you see two nested loops searching for a match, try one loop plus a hash map of what you’ve seen.
Two Sum: look up the complement first, then store. Group Anagrams: group by a canonical key.
Say the trade-off out loud: O(n) memory for O(n) time.

O(1) is the average. The worst case depends on hash quality: Java treeifies crowded buckets (O(log n)), and Swift and Kotlin/JVM seed or spread hashes against flooding.
Keys must be immutable in the fields used by equals/hashCode (or Hashable), and the two must agree.
Iteration order is unspecified, except LinkedHashMap and Kotlin’s mutableMapOf. Never let output or tests depend on it.
With a small fixed alphabet, an array of counts beats a map: mention it as the follow-up.