Live Coding Round in Go

Big-O describes how an algorithm's time or memory grows with the input size n, ignoring constant factors: O(1) stays flat, O(n) doubles when n doubles, O(n²) quadruples. In a live round you state both the time and the extra memory of your solution. Slice: s[i] is O(1); slices.Contains scans, O(n); append is amortised O(1); slices.Insert and slices.Delete in the middle shift the tail, O(n). Map: get, put and delete are O(1) on average; range is O(n), in random order. Sorted slice: slices.BinarySearch is O(log n), about 20 comparisons for a million elements, but each insert that keeps the order is O(n). It fits data built once and read often. Space: count only what you allocate beyond the input: a seen map is O(n), an in-place two-pointer pass O(1). Most speed-ups trade memory for time, which is why both are asked. Constants still matter: for a dozen elements a slice scan often beats a map, because the slice is one contiguous block and the map hashes every key.

Count the elements of one slice in a map, then walk the other and keep every element whose count is still above zero, decrementing it: O(n + m) time and O(min(n, m)) extra memory, instead of O(n·m) for two nested loops. Ask about duplicates first: should [1 1 2] and [1 1 1] give [1 1] or [1]? Counts in a map[T]int keep multiplicity; for set semantics use a map[T]struct{} and delete the key after its first match. Count the smaller slice: the map then holds at most min(n, m) keys. Output order: build the result while walking a slice, never by ranging over the map, whose order is random and changes between runs. Both slices already sorted: two pointers that advance past the smaller value give O(n + m) with no map at all. Generic signature: [T comparable] accepts exactly the types a map key accepts.

Use a stack: push every opening bracket, and on a closing one pop and check that it is the matching kind. The string is balanced when no pop fails and the stack is empty at the end: O(n) time, O(n) memory in the worst case. A slice is the stack: append pushes, s[len(s)-1] peeks, s = s[:len(s)-1] pops. Go has no stack type and needs none. Counting misses the order: ([)] and )( have matching counts of every kind and are still unbalanced. Only a stack remembers which bracket was opened last. The forgotten check: (( never fails a pop, so only the final len(stack) == 0 rejects it. A closing bracket on an empty stack is an immediate false. Check it before peeking, or stack[len(stack)-1] panics with index out of range [-1]. Bytes are safe here: UTF-8 never uses an ASCII byte inside a multi-byte character, so scanning s[i] skips Привет correctly with no rune decoding.

Move two pointers inward from both ends, skip anything that is not a letter or digit, and compare the rest with unicode.ToLower. Indexing s[i] reads bytes, and each Cyrillic letter is two bytes, so a byte-by-byte mirror compares the first byte of one letter with the second byte of another. Two pointers: O(n) time and O(1) extra memory, with no reversed or cleaned-up copy of the string. Decode from both ends: utf8.DecodeRuneInString(s[i:]) returns the first rune and its width in bytes, utf8.DecodeLastRuneInString(s[:j]) the last one, so both pointers always land on rune boundaries. The shortcut []rune(s) is fine in an interview, but say that it costs O(n) extra memory, 4 bytes per character. Filter and fold: unicode.IsLetter or unicode.IsDigit decides what counts, and unicode.ToLower makes А equal а. Edge cases: an empty string, or one made only of punctuation, is a palindrome. A rune is still not always one visible character: an emoji with a skin-tone modifier is two.

Keep two flags, up and down, both true at the start: a pair with a[i-1] > a[i] clears up, a pair with a[i-1] < a[i] clears down, and the slice is monotonic if either flag survives. One pass, O(n) time, O(1) memory, nothing sorted. Equal neighbours clear neither flag, so [2 2 2] and [1 2 2 3] pass. Choosing the direction from the first pair is the classic bug: in [3 3 1] the first pair is equal, so the direction is unknown until the first unequal pair. Two flags avoid the question. Empty and one-element slices are monotonic; a loop from i := 1 handles them without a special case. Stop early once both flags are cleared: on unsorted input the loop ends after a few elements. Two passes also work: slices.IsSorted(a) for one direction, slices.IsSortedFunc with a reversed cmp.Compare for the other. Correct, but not what was asked.

Walk the list once with prev and cur: save cur.Next, point cur.Next back at prev, then move both one node on. When cur is nil, prev is the new head. O(n) time and O(1) extra memory. Save the next node first: overwriting cur.Next before saving it cuts off the rest of the list, the most common slip in a live attempt. Return the new head: the old head is now the tail with Next == nil, so the caller writes head = Reverse(head). A version that returns nothing leaves the caller holding a one-node list. Empty and one-node lists need no special case: the loop runs zero times or once. The recursive version is shorter but uses one stack frame per node, O(n) memory. A goroutine's stack grows on demand, so it survives a million nodes where a fixed-size OS thread stack (8 MB by default on Linux) would not; but the limit is 1 GB on 64-bit systems (the stack doubles, so it stops at 512 MB in practice), and a list of roughly 16 million nodes ends in fatal error: stack overflow, which recover cannot catch.

It is O(n²): slices.Contains scans everything kept so far, so with mostly distinct addresses the k-th one is compared with up to k-1 others, about n²/2 comparisons in total. A map[string]struct{} of seen addresses answers "seen?" in O(1) on average, and the whole function becomes O(n). Hidden loops: slices.Contains, slices.Index, strings.Contains and slices.Insert look like one step but cost O(n). Count them when you state complexity. Measured: 50,000 distinct addresses take 1.2 s, 200,000 take 15 s (twelve times longer for four times the input); the map version does 200,000 in about 20 ms. Quote the worst case: if every address is the same, out stays one element long and the loop is O(n), but production sends mostly distinct input. Space: the set costs O(n) memory, traded for time. Order survives: the slice still collects the output; ranging over the map instead would return the addresses in random order. Without a map: slices.Sort plus slices.Compact is O(n log n), but loses the input order. Strictly it is O(n·L) for addresses of length L, since lowering and hashing read every byte.

Give every word a key that all its anagrams share, and append the word to groups[key]. The key is either the word's letters sorted, O(k log k) for a word of length k, or a [26]int of letter counts, O(k), which works because Go arrays are comparable and can be map keys. Counts as the key: map[[26]int][]string is legal; a []int key is not and fails with invalid map key type []int. The array takes one pass over the word to build, but it only covers a fixed alphabet such as a to z: a capital letter or щ would index out of range and panic. Sorted runes as the key: rs := []rune(w); slices.Sort(rs); key := string(rs) works for any alphabet, пила and липа included, at O(k log k) per word. Total cost: O(n·k) with counts, O(n·k log k) with sorting, plus O(n·k) memory for the groups and keys. Output order: ranging over the map returns the groups in random order. When the expected output follows first appearance, keep an index from key to position, as below, or sort the result. Clarify the input: whether Listen and Silent count, and whether spaces matter. Normalise the word before building the key.

Keep a window with no repeats and a map from each character to where it was last seen. When the current character was last seen inside the window, move start just past that position; the answer is the widest window seen. Both edges only move forward: O(n). **Never move start back**: start = max(start, last[r]+1). Without max, in abba the final a pulls start back to 1, the window again holds both bs, and the answer comes out 3 instead of 2. Why O(n): the right edge advances once per character and the left edge only jumps forward, so each character enters and leaves the window at most once. Runes, not bytes: s[i] is a byte, and Cyrillic letters are two bytes each, often with the same first byte, so a byte-based version returns 5 for the four-letter щука. for _, r := range s decodes runes; count positions in runes, not byte offsets. A fixed alphabet: for ASCII a [128]int array replaces the map, with no hashing and no allocation. The pattern: grow the right edge every step and shrink the left edge only while the window breaks the rule. The same loop solves "longest run of ones with at most k zeros flipped".

Sort by start, then walk once: if the next interval starts before the last merged one ends, extend that end to the larger of the two; otherwise start a new interval. After sorting, intervals that can overlap are neighbours, so one pass is enough: O(n log n) overall, set by the sort. Why sort: unsorted, an interval can overlap one at the far end of the slice, and comparing every pair is O(n²). Sorted by start, an interval can only overlap the last merged one. Take the larger end: [1,10] followed by [2,3] must stay [1,10]. Assigning last.End = cur.End shrinks it, the most common bug. Touching intervals: whether [1,3] and [3,5] merge is the <= versus < in one line. For booking slots where 3 is the end time they usually should; ask. Sorting in Go: slices.SortFunc with cmp.Compare(a.Start, b.Start) sorts in place, so clone first if the caller's slice must keep its order. Pointer into the result: last := &out[len(out)-1] is safe because it is taken fresh on every iteration, after any append. Kept across an append, it could point into a stale array.

The loop mixes two conventions: hi := len(ts)-1 with lo <= hi is a closed range, which needs hi = mid - 1, but hi = mid belongs to a half-open one. Once lo == hi and ts[mid] >= t, hi = mid changes nothing, and the loop spins forever. When it hangs: for every t up to the last element. A t past the end returns, because then only lo = mid + 1 runs, and so does an empty slice, which never enters the loop; a test that searches only for missing values stays green. Pick one invariant and keep it: half-open [lo, hi), with everything before lo below t and everything from hi on at or above it. The loop runs while the range is non-empty (lo < hi), each branch shrinks it, and at the end lo == hi is the answer, len(ts) when there is none. Midpoint: lo + (hi-lo)/2 cannot overflow, unlike (lo+hi)/2; with a 64-bit int that matters only at absurd lengths, but interviewers like to hear it. In real code: slices.BinarySearch(ts, t) returns exactly this position plus found, and sort.Search(len(ts), func(i int) bool { return ts[i] >= t }) takes any monotone predicate. Both return a wrong position, with no error, on unsorted input. Tests that catch it: an empty slice, one element, t before the first, between two, on a run of duplicates and after the last, run with go test -timeout 10s so a hang fails fast.

h.Push and h.Pop are the type's own methods, which only append and remove the last element; heap order is kept by the package functions heap.Push(h, x) and heap.Pop(h). So every Pop drops the entry just pushed, and topK returns the first k words in random map order. How the two layers fit: heap.Interface asks you to write Push and Pop as a plain append and remove-last. heap.Push calls yours and then sifts the new element up; heap.Pop swaps the root to the end, sifts down and then calls yours. Called directly, nothing is sifted. Why a min-heap for the top k: the heap holds only k entries and its root is the weakest of them, so each new word costs at most O(log k). Total O(n log k) time and O(k) memory, against O(n log n) to sort all n distinct words. A heap is not sorted: only parent and child are ordered. Popping everything yields the least frequent first, so fill the result from the end, or sort the k entries. Ties: with equal counts the survivors still depend on map order. Compare the word as a second key in Less when the output must be deterministic. When sorting is enough: for a few thousand distinct words, slices.SortFunc over all of them is simpler; offer the heap for large inputs and streams.

A map from key to a node of a doubly linked list that keeps entries from most to least recently used. Get finds the node through the map and moves it to the front; Put inserts at the front and, over capacity, removes the back node and deletes its key from the map. Every step is O(1). A map alone has no order, and Go's map order is random by design, so finding the least recently used entry would mean scanning stored timestamps, O(n). A slice for the order fails too: moving an element to the front shifts everything before it, O(n). **container/list** is the standard doubly linked list: PushFront, MoveToFront, Back and Remove are all O(1). Element.Value is any, so you type-assert it back. Store the key in the node: eviction starts from the back of the list, and without the key you cannot delete the map entry, so the map keeps growing. **Get writes**: it reorders the list, so a concurrent cache needs a sync.Mutex around Get too. Taking only RLock in Get because it "just reads" is a data race on the list. In production: github.com/hashicorp/golang-lru/v2 is a generic, goroutine-safe implementation of the same idea.

Scan every cell; each time you meet land that is not yet visited, count one island and flood-fill it, marking every connected land cell as visited, with BFS or DFS. Every cell is handled a constant number of times: O(rows × cols) time and memory. Either traversal counts islands: DFS is shorter to write, BFS also gives shortest distances, which the "fewest steps" follow-ups need. Recursion depth: goroutine stacks grow on demand, so a recursive DFS survives grids that would overflow a fixed-size OS thread stack (8 MB by default on Linux). The limit is still 1 GB on 64-bit systems, and since the stack doubles it stops at 512 MB in practice: an all-land 3000×3000 grid recurses 9 million frames deep, and at 60 or more bytes per frame it dies with fatal error: stack overflow, which recover cannot catch. An explicit queue or stack has no such limit. Mark on enqueue, not on dequeue: otherwise one cell can sit in the queue up to four times, once per neighbour. A slice as the queue: queue = queue[1:] is an O(1) dequeue; the consumed prefix stays allocated until append moves the queue to a new array, which is fine for one flood fill. Changing the input: overwriting visited 1s with 0s saves the seen slice, but ask first: the caller may still need the grid.

Hold the current head of each input: read one value from each, send the smaller, and refill only the side it came from. When one input closes, the rest of the other flows through, and the output is closed once both are drained. O(n + m) time, and only two values are held at any moment. **Not select**: select takes whichever channel is ready first, which is fan-in and loses the order. A sorted merge needs both heads before every send, so it waits on each input in turn. Closed versus zero: v, ok := <-ch tells a real 0 from a closed channel; treating the zero value as "no more input" breaks on input that contains 0. **<= keeps it stable: on equal values the left input goes first, as in merge sort. Cancellation**: every receive and every send also selects on ctx.Done(), so a consumer that stops reading, or an input that never closes, does not park the goroutine forever. Ownership: the merge goroutine is the only sender on out, so it closes it with defer close(out). k channels: keep the k heads in a min-heap of (value, source) pairs from container/heap: pop the smallest, send it, push the next value from that source. O(N log k) for N values in total.

This is a topological sort. A depth-first search that appends a service only after all its dependencies yields a valid start order directly; tracking which services are on the current path catches a cycle the moment the search steps back onto one, and that path is the cycle to report. O(V + E). Why three states, not a visited flag A done service can be reached again through a diamond (api and worker both need db): that is fine and must not look like a cycle. onPath means "an ancestor of the current service". Reaching one is a back edge, and path from it to here is the cycle: api -> auth -> config -> api. A single boolean cannot tell those cases apart: it either reports diamonds as cycles or silently skips real ones. Kahn's algorithm, the BFS alternative Count each service's unmet dependencies, queue those with none, and on emitting one decrement its dependents, queueing those that reach zero. It is iterative, and each wave of the queue can start in parallel. If fewer services come out than went in, the rest contain a cycle, but Kahn does not say which one. Details interviewers check Edge direction: "api depends on db" means db starts first. Walking dependencies and appending after them yields that order; walking the reverse edges needs the result reversed. Determinism: Go map order is random, so sort the keys, or the order and the reported cycle change from run to run and break tests. Recursion depth is the longest dependency chain, small for services; for a graph with millions of nodes use Kahn. Unknown names: a dependency that is not a key is treated as a leaf here; in a config loader it is more likely a typo worth an error.

Fetch each page in its own goroutine: a mutex-guarded visited set claims a URL before it is scheduled, a buffered channel caps fetches in flight, and a sync.WaitGroup counts unfinished pages. A page adds its links to the count before its own Done, so Wait returns only when no work is left. Termination A worker pool knows its input up front and closes the jobs channel when it runs out. A crawler's work grows while it runs, so there is no moment to close a channel; the count of pending pages is the signal. wg.Add(1) must run in the parent before go, while the parent's own Done is still pending. The count then reaches zero only after the last page has scheduled its last child. Each URL once Check and mark in one critical section. Checking under RLock and marking later under Lock lets two goroutines both pass the check and fetch the same page. Mark when scheduling, not when fetching: a URL linked from ten pages is claimed by the first and skipped by the other nine. At most 10 in flight The semaphore wraps only the fetch and is released before the children are scheduled. Holding the slot while descending into children synchronously stalls the crawl once all 10 holders wait for a free slot. Goroutines waiting for a slot are cheap but unbounded. A fixed pool of 10 workers reading a queue, with a separate counter of pending work, bounds them too. Also fetch takes ctx, and waiting for a slot also selects on ctx.Done(), so cancelling stops the crawl quickly. Reading visited after wg.Wait() needs no lock: every Done happens before Wait returns.

Keep the backends in a slice and an atomic.Uint64 counter: each call takes its starting index with Add(1), tries backends from there around the ring and returns the first success. It stops after one full round or once ctx is done, and returns every failure joined with errors.Join. The counter is shared state: b.next++ from concurrent calls is a data race, and a mutex would queue every call on one lock for a single increment. An unsigned counter also keeps % n from ever going negative. **Check ctx between attempts**: once the caller has given up, trying the remaining backends only adds load. Keep ctx.Err() in the joined error, so errors.Is(err, context.Canceled) still works. Retrying on the neighbour doubles its load: with backends a, b, c and b down, every call that starts at b lands on c, so c serves two thirds of the calls. A health check that takes b out of the rotation evens it out again. Not every error deserves another backend: a timeout or connection refused does; a 400 or a validation error fails everywhere and only multiplies load. Classify errors before retrying. Idempotency: a request that timed out may still have been executed. Retry only operations that are safe to repeat, or send an idempotency key. What the interviewer asks next: a per-attempt timeout (context.WithTimeout per try) so one hanging backend cannot burn the whole budget, health checks or a circuit breaker per backend, and backoff.