Visualization Exercise: Tries and Sets | Data Structures

Hands-on problem solving with advanced data structures commonly encountered in senior engineering interviews.

Problem 1: Implement Autocomplete with a Trie

Specification

Implement a Trie that supports:

insert(word: String)
findWordsWithPrefix(prefix: String): List<String>

Implementation

class AutocompleteTrie {
    private class Node {
        val children = HashMap<Char, Node>()
        var isWord = false
    }

    private val root = Node()

    fun insert(word: String) {
        var curr = root
        for (ch in word) {
            curr = curr.children.computeIfAbsent(ch) { Node() }
        }
        curr.isWord = true
    }

    fun findWordsWithPrefix(prefix: String): List<String> {
        var curr = root
        // 1. Walk to the end of prefix
        for (ch in prefix) {
            curr = curr.children[ch] ?: return emptyList()
        }

        // 2. Collect all words in subtree via DFS
        val results = mutableListOf<String>()
        collect(curr, StringBuilder(prefix), results)
        return results
    }

    private fun collect(node: Node, currentWord: StringBuilder, results: MutableList<String>) {
        if (node.isWord) {
            results.add(currentWord.toString())
        }
        for ((ch, child) in node.children) {
            currentWord.append(ch)
            collect(child, currentWord, results)
            currentWord.deleteCharAt(currentWord.length - 1) // Backtrack
        }
    }
}

Problem 2: Number of Islands (Union-Find)

Specification

Given an m × n 2D binary grid representing land ('1') and water ('0'), return the number of connected land islands.

Union-Find Approach

Treat each land cell (r, c) as a node with 1D index r × cols + c.
For each land cell, perform union with its adjacent right and down land neighbors.
The number of disjoint sets among land cells equals the total island count!

class IslandCounter(private val grid: Array<CharArray>) {
    private val rows = grid.size
    private val cols = grid[0].size
    private val parent = IntArray(rows * cols) { it }
    var count = 0

    init {
        for (r in 0 until rows) {
            for (c in 0 until cols) {
                if (grid[r][c] == '1') count++
            }
        }
    }

    fun find(i: Int): Int {
        if (parent[i] != i) parent[i] = find(parent[i])
        return parent[i]
    }

    fun union(x: Int, y: Int) {
        val rootX = find(x)
        val rootY = find(y)
        if (rootX != rootY) {
            parent[rootX] = rootY
            count-- // Two islands merged into one!
        }
    }
}

Summary

Autocomplete navigates to the prefix node and launches a DFS backtracking traversal over child branches.
Union-Find models connected component clustering problems with effortless elegance.