Data Structures & Algorithms

fun main() {
    val nums = mutableListOf(5, 3, 8)
    nums.add(1)          // append: O(1) amortised
    nums.add(0, 9)       // insert at front: shifts everything, O(n)
    println(nums)
    println(nums[2])     // index access: O(1)
    nums.removeAt(0)
    println(nums)
    println(nums.size)

    val squares = IntArray(5) { i -> i * i }   // fixed size, unboxed ints
    println(squares.joinToString())
    println(squares.sum())
}

fun main() {
    val text = "the cat and the hat and the bat"
    val counts = mutableMapOf<String, Int>()   // LinkedHashMap: insertion order
    for (word in text.split(" ")) {
        counts[word] = counts.getOrDefault(word, 0) + 1
    }
    println(counts)
    println(counts["the"])
    println(counts["dog"])
    println("cat" in counts)

    val seen = HashSet<Int>()
    val dupes = mutableListOf<Int>()
    for (n in listOf(4, 1, 4, 7, 1, 9)) {
        if (!seen.add(n)) dupes.add(n)    // add() returns false if already present
    }
    println(dupes)
    println(seen.sorted())
}

fun main() {
    val words = listOf("eat", "tea", "tan", "ate", "nat", "bat")
    val groups = LinkedHashMap<String, MutableList<String>>()
    for (w in words) {
        val key = w.toCharArray().sorted().joinToString("")
        groups.getOrPut(key) { mutableListOf() }.add(w)
    }
    println(groups)
    println(groups.values.map { it.size })
    println(words.groupingBy { it.first() }.eachCount())
}

class Stack<T> {
    private val items = mutableListOf<T>()

    fun push(item: T) { items.add(item) }

    fun pop(): T {
        check(items.isNotEmpty()) { "pop from empty stack" }
        return items.removeAt(items.lastIndex)
    }

    fun peek(): T? = items.lastOrNull()
    fun isEmpty() = items.isEmpty()
    val size: Int get() = items.size
}

fun main() {
    val s = Stack<Int>()
    s.push(10); s.push(20); s.push(30)
    println("${s.pop()} ${s.size} ${s.peek()}")
    val words = Stack<String>()
    println(words.peek())
    println(words.isEmpty())
}

fun isBalanced(s: String): Boolean {
    val pairs = mapOf(')' to '(', ']' to '[', '}' to '{')
    val stack = ArrayDeque<Char>()
    for (c in s) {
        when (c) {
            '(', '[', '{' -> stack.addLast(c)
            ')', ']', '}' -> if (stack.removeLastOrNull() != pairs[c]) return false
        }
    }
    return stack.isEmpty()
}

fun main() {
    for (s in listOf("([]{})", "([)]", "((", "a(b)c")) {
        println("$s -> ${isBalanced(s)}")
    }
}

fun main() {
    val queue = ArrayDeque<String>()
    queue.addLast("ana")
    queue.addLast("ben")
    queue.addLast("cy")
    println(queue.removeFirst())   // first in, first out
    queue.addLast("dee")
    println(queue)
    println(queue.first())         // peek at the front

    val deque = ArrayDeque(listOf(2, 3))
    deque.addFirst(1)
    deque.addLast(4)
    println(deque)
    println("${deque.removeFirst()} ${deque.removeLast()} $deque")
}

class Node<T>(val value: T, var next: Node<T>? = null)

class LinkedList<T> {
    private var head: Node<T>? = null
    private var tail: Node<T>? = null
    var size = 0
        private set

    fun addFirst(value: T) {
        val node = Node(value, head)
        head = node
        if (tail == null) tail = node
        size++
    }

    fun addLast(value: T) {
        val node = Node(value)
        val t = tail
        if (t == null) head = node else t.next = node
        tail = node
        size++
    }

    fun reverse() {
        tail = head
        var prev: Node<T>? = null
        var cur = head
        while (cur != null) {
            val next = cur.next
            cur.next = prev
            prev = cur
            cur = next
        }
        head = prev
    }

    override fun toString(): String {
        val parts = mutableListOf<String>()
        var cur = head
        while (cur != null) { parts.add(cur.value.toString()); cur = cur.next }
        return parts.joinToString(" -> ", postfix = " -> null")
    }
}

fun main() {
    val list = LinkedList<Int>()
    list.addLast(2); list.addLast(3); list.addFirst(1)
    println(list)
    println(list.size)
    list.reverse()
    println(list)
    list.addLast(0)
    println(list)
}

fun factorial(n: Int): Long = if (n <= 1) 1 else n * factorial(n - 1)

tailrec fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)

// fast power: halve the exponent each step -> O(log n) calls
fun power(base: Long, exp: Int): Long = when {
    exp == 0 -> 1
    exp % 2 == 0 -> { val half = power(base, exp / 2); half * half }
    else -> base * power(base, exp - 1)
}

fun main() {
    println(factorial(5))
    println(factorial(20))
    println(gcd(48, 18))
    println(power(2, 10))
    println(power(3, 13))
}

class BST {
    private class Node(val key: Int) {
        var left: Node? = null
        var right: Node? = null
    }

    private var root: Node? = null

    fun insert(key: Int) { root = insert(root, key) }

    private fun insert(node: Node?, key: Int): Node {
        if (node == null) return Node(key)
        if (key < node.key) node.left = insert(node.left, key)
        else if (key > node.key) node.right = insert(node.right, key)
        return node   // duplicates are ignored
    }

    fun contains(key: Int): Boolean {
        var cur = root
        while (cur != null) {
            if (key == cur.key) return true
            cur = if (key < cur.key) cur.left else cur.right
        }
        return false
    }

    fun inOrder(): List<Int> {
        val out = mutableListOf<Int>()
        fun walk(n: Node?) {
            if (n == null) return
            walk(n.left); out.add(n.key); walk(n.right)
        }
        walk(root)
        return out
    }

    fun height(): Int {
        fun h(n: Node?): Int = if (n == null) 0 else 1 + maxOf(h(n.left), h(n.right))
        return h(root)
    }
}

fun main() {
    val tree = BST()
    for (k in listOf(50, 30, 70, 20, 40, 60, 80, 30)) tree.insert(k)
    println(tree.inOrder())
    println("${tree.contains(60)} ${tree.contains(65)}")
    println(tree.height())
}

import java.util.TreeMap

fun main() {
    val scores = TreeMap<String, Int>()
    scores["mia"] = 88
    scores["al"] = 72
    scores["zed"] = 95
    scores["kim"] = 81
    println(scores)                    // always sorted by key
    println(scores.firstKey() + " " + scores.lastKey())
    println(scores.headMap("l"))       // keys strictly before "l"
    println(scores.ceilingKey("b"))    // smallest key >= "b"

    val set = sortedSetOf(5, 1, 9, 3)
    println(set)
    println(set.higher(3))             // smallest element > 3
}

class MinHeap {
    private val a = mutableListOf<Int>()
    val size: Int get() = a.size

    fun push(x: Int) {
        a.add(x)
        var i = a.lastIndex
        while (i > 0) {
            val parent = (i - 1) / 2
            if (a[parent] <= a[i]) break
            a[parent] = a[i].also { a[i] = a[parent] }   // swap
            i = parent
        }
    }

    fun pop(): Int {
        val top = a[0]
        val last = a.removeAt(a.lastIndex)
        if (a.isNotEmpty()) {
            a[0] = last
            var i = 0
            while (true) {
                val l = 2 * i + 1
                val r = l + 1
                var smallest = i
                if (l < a.size && a[l] < a[smallest]) smallest = l
                if (r < a.size && a[r] < a[smallest]) smallest = r
                if (smallest == i) break
                a[i] = a[smallest].also { a[smallest] = a[i] }
                i = smallest
            }
        }
        return top
    }
}

fun main() {
    val heap = MinHeap()
    for (x in listOf(7, 2, 9, 4, 1)) heap.push(x)
    val out = mutableListOf<Int>()
    while (heap.size > 0) out.add(heap.pop())
    println(out)
}

import java.util.PriorityQueue

data class Task(val name: String, val priority: Int)

fun main() {
    val minHeap = PriorityQueue(listOf(7, 2, 9, 4, 1))
    println(minHeap.peek())

    val maxHeap = PriorityQueue<Int>(reverseOrder())
    maxHeap.addAll(listOf(7, 2, 9, 4, 1))
    println(maxHeap.poll())

    val tasks = PriorityQueue(compareBy<Task> { it.priority }.thenBy { it.name })
    tasks.add(Task("deploy", 2))
    tasks.add(Task("fix bug", 1))
    tasks.add(Task("docs", 3))
    tasks.add(Task("alert", 1))
    val order = mutableListOf<String>()
    while (tasks.isNotEmpty()) order.add(tasks.poll().name)
    println(order)

    val k = 3
    val top = PriorityQueue<Int>()
    for (x in listOf(5, 12, 3, 20, 8, 15)) {
        top.add(x)
        if (top.size > k) top.poll()   // evict the smallest
    }
    println(top.sortedDescending())
}

val graph: Map<String, List<String>> = mapOf(
    "A" to listOf("B", "C"),
    "B" to listOf("D"),
    "C" to listOf("D", "E"),
    "D" to listOf("F"),
    "E" to listOf("F"),
    "F" to emptyList(),
)

fun bfs(start: String): List<String> {
    val visited = mutableSetOf(start)
    val queue = ArrayDeque(listOf(start))
    val order = mutableListOf<String>()
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        order.add(node)
        for (next in graph.getValue(node)) {
            if (visited.add(next)) queue.addLast(next)
        }
    }
    return order
}

fun dfs(node: String, visited: MutableSet<String> = mutableSetOf()): List<String> {
    if (!visited.add(node)) return emptyList()
    val order = mutableListOf(node)
    for (next in graph.getValue(node)) order += dfs(next, visited)
    return order
}

fun main() {
    println("BFS: ${bfs("A")}")
    println("DFS: ${dfs("A")}")
}

fun binarySearch(items: List<Int>, target: Int): Int {
    var lo = 0
    var hi = items.lastIndex
    while (lo <= hi) {
        val mid = lo + (hi - lo) / 2
        when {
            items[mid] == target -> return mid
            items[mid] < target -> lo = mid + 1
            else -> hi = mid - 1
        }
    }
    return -1
}

fun main() {
    val sorted = listOf(3, 8, 15, 23, 42, 57, 91)
    println(binarySearch(sorted, 42))
    println(binarySearch(sorted, 5))
    println(sorted.binarySearch(42))
    println(sorted.binarySearch(5))          // -(1) - 1
    println(-(sorted.binarySearch(5) + 1))   // insertion point
    val words = listOf("apple", "kiwi", "mango", "pear")
    println(words.binarySearch("mango"))
    println(words.binarySearch { it.compareTo("kiwi") })
}

fun mergeSort(xs: List<Int>): List<Int> {
    if (xs.size <= 1) return xs
    val mid = xs.size / 2
    val left = mergeSort(xs.subList(0, mid))
    val right = mergeSort(xs.subList(mid, xs.size))
    val out = ArrayList<Int>(xs.size)
    var i = 0
    var j = 0
    while (i < left.size && j < right.size) {
        if (left[i] <= right[j]) out.add(left[i++]) else out.add(right[j++])
    }
    while (i < left.size) out.add(left[i++])
    while (j < right.size) out.add(right[j++])
    return out
}

fun main() {
    println(mergeSort(listOf(38, 27, 43, 3, 9, 82, 10)))
    println(mergeSort(emptyList()))
}

data class Dev(val name: String, val lang: String, val years: Int)

fun main() {
    val devs = listOf(
        Dev("Ravi", "Kotlin", 5), Dev("Ana", "Java", 8),
        Dev("Li", "Kotlin", 2), Dev("Sam", "Java", 3), Dev("Zoe", "Kotlin", 5),
    )
    println(listOf(5, 2, 9, 1).sorted())
    println(listOf(5, 2, 9, 1).sortedDescending())
    println(devs.sortedBy { it.years }.map { it.name })
    val byLangThenSenior = compareBy<Dev> { it.lang }.thenByDescending { it.years }.thenBy { it.name }
    println(devs.sortedWith(byLangThenSenior).map { it.name })

    val fruit = mutableListOf("pear", "fig", "banana")
    fruit.sortBy { it.length }     // in place, returns Unit
    println(fruit)
}

val memo = HashMap<Int, Long>()

fun fib(n: Int): Long {
    if (n <= 1) return n.toLong()
    return memo.getOrPut(n) { fib(n - 1) + fib(n - 2) }   // top-down
}

fun fibTable(n: Int): Long {                            // bottom-up, O(1) space
    if (n <= 1) return n.toLong()
    var prev = 0L
    var cur = 1L
    repeat(n - 1) {
        val next = prev + cur
        prev = cur
        cur = next
    }
    return cur
}

fun minCoins(coins: IntArray, amount: Int): Int {
    val dp = IntArray(amount + 1) { Int.MAX_VALUE }
    dp[0] = 0
    for (a in 1..amount) {
        for (c in coins) {
            if (c <= a && dp[a - c] != Int.MAX_VALUE) dp[a] = minOf(dp[a], dp[a - c] + 1)
        }
    }
    return if (dp[amount] == Int.MAX_VALUE) -1 else dp[amount]
}

fun main() {
    println(fib(50))
    println(fibTable(90))
    println(minCoins(intArrayOf(1, 5, 10, 25), 63))
    println(minCoins(intArrayOf(2), 3))
}