Data Structures

Big-O describes how performance scales as input grows. Not "how fast" but "how much slower when data doubles."

O(1)     Constant    HashMap.get()       10 items: 1 step. 10M items: 1 step.
O(log n) Logarithmic TreeMap.get()        10 items: 3 steps. 10M items: 23 steps.
O(n)     Linear      List.contains()      10 items: 10 steps. 10M items: 10M steps.
O(n log n) Loglinear  List.sorted()       10 items: 33 steps. 10M items: 230M steps.
O(n^2)   Quadratic   Nested loops         10 items: 100 steps. 10M items: 100 TRILLION.

Why this matters practically:

// Checking if user exists — two approaches:
val users: List<User> = loadUsers()        // 100K users

// O(n) — scan the whole list:
users.any { it.id == targetId }             // up to 100K comparisons

// O(1) — use a HashSet:
val userIds: Set<String> = users.map { it.id }.toSet()
userIds.contains(targetId)                  // 1 hash lookup

// At 100K users: List search ~5ms, Set lookup ~0.001ms
// At 10M users: List search ~500ms, Set lookup ~0.001ms (still!)

Common Big-O by data structure:

Operation       ArrayList   LinkedList   HashMap   TreeMap   HashSet
get(index)      O(1)        O(n)         -         -         -
get(key)        -           -            O(1)      O(log n)  -
contains(val)   O(n)        O(n)         O(1)*     O(log n)  O(1)
add(end)        O(1)**      O(1)         O(1)      O(log n)  O(1)
add(middle)     O(n)        O(1)***      -         -         -
remove          O(n)        O(1)***      O(1)      O(log n)  O(1)

* HashMap: O(1) amortized, O(n) worst case (hash collisions)
** ArrayList: O(1) amortized, O(n) when array needs resizing
*** LinkedList: O(1) for remove/add IF you already have the node reference

Interview tip: don't just memorize. Understand WHY: HashMap is O(1) because hash function jumps directly to the bucket. ArrayList.get(i) is O(1) because array index = memory offset. LinkedList.get(i) is O(n) because you must walk node by node.

ArrayList — contiguous array in memory:

Memory: [elem0][elem1][elem2][elem3][elem4]
         ^all elements side by side in RAM

get(2):    jump to position 2 in array = O(1). Instant.
add(end):  put element at the end = O(1). Occasionally O(n) when array needs resizing (copies to bigger array).
add(1, x): shift elements 1-4 right, insert at position 1 = O(n).

LinkedList — nodes scattered in memory:

Memory: [node0]---> [node1]---> [node2]---> [node3]
        scattered randomly across RAM

get(2):    start at node0, follow .next twice = O(n). Slow.
add(end):  create node, link to tail = O(1).
add(after node1): create node, relink pointers = O(1). But FINDING node1 is O(n).

Why ArrayList wins in practice — CPU cache locality:

Modern CPUs load memory in 64-byte cache lines. ArrayList: elements are contiguous, one cache load brings multiple elements. LinkedList: nodes scattered, each .next pointer is a cache miss (100x slower than cache hit).

Even for "insert in middle" — ArrayList's O(n) array copy uses fast System.arraycopy() (memcpy, CPU-optimized). LinkedList's O(1) insert requires O(n) traversal to find the position first, plus cache misses along the way.

When to use LinkedList: almost never. Java's own documentation recommends ArrayList for most cases. LinkedList is useful as a Queue/Deque implementation (add/remove at both ends), but even there ArrayDeque is faster.

Kotlin: listOf() and mutableListOf() both create ArrayList. There's no convenient way to create LinkedList — by design.

C#: List<T> is ArrayList. LinkedList<T> exists but rarely used. Same conclusion.

HashMap internals step by step:

map.put("alex", User("Alex"))

1. Calculate hash: "alex".hashCode() = 3052242
2. Find bucket index: 3052242 % 16 = 2  (16 = initial array size)
3. Go to bucket[2]
4. If empty: store (key, value) as first node
   If occupied: check each node with .equals()
     If key matches: replace value
     If no match: add to end of chain (linked list)

map.get("alex")
1. hashCode() = 3052242, bucket = 2
2. Walk chain in bucket[2], call .equals() on each key
3. Found "alex" -> return User("Alex")

Hash collision — multiple keys in same bucket:

// "Aa".hashCode() == "BB".hashCode() in Java! (collision)
map.put("Aa", 1)   // bucket 5: [Aa=1]
map.put("BB", 2)   // bucket 5: [Aa=1] -> [BB=2]  (linked list)

// Before Java 8: long chains = O(n) lookup
// Java 8+: if chain > 8 elements, converts to red-black tree = O(log n)
// This prevents DoS attacks using crafted hash collisions

Resizing (rehashing):

// Load factor = 0.75 (default). When 75% of buckets filled -> resize.
// Array doubles: 16 -> 32 -> 64 -> 128...
// ALL entries rehashed to new bucket positions.
// This is O(n) but happens rarely (amortized O(1) per put).

Why hashCode() and equals() contract matters:

// RULE: if a.equals(b) then a.hashCode() == b.hashCode()
// If you break this: put(key1, value), get(key2) where key1.equals(key2)
//   but hashCode differs -> different bucket -> key not found!
// Kotlin data class generates both correctly from constructor properties.
// This is why body properties in data class are excluded from hashCode() — gotcha!

Kotlin: mapOf() creates LinkedHashMap (preserves insertion order). hashMapOf() creates HashMap (no order guarantee). C#: Dictionary<K,V> is the equivalent of HashMap.

val hash = hashMapOf("banana" to 2, "apple" to 1, "cherry" to 3)
// Iteration order: unpredictable. Maybe "cherry", "apple", "banana"

val linked = linkedMapOf("banana" to 2, "apple" to 1, "cherry" to 3)
// Iteration order: insertion order. Always "banana", "apple", "cherry"

val tree = sortedMapOf("banana" to 2, "apple" to 1, "cherry" to 3)
// Iteration order: sorted by key. Always "apple", "banana", "cherry"

Performance comparison:

Operation    HashMap      LinkedHashMap    TreeMap
put          O(1)         O(1)             O(log n)
get          O(1)         O(1)             O(log n)
remove       O(1)         O(1)             O(log n)
Iteration    unpredictable insertion order  sorted order
Memory       lowest       +linked list     +tree nodes

When to use each:

HashMap: default choice. Fastest. Use when you don't care about order. Caches, lookup tables, frequency counters.

LinkedHashMap: when insertion order matters. LRU cache (override removeEldestEntry), maintaining config key order, JSON serialization where field order matters.

TreeMap: when you need sorted keys or range queries. "All transactions between March and June" with date keys. NavigableMap methods: firstKey(), lastKey(), subMap(from, to), floorKey(), ceilingKey().

Kotlin note: mapOf() creates LinkedHashMap (preserves insertion order). hashMapOf() for HashMap. sortedMapOf() for TreeMap. C#: Dictionary = HashMap, SortedDictionary = TreeMap. No built-in LinkedHashMap in C#.

val hashSet = hashSetOf(3, 1, 4, 1, 5, 9)
// Contains: {1, 3, 4, 5, 9} — no order guaranteed
// hashSet.contains(4) → O(1) — instant

val treeSet = sortedSetOf(3, 1, 4, 1, 5, 9)
// Contains: {1, 3, 4, 5, 9} — SORTED!
// treeSet.contains(4) → O(log n) — slightly slower
// treeSet.first() → 1  (minimum)
// treeSet.last() → 9   (maximum)
// treeSet.subSet(3, 6) → {3, 4, 5}  (range query!)

Under the hood: HashSet is literally a HashMap where values are a dummy constant. set.add(x) calls map.put(x, PRESENT). set.contains(x) calls map.containsKey(x). Same for TreeSet — it's a TreeMap wrapper.

When to use TreeSet: maintaining a sorted leaderboard, finding nearest elements (floor/ceiling), range queries. In a bank: "all transaction amounts between $100 and $500" → TreeSet of amounts.

Kotlin: setOf() creates LinkedHashSet (insertion order). hashSetOf() for HashSet. sortedSetOf() for TreeSet. C#: HashSet<T> and SortedSet<T>.

// List = read-only interface (no add, remove, set)
val list: List<Int> = listOf(1, 2, 3)
list.add(4)     // COMPILE ERROR — no add method
list[0] = 5     // COMPILE ERROR — no set method

// MutableList = read-write interface
val mutable: MutableList<Int> = mutableListOf(1, 2, 3)
mutable.add(4)  // OK
mutable[0] = 5  // OK

The trap — read-only is NOT immutable:

val mutable = mutableListOf(1, 2, 3)
val readOnly: List<Int> = mutable  // upcast to read-only interface

readOnly.add(4)     // COMPILE ERROR — good, can't add through readOnly

mutable.add(4)      // OK — mutable still has the reference!
println(readOnly)   // [1, 2, 3, 4] — readOnly sees the change!
// readOnly is just a VIEW of the same mutable list object.

How to get true immutability:

// Defensive copy:
val immutable: List<Int> = mutable.toList()  // NEW list, separate object
mutable.add(4)
println(immutable)  // [1, 2, 3] — not affected!

// Or use Kotlin immutable collections library (kotlinx.collections.immutable):
val persistent = persistentListOf(1, 2, 3)
val newList = persistent.add(4)  // returns NEW list, original unchanged

Why this matters for our banking tutorial: the AccountRepository.getAll() bug. Returning the internal MutableList as List gives callers a read-only view — but they still see mutations when add() is called internally. Fix: return accounts.toList() — defensive copy.

Java: Collections.unmodifiableList() — throws at runtime on add(). List.of() (Java 9+) — truly immutable. C#: IReadOnlyList<T> = read-only view. ImmutableList<T> = truly immutable.

// List (eager) — creates intermediate lists at EACH step:
val result = (1..1_000_000)
    .filter { it % 2 == 0 }     // creates List of 500K elements
    .map { it * 2 }              // creates ANOTHER List of 500K elements
    .take(10)                    // creates List of 10 elements
    .toList()
// Processed ALL 1M elements. Created 3 intermediate lists. Wasteful.

// Sequence (lazy) — processes one element at a time:
val result = (1..1_000_000).asSequence()
    .filter { it % 2 == 0 }     // no list created — just remembers the filter
    .map { it * 2 }              // no list created — just remembers the transform
    .take(10)                    // stops after finding 10!
    .toList()                    // NOW executes — processes ~20 elements total
// Only processed ~20 elements. Zero intermediate lists.

How lazy evaluation works:

List: process ALL elements through filter. Then ALL results through map. Then take 10. Horizontal — complete each step for all elements before moving on.

Sequence: take element 1 → filter → map → collect. Take element 2 → filter → map → collect. Vertical — process each element through the entire chain. Stop early with take(10).

When to use Sequence:

Large collections (10K+ elements) with multiple chained operations (filter + map + take). Early termination (first, take, any, none). Reading from files or I/O (process line by line without loading all into memory).

When NOT to use Sequence:

Small collections (under 1000 elements) — overhead of laziness exceeds benefit. Single operation (just .filter) — no intermediate lists anyway. When you need the entire result — no early termination advantage.

Across languages:

Kotlin: list.filter{}.map{}       — eager (creates intermediates)
        list.asSequence().filter{} — lazy
Java:   list.stream().filter()     — lazy (streams are always lazy)
C#:     list.Where().Select()      — lazy (LINQ is always lazy)
        list.Where().ToList()      — materializes

Kotlin chose eager by default because it's simpler and safer (no surprise side effects from lazy evaluation). Sequence is opt-in when you need performance.

Why collisions are inevitable: hashCode() returns an int (2^32 = ~4 billion values). If you have more than 4 billion objects, collisions are mathematically guaranteed. Even with fewer objects, the birthday paradox means collisions happen sooner than you'd expect.

Collision resolution in Java HashMap:

// Java 7: chaining with linked list
bucket[5]: [key1=val1] -> [key2=val2] -> [key3=val3]
// get(key2): hash -> bucket 5 -> walk list, call equals() on each
// O(n) worst case for long chains

// Java 8+: linked list converts to red-black tree when chain > 8
bucket[5]: [key1=val1] -> [key2=val2] -> ... -> [key8=val8]
// 9th collision: converts to balanced tree
// O(log n) worst case instead of O(n)
// Converts back to list when chain < 6 (hysteresis to avoid thrashing)

The hashCode/equals contract:

// RULE 1: if a.equals(b) then a.hashCode() == b.hashCode()
//   Both go to the same bucket. equals() finds the match. Correct.

// BREAKING RULE 1: equals returns true but hashCode differs
//   a goes to bucket 3, b goes to bucket 7.
//   map.put(a, val) stores in bucket 3.
//   map.get(b) looks in bucket 7. Not found! BUG.

// RULE 2 (not required but desired): different objects should have different hashCodes
//   If all objects return hashCode() = 42, everything goes in one bucket.
//   HashMap degrades to a linked list / tree. O(n) or O(log n) instead of O(1).

Kotlin data class: auto-generates both hashCode() and equals() from constructor properties. Body properties are excluded! This is the data class body property trap we discussed — loginCount in the body doesn't affect hashCode, so two Users with different loginCount have the same hash.

// Java — verbose with stream/collect:
List<String> names = users.stream()
    .filter(u -> u.getAge() > 18)
    .map(User::getName)
    .sorted()
    .collect(Collectors.toList());

Map<String, List<User>> byCity = users.stream()
    .collect(Collectors.groupingBy(User::getCity));

// Kotlin — direct, concise:
val names = users
    .filter { it.age > 18 }
    .map { it.name }
    .sorted()
// Returns List directly. No .stream(), no .collect().

val byCity = users.groupBy { it.city }
// Returns Map<String, List<User>> directly.

Essential Kotlin collection functions:

// Transforming:
.map { transform }          // [1,2,3] -> [2,4,6]        C#: .Select()
.flatMap { toList }         // [[1,2],[3]] -> [1,2,3]    C#: .SelectMany()
.associate { it to value }  // List -> Map                C#: .ToDictionary()

// Filtering:
.filter { predicate }       // keep matching              C#: .Where()
.filterNotNull()            // remove nulls               C#: .Where(x => x != null)
.distinct()                 // remove duplicates           C#: .Distinct()

// Aggregating:
.groupBy { key }            // group into Map              C#: .GroupBy()
.partition { predicate }    // split into (match, rest)    C#: n/a
.sumOf { selector }         // sum by property             C#: .Sum()
.count { predicate }        // count matching              C#: .Count()

// Finding:
.first { predicate }        // first match or throw        C#: .First()
.firstOrNull { pred }       // first match or null         C#: .FirstOrDefault()
.any { predicate }          // at least one matches        C#: .Any()
.all { predicate }          // all match                   C#: .All()
.none { predicate }         // none match                  C#: n/a

// Ordering:
.sorted()                   // natural order               C#: .OrderBy()
.sortedBy { selector }      // by property                 C#: .OrderBy(x => x.Prop)
.sortedByDescending { }     // reverse                     C#: .OrderByDescending()

All of these return new collections (immutable-friendly). None mutate the original. All are inline functions — zero lambda allocation overhead.

// Queue interface — FIFO:
val queue: Queue<String> = ArrayDeque()
queue.offer("first")      // add to tail
queue.offer("second")
queue.offer("third")
queue.poll()               // remove from head -> "first"
queue.peek()               // look at head without removing -> "second"

Implementations:

ArrayDeque: fastest general-purpose queue AND stack. Backed by resizable circular array. O(1) for add/remove at both ends. No capacity limits. Recommended over LinkedList and Stack. Kotlin's ArrayDeque is the same.

PriorityQueue: elements sorted by priority (natural order or Comparator). Not FIFO — highest priority element comes out first. Backed by binary heap. O(log n) add/remove, O(1) peek.

val pq = PriorityQueue<Int>()  // min-heap by default
pq.addAll(listOf(5, 1, 3))
pq.poll()  // 1 (smallest first)
pq.poll()  // 3
pq.poll()  // 5

// Max-heap:
val maxPq = PriorityQueue<Int>(reverseOrder())
// Use for: "top N elements", scheduling by priority, Dijkstra's algorithm

BlockingQueue (java.util.concurrent): thread-safe. put() blocks when full. take() blocks when empty. Used for producer-consumer pattern in multi-threaded code. Implementations: ArrayBlockingQueue (bounded), LinkedBlockingQueue (optionally bounded).

In Kotlin coroutines: use Channel instead of BlockingQueue. Channel suspends (frees thread) instead of blocking.

Deque (Double-Ended Queue): add/remove from both ends. Can be used as both queue (FIFO) and stack (LIFO). ArrayDeque implements Deque.

// DON'T — legacy Stack:
val stack = java.util.Stack<Int>()
stack.push(1)   // synchronized internally — overhead even in single-threaded code
stack.pop()     // synchronized again
// Stack extends Vector (synchronized ArrayList). Designed in Java 1.0.
// Every operation takes a lock. No one needs this for a local stack.

// DO — ArrayDeque as stack:
val stack = ArrayDeque<Int>()
stack.addFirst(1)  // push
stack.removeFirst() // pop
stack.peekFirst()   // peek
// Or in Kotlin:
stack.addLast(1)   // push (Kotlin convention — add to end)
stack.removeLast() // pop
// No synchronization. Faster. Modern.

Java's legacy collection classes to avoid:

Legacy (avoid)        Modern replacement
Stack                 ArrayDeque (as stack)
Vector                ArrayList (or ConcurrentList if thread-safe needed)
Hashtable             HashMap (or ConcurrentHashMap if thread-safe needed)
Enumeration           Iterator
StringBuffer          StringBuilder (or StringBuffer only if shared across threads)

All legacy classes are synchronized on every operation — designed when Java had no other concurrency tools. Modern code: use unsynchronized classes + explicit locking where needed. In Kotlin coroutines: use Mutex or Channel for thread safety.

// Collections.synchronizedMap — coarse-grained locking:
val map = Collections.synchronizedMap(HashMap<String, Int>())
// EVERY operation (get, put, contains) acquires ONE lock on entire map
// Thread 1 puts key "A" — locks entire map
// Thread 2 wants to get key "Z" — WAITS for Thread 1
// Terrible concurrency — effectively single-threaded access

// ConcurrentHashMap — fine-grained locking:
val map = ConcurrentHashMap<String, Int>()
// Thread 1 puts key "A" (bucket 5) — locks ONLY bucket 5
// Thread 2 gets key "Z" (bucket 12) — no lock needed for reads!
// Both proceed simultaneously. True concurrency.

Key operations that are atomic:

// putIfAbsent — atomic check-and-put:
map.putIfAbsent("key", value)
// If key doesn't exist: insert and return null
// If key exists: return existing value, don't overwrite
// ALL ATOMIC — no race condition between check and put

// computeIfAbsent — atomic compute-and-put:
map.computeIfAbsent("key") { expensiveComputation() }
// If key doesn't exist: compute value, insert, return it
// If key exists: return existing value
// Computation runs at most ONCE per key — even with concurrent calls

// merge — atomic read-modify-write:
map.merge("counter", 1) { old, new -> old + new }
// If key doesn't exist: insert value 1
// If key exists: apply function (old + new)
// Atomic — no lost updates

Restrictions: no null keys or values (HashMap allows one null key). This is by design — null is ambiguous in concurrent context (does get() returning null mean "not found" or "value is null"?).

In our banking tutorial: we used ConcurrentHashMap in InMemoryAccountRepository for thread-safe account storage without external locking.

// Pair — two values:
val pair = "Alex" to 25          // creates Pair("Alex", 25)
val (name, age) = pair           // destructuring

// Triple — three values:
val triple = Triple("Alex", 25, "Almaty")
val (name, age, city) = triple

// The 'to' infix function creates Pairs — used in mapOf():
val map = mapOf("key1" to "value1", "key2" to "value2")
// "key1" to "value1" = Pair("key1", "value1")

Good uses — local, temporary, obvious meaning:

// Lock ordering in our banking tutorial:
val (first, second) = if (from.id < to.id) from to to else to to from
// Local variable. Meaning clear from context. Pair is fine.

// Partition returns Pair:
val (even, odd) = numbers.partition { it % 2 == 0 }
// stdlib function. Well-documented. Pair is expected.

// Map entries:
for ((key, value) in map) { ... }
// Destructuring Map.Entry. Standard pattern.

Bad uses — public API, domain model:

// BAD — unclear meaning:
fun getUser(): Pair<String, Int>?  // what is String? what is Int?
fun processOrder(): Triple<Boolean, String, Long>?  // what??

// GOOD — named data class:
data class UserInfo(val name: String, val age: Int)
fun getUser(): UserInfo?

data class OrderResult(val success: Boolean, val message: String, val orderId: Long)
fun processOrder(): OrderResult?
// Self-documenting. IDE shows property names. Can add methods later.

C# equivalent: ValueTuple<string, int> or named tuples (string Name, int Age). C# named tuples are better than Kotlin Pair because they have field names. Java: no built-in Pair (Map.Entry is the closest). Libraries: Apache Commons Pair, JavaFX Pair.

val map = mutableMapOf("a" to 1, "b" to 2)

// getOrDefault — read-only, doesn't modify map:
map.getOrDefault("c", 0)     // returns 0 (default)
println(map)                  // {a=1, b=2} — unchanged!

// getOrPut — modifies map if key absent:
map.getOrPut("c") { 0 }      // returns 0 AND stores it
println(map)                  // {a=1, b=2, c=0} — "c" added!

Practical use — counting/grouping pattern:

// Word frequency counter:
val freq = mutableMapOf<String, Int>()
for (word in words) {
    freq[word] = freq.getOrDefault(word, 0) + 1
}
// Or with getOrPut + merge:
// freq.merge(word, 1) { a, b -> a + b }

// Grouping into lists:
val byCity = mutableMapOf<String, MutableList<User>>()
for (user in users) {
    byCity.getOrPut(user.city) { mutableListOf() }.add(user)
}
// getOrPut creates the list on first encounter, then add() appends.
// Of course, Kotlin has users.groupBy { it.city } which does this in one call.

Java equivalents:

map.getOrDefault("c", 0)                    // same in Java 8+
map.computeIfAbsent("c", k -> new ArrayList<>())  // like getOrPut
map.putIfAbsent("c", 0)                     // simpler version

Thread safety note: on HashMap, getOrPut is NOT atomic. Two threads can both see key absent, both compute, one overwrites the other. For thread-safe version: ConcurrentHashMap.computeIfAbsent() which IS atomic.

Reference types in JVM (strongest to weakest):

Strong reference (default): val user = User(). As long as any strong reference exists, GC CANNOT collect the object. This is what you use 99% of the time.

Weak reference: val ref = WeakReference(user). GC CAN collect the object even while weak references exist. After collection, ref.get() returns null.

Soft reference: val ref = SoftReference(user). Similar to weak but GC only collects when memory is low. Better for caches — objects survive longer.

// WeakReference usage:
val strong = User("Alex")              // strong ref — keeps object alive
val weak = WeakReference(strong)       // weak ref — doesn't keep alive

println(weak.get()?.name)              // "Alex" — object still exists

// Remove strong reference:
// strong = null  (or goes out of scope)

System.gc()                            // GC collects the User
println(weak.get())                    // null! Object was collected.

WeakHashMap — cache that auto-evicts:

val cache = WeakHashMap<Key, ExpensiveObject>()
cache[key] = computeExpensiveObject(key)
// If 'key' has no other strong references, the entry is automatically
// removed from the map by GC. No manual eviction needed.
// Useful for: metadata caches, canonicalization maps

In practice: most applications use Caffeine cache (bounded by size/time) instead of WeakHashMap. WeakReference is used in frameworks: Spring's bean references, Android's Activity references (to avoid memory leaks when Activity is destroyed).

C#: WeakReference<T> — same concept. ConditionalWeakTable for metadata attached to objects without preventing GC.

Enum vs sealed class:

// Enum — all variants have same shape, singletons:
enum class Color { RED, GREEN, BLUE }
// Color.RED is always the same object. No per-instance data.

// Sealed class — each variant has different data:
sealed class TransferResult {
    data class Success(val txId: String, val amount: Money) : TransferResult()
    data class Failed(val reason: String, val code: Int) : TransferResult()
    data object SelfTransfer : TransferResult()
}
// Success has txId + amount. Failed has reason + code. SelfTransfer has nothing.
// Each Success is a different instance (different txId).

The killer feature — exhaustive when:

fun handle(result: TransferResult): String = when (result) {
    is TransferResult.Success -> "Transferred ${result.amount}"
    is TransferResult.Failed -> "Error: ${result.reason}"
    is TransferResult.SelfTransfer -> "Can't transfer to self"
    // No 'else' needed! Compiler knows all cases.
}

// Add a new subclass later:
data class CurrencyMismatch(val from: String, val to: String) : TransferResult()
// EVERY 'when' without handling CurrencyMismatch becomes a COMPILE ERROR.
// Compiler forces you to handle the new case everywhere. No forgotten branches.

This is an algebraic data type (ADT) — a fundamental concept from functional programming. The sealed class is a "sum type" — the value is ONE OF the known variants. Combined with data class (a "product type" — the value has ALL the listed fields), you get expressive, type-safe domain modeling.

Use for: API results (Success/Error/Loading), state machines (Idle/Loading/Ready/Error), domain events (Created/Updated/Deleted), command pattern, parser tokens.

C#: no direct equivalent until C# 11's "discriminated unions" (still not as clean). Usually modeled with abstract class + switch with pattern matching. Java: sealed classes added in Java 17 with permits clause — similar but more verbose.

// Array — JVM array, fixed size:
val arr = arrayOf(1, 2, 3)
arr[0] = 10        // OK — elements mutable
arr.add(4)          // DOESN'T EXIST — can't resize array
arr.size            // 3 — always 3

// List — Kotlin collection, rich API:
val list = listOf(1, 2, 3)
list[0] = 10        // COMPILE ERROR — listOf returns read-only List
list.filter { it > 1 }  // OK — rich collection API
list.map { it * 2 }     // OK — transformation API

// MutableList — resizable:
val mutable = mutableListOf(1, 2, 3)
mutable.add(4)      // OK — [1, 2, 3, 4]
mutable[0] = 10     // OK — [10, 2, 3, 4]

Specialized arrays for primitives — no boxing:

// IntArray = JVM int[] (primitive, no boxing):
val ints = IntArray(1000) { it * 2 }     // 1000 ints, ~4KB

// Array<Int> = JVM Integer[] (boxed objects):
val boxed = Array(1000) { it * 2 }       // 1000 Integer objects, ~16KB
// Each Integer = 16 bytes (object header + int value)
// IntArray is 4x more memory-efficient

// Also: LongArray, DoubleArray, ByteArray, BooleanArray, etc.

When to use Array:

Performance-critical inner loops with primitives (IntArray avoids boxing). JVM interop — Java methods that take int[] need IntArray. main(args: Array<String>) — by convention.

When to use List (almost always):

Everything else. Better API (filter, map, groupBy). Type-safe immutability (List vs MutableList). Covariant — List<Cat> assignable to List<Animal> (Array is NOT covariant in Kotlin for safety).

data class User(val id: String, val city: String, val name: String)
val users = listOf(
    User("1", "London", "Alex"),
    User("2", "London", "Maria"),
    User("3", "Berlin", "Hans")
)

// groupBy — one key, MANY values:
val byCity: Map<String, List<User>> = users.groupBy { it.city }
// { "London": [Alex, Maria], "Berlin": [Hans] }
// Multiple users per city — List as value

// associateBy — one key, ONE value:
val byId: Map<String, User> = users.associateBy { it.id }
// { "1": Alex, "2": Maria, "3": Hans }
// One user per ID — single value (if duplicate key: last wins!)

// associate — custom key AND value:
val idToName: Map<String, String> = users.associate { it.id to it.name }
// { "1": "Alex", "2": "Maria", "3": "Hans" }
// Transform both key and value

Common mistake — using associateBy when groupBy is needed:

// WRONG — if multiple users in same city, only last one kept:
val byCity = users.associateBy { it.city }
// { "London": Maria, "Berlin": Hans }  — Alex LOST!

// RIGHT — groupBy keeps all:
val byCity = users.groupBy { it.city }
// { "London": [Alex, Maria], "Berlin": [Hans] }

Java equivalents:

// groupBy:
users.stream().collect(Collectors.groupingBy(User::getCity))

// associateBy:
users.stream().collect(Collectors.toMap(User::getId, u -> u))

// Kotlin is much more concise — no stream(), no Collectors.

C# equivalents: groupBy = .GroupBy(u => u.City). associateBy = .ToDictionary(u => u.Id). associate = .ToDictionary(u => u.Id, u => u.Name).

// Double — binary floating-point, APPROXIMATION:
println(0.1 + 0.2)          // 0.30000000000000004
println(1.0 - 0.9)          // 0.09999999999999998
println(0.1 + 0.2 == 0.3)   // false!

// BigDecimal — exact decimal arithmetic:
val a = BigDecimal("0.1")
val b = BigDecimal("0.2")
println(a + b)               // 0.3 (exact)
println(a + b == BigDecimal("0.3"))  // true

Why Double is approximate: 0.1 in binary is like 1/3 in decimal — infinite repeating. Computer stores a finite approximation. Each operation compounds the error.

BigDecimal gotchas in Kotlin:

// WRONG — creates from Double, already has error:
val bad = BigDecimal(0.1)    // 0.1000000000000000055511151231257827021181583404541015625

// RIGHT — creates from String, exact:
val good = BigDecimal("0.1") // 0.1 (exact)

// WRONG — using == for comparison:
BigDecimal("2.0") == BigDecimal("2.00")  // false! Different scale.

// RIGHT — using compareTo:
BigDecimal("2.0").compareTo(BigDecimal("2.00")) == 0  // true
// In Kotlin: BigDecimal("2.0") >= BigDecimal("2.00")  // true (uses compareTo)

In our banking tutorial: Money uses BigDecimal for amount. operator fun plus/minus use BigDecimal arithmetic. No floating-point errors in any calculation.

Alternative: represent money as Long cents (100 = $1.00). Simpler, faster, no precision issues. Used internally by Stripe, many payment processors. But harder to work with for multi-currency (different decimal places: JPY has 0, BHD has 3).

C#: decimal type is built-in exact decimal — no need for a special class. This is one area where C# is more ergonomic than Java/Kotlin.

Decision tree for choosing data structures:

"I need to look up values by a key" → Map. Which Map? HashMap (no order, fastest), LinkedHashMap (insertion order), TreeMap (sorted keys), ConcurrentHashMap (thread-safe).

"I need to check if an element exists" → Set. HashSet (O(1) contains), TreeSet (sorted, range queries), LinkedHashSet (insertion order).

"I need an ordered sequence of elements" → List. ArrayList (random access, iteration), LinkedList (almost never — ArrayDeque for queue/stack).

"I need elements processed by priority" → PriorityQueue. Min-heap by default. Custom Comparator for max-heap or complex ordering.

"I need a FIFO queue" → ArrayDeque (single-threaded), Channel (coroutines), BlockingQueue (threads).

"I need thread safety" → ConcurrentHashMap (map), CopyOnWriteArrayList (rare writes, frequent reads), Channel/Mutex (coroutines).

Real-world banking examples:

Accounts by ID          → HashMap<AccountId, Account>
Active sessions         → ConcurrentHashMap (multi-threaded)
Transaction history     → ArrayList (ordered by time, iterate sequentially)
Unique transaction IDs  → HashSet (deduplication check)
Sorted leaderboard      → TreeMap<Score, User>
Transfer queue          → Channel (coroutines) or PriorityQueue (by amount)
Currency exchange rates → Map<String, BigDecimal> (USD → rate)
Recent N transactions   → ArrayDeque as circular buffer (fixed size)

For the interview: don't just name the data structure. Explain WHY: "I'd use HashMap because the primary operation is lookup by account ID, which is O(1). If we needed sorted iteration by balance, I'd switch to TreeMap, accepting O(log n) per operation for sorted order."