Post

Ten More Coding Interview Questions in Kotlin: Monotonic Stacks, Quickselect, Tries, and the Traps Around Them

Part two of the Kotlin coding round: ten problems covering ten patterns the first post did not, each with an idiomatic solution, its complexity, the per-problem mistake interviewers listen for, and a second set of Kotlin-specific traps, including the JDK 21 removeLast clash.

Posted
By Michael Masters & Claude
16 min read
Ten More Coding Interview Questions in Kotlin: Monotonic Stacks, Quickselect, Tries, and the Traps Around Them

The first ten covered hash maps, stacks, sort-and-sweep, sliding windows, grid search, cache design, heaps, binary search, linked lists, and one-dimensional dynamic programming. That is most of a senior coding round. This post covers the rest: the patterns that appear when the interviewer reaches for a harder second problem, or when the first problem’s follow-up changes shape.

The ten here are canonical keys, prefix and suffix scans, Kadane’s algorithm, monotonic stacks, two pointers, bounded tree recursion, topological sort, quickselect, backtracking, and the trie. As before, every snippet was compiled and run against a test harness before publishing. The Kotlin-specific gotchas are a new set; the first post’s ten still apply.

The Question

The second coding problem in a senior loop is usually chosen to test a different axis than the first. If the first was a clean array problem, the second is a tree or a graph. If the first was iteration, the second is recursion with state. If the first was “write it,” the second is “now do it in O(1) extra space” or “now do it for a stream.” The problems below are the ones that show up in that slot.

What They Are Really Checking

  1. Can you handle state that is not a flat array? Trees, graphs, and tries have pointers, nulls, and recursion. The interviewer is watching for null handling and for whether you know when recursion is unsafe.
  2. Do you know the invariant? Monotonic stacks, two pointers, and Kadane each depend on one sentence being true at every step. Candidates who can say the sentence write correct code. Candidates who cannot write code that passes the example and fails the edge.
  3. Do you know the trade between expected and worst case? Quickselect is O(n) expected and O(n²) worst. Saying that unprompted, and saying what a random pivot does about it, is a senior tell.
  4. Do you copy what needs copying? Backtracking’s most common bug is adding the same mutable list to the results. It is a Kotlin bug and a Java bug and a Python bug, and it is the bug interviewers see most.
  5. Do you know what is in your language’s standard library and what is Java’s? The second set of Kotlin traps below are the ones that show up in exactly these problems.

The Gotchas

Kotlin-specific traps that recur across these ten. The first post’s set is still in force; these are new.

Gotcha 1: Char.toInt() is deprecated. Modern Kotlin wants c.code. But c - 'a' has always returned an Int and works on every version, so it is the safer thing to write on a whiteboard when you do not know which compiler the interviewer’s environment runs.

Gotcha 2: Sorting a string is not one call. s.toCharArray().sorted() returns a List<Char>, and you still need joinToString("") to get a String back. It allocates three times. For anagram keys, a 26-slot count array is both cheaper and less error-prone.

Gotcha 3: MutableList.removeLast() collides with JDK 21. Java 21 added removeLast() to java.util.List. Kotlin code that calls removeLast() on a MutableList can resolve to the Java method at compile time and throw NoSuchMethodError on an older runtime. removeAt(lastIndex) has no such problem. kotlin.collections.ArrayDeque.removeLast() is a member and is fine.

Gotcha 4: Adding the live path to the results. In backtracking, result.add(path) adds a reference. Every later mutation of path changes every “result.” result.add(ArrayList(path)) is the fix, and forgetting it produces a list of identical empty lists that passes no test.

Gotcha 5: The shared-row bug in 2D arrays. val row = IntArray(m); val grid = Array(n) { row } gives you n references to one row. Array(n) { IntArray(m) } gives you n rows. The lambda runs once per element, which is the point.

Gotcha 6: A local recursive lambda does not compile. val dfs = { ... dfs(...) ... } fails because the lambda references itself in its own initializer. Use a local fun dfs(...) instead, which is also faster because it does not allocate a function object.

Gotcha 7: Pair and Triple in hot loops. nums.map { it[0] to it[1] } allocates a Pair per element and boxes both ints. In a graph with a million edges, that is a million objects. Read the array directly, or encode into an Int as the grid problem in part one did.

Gotcha 8: var sum = 0 infers Int. Kadane, prefix sums, and products overflow silently. var sum = 0L is one character and it is the character interviewers look for when the bounds are large.

Gotcha 9: Skewed trees are linked lists. Recursion on a tree is O(height) deep, and a degenerate tree’s height is n. If the interviewer says “the tree may be unbalanced,” say that you would switch to an explicit stack.

Gotcha 10: Building strings with + in a loop. Each + copies. Serializing a tree or a trie by concatenation is O(n²). StringBuilder, or joinToString, or buildString { } on newer compilers.

How to Answer

Same discipline as part one: name the pattern, say the invariant, list the edge cases, write the code, state the complexity, name the alternative.

1. Group Anagrams (canonical key)

1
2
3
4
5
6
7
8
9
10

fun groupAnagrams(strs: Array<String>): List<List<String>> {
    val groups = HashMap<String, MutableList<String>>()
    for (s in strs) {
        val counts = IntArray(26)
        for (c in s) counts[c - 'a']++
        val key = counts.joinToString(",")
        groups.getOrPut(key) { ArrayList() }.add(s)
    }
    return groups.values.toList()
}

O(n × k) time for n words of length k, versus O(n × k log k) for a sorted-string key. O(n × k) space.

  • The comma in joinToString(",") matters. Without it, counts 1,11 and 11,1 produce the same key.
  • The count key assumes lowercase ASCII. Ask. For Unicode, the sorted-string key or a HashMap<Char, Int> is the fallback.
  • getOrPut is the idiom; computeIfAbsent is Java’s and works too.
  • The order of groups and within groups is unspecified. Say so.

2. Product of Array Except Self (prefix and suffix)

1
2
3
4
5
6
7
8
9

fun productExceptSelf(nums: IntArray): IntArray {
    val n = nums.size
    val out = IntArray(n)
    var prefix = 1
    for (i in 0 until n) { out[i] = prefix; prefix *= nums[i] }
    var suffix = 1
    for (i in n - 1 downTo 0) { out[i] *= suffix; suffix *= nums[i] }
    return out
}

O(n) time, O(1) extra space beyond the output.

  • The division approach fails on zeros, and the problem usually forbids it anyway. The two-pass version is the answer.
  • Products overflow fast. Say Long if the interviewer’s bounds permit large values.
  • downTo is inclusive on both ends, unlike until.

3. Maximum Subarray (Kadane)

1
2
3
4
5
6
7
8
9

fun maxSubArray(nums: IntArray): Int {
    var best = nums[0]
    var cur = nums[0]
    for (i in 1 until nums.size) {
        cur = maxOf(nums[i], cur + nums[i])
        best = maxOf(best, cur)
    }
    return best
}

O(n) time, O(1) space. The invariant: cur is the best sum of a subarray ending at i.

  • Initializing best = 0 returns the wrong answer for an all-negative array. Start from nums[0].
  • maxOf(nums[i], cur + nums[i]) is “extend or restart.” Say those words.
  • If they want the indices, track where cur last restarted.
  • Sums over large ranges want Long.

4. Daily Temperatures (monotonic stack)

Days until a warmer temperature, or 0.

1
2
3
4
5
6
7
8
9
10
11
12

fun dailyTemperatures(temps: IntArray): IntArray {
    val out = IntArray(temps.size)
    val stack = ArrayDeque<Int>()            // indices; temperatures decrease from bottom to top
    for (i in temps.indices) {
        while (stack.isNotEmpty() && temps[stack.last()] < temps[i]) {
            val j = stack.removeLast()
            out[j] = i - j
        }
        stack.addLast(i)
    }
    return out
}

O(n) time amortized, because each index is pushed and popped at most once. O(n) space.

  • Push indices, not temperatures. You need the distance.
  • Strict <. An equal temperature is not warmer.
  • The invariant, said aloud: the stack holds indices whose answer is not yet known, in decreasing order of temperature.
  • out defaults to 0, which is the right answer for days that never get warmer.

5. Trapping Rain Water (two pointers)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

fun trap(height: IntArray): Int {
    var l = 0
    var r = height.size - 1
    var lMax = 0
    var rMax = 0
    var water = 0
    while (l < r) {
        if (height[l] < height[r]) {
            lMax = maxOf(lMax, height[l]); water += lMax - height[l]; l++
        } else {
            rMax = maxOf(rMax, height[r]); water += rMax - height[r]; r--
        }
    }
    return water
}

O(n) time, O(1) space, versus O(n) space for the prefix-max and suffix-max array version.

  • The invariant: move the side with the shorter wall, because the water above it is bounded by that side’s running max regardless of what is further in. If you cannot say this, write the two-array version instead; it is easier to defend.
  • Update the running max before computing the water at that index.
  • Empty and single-element arrays return 0 without special-casing, because the loop does not run.

6. Validate a Binary Search Tree (bounded recursion)

1
2
3
4
5
6
7
8
9
10

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

fun isValidBST(root: TreeNode?): Boolean {
    fun valid(node: TreeNode?, lo: Long, hi: Long): Boolean {
        if (node == null) return true
        if (node.value <= lo || node.value >= hi) return false
        return valid(node.left, lo, node.value.toLong()) && valid(node.right, node.value.toLong(), hi)
    }
    return valid(root, Long.MIN_VALUE, Long.MAX_VALUE)
}

O(n) time, O(height) stack.

  • The classic wrong answer checks each node against its parent only. A node can be greater than its parent and still violate a grandparent’s bound. Carry the bounds.
  • Long bounds so that a tree containing Int.MIN_VALUE or Int.MAX_VALUE validates correctly. This is a real test case on every platform.
  • Strict inequalities reject duplicates. Ask whether duplicates are allowed and on which side.
  • The alternative is an in-order traversal checking that values strictly increase. Same complexity; some interviewers prefer it.

7. Course Schedule (topological sort)

Can all courses be taken given prerequisite pairs [course, prereq]?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
    val adj = Array(numCourses) { ArrayList<Int>() }
    val indegree = IntArray(numCourses)
    for (p in prerequisites) {
        val course = p[0]
        val prereq = p[1]
        adj[prereq].add(course)
        indegree[course]++
    }
    val queue = ArrayDeque<Int>()
    for (i in 0 until numCourses) if (indegree[i] == 0) queue.addLast(i)
    var taken = 0
    while (queue.isNotEmpty()) {
        val c = queue.removeFirst()
        taken++
        for (next in adj[c]) if (--indegree[next] == 0) queue.addLast(next)
    }
    return taken == numCourses
}

O(V + E) time and space. This is Kahn’s algorithm.

  • Edge direction. The prerequisite points to the course, not the other way. Draw one edge before coding.
  • taken == numCourses is the cycle check. If a cycle exists, its nodes never reach indegree zero and are never taken.
  • Array(numCourses) { ArrayList<Int>() }, not a shared list. Gotcha 5.
  • The depth-first alternative with white, gray, and black coloring finds the cycle itself, which the follow-up “return the order” or “which courses are in the cycle” sometimes wants.

8. Kth Largest Element (quickselect)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

fun findKthLargest(nums: IntArray, k: Int): Int {
    val target = nums.size - k                  // index in ascending order
    var lo = 0
    var hi = nums.size - 1
    while (lo < hi) {
        val pivotIndex = kotlin.random.Random.nextInt(lo, hi + 1)
        val p = partition(nums, lo, hi, pivotIndex)
        when {
            p == target -> return nums[p]
            p < target -> lo = p + 1
            else -> hi = p - 1
        }
    }
    return nums[lo]
}

private fun partition(a: IntArray, lo: Int, hi: Int, pivotIndex: Int): Int {
    val pivot = a[pivotIndex]
    swap(a, pivotIndex, hi)
    var store = lo
    for (i in lo until hi) if (a[i] < pivot) { swap(a, store, i); store++ }
    swap(a, store, hi)
    return store
}

private fun swap(a: IntArray, i: Int, j: Int) { val t = a[i]; a[i] = a[j]; a[j] = t }

O(n) expected time, O(n²) worst case, O(1) space.

  • “Kth largest” is index n - k in ascending order. Off-by-one here is the most common bug.
  • A random pivot is what makes the expected case O(n). A fixed pivot on sorted input is O(n²), and interviewers will ask.
  • This mutates the input. Say so.
  • The heap version is O(n log k) and is the right answer when the data is a stream. Know which the interviewer wants by asking whether the array fits in memory.

9. Subsets (backtracking)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

fun subsets(nums: IntArray): List<List<Int>> {
    val result = ArrayList<List<Int>>()
    val path = ArrayList<Int>()
    fun backtrack(start: Int) {
        result.add(ArrayList(path))            // copy, or every result is the same list
        for (i in start until nums.size) {
            path.add(nums[i])
            backtrack(i + 1)
            path.removeAt(path.lastIndex)
        }
    }
    backtrack(0)
    return result
}

O(n × 2ⁿ) time and space, because the output has 2ⁿ subsets of average length n/2. The complexity is bounded by the output, and saying so shows you know the question is about generation, not search.

  • The copy. Gotcha 4. This is the bug.
  • start is what makes these subsets and not permutations. Each element is considered once, in order.
  • Duplicates in the input need a sort and a skip of equal neighbors at the same depth.
  • The bitmask version iterates 0 until (1 shl n) and is the one to mention as the alternative.

10. Trie (design)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Trie {
    private class Node {
        val children = arrayOfNulls<Node>(26)
        var terminal = false
    }
    private val root = Node()

    fun insert(word: String) {
        var node = root
        for (c in word) {
            val i = c - 'a'
            node = node.children[i] ?: Node().also { node.children[i] = it }
        }
        node.terminal = true
    }

    fun search(word: String): Boolean = find(word)?.terminal == true
    fun startsWith(prefix: String): Boolean = find(prefix) != null

    private fun find(s: String): Node? {
        var node = root
        for (c in s) node = node.children[c - 'a'] ?: return null
        return node
    }
}

O(k) for each operation on a word of length k. Space is O(total characters × 26 references) with the array layout.

  • The terminal flag. Without it, search("app") returns true after inserting only "apple". This is the bug interviewers plant.
  • arrayOfNulls<Node>(26) gives Array<Node?>. Twenty-six references per node is the fast layout for lowercase ASCII; a HashMap<Char, Node> is the general one and the follow-up.
  • ?: return null inside the loop is the idiom for early exit in an expression position. Interviewers who write Kotlin will notice it approvingly.
  • Follow-ups go to autocomplete (collect all terminals below a node) and wildcard search (branch on .).

The patterns, in one table

Problem Pattern Time Space The one thing to say
Group Anagrams Canonical key O(nk) O(nk) Count array, comma-joined
Product Except Self Prefix and suffix scan O(n) O(1) Two passes, no division
Maximum Subarray Kadane O(n) O(1) Extend or restart; start at nums[0]
Daily Temperatures Monotonic stack O(n) O(n) Indices; strict <; each pushed once
Trapping Rain Water Two pointers O(n) O(1) Move the shorter wall
Validate BST Bounded recursion O(n) O(h) Carry Long bounds
Course Schedule Topological sort O(V + E) O(V + E) taken == numCourses is the cycle check
Kth Largest Quickselect O(n) expected O(1) Index n - k; random pivot
Subsets Backtracking O(n 2ⁿ) O(n 2ⁿ) Copy the path
Trie Prefix tree O(k) O(chars × 26) The terminal flag

Follow-Up Questions to Expect

  • “Return the order, not just whether it is possible.” For Course Schedule, the order the queue emits is a valid topological order. Collect it.
  • “Now with duplicates.” Subsets needs sort and skip. Validate BST needs a decision about which side duplicates go. Kth Largest is unaffected.
  • “What if the tree is very deep?” Explicit stack. Gotcha 9. Have the iterative in-order traversal ready for the BST question.
  • “What if the input is a stream?” Kth Largest becomes the heap. Maximum Subarray still works because Kadane is single-pass. Group Anagrams needs a streaming hash map, which is what you already have.
  • “Make the trie support wildcards.” A recursive search that branches on . across all children. Say the complexity becomes O(26^wildcards × k) in the worst case.
  • “Why did you use a random pivot?” Because the adversarial input for a fixed pivot is trivial to construct, and expected linear time is the whole point of quickselect.

Key Takeaways

  • Say the invariant before writing the loop. Monotonic stack, two pointers, and Kadane are each one sentence.
  • Carry bounds in tree recursion. Parent-only checks are the wrong answer.
  • Copy the path in backtracking. It is the bug.
  • Kahn’s algorithm: edges from prerequisite to course, and the count of processed nodes is the cycle check.
  • Quickselect is expected O(n) with a random pivot, and you say “expected” out loud.
  • c - 'a' over Char.toInt(), removeAt(lastIndex) over removeLast() on a MutableList, Array(n) { IntArray(m) } over a shared row, a local fun over a recursive lambda, 0L over 0.
  • The first post’s ten gotchas still apply. Together they are the Kotlin fluency checklist.

Further Reading

coding, interview-process
kotlin coding-interview monotonic-stack two-pointers topological-sort quickselect backtracking trie
This post is licensed under CC BY 4.0 by the author.