Irbisa · Cheatsheet

Live Coding Round in Kotlin

Hashing, two pointers, sliding window, stacks, binary search, heaps, graphs, and coroutine tasks such as concurrency limits

Middle Developer · 18 questions

  1. 01

    What is Big-O notation, and what does contains cost on a List, on a HashSet and on a sorted list searched with binarySearch?

    Big-O describes how running time or memory grows with the input size n, ignoring constant factors.

    fun main() {    val ids = List(100_000) { it * 2 }           // sorted: 0, 2, 4, ...    val idSet = ids.toHashSet()                   // O(n) to build, once     println(199_998 in ids)                       // O(n): compares element by element    println(199_998 in idSet)                     // O(1) on average: hash, then one bucket…
  2. 02

    Given an IntArray and a target, return the indices of the two numbers that add up to it. How do you get from O(n²) to O(n)?

    The brute force checks every pair, O(n²).

    // Brute force: every pair, O(n²) time, O(1) memoryfun twoSumSlow(nums: IntArray, target: Int): Pair<Int, Int>? {    for (i in nums.indices) for (j in i + 1 until nums.size) {        if (nums[i] + nums[j] == target) return i to j    }    return null…
  3. 03

    Check whether a string is a palindrome, ignoring case and anything that is not a letter or digit, without building a reversed copy.

    Two indices walk toward each other from both ends: skip any character that is not isLetterOrDigit(), compare the rest with lowercaseChar(), and stop at the first mismatch.

    fun isPalindrome(s: String): Boolean {    var i = 0    var j = s.lastIndex    while (i < j) {        when {            !s[i].isLetterOrDigit() -> i++           // skip spaces and punctuation…
  4. 04

    Check whether a string of ()[]{} brackets is balanced. Which data structure do you use, and what does it cost?

    A stack: push every opening bracket, and on a closing one pop and check that it is the matching type.

    private val opening = mapOf(')' to '(', ']' to '[', '}' to '{') fun isBalanced(s: String): Boolean {    val stack = ArrayDeque<Char>()                  // kotlin.collections.ArrayDeque    for (c in s) {        when (c) {…
  5. 05

    Compress a string with run-length encoding in one pass, so that AAABCCD becomes A3BC2D.

    Walk the string once, counting how many times the current character repeats.

    fun rle(s: String): String {    if (s.isEmpty()) return s    val out = StringBuilder()    var count = 1    for (i in 1..s.length) {                    // one step past the end flushes the last run        if (i < s.length && s[i] == s[i - 1]) {…
  6. 06

    Reverse a singly linked list in place. Write it iteratively, then say what the recursive version costs.

    Walk the list with prev, cur and a saved next: remember cur.next, point cur.next back at prev, then step both forward.

    class Node(val value: Int, var next: Node? = null) // Iterative: O(n) time, O(1) extra memoryfun reverse(head: Node?): Node? {    var prev: Node? = null    var cur = head…
  7. 07

    What is the time complexity of this function, and how do you bring it down to O(n)?

    data class Post(val id: Long, val tags: List<String>) // posts: 10,000 posts with 5 tags each; followed: 2,000 tagsfun followedTags(posts: List<Post>, followed: List<String>): List<String> {    val result = mutableListOf<String>()    for (post in posts) {        for (tag in post.tags) {            if (tag in followed && tag !in result) result.add(tag)        }    }    return result}

    It is O(T · F): for each of the T tags, tag in followed scans the whole followed list, and tag !in result scans result as well.

  8. 08

    Group a list of words into anagrams. What do you use as the map key, and what does the whole thing cost?

    Use a key that is equal for all anagrams: the word's letters sorted, so eat, tea and ate all map to aet, and groupBy does the rest.

    // Key = the sorted letters: O(n · k log k) for n words of length kfun groupAnagrams(words: List<String>): List<List<String>> =    words.groupBy { word ->        String(word.toCharArray().apply { sort() })   // "tea" and "eat" both give "aet"    }.values.toList()…
  9. 09

    Find the length of the longest substring without repeating characters in O(n), and walk through how the sliding window moves.

    Keep a window [start, end] with no repeats and a map from each character to the index where it was last seen.

    fun longestUniqueRun(s: String): Int {    val lastSeen = HashMap<Char, Int>()   // character -> index where it was last seen    var start = 0                          // the window is s[start..end]    var best = 0    for (end in s.indices) {        val prev = lastSeen[s[end]]…
  10. 10

    Find the contiguous subarray with the largest sum in O(n), and return its bounds, not only the sum.

    Kadane's algorithm: walk once, keeping the sum of the best run that ends at the current index.

    data class Best(val sum: Long, val from: Int, val to: Int)   // to is inclusive fun maxSubarray(a: IntArray): Best {    require(a.isNotEmpty()) { "an empty array has no subarray" }    var best = Best(a[0].toLong(), 0, 0)    var sum = 0L                     // Long: a million large Ints overflow an Int…
  11. 11

    Merge overlapping intervals such as booking slots [1,3] [2,6] [8,10], and explain why you sort first.

    Sort by start, then walk once: if the next interval starts before the last merged one ends, extend that one's end to the larger of the two ends; otherwise start a new block.

    fun merge(intervals: List<IntRange>): List<IntRange> {    if (intervals.isEmpty()) return emptyList()    val sorted = intervals.sortedBy { it.first }   // O(n log n): overlaps become neighbours    val result = mutableListOf(sorted[0])    for (i in 1 until sorted.size) {        val next = sorted[i]…
  12. 12

    Find the bug: this binary search for the first occurrence of target hangs forever on some inputs.

    // Returns the index of the first `target` in a sorted array, or -1fun firstIndexOf(a: IntArray, target: Int): Int {    var lo = 0    var hi = a.size - 1    while (lo < hi) {        val mid = (lo + hi) / 2        if (a[mid] < target) lo = mid else hi = mid    }    return if (a.isNotEmpty() && a[lo] == target) lo else -1} // firstIndexOf(intArrayOf(1, 2, 2, 2, 5), 2) never returns

    lo = mid does not shrink the range: once hi == lo + 1, mid equals lo, and if a[mid] < target the loop assigns lo the same value forever.

  13. 13

    Return the k most frequent elements of an array. When do you use a PriorityQueue, and when bucket sort?

    Count with a map first (groupingBy { it }.eachCount()), then pick the top k: a min-heap of size k gives O(n + m log k) for m distinct values, and bucket sort by count gives O(n), because no count can exceed n.

    // Heap: O(n + m log k) for m distinct valuesfun topKFrequent(nums: IntArray, k: Int): List<Int> {    val counts = nums.asList().groupingBy { it }.eachCount()   // value -> count, O(n)    val heap = PriorityQueue<Map.Entry<Int, Int>>(compareBy { it.value })   // min-heap    for (entry in counts.entries) {        heap.add(entry)…
  14. 14

    Count the islands in a grid of 0s and 1s. BFS or DFS, and what goes wrong with deep recursion on a large grid?

    Scan every cell; each unvisited land cell starts a new island, which you flood with BFS or DFS to mark all of its land as visited.

    private val steps = listOf(1 to 0, -1 to 0, 0 to 1, 0 to -1) fun countIslands(grid: Array<IntArray>): Int {    val rows = grid.size    val cols = grid.firstOrNull()?.size ?: return 0    val seen = Array(rows) { BooleanArray(cols) }   // or flip 1 to 0 if the input may change…
  15. 15

    In what order does this code print A to E, and why does A not come first?

    fun main() {    runBlocking {        launch { println("A") }        println("B")        coroutineScope {            launch {                delay(100)                println("C")            }            println("D")        }        println("E")    }}

    It prints B, D, A, C, E.

  16. 16

    Download 100 images with at most 4 requests in flight at a time. Write it with coroutines and return the results in input order.

    Start one async per URL inside coroutineScope, wrap each request in withPermit { } on a Semaphore(4), and finish with awaitAll().

    suspend fun <T> downloadAll(    urls: List<String>,    maxInFlight: Int = 4,    load: suspend (String) -> T,): List<T> = coroutineScope {    val permits = Semaphore(maxInFlight)…
  17. 17

    Given Gradle modules and their dependencies, return an order to build them, or report the cycle that makes it impossible.

    It is a topological sort of a directed graph.

    sealed interface BuildPlan {    data class Order(val modules: List<String>) : BuildPlan    data class Cycle(val path: List<String>) : BuildPlan} // deps: module -> the modules it depends on (they must be built first)…
  18. 18

    Query two mirrors in parallel, return the first successful answer, cancel the other, and fall back to the cache after 2 seconds. Write it with coroutines.

    Launch both requests inside a channelFlow, send each success and swallow each network failure, and take the first value with firstOrNull(), which cancels the flow and the losing request.

    // The first source that succeeds wins; null if every one of them failssuspend fun <T> firstSuccess(vararg sources: suspend () -> T): T? =    channelFlow {        for (source in sources) launch {            try {                send(source())…