Mock interviews with follow-ups

How you are scored#

Most large companies use a rubric close to this one. Each area gets a rating, and the hiring committee reads the interviewer's notes, not only the final result.

Mock 1: Top K Frequent Words#

Interviewer: Given a list of words and an integer k, return the k most frequent words. Sort by frequency, highest first; words with the same frequency go in alphabetical order.

Clarify (minute 0–4). "Can k be larger than the number of distinct words?" No, it's valid. "Are the words lowercase ASCII?" Yes. "How many words?" Up to 10⁴ or so. "So for [i love leetcode i love coding] and k = 2, I return [i love]: both appear twice and i comes first alphabetically." Correct.

Approach (minute 4–9). "Count with a map, which is O(n). Then I need the top k by (count descending, word ascending). The simplest way is to sort all distinct words with that two-key comparator: O(m log m) for m distinct words. That's fine for 10⁴. If m were huge relative to k, I'd use a size-k heap for O(m log k); should I start with the sort?" Start with the sort.

Code (minute 9–20). The comparator is where people slip. cmp.Or makes the two keys explicit: compare counts in reverse, and if they're equal, compare words.

Test (minute 20–24). Trace the example: counts are i:2, love:2, leetcode:1, coding:1. After sorting: i, love, coding, leetcode. Taking 2 gives [i love]. Edge cases: k equal to the number of distinct words (slice all[:k] is fine), and all words different (pure alphabetical order).

Follow-up (minute 24–40). "Now the words are a stream of billions, and memory matters." "Keep the count map, but instead of sorting, keep a min-heap of size k whose root is the weakest of the current top k. Push each word; when the size exceeds k, pop the weakest. That's O(m log k) time and O(k) for the candidates. At the end, pop everything and fill the answer from the back, because the weakest come out first." Then the deeper follow-up: "The count map itself doesn't fit." "Then exact counting isn't possible in one machine's memory. Either shard by hash of the word across machines and merge the top k from each, or use an approximate structure like a count-min sketch with a small heap of heavy hitters, accepting some error."

package main
 
import (
	"cmp"
	"container/heap"
	"fmt"
	"slices"
)
 
type wc struct {
	word  string
	count int
}
 
// better reports whether a ranks above b: higher count, then alphabetical.
func better(a, b wc) bool {
	if a.count != b.count {
		return a.count > b.count
	}
	return a.word < b.word
}
 
// topKSort: count, then sort everything. O(n log n).
func topKSort(words []string, k int) []string {
	counts := map[string]int{}
	for _, w := range words {
		counts[w]++
	}
	all := make([]wc, 0, len(counts))
	for w, c := range counts {
		all = append(all, wc{w, c})
	}
	slices.SortFunc(all, func(a, b wc) int {
		return cmp.Or(cmp.Compare(b.count, a.count), cmp.Compare(a.word, b.word))
	})
	out := make([]string, 0, k)
	for _, x := range all[:k] {
		out = append(out, x.word)
	}
	return out
}
 
// worstFirst is a heap whose root is the weakest of the current top k.
type worstFirst []wc
 
func (h worstFirst) Len() int           { return len(h) }
func (h worstFirst) Less(i, j int) bool { return better(h[j], h[i]) }
func (h worstFirst) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *worstFirst) Push(x any)        { *h = append(*h, x.(wc)) }
func (h *worstFirst) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}
 
// topKHeap: keep only k candidates. O(n log k), the follow-up answer.
func topKHeap(words []string, k int) []string {
	counts := map[string]int{}
	for _, w := range words {
		counts[w]++
	}
	h := &worstFirst{}
	for w, c := range counts {
		heap.Push(h, wc{w, c})
		if h.Len() > k {
			heap.Pop(h) // drop the weakest
		}
	}
	out := make([]string, k)
	for i := k - 1; i >= 0; i-- { // pop weakest first, fill from the back
		out[i] = heap.Pop(h).(wc).word
	}
	return out
}
 
func main() {
	words := []string{"i", "love", "leetcode", "i", "love", "coding"}
	fmt.Println(topKSort(words, 2), topKHeap(words, 2))
	words = []string{"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"}
	fmt.Println(topKSort(words, 4), topKHeap(words, 4))
}

[i love] [i love]
[the is sunny day] [the is sunny day]

Mock 2: Number of Islands, then islands that grow#

Interviewer: Given a grid of '1' (land) and '0' (water), count the islands. Land connects horizontally and vertically.

Clarify. "Can I modify the grid?" Yes. "Diagonals don't connect?" Correct. "Can the grid be empty?" Assume at least one cell.

Approach. "Each unvisited land cell starts a new island. When I find one, I count it and flood-fill it to mark the whole island as visited, so it isn't counted again. Every cell is visited a constant number of times: O(m·n). I'll mark cells by setting them to '0', which saves a visited array. If modifying the input isn't allowed, I'd use a separate [][]bool."

Test. Trace the 4×5 example: the top-left 2×2 block is one island, the middle cell another, the bottom-right pair a third. Mention that recursion depth can reach m·n for a grid that is all land. "With 10⁶ cells I would switch to an explicit stack or BFS queue; Go's stack grows dynamically, so it would survive, but it's wasteful."

Follow-up. "Now the grid starts as all water and you receive positions one at a time that become land. After each one, report the number of islands." "Rerunning the flood fill is O(m·n) per addition, too slow for many additions. This is dynamic connectivity, which is union-find: each new land cell adds 1 island, then I union it with each land neighbor, and every successful union merges two islands, so I subtract 1. Union by size plus path compression makes each operation nearly O(1)." Then: "What if the same position is added twice?" "The land check skips it, and the count stays the same. Good catch to ask about."

package main
 
import "fmt"
 
// numIslands: flood-fill each new island. O(m·n).
func numIslands(grid [][]byte) int {
	m, n := len(grid), len(grid[0])
	var sink func(r, c int)
	sink = func(r, c int) {
		if r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != '1' {
			return
		}
		grid[r][c] = '0' // mark visited by sinking it
		sink(r+1, c)
		sink(r-1, c)
		sink(r, c+1)
		sink(r, c-1)
	}
	count := 0
	for r := range m {
		for c := range n {
			if grid[r][c] == '1' {
				count++
				sink(r, c)
			}
		}
	}
	return count
}
 
// Follow-up: land is added one cell at a time; report the island count after each addition.
type DSU struct{ parent, size []int }
 
func NewDSU(n int) *DSU {
	d := &DSU{make([]int, n), make([]int, n)}
	for i := range d.parent {
		d.parent[i], d.size[i] = i, 1
	}
	return d
}
 
func (d *DSU) Find(x int) int {
	for d.parent[x] != x {
		d.parent[x] = d.parent[d.parent[x]] // path halving
		x = d.parent[x]
	}
	return x
}
 
func (d *DSU) Union(a, b int) bool {
	a, b = d.Find(a), d.Find(b)
	if a == b {
		return false
	}
	if d.size[a] < d.size[b] {
		a, b = b, a
	}
	d.parent[b] = a
	d.size[a] += d.size[b]
	return true
}
 
func numIslands2(m, n int, positions [][2]int) []int {
	d := NewDSU(m * n)
	land := make([]bool, m*n)
	count := 0
	var out []int
	for _, p := range positions {
		id := p[0]*n + p[1]
		if !land[id] {
			land[id] = true
			count++ // a new island, until it merges
			for _, dd := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {
				r, c := p[0]+dd[0], p[1]+dd[1]
				if r >= 0 && r < m && c >= 0 && c < n && land[r*n+c] && d.Union(id, r*n+c) {
					count--
				}
			}
		}
		out = append(out, count)
	}
	return out
}
 
func main() {
	grid := [][]byte{
		[]byte("11000"),
		[]byte("11000"),
		[]byte("00100"),
		[]byte("00011"),
	}
	fmt.Println(numIslands(grid))
	fmt.Println(numIslands2(3, 3, [][2]int{{0, 0}, {0, 1}, {1, 2}, {2, 1}, {1, 1}}))
}

3
[1 1 2 3 1]

Trace of the follow-up: (0,0) creates island 1; (0,1) joins it; (1,2) is alone, making 2; (2,1) is alone, making 3; (1,1) touches all three groups and merges them into 1.

Mock 3: a time-based key-value store#

Interviewer: Design Set(key, value, timestamp) and Get(key, timestamp). Get returns the value set for the key at the largest timestamp ≤ the given one, or "" if there is none. Timestamps for Set are strictly increasing.

Clarify. "So the store keeps every version, not just the latest?" Yes. "How many calls?" Up to 2·10⁵. "Is it used from multiple goroutines?" Single-threaded for now.

Approach. "A map from key to a slice of (timestamp, value). Because Set timestamps increase, appending keeps each slice sorted, so Get is a binary search: find the first entry with a timestamp after ts; the one just before it is the answer. Set is O(1) amortized and Get is O(log n). sort.Search gives me exactly that 'first index where the condition is true' search."

Test. Set foo=bar at 1. Get(foo, 1) gives "bar". Get(foo, 3) also gives "bar", the latest at or before 3. Set foo=bar2 at 4, then Get(foo, 4) and Get(foo, 5) give "bar2", while Get(foo, 0) finds nothing before 0 and returns "". A missing key gives a nil slice, and searching it returns index 0, so it also returns "" with no special case.

Follow-up. "Now many goroutines call Set and Get concurrently." "A Go map isn't safe for concurrent writes; the runtime can crash with 'concurrent map writes'. I'd add a sync.RWMutex: Get takes the read lock, so reads run in parallel, and Set takes the write lock. And there's a subtle consequence: with concurrent writers, a Set with timestamp 7 can take the lock before one with timestamp 6, so 'append keeps it sorted' is no longer true. I'd insert at the binary-searched position, which is still an append in the common in-order case. I'd also run the tests with go test -race." Interviewers value catching that broken invariant more than adding the lock itself.

package main
 
import (
	"fmt"
	"slices"
	"sort"
	"sync"
)
 
type entry struct {
	ts  int
	val string
}
 
// TimeMap stores every version of a key; Get returns the latest at or before ts.
// Each key's versions are kept sorted by timestamp.
type TimeMap struct {
	mu   sync.RWMutex // follow-up: safe for concurrent use
	data map[string][]entry
}
 
func NewTimeMap() *TimeMap { return &TimeMap{data: map[string][]entry{}} }
 
func (t *TimeMap) Set(key, val string, ts int) {
	t.mu.Lock()
	defer t.mu.Unlock()
	es := t.data[key]
	// In order (the usual case), i == len(es) and this is an append. Concurrent writers can
	// arrive out of order, so insert at the sorted position instead of assuming the end.
	i := sort.Search(len(es), func(i int) bool { return es[i].ts > ts })
	t.data[key] = slices.Insert(es, i, entry{ts, val})
}
 
func (t *TimeMap) Get(key string, ts int) string {
	t.mu.RLock()
	defer t.mu.RUnlock()
	es := t.data[key]
	// first entry with a timestamp after ts; the one before it is the answer
	i := sort.Search(len(es), func(i int) bool { return es[i].ts > ts })
	if i == 0 {
		return ""
	}
	return es[i-1].val
}
 
func main() {
	tm := NewTimeMap()
	tm.Set("foo", "bar", 1)
	fmt.Printf("%q %q\n", tm.Get("foo", 1), tm.Get("foo", 3))
	tm.Set("foo", "bar2", 4)
	fmt.Printf("%q %q %q\n", tm.Get("foo", 4), tm.Get("foo", 5), tm.Get("foo", 0))
 
	// Many writers and readers at once; run with -race to check.
	var wg sync.WaitGroup
	for i := range 100 {
		wg.Add(2)
		go func() { defer wg.Done(); tm.Set("k", fmt.Sprint(i), i) }()
		go func() { defer wg.Done(); tm.Get("k", 50) }()
	}
	wg.Wait()
	es := tm.data["k"]
	sorted := slices.IsSortedFunc(es, func(a, b entry) int { return a.ts - b.ts })
	fmt.Println(len(es), "versions stored, sorted:", sorted, "get(k, 50):", tm.Get("k", 50))
}

"bar" "bar"
"bar2" "bar2" ""
100 versions stored, sorted: true get(k, 50): 50

What the follow-ups have in common#

The three follow-ups test the same handful of instincts. Prepare these for every problem you practice:

Running your own mocks#

• Time it. 45 minutes total: 5 to clarify, 5 to plan, 20 to code, 5 to test, 10 for follow-ups.
• Talk the whole time, even when practicing alone. Record yourself and watch it back; you'll notice silences you didn't know about.
• Use a plain editor with no autocomplete, or a shared doc, because many interviews do.
• Score yourself on the four rubric rows after each mock and keep a log. The weakest row is what you practice next.
• Practice as the interviewer too. Watching someone else stall teaches you what a hint looks like and how to accept one.

Summary#

• Interviews score problem solving, coding, communication and testing; the notes matter as much as the code.
• Spend the first minutes clarifying and stating a baseline with its complexity, then improve it.
• Follow-ups probe bounded memory, changing data, concurrency, space and two-variable complexity. Prepare an answer for each.
• Top K → size-k heap whose root is the weakest; growing islands → union-find; versioned store → binary search, then RWMutex and the broken sorted invariant.
• Rehearse whole interviews on a timer, out loud, and score yourself with the rubric.