Ten Coding Interview Questions in Kotlin, Part Three: Union-Find, Dijkstra, KMP, and the Bit Operators Kotlin Does Not Have

Parts one and two covered twenty patterns. These ten are the ones left, and they skew toward the second or third problem in a senior loop: the interviewer has confirmed you can write a loop and wants to see whether you know the algorithms with names. Union-find, Dijkstra, and KMP are the three most likely to be asked by name. The rest are the shapes that show up when a familiar problem gets a constraint that breaks the familiar solution.

Every snippet was compiled and run against a test harness before publishing, as before. The Kotlin gotchas are a third, new set, and this one is heavier on the language than the earlier two, because bit manipulation and string handling are where Kotlin diverges from Java most visibly.

The Question

The forms this round takes:

• “Count the connected components.” “Are these two nodes connected?” “Detect the redundant edge.” (union-find)
• “Every number appears twice except one. Find it in O(1) space.” (bit manipulation)
• “Longest common subsequence.” “Edit distance.” (two-dimensional dynamic programming)
• “How many meeting rooms do we need?” (interval scheduling with a heap)
• “Implement indexOf.” Then: “now in linear time.” (KMP)
• “Shortest path with weighted edges.” (Dijkstra)
• “Minimum speed to finish in time.” “Smallest capacity to ship in D days.” (binary search on the answer)
• “Longest increasing subsequence, faster than quadratic.” (patience sorting)
• “Serialize and deserialize a binary tree.” (tree encoding)
• “Median of a stream.” (two heaps)

What They Are Really Checking

1. Do you know the named algorithms? Union-find, Dijkstra, and KMP are expected knowledge at the senior level. Not deriving them on the spot; knowing them.
2. Can you recognize when a familiar tool needs a twist? Binary search over an answer space instead of an index. A heap keyed on end times instead of values. Two heaps instead of one.
3. Do you know the complexity story, including the amortized one? Union-find is “nearly constant” for a specific reason. Dijkstra is O((V + E) log V) with a specific heap discipline. Say the reason.
4. Can you write bit manipulation in this language? Kotlin has no ^, &, or | on integers. Candidates who write them anyway have not written Kotlin.
5. Do you handle the sentinel and the empty case? Serialization needs a null marker. Median needs the odd and even case. KMP needs the empty pattern.

The Gotchas

A third set of Kotlin traps. The twenty from the earlier posts still apply.

Gotcha 1: Bitwise operators are named functions. and, or, xor, shl, shr, ushr, and inv(). There is no ^, &, |, <<, >>, or >>> on integers. Writing a ^ b is a compile error, and writing it on a whiteboard tells the interviewer which language you actually think in.

Gotcha 2: shr versus ushr on negatives. shr is an arithmetic shift and preserves the sign bit; ushr is logical. A bit-counting loop written with shr on a negative Int never reaches zero. Use ushr, or use the n and (n - 1) trick, which does not shift at all.

Gotcha 3: Shift counts wrap and 1 shl 31 is negative. Shift amounts on Int are taken modulo 32, so 1 shl 32 is 1, not zero. And bit 31 is the sign bit. Masks above bit 30 want 1L shl n.

Gotcha 4: Ceiling division that overflows. (a + b - 1) / b overflows when a is near Int.MAX_VALUE. (a - 1) / b + 1 gives the same answer for a >= 1 and cannot overflow.

Gotcha 5: One-based DP tables. A two-dimensional table over two strings is Array(m + 1) { IntArray(n + 1) }, and the strings are indexed with i - 1 and j - 1. Mixing zero-based and one-based in the same loop is the most common bug in this class of problem.

Gotcha 6: Kotlin’s split is literal; Java’s is a regex. "a.b".split(".") in Kotlin gives ["a", "b"]; in Java it gives an empty array, because . is a regex. Coming the other way, Kotlin will not split on a regex unless you pass a Regex. And in both languages a trailing delimiter yields an empty final token, which a tokenizer has to expect.

Gotcha 7: binarySearch returns a negative insertion point. When the element is absent, the result is -(insertionPoint) - 1. Decode it with -(pos + 1). Forgetting the - 1 puts elements one slot off.

Gotcha 8: max() changed meaning across versions. In Kotlin 1.4 through 1.6 max() on a collection was deprecated and returned a nullable; from 1.7 it returns non-null and throws on empty. maxOrNull() has meant the same thing on every version since 1.4. Use it when you do not know the interviewer’s compiler.

Gotcha 9: poll() and peek() return null on an empty queue. They are Java platform types, so Kotlin will not force you to handle the null, and the exception comes later and elsewhere. Check isNotEmpty() before you rely on them.

Gotcha 10: Nested it shadows silently. Two nested lambdas both using it compile, and the inner one hides the outer. Name the parameters the moment you nest.

How to Answer

Same discipline: name the pattern, say the invariant, list the edges, write it, state the complexity and the alternative.

1. Number of Connected Components (union-find)

class UnionFind(n: Int) {
    private val parent = IntArray(n) { it }
    private val rank = IntArray(n)
    var components = n
        private set

    fun find(x: Int): Int {
        var root = x
        while (parent[root] != root) root = parent[root]
        var cur = x                                   // path compression: point everything at the root
        while (parent[cur] != root) { val next = parent[cur]; parent[cur] = root; cur = next }
        return root
    }

    fun union(a: Int, b: Int): Boolean {
        val ra = find(a)
        val rb = find(b)
        if (ra == rb) return false                    // already connected: this edge is redundant
        if (rank[ra] < rank[rb]) parent[ra] = rb
        else if (rank[ra] > rank[rb]) parent[rb] = ra
        else { parent[rb] = ra; rank[ra]++ }
        components--
        return true
    }
}

fun countComponents(n: Int, edges: Array<IntArray>): Int {
    val uf = UnionFind(n)
    for (e in edges) uf.union(e[0], e[1])
    return uf.components
}

Near-constant amortized time per operation with both path compression and union by rank; O(n) space.

• union returning false is the answer to “find the redundant edge” and “does this edge create a cycle” for free.
• Path compression alone or union by rank alone is still O(log n) amortized. Both together is the inverse Ackermann bound, and saying “inverse Ackermann” is the senior tell.
• The alternative is breadth-first search from every unvisited node, O(V + E), which is fine when all edges are known up front and wrong when edges arrive over time.

2. Single Number and Bit Counting (bit manipulation)

fun singleNumber(nums: IntArray): Int {
    var acc = 0
    for (n in nums) acc = acc xor n                   // pairs cancel; the singleton survives
    return acc
}

fun countSetBits(x: Int): Int {
    var n = x
    var count = 0
    while (n != 0) { n = n and (n - 1); count++ }    // clears the lowest set bit each step
    return count
}

O(n) and O(bits set), both O(1) space.

• xor is commutative and associative, and a xor a == 0. Say those three facts; they are the proof.
• n and (n - 1) works on negatives, where a shr loop does not. Gotcha 2.
• The follow-ups are “every number appears three times except one,” which needs per-bit counting modulo 3, and “two numbers appear once,” which partitions on a differing bit.

3. Longest Common Subsequence (two-dimensional DP)

fun longestCommonSubsequence(a: String, b: String): Int {
    val dp = Array(a.length + 1) { IntArray(b.length + 1) }
    for (i in 1..a.length) for (j in 1..b.length) {
        dp[i][j] = if (a[i - 1] == b[j - 1]) dp[i - 1][j - 1] + 1
                   else maxOf(dp[i - 1][j], dp[i][j - 1])
    }
    return dp[a.length][b.length]
}

O(m × n) time and space; O(min(m, n)) space with two rolling rows.

• The recurrence in one sentence: if the last characters match, extend the diagonal; otherwise take the better of dropping one character from either string.
• The extra row and column of zeros are the base case. Gotcha 5.
• Edit distance is the same table with a third option and a cost of one for substitution. Say that when they ask “what else is this shape.”

4. Meeting Rooms II (interval scheduling with a heap)

import java.util.PriorityQueue

fun minMeetingRooms(intervals: Array<IntArray>): Int {
    if (intervals.isEmpty()) return 0
    intervals.sortBy { it[0] }
    val ends = PriorityQueue<Int>()                   // min-heap of end times: one entry per occupied room
    for (m in intervals) {
        if (ends.isNotEmpty() && ends.peek() <= m[0]) ends.poll()   // the earliest-ending room is free again
        ends.add(m[1])
    }
    return ends.size
}

O(n log n) time, O(n) space.

• Sort by start; the heap holds end times. Reusing a room is popping the earliest end if it is at or before the new start.
• <= means a meeting can start the minute another ends. Ask whether that is the rule.
• The heap’s size at the end is the peak concurrency, because a room is never removed without being replaced. The alternative is the two-pointer sweep over sorted starts and sorted ends, same complexity, no heap.

5. Substring Search (KMP)

fun indexOf(text: String, pattern: String): Int {
    if (pattern.isEmpty()) return 0
    val lps = IntArray(pattern.length)                // longest proper prefix of pattern[0..i] that is also a suffix
    var len = 0
    var i = 1
    while (i < pattern.length) {
        if (pattern[i] == pattern[len]) { len++; lps[i] = len; i++ }
        else if (len > 0) len = lps[len - 1]
        else { lps[i] = 0; i++ }
    }
    var t = 0
    var p = 0
    while (t < text.length) {
        if (text[t] == pattern[p]) {
            t++; p++
            if (p == pattern.length) return t - p
        } else if (p > 0) p = lps[p - 1]
        else t++
    }
    return -1
}

O(n + m) time, O(m) space, versus O(n × m) for the naive scan.

• The invariant: lps[i] is the length of the longest proper prefix of the pattern that is also a suffix of pattern[0..i]. On a mismatch, the pattern slides to that prefix instead of restarting.
• The naive scan is the right answer until the interviewer says “linear.” Write it first if they have not; it is ten lines and it passes.
• The empty pattern returns 0 by convention. Say the convention.

6. Network Delay Time (Dijkstra)

import java.util.PriorityQueue

fun networkDelayTime(times: Array<IntArray>, n: Int, source: Int): Int {
    val adj = Array(n + 1) { ArrayList<IntArray>() }  // node -> list of [neighbor, weight]
    for (t in times) adj[t[0]].add(intArrayOf(t[1], t[2]))
    val dist = IntArray(n + 1) { Int.MAX_VALUE }
    dist[source] = 0
    val heap = PriorityQueue<IntArray>(compareBy { it[1] })   // [node, distance]
    heap.add(intArrayOf(source, 0))
    while (heap.isNotEmpty()) {
        val (node, d) = heap.poll()
        if (d > dist[node]) continue                  // stale entry: a shorter path was already settled
        for (edge in adj[node]) {
            val next = edge[0]
            val nd = d + edge[1]
            if (nd < dist[next]) { dist[next] = nd; heap.add(intArrayOf(next, nd)) }
        }
    }
    var best = 0
    for (v in 1..n) { if (dist[v] == Int.MAX_VALUE) return -1; best = maxOf(best, dist[v]) }
    return best
}

O((V + E) log V) time with a binary heap, O(V + E) space.

• The stale-entry check is the whole trick with a heap that cannot decrease a key: push duplicates, skip the ones that are already beaten.
• Dijkstra needs non-negative weights. Say it, and say Bellman-Ford for negative ones.
• IntArray in the heap instead of Pair avoids boxing. Part two’s gotcha 7.

7. Koko Eating Bananas (binary search on the answer)

fun minEatingSpeed(piles: IntArray, hours: Int): Int {
    fun hoursNeeded(speed: Int): Long {
        var total = 0L
        for (p in piles) total += (p - 1) / speed + 1  // ceiling division without overflow
        return total
    }
    var lo = 1
    var hi = piles.maxOrNull() ?: 1
    while (lo < hi) {
        val mid = lo + (hi - lo) / 2
        if (hoursNeeded(mid) <= hours) hi = mid else lo = mid + 1
    }
    return lo
}

O(n log M) where M is the largest pile.

• The insight: the answer is monotonic. If speed k works, every faster speed works. That is what makes the answer space binary-searchable.
• lo < hi with hi = mid finds the leftmost feasible value. This is a different loop shape from part one’s index search, and mixing them up is the bug.
• The accumulator is Long and the ceiling division is overflow-safe. Gotchas 4 and part two’s 8.
• Same shape: capacity to ship packages in D days, minimum days to make M bouquets, split array largest sum.

8. Longest Increasing Subsequence (patience sorting)

fun lengthOfLIS(nums: IntArray): Int {
    val tails = IntArray(nums.size)                   // tails[k] = smallest tail of any increasing subsequence of length k + 1
    var size = 0
    for (n in nums) {
        var pos = tails.binarySearch(n, 0, size)
        if (pos < 0) pos = -(pos + 1)                 // insertion point
        tails[pos] = n
        if (pos == size) size++
    }
    return size
}

O(n log n) time, O(n) space, versus O(n²) for the plain DP.

• tails is sorted by construction, which is why binary search applies. Say the invariant in the comment out loud.
• binarySearch finding an equal element returns its index, so duplicates replace rather than extend, which is what “strictly increasing” needs. For non-strict, search for n + 1.
• tails is not the subsequence. Reconstructing it needs a parent array. Interviewers ask.

9. Serialize and Deserialize a Binary Tree (tree encoding)

class TreeNode(var value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun serialize(root: TreeNode?): String {
    val sb = StringBuilder()
    fun go(node: TreeNode?) {
        if (node == null) { sb.append("#,"); return }
        sb.append(node.value).append(',')
        go(node.left)
        go(node.right)
    }
    go(root)
    return sb.toString()
}

fun deserialize(data: String): TreeNode? {
    val tokens = data.split(',')                      // literal delimiter; the trailing comma yields an empty last token we never read
    var i = 0
    fun build(): TreeNode? {
        val tok = tokens[i++]
        if (tok == "#") return null
        val node = TreeNode(tok.toInt())
        node.left = build()
        node.right = build()
        return node
    }
    return build()
}

O(n) both ways.

• Preorder with an explicit null marker is enough to rebuild the tree uniquely. Without the marker, preorder alone is ambiguous.
• StringBuilder, not +. Part two’s gotcha 10.
• The local fun build() closes over var i. Kotlin allows it; a val lambda would not compile. Part two’s gotcha 6.
• The follow-up is “do it iteratively,” which is level order with a queue and the same null marker.

10. Median From a Data Stream (two heaps)

import java.util.PriorityQueue

class MedianFinder {
    private val low = PriorityQueue<Int>(compareByDescending { it })   // max-heap: the smaller half
    private val high = PriorityQueue<Int>()                             // min-heap: the larger half

    fun addNum(num: Int) {
        low.add(num)
        high.add(low.poll())                           // route through low so every low <= every high
        if (high.size > low.size) low.add(high.poll()) // keep low the same size or one larger
    }

    fun findMedian(): Double =
        if (low.size > high.size) low.peek().toDouble()
        else (low.peek() + high.peek()) / 2.0
}

O(log n) per insert, O(1) per median, O(n) space.

• The invariant, in two halves: every element in low is at most every element in high, and low is the same size as high or one larger. Both lines of addNum exist to restore those two facts.
• / 2.0, not / 2. Integer division is the bug in the even case.
• The follow-up is a sliding-window median, which needs lazy deletion or an ordered multiset, and saying “that is a different data structure” is correct.

The patterns, in one table

Problem	Pattern	Time	Space	The one thing to say
Connected Components	Union-find	~O(α(n)) per op	O(n)	Both compression and rank; union returns false on a redundant edge
Single Number	XOR	O(n)	O(1)	Pairs cancel; n and (n - 1) clears a bit
Longest Common Subsequence	2D DP	O(mn)	O(mn)	One-based table; extend the diagonal on a match
Meeting Rooms II	Heap of end times	O(n log n)	O(n)	Sort by start; pop the earliest end if free
Substring Search	KMP	O(n + m)	O(m)	The failure table slides, never restarts
Network Delay	Dijkstra	O((V + E) log V)	O(V + E)	Skip stale heap entries; non-negative weights only
Koko	Binary search on the answer	O(n log M)	O(1)	Monotonic feasibility; lo < hi, hi = mid
LIS	Patience sorting	O(n log n)	O(n)	tails is sorted, not the subsequence
Serialize a Tree	Preorder with sentinels	O(n)	O(n)	The null marker makes it unique
Stream Median	Two heaps	O(log n) insert	O(n)	Route through low; / 2.0

Thirty patterns across three posts. That is the coding round for a senior loop, and a candidate who can do all thirty in their language of choice is not going to be filtered out on the coding screen.

Follow-Up Questions to Expect

• “Why inverse Ackermann?” Because with both optimizations the amortized cost per operation is bounded by a function that grows slower than anything you will ever measure. Say that you know the name of the bound and that for interview purposes it is constant.
• “Dijkstra with negative edges?” It breaks. Bellman-Ford handles them in O(VE), and a negative cycle means no answer.
• “Every number appears three times except one.” Count each bit position modulo 3. The bits that are 1 mod 3 belong to the singleton.
• “Reconstruct the LIS, not just its length.” Keep a parent index for each element and the index of the tail at each length, then walk back.
• “Serialize with less space.” Preorder plus inorder without markers, for trees with unique values; or a compact binary encoding. Say the trade: markers cost bytes, no markers cost uniqueness assumptions.
• “Median over a sliding window.” An ordered multiset, or two heaps with lazy deletion. Both are a different problem class from the stream version.

Key Takeaways

• Union-find, Dijkstra, and KMP are expected by name. Know them cold, and know their one-line invariants.
• Binary search on the answer works whenever feasibility is monotonic. Different loop shape from index search.
• Two-dimensional DP tables are one-based; the strings are indexed with i - 1.
• Kotlin bit operators are and, or, xor, shl, shr, ushr, inv(). ushr for negatives. 1L shl n above bit 30.
• split is literal in Kotlin and regex in Java. Trailing delimiters produce an empty token.
• (a - 1) / b + 1 for ceiling division; maxOrNull() for version stability; poll() returns null on empty.
• Thirty patterns, three posts. That is the whole coding screen.

Further Reading

• Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, for union-find (chapter 21), Dijkstra (chapter 24), and KMP (chapter 32)
• Sedgewick and Wayne, Algorithms, chapter 1.5 for the union-find case study, which is the best short treatment
• Kotlin documentation, Bitwise and bit shift operations and split
• Parts one and two, and the find the bug post that drills the gotchas