Live Coding Round in Kotlin

Big-O describes how running time or memory grows with the input size n, ignoring constant factors. contains is O(n) on a List, O(1) on average on a HashSet, and binarySearch on a sorted list is O(log n). Constants drop out: 2n + 10 and n are both O(n); only the shape of the curve matters. At n = 1,000,000, O(log n) is about 20 steps, O(n) a million, O(n²) a trillion. The usual ladder: O(1), O(log n), O(n), O(n log n) for a good sort such as sorted(), O(n²) for nested loops over the same data, O(2^n) for trying every subset. Average, worst, amortised: a HashSet lookup is O(1) on average but degrades when many keys collide in one bucket. Appending to an ArrayList is amortised O(1): a rare O(n) copy spread over many cheap adds. **binarySearch needs sorted input**: sorting first costs O(n log n), so it pays off only when you search the same list many times. For an absent element it returns -(insertionPoint) - 1. Memory counts too: building a HashSet from a list costs O(n) time and O(n) extra memory once, the usual price of O(1) lookups. In a live round, state the time and the space of your solution before the interviewer asks.

The brute force checks every pair, O(n²). The O(n) version walks the array once with a HashMap from value to index: for each element it looks up target - x, and if that value was seen earlier, the two indices are the answer. Look up before you insert: otherwise [3] with target 6 pairs the element with itself; the order also handles duplicates such as [3, 3], where the second 3 finds the first. The trade: O(n) time for O(n) extra memory. The brute force needs O(1) memory, which is the honest answer when memory is the constraint. The sorted variant: if the array is already sorted, two pointers from both ends give O(n) time and O(1) memory: move the left one when the sum is too small, the right one when it is too large. Sorting an unsorted array first loses the original indices unless you sort index pairs. Clarify first: is there always exactly one answer, may an element be used twice, and what to return when nothing matches (null here, rather than an empty array or an exception)?

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. That is O(n) time and O(1) extra memory. Why not the one-liner: comparing s.filter { it.isLetterOrDigit() }.lowercase() with its reversed() is also O(n), but it builds three new strings and always scans the whole input. The task asks for the two-pointer version. One move per step: each pass either skips one character or compares one pair, so i < j is checked before every access and the indices never cross. Edge cases: "" and ".," are palindromes (nothing to compare); "0P" is not, which catches a version that drops digits. Unicode: isLetterOrDigit() and lowercaseChar() handle Cyrillic, so «А роза упала на лапу Азора» passes. They work per UTF-16 Char: an emoji is two surrogate Chars, neither is a letter, so it is skipped like punctuation.

A stack: push every opening bracket, and on a closing one pop and check that it is the matching type. The string is balanced if no pop fails and the stack is empty at the end. O(n) time, and O(n) memory in the worst case. Three ways to fail: a closing bracket with nothing open (")"), the wrong type ("([)]"), and brackets still open at the end ("(("). The last one is the check people forget. Why a counter is not enough: one counter works for a single bracket type, but "([)]" has the right counts in the wrong order. Which stack in Kotlin: ArrayDeque with addLast and removeLastOrNull. java.util.Stack extends Vector and synchronizes every call, which nothing here needs. A map from closing to opening bracket keeps the matching in one place, so supporting <> is one more entry.

Walk the string once, counting how many times the current character repeats. When the character changes, append it to a StringBuilder, plus the count if it is above 1. The last run has no change after it, so it must be flushed too: that is the step people forget. O(n) time. **StringBuilder, not +=**: a String is immutable, so result += ... in a loop copies the whole result every time and turns one pass into O(n²). The last run: the solution's loop runs to s.length, one step past the last index, so the final run is written by the same branch. A loop that stops at the last index needs an extra append after it. Counts above 9: append(count) writes 12 as two digits, so a decoder reads digits until the next letter. Ask first: what about an empty string, lowercase letters or digits in the input ("A12" could not be decoded)? The version candidates report from Yandex interviews also expects an error for anything outside A–Z. Test aloud: "", "A", "ABAB" (nothing to compress) and twelve As (gives A12).

Walk the list with prev, cur and a saved next: remember cur.next, point cur.next back at prev, then step both forward. When cur becomes null, prev is the new head. O(n) time, O(1) extra memory. **Save next first**: once cur.next = prev runs, the rest of the list is reachable only through the saved reference. Losing it is the classic bug. **Return prev, not head**: the old head is now the tail, with next == null. The recursive version reverses the rest of the list, then makes the second node point back at the first. Also O(n) time, but O(n) stack frames: one per node. A 200,000-node list already ends in StackOverflowError on a default JVM thread stack. **tailrec does not rescue it**: the recursive call has to be the last operation, and this version still works after the call returns. A version that carries prev as a parameter can be tailrec, and the compiler turns it into the same loop. Edge cases: an empty list and a single node come back unchanged; trace one, two and three nodes aloud.

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. Put both into hash sets and the function becomes O(T + F). **in hides the loop**: on a List, contains compares element by element, so one innocent line inside a loop makes the function quadratic. Here 50,000 tags against 2,000 followed ones is about 100 million string comparisons. Measured: on random data of that size the original took about 800 ms on a JVM and the set version under 40 ms, with the same output. On a phone's main thread, 800 ms is a frozen screen. The fix: followed.toHashSet() once, O(F), and every lookup is O(1) on average. result becomes a LinkedHashSet: add ignores duplicates in O(1) and keeps the first-seen order, which a plain HashSet would lose. The chain version: flatMap, filter { it in wanted }, distinct(). distinct() keeps its own HashSet, so it is linear too, as long as wanted is a set and not the original list. Where else it hides: indexOf or contains on a List inside a loop, and removeAt(0) on an ArrayList in a loop, which shifts the whole array every time.

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. For n words of length k that is O(n · k log k); counting letters instead of sorting gives O(n · k). **groupBy keeps order**: it builds a LinkedHashMap, so groups come out in the order their first word appeared, which makes the output easy to check. The counting key: for lowercase a–z, an IntArray(26) of letter counts is the signature; it beats sorting once words get long. The array trap: the IntArray itself cannot be the key, because arrays use identity equals and hashCode, so every word would get a group of its own. Convert it with toList() or joinToString(","). Clarify the alphabet: uppercase letters, spaces or Cyrillic break the 26-slot version (c - 'a' goes out of range). The sorted key works for any characters; call lowercase() first if case should not matter. Memory: O(n · k) for the keys and the groups, the same order as the input.

Keep a window [start, end] with no repeats and a map from each character to the index where it was last seen. Move end one step at a time; if the new character was seen inside the window, jump start just past that earlier copy. The answer is the widest window seen. **Walk it on pwwkew**: p, pw (2); the second w was seen at 1, so start jumps to 2 and the window is w; then wk, wke (3); the last w was seen at 2, so start jumps to 3: kew (3). The answer is 3. **The prev >= start check**: in abba, the final a was last seen at 0, already outside the window [2, 3]. Without the check start moves back to 1 and the answer comes out 3 instead of 2. Why O(n): end moves n times and start only ever moves forward, so each character enters and leaves the window at most once. Restarting a scan from every position is O(n²). The other form keeps a HashSet of the window and removes characters from the left until the duplicate is gone: also O(n), with up to 2n steps. Small alphabets: for ASCII input an IntArray(128) of last positions replaces the map and avoids boxing.

Kadane's algorithm: walk once, keeping the sum of the best run that ends at the current index. When that running sum has dropped to zero or below, start a new run here, since a non-positive prefix can only lower what follows. Record the start on every restart and the bounds on every new best. Example: in [-2, 1, -3, 4, -1, 2, 1, -5, 4] the run restarts at 4 (index 3) and peaks at index 6: sum 6, bounds 3..6. All negative: start the best at the first element, not at 0, or [-3, -1, -2] reports 0 for an empty subarray instead of -1 at index 1. Ask whether an empty subarray is allowed. Bounds: save from when the run restarts, and copy from and i only when the sum beats the best. Updating them on every step reports the last run, not the best one. Why it works: the best subarray ending at i is either a[i] alone or the best one ending at i - 1 plus a[i]. That recurrence is dynamic programming with O(1) memory. Overflow: sum into a Long; two Int.MAX_VALUE elements already overflow an Int. Ties: > keeps the first best run and >= the last; say which one you return.

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. The sort costs O(n log n) and dominates, the walk is O(n). Why sort: once intervals are ordered by start, anything that overlaps the current block comes right after it, so one comparison with the last merged interval is enough. Unsorted, every interval has to be checked against all the others, O(n²). **maxOf on the end**: [1,10] followed by [2,3] must stay [1,10]; taking the next interval's end would shrink it to [1,3]. Touching intervals: ask whether [1,3] and [3,5] merge. Closed ranges share the point 3 (<=); bookings as half-open times, 1–3 and 3–5, do not overlap (<). Kotlin fit: IntRange is a closed interval with first and last. For times, a data class Slot(val start: Long, val end: Long) with an explicitly exclusive end is clearer. Leave the input alone: sortedBy returns a new list; sortBy on the caller's MutableList would reorder it behind their back. Follow-ups: inserting one interval into an already merged list is O(n) with no re-sort; "can one person attend all these meetings" is the same sort plus a check of neighbours.

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. A mid smaller than the target cannot be the answer, so the fix is lo = mid + 1. **Trace [1, 2, 2, 2, 5] with target 2**: hi drops to 2, then 1; with lo = 0 and hi = 1, mid = 0 and a[0] = 1 < 2, so lo stays 0. Any input that reaches that state hangs, including [1, 3] with target 3. The invariant: with a half-open range [lo, hi) the first match is always inside it. lo = mid + 1 drops a too-small mid, hi = mid keeps a candidate, so every iteration shrinks the range and the loop ends. **hi = a.size: also covers "insert at the end" and removes the separate empty-array check. Why not the stdlib**: binarySearch returns some matching index, not necessarily the first, which is why the task asks for this lower-bound search. Overflow: (lo + hi) / 2 overflows once lo + hi passes Int.MAX_VALUE; (lo + hi) ushr 1 or lo + (hi - lo) / 2 does not. Rare with arrays on a phone, but interviewers ask. Test it: an empty array, one element, a target below the first and above the last element, and all elements equal.

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. Min-heap, not max-heap: keep at most k entries and evict the smallest count whenever the heap grows past k; the survivors are the answer. A max-heap of all m entries works too, but costs O(m log m) to fill and O(m) memory. **PriorityQueue details**: a binary heap from java.util. add and poll are O(log k), but iterating it does not follow priority order, so drain it with poll() to sort the result. Bucket sort: an array of n + 1 lists indexed by frequency, read from the highest index down until k values are collected. O(n) time and memory, no comparisons. Choosing: the heap when k is small and the data is large or arrives as a stream, since it keeps only k entries beyond the counts; buckets when everything is in memory and you want the linear bound. Quickselect over the distinct values is a third answer: O(m) on average, O(m²) in the worst case. Ties: say how you break them. The buckets return tied values in first-seen order, because groupingBy keeps it; the heap gives no fixed order unless the comparator adds a second key.

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. Either way it is O(rows · cols). Recursive DFS needs one stack frame per cell of an island, so a large island overflows the stack. The overflow is real: a 1000 × 1000 grid of land is one island of a million cells, and recursive DFS throws StackOverflowError on a default thread, whose stack holds only some tens of thousands of small frames. BFS with an ArrayDeque, or DFS with your own stack, keeps that work on the heap. Mark on enqueue: setting seen when a cell is added, not when it is removed, stops the same cell from being queued by several neighbours. Visited array or mutation: flipping 1 to 0 in place saves memory but destroys the caller's grid; a BooleanArray per row costs a byte per cell and leaves the input intact. Four or eight neighbours: ask whether diagonals connect; it is one change in the steps list. Union-find is the other answer, and the better one for the follow-up where land cells are added one by one and the count is asked after each.

It prints B, D, A, C, E. launch only schedules a coroutine, which runBlocking's single thread runs when the parent suspends; coroutineScope runs its block at once, then suspends until its child finishes, so E waits for C. **B before A**: the parent coroutine keeps the thread until it suspends; launch puts A in runBlocking's event-loop queue and returns. **D before A**: entering coroutineScope is not a suspension. Its body runs immediately, queues the inner launch and prints D. **Then A and C**: at the end of its block coroutineScope suspends to wait for its child, the thread is free, and the queue runs A, then starts the inner coroutine, which prints C after 100 ms. **E last**: coroutineScope returns only after all its children complete. That is structured concurrency. Variations interviewers ask: launch(start = CoroutineStart.UNDISPATCHED) prints A first (A B D C E); a yield() after println("B") gives B A D C E; replacing coroutineScope with launch gives B E A D C, because nothing waits any more. Only on one thread: under a multi-threaded dispatcher such as Dispatchers.Default, A can run in parallel with B and the order is no longer fixed.

Start one async per URL inside coroutineScope, wrap each request in withPermit { } on a Semaphore(4), and finish with awaitAll(). A hundred coroutines are cheap; the semaphore is what limits the requests, and awaitAll keeps the input order. Order comes free: the Deferreds are created in input order and awaitAll returns their values in that order, however the downloads finish. **The limitedParallelism(4) trap**: it limits the threads that run the coroutines, not the open requests. A suspending call (Retrofit suspend, Ktor) frees its thread while it waits, so all 100 calls start at once: with a fake suspending loader the peak was 100, not 4. Retrofit's calls then queue in OkHttp's dispatcher at 5 per host, a limit you did not choose. limitedParallelism caps only blocking calls. **chunked(4) is the slow answer: each batch waits for its slowest download, so most of the time fewer than 4 requests run. Failure**: inside coroutineScope the first exception cancels the other downloads and is rethrown. If one broken image must not sink the batch, catch inside async and return null or a Result. Flow alternative: flatMapMerge(concurrency = 4) limits concurrency too, but emits in completion order, so you carry the index to restore the order. Workers: four coroutines pulling URLs from a Channel are equally valid, and better when the URLs arrive as an endless stream.

It is a topological sort of a directed graph. A DFS that appends a module only after all its dependencies gives a valid build order; reaching a module that is still on the current path is a back edge, and the path from it is the cycle. O(V + E). The DFS Three states: not visited, on the current path, done. A HashSet for done and a LinkedHashSet for the path give O(1) checks and keep the path in order, so the cycle can be printed straight from it. Post-order is the build order: a module is appended only after all of its dependencies, so :core:model comes before :core:network, which comes before the features and :app. Reporting the cycle: on a back edge, the path from the repeated module onward, plus that module again, is the cycle: :feature:feed -> :core:network -> :core:auth -> :feature:feed. Gradle refuses such a graph with a circular dependency error. Leaf modules: one that appears only as a dependency, such as :core:ui, is still visited and placed in the order. Kahn's algorithm instead Count each module's unbuilt dependencies, queue every module with none, then repeatedly take one, append it and decrement its dependents. Modules left over when the queue empties are in or behind a cycle. It is iterative, so there is no stack depth limit, and it exposes parallelism: modules waiting in the queue together can build at the same time, the idea behind Gradle's --parallel. Its weakness: the leftovers prove a cycle exists but do not name the path; a DFS over them finds it. Edge cases A module that depends on itself is a cycle of length one; an empty map gives an empty order. Recursion depth equals the longest dependency chain: fine for 40 modules, not for a graph with a million nodes, where Kahn's version is the safer answer. Several orders are valid; iterate the modules in a fixed order if the output must be reproducible.

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. Wrap that in withTimeoutOrNull(2_000) and read the cache when the result is null. Why this shape First successful, not first finished: a mirror that fails in 50 ms must not win. Catching IOException inside its launch drops that result while the other request keeps going. Cancellation is automatic: firstOrNull() stops collecting after one element, which cancels the channelFlow scope and every child still running. A Retrofit or Ktor call cancelled this way also cancels its HTTP request. Both mirrors fail: every child finishes without sending, the channel closes and firstOrNull() returns null, so the cache answers at once instead of after 2 seconds. The timeout: withTimeoutOrNull cancels the block and returns null. withTimeout would throw TimeoutCancellationException, a CancellationException that a broad catch easily swallows. Answers that look right **select { a.onAwait { it }; b.onAwait { it } }** returns the first Deferred to complete, and a failure counts: the fast failure is rethrown from select, and inside coroutineScope it also cancels the sibling. Even with each async returning null on failure, select picks that null; you would have to loop until a value arrives or all are done. **awaitAll() waits for both, so the fast mirror's lead is wasted. Catch narrowly**: catch (e: Exception) in a child also catches the CancellationException that stops the loser. Here it is harmless, but in a retry loop it keeps a cancelled request alive. Testing With runTest and fake APIs built on delay, virtual time runs all four cases instantly: fast primary, primary failing first, both failing, and both slower than 2 seconds.