What is Big-O notation, and what do lookup, insert and delete cost on a Go slice, a map and a sorted slice?

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.

Write a function that returns the intersection of two unsorted slices of any length. What does it cost, and what do you ask about duplicates first?

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.

Check that a string of brackets like ([]{}) is balanced. Which structure do you use, and which inputs break a solution that only counts brackets?

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

Check whether a string is a palindrome ignoring case, spaces and punctuation, so А роза упала на лапу Азора passes. Why does comparing s[i] with s[len(s)-1-i] fail?

Move two pointers inward from both ends, skip anything that is not a letter or digit, and compare the rest with `unicode.ToLower`.

Check in one pass whether a slice is monotonic, entirely non-decreasing or entirely non-increasing. Which inputs do quick solutions get wrong?

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.

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

Walk the list once with `prev` and `cur`: save `cur.Next`, point `cur.Next` back at `prev`, then move both one node on.

Deduplicating 200,000 addresses with this function takes about 15 seconds. What is its time complexity, and how do you bring it down to O(n)?

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.

Merge overlapping intervals such as booking slots [1,3] [2,6] [8,10] [9,12]. Why do you sort first, and what does it cost?

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.

Implement an LRU cache with O(1) Get and Put. Which two structures do you combine in Go, and why is a map alone not enough?

A map from key to a node of a doubly linked list that keeps entries from most to least recently used.

Count the islands in a grid of 0s and 1s. BFS or DFS, and why can a recursive DFS crash on a 3000×3000 map in Go?

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.

Two channels each deliver numbers in ascending order. Merge them into one ascending channel. Why does a select over both not work, and what changes for k channels?

Hold the current head of each input: read one value from each, send the smaller, and refill only the side it came from.

Write a concurrent crawler: follow links from one URL up to depth 2, fetch each URL once, with at most 10 fetches in flight. How does it know it has finished?

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.

Write a client-side balancer over unreliable backends: spread calls round-robin, and on a failure retry the next backend until one succeeds or the context ends.

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.

Irbisa · Cheatsheet

Live Coding Round in Go

Q: Reverse a singly linked list in place. Write it iteratively, and say what the recursive version costs in Go.

Walk the list once with `prev` and `cur`: save `cur.Next`, point `cur.Next` back at `prev`, then move both one node on.

Q: Deduplicating 200,000 addresses with this function takes about 15 seconds. What is its time complexity, and how do you bring it down to O(n)?

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.

Big O, hashing, two pointers, sliding window, stacks, binary search, heaps and graphs in Go, plus concurrent tasks such as a bounded worker pool

Middle Developer · 18 questions

01
What is Big-O notation, and what do lookup, insert and delete cost on a Go slice, a map and a sorted slice?
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.
02
Write a function that returns the intersection of two unsorted slices of any length. What does it cost, and what do you ask about duplicates first?
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.
```
// Intersect returns the values present in both slices, as many times as// they occur in both: [1 1 2 3] and [1 1 1 3] give [1 1 3].func Intersect[T comparable](a, b []T) []T {	if len(a) > len(b) {		a, b = b, a // count the smaller slice: O(min(n, m)) memory	}…
```
03
Check that a string of brackets like ([]{}) is balanced. Which structure do you use, and which inputs break a solution that only counts brackets?
Use a stack: push every opening bracket, and on a closing one pop and check that it is the matching kind.
```
var opening = map[byte]byte{')': '(', ']': '[', '}': '{'} func Balanced(s string) bool {	var stack []byte	for i := 0; i < len(s); i++ { // bytes are safe: UTF-8 never hides '(' inside a letter		switch c := s[i]; c {…
```
04
Check whether a string is a palindrome ignoring case, spaces and punctuation, so А роза упала на лапу Азора passes. Why does comparing s[i] with s[len(s)-1-i] fail?
Move two pointers inward from both ends, skip anything that is not a letter or digit, and compare the rest with unicode.ToLower.
```
func IsPalindrome(s string) bool {	i, j := 0, len(s) // byte offsets: s[i:j] is what is left to check	for i < j {		l, lw := utf8.DecodeRuneInString(s[i:])		if !isAlnum(l) {			i += lw…
```
05
Check in one pass whether a slice is monotonic, entirely non-decreasing or entirely non-increasing. Which inputs do quick solutions get wrong?
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.
```
func IsMonotonic[T cmp.Ordered](a []T) bool {	up, down := true, true	for i := 1; i < len(a); i++ {		if a[i-1] > a[i] {			up = false		}…
```
06
Reverse a singly linked list in place. Write it iteratively, and say what the recursive version costs in Go.
Walk the list once with prev and cur: save cur.Next, point cur.Next back at prev, then move both one node on.
```
type Node[T any] struct {	Val  T	Next *Node[T]} func Reverse[T any](head *Node[T]) *Node[T] {…
```
07
Deduplicating 200,000 addresses with this function takes about 15 seconds. What is its time complexity, and how do you bring it down to O(n)?
```
// uniqueEmails returns each address once, case-insensitively, in input order.func uniqueEmails(emails []string) []string {	var out []string	for _, e := range emails {		e = strings.ToLower(strings.TrimSpace(e))		if !slices.Contains(out, e) {			out = append(out, e)		}	}	return out}
```
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.

Group a list of words into anagrams, so that `eat`, `tea` and `ate` end up together. What do you use as the map key in Go, and what does it cost?

Give every word a key that all its anagrams share, and append the word to groups[key].

func GroupAnagrams(words []string) [][]string {	index := map[[26]int]int{} // letter counts -> position in groups	var groups [][]string	for _, w := range words {		var key [26]int // an array is comparable, so it can be a map key		for i := 0; i < len(w); i++ {…

Find the length of the longest substring without repeating characters in O(n). How does the window move, and what changes for non-ASCII text?

Keep a window with no repeats and a map from each character to where it was last seen.

func LongestUnique(s string) int {	last := map[rune]int{} // rune -> its position (in runes) when last seen	best, start, pos := 0, 0, 0	for _, r := range s { // runes, not bytes: "щука" is 4 characters, not 8		if p, seen := last[r]; seen {			start = max(start, p+1) // never move the left edge back…

10
Merge overlapping intervals such as booking slots [1,3] [2,6] [8,10] [9,12]. Why do you sort first, and what does it cost?
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.
```
type Interval struct{ Start, End int } func Merge(xs []Interval) []Interval {	if len(xs) == 0 {		return nil	}…
```

Find the bug: this binary search for the first timestamp at or after `t` hangs forever on some inputs.

// firstAtOrAfter returns the index of the first element >= t,// or len(ts) if there is none. ts is sorted.func firstAtOrAfter(ts []int64, t int64) int {	lo, hi := 0, len(ts)-1	for lo <= hi {		mid := lo + (hi-lo)/2		if ts[mid] < t {			lo = mid + 1		} else {			hi = mid // mid may be the answer, so keep it		}	}	return lo}

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.

Find the bug: `topK` on `container/heap` returns `k` words, but rarely the most frequent ones, and a different set on every run.

type entry struct {	word  string	count int} // topK uses minHeap, a []entry implementing heap.Interface (least frequent at the root).func topK(counts map[string]int, k int) []entry {	h := &minHeap{}	for w, c := range counts {		h.Push(entry{w, c})		if h.Len() > k {			h.Pop() // drop the least frequent		}	}	return *h}

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).

13
Implement an LRU cache with O(1) Get and Put. Which two structures do you combine in Go, and why is a map alone not enough?
A map from key to a node of a doubly linked list that keeps entries from most to least recently used.
```
type LRU[K comparable, V any] struct {	cap   int	order *list.List          // front = most recently used	items map[K]*list.Element // key -> its node in order}…
```
14
Count the islands in a grid of 0s and 1s. BFS or DFS, and why can a recursive DFS crash on a 3000×3000 map in Go?
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.
```
func CountIslands(grid [][]byte) int {	if len(grid) == 0 {		return 0	}	rows, cols := len(grid), len(grid[0])	seen := make([]bool, rows*cols) // leaves the caller's grid untouched…
```
15
Two channels each deliver numbers in ascending order. Merge them into one ascending channel. Why does a select over both not work, and what changes for k channels?
Hold the current head of each input: read one value from each, send the smaller, and refill only the side it came from.
```
func MergeSorted[T cmp.Ordered](ctx context.Context, a, b <-chan T) <-chan T {	out := make(chan T)	go func() {		defer close(out) // the only sender closes, once		va, okA := recv(ctx, a)		vb, okB := recv(ctx, b)…
```

Given services and the services each one depends on, return an order to start them in, or report the cycle that makes it impossible.

This is a topological sort.

// StartOrder lists services so that each one comes after everything it// depends on, or returns the first dependency cycle it finds.func StartOrder(deps map[string][]string) ([]string, error) {	const (		onPath = iota + 1 // on the current DFS path; 0 means not visited yet		done…

17
Write a concurrent crawler: follow links from one URL up to depth 2, fetch each URL once, with at most 10 fetches in flight. How does it know it has finished?
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.
```
type FetchFunc func(ctx context.Context, url string) (links []string, err error) // Crawl fetches every URL within maxDepth links of start, each once, with at// most limit fetches in flight, and returns the URLs it scheduled.func Crawl(ctx context.Context, fetch FetchFunc, start string, maxDepth, limit int) []string {	var (…
```
18
Write a client-side balancer over unreliable backends: spread calls round-robin, and on a failure retry the next backend until one succeeds or the context ends.
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.
```
type Backend interface {	Invoke(ctx context.Context, req []byte) ([]byte, error)} type Balancer struct {	backends []Backend…
```

Live Coding Round in Go

What is Big-O notation, and what do lookup, insert and delete cost on a Go slice, a map and a sorted slice?

Write a function that returns the intersection of two unsorted slices of any length. What does it cost, and what do you ask about duplicates first?

Check that a string of brackets like `([]{})` is balanced. Which structure do you use, and which inputs break a solution that only counts brackets?

Check whether a string is a palindrome ignoring case, spaces and punctuation, so `А роза упала на лапу Азора` passes. Why does comparing `s[i]` with `s[len(s)-1-i]` fail?

Check in one pass whether a slice is monotonic, entirely non-decreasing or entirely non-increasing. Which inputs do quick solutions get wrong?

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

Deduplicating 200,000 addresses with this function takes about 15 seconds. What is its time complexity, and how do you bring it down to O(n)?

Group a list of words into anagrams, so that `eat`, `tea` and `ate` end up together. What do you use as the map key in Go, and what does it cost?

Find the length of the longest substring without repeating characters in O(n). How does the window move, and what changes for non-ASCII text?

Merge overlapping intervals such as booking slots `[1,3] [2,6] [8,10] [9,12]`. Why do you sort first, and what does it cost?

Find the bug: this binary search for the first timestamp at or after `t` hangs forever on some inputs.

Find the bug: `topK` on `container/heap` returns `k` words, but rarely the most frequent ones, and a different set on every run.

Implement an LRU cache with O(1) `Get` and `Put`. Which two structures do you combine in Go, and why is a map alone not enough?

Count the islands in a grid of `0`s and `1`s. BFS or DFS, and why can a recursive DFS crash on a 3000×3000 map in Go?

Two channels each deliver numbers in ascending order. Merge them into one ascending channel. Why does a `select` over both not work, and what changes for k channels?

Given services and the services each one depends on, return an order to start them in, or report the cycle that makes it impossible.

Write a concurrent crawler: follow links from one URL up to depth 2, fetch each URL once, with at most 10 fetches in flight. How does it know it has finished?

Write a client-side balancer over unreliable backends: spread calls round-robin, and on a failure retry the next backend until one succeeds or the context ends.

What is Big-O notation, and what do lookup, insert and delete cost on a Go slice, a map and a sorted slice?

Write a function that returns the intersection of two unsorted slices of any length. What does it cost, and what do you ask about duplicates first?

Check that a string of brackets like ([]{}) is balanced. Which structure do you use, and which inputs break a solution that only counts brackets?

Check whether a string is a palindrome ignoring case, spaces and punctuation, so А роза упала на лапу Азора passes. Why does comparing s[i] with s[len(s)-1-i] fail?

Check in one pass whether a slice is monotonic, entirely non-decreasing or entirely non-increasing. Which inputs do quick solutions get wrong?

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

Deduplicating 200,000 addresses with this function takes about 15 seconds. What is its time complexity, and how do you bring it down to O(n)?

Group a list of words into anagrams, so that eat, tea and ate end up together. What do you use as the map key in Go, and what does it cost?

Find the length of the longest substring without repeating characters in O(n). How does the window move, and what changes for non-ASCII text?

Merge overlapping intervals such as booking slots [1,3] [2,6] [8,10] [9,12]. Why do you sort first, and what does it cost?

Find the bug: this binary search for the first timestamp at or after t hangs forever on some inputs.

Find the bug: topK on container/heap returns k words, but rarely the most frequent ones, and a different set on every run.

Implement an LRU cache with O(1) Get and Put. Which two structures do you combine in Go, and why is a map alone not enough?

Count the islands in a grid of 0s and 1s. BFS or DFS, and why can a recursive DFS crash on a 3000×3000 map in Go?

Two channels each deliver numbers in ascending order. Merge them into one ascending channel. Why does a select over both not work, and what changes for k channels?

Given services and the services each one depends on, return an order to start them in, or report the cycle that makes it impossible.

Write a concurrent crawler: follow links from one URL up to depth 2, fetch each URL once, with at most 10 fetches in flight. How does it know it has finished?

Write a client-side balancer over unreliable backends: spread calls round-robin, and on a failure retry the next backend until one succeeds or the context ends.

Check that a string of brackets like `([]{})` is balanced. Which structure do you use, and which inputs break a solution that only counts brackets?

Check whether a string is a palindrome ignoring case, spaces and punctuation, so `А роза упала на лапу Азора` passes. Why does comparing `s[i]` with `s[len(s)-1-i]` fail?

Group a list of words into anagrams, so that `eat`, `tea` and `ate` end up together. What do you use as the map key in Go, and what does it cost?

Merge overlapping intervals such as booking slots `[1,3] [2,6] [8,10] [9,12]`. Why do you sort first, and what does it cost?

Find the bug: this binary search for the first timestamp at or after `t` hangs forever on some inputs.

Find the bug: `topK` on `container/heap` returns `k` words, but rarely the most frequent ones, and a different set on every run.

Implement an LRU cache with O(1) `Get` and `Put`. Which two structures do you combine in Go, and why is a map alone not enough?

Count the islands in a grid of `0`s and `1`s. BFS or DFS, and why can a recursive DFS crash on a 3000×3000 map in Go?

Two channels each deliver numbers in ascending order. Merge them into one ascending channel. Why does a `select` over both not work, and what changes for k channels?