Что такое нотация Big-O и сколько стоят поиск, вставка и удаление в слайсе Go, в map и в отсортированном слайсе?

Big-O описывает, как время работы или память алгоритма растут с размером входа n, без учёта констант: O(1) не растёт, O(n) удваивается вместе с n, O(n²) растёт вчетверо.

Напишите функцию, которая возвращает пересечение двух неупорядоченных слайсов любой длины. Сколько она стоит и что нужно сначала уточнить про дубликаты?

Посчитайте элементы одного слайса в map, затем пройдите по второму и оставляйте каждый элемент, чей счётчик ещё больше нуля, уменьшая его: O(n + m) по времени и O(min(n, m)) дополнительной памяти вместо O(n·m) у двух вложенных циклов.

Проверьте, что строка из скобок вроде ([]{}) сбалансирована. Какую структуру вы используете и на каких входах ломается решение, которое просто считает скобки?

Нужен стек: каждую открывающую скобку кладите в него, на закрывающей снимайте верхнюю и проверяйте, что она того же вида.

Проверьте, является ли строка палиндромом без учёта регистра, пробелов и знаков препинания, чтобы А роза упала на лапу Азора проходила. Почему сравнение s[i] с s[len(s)-1-i] не работает?

Двигайте два указателя с концов к центру, пропускайте всё, что не буква и не цифра, и сравнивайте остальное через `unicode.ToLower`.

Проверьте за один проход, монотонен ли слайс, то есть целиком неубывающий или целиком невозрастающий. На каких входах ошибаются быстрые решения?

Заведите два флага, `up` и `down`, оба `true` в начале: пара с `a[i-1] > a[i]` сбрасывает `up`, пара с `a[i-1] < a[i]` сбрасывает `down`, и слайс монотонен, если уцелел хотя бы один флаг.

Разверните односвязный список на месте. Напишите итеративную версию и скажите, во что обходится рекурсивная в Go.

Пройдите список один раз с `prev` и `cur`: сохраните `cur.Next`, направьте `cur.Next` назад на `prev`, затем сдвиньте оба на узел вперёд.

Дедупликация 200 000 адресов этой функцией занимает около 15 секунд. Какова её временная сложность и как довести её до O(n)?

Сложность равна O(n²): `slices.Contains` просматривает всё, что уже собрано, поэтому при почти уникальных адресах k-й адрес сравнивается с k-1 предыдущими, всего около n²/2 сравнений.

Сгруппируйте список слов по анаграммам, чтобы eat, tea и ate оказались вместе. Что вы используете как ключ map в Go и сколько это стоит?

Дайте каждому слову ключ, общий для всех его анаграмм, и добавляйте слово в `groups[key]`.

Найдите длину самой длинной подстроки без повторяющихся символов за O(n). Как движется окно и что меняется для текста не в ASCII?

Держите окно без повторов и map от каждого символа к позиции, где он встречался последний раз.

Объедините пересекающиеся интервалы, например слоты бронирования [1,3] [2,6] [8,10] [9,12]. Зачем сначала сортировать и сколько это стоит?

Отсортируйте по началу и пройдите один раз: если следующий интервал начинается раньше, чем кончается последний объединённый, растяните его конец до большего из двух; иначе начните новый интервал.

Найдите баг: этот бинарный поиск первой метки времени не раньше t на некоторых входах зависает навсегда.

Цикл смешивает два соглашения: `hi := len(ts)-1` с `lo <= hi` задают закрытый диапазон, которому нужно `hi = mid - 1`, а `hi = mid` относится к полуоткрытому.

Найдите баг: topK на container/heap возвращает k слов, но редко самые частые, и при каждом запуске другой набор.

`h.Push` и `h.Pop` здесь собственные методы типа, которые только дописывают и удаляют последний элемент; порядок кучи поддерживают функции пакета `heap.Push(h, x)` и `heap.Pop(h)`.

Реализуйте LRU-кэш с Get и Put за O(1). Какие две структуры вы сочетаете в Go и почему одной map недостаточно?

Нужна map от ключа к узлу двусвязного списка, который хранит записи от самой недавно использованной к самой давней.

Посчитайте острова в сетке из 0 и 1. BFS или DFS, и почему рекурсивный DFS в Go может упасть на карте 3000×3000?

Пройдите все клетки; каждый раз, встретив ещё не посещённую сушу, засчитайте остров и залейте его через BFS или DFS, отметив все связанные с ней клетки суши.

Два канала отдают числа по возрастанию. Слейте их в один канал по возрастанию. Почему не подходит select по обоим и что меняется для k каналов?

Держите текущую голову каждого входа: прочитайте по одному значению из обоих, отправьте меньшее и дочитывайте только ту сторону, откуда оно взято.

Даны сервисы и сервисы, от которых зависит каждый из них. Верните порядок их запуска или сообщите о цикле, из-за которого это невозможно.

Задача сводится к топологической сортировке.

Напишите конкурентный краулер: пройти по ссылкам от одного URL до глубины 2, скачать каждый URL один раз, не больше 10 загрузок одновременно. Как он понимает, что закончил?

Скачивайте каждую страницу в своей горутине: множество `visited` под мьютексом помечает URL до того, как его запланировать, буферизованный канал ограничивает число одновременных загрузок, а `sync.WaitGroup` считает незаконченные страницы.

Напишите клиентский балансировщик над ненадёжными бэкендами: распределяйте вызовы по кругу (round-robin), а при ошибке пробуйте следующий бэкенд, пока один не ответит или не истечёт контекст.

Держите бэкенды в слайсе и счётчик `atomic.Uint64`: каждый вызов берёт свой стартовый индекс через `Add(1)`, перебирает бэкенды по кругу с этого места и возвращает первый успешный ответ.

Irbisa · Шпаргалка

Live coding на Go

Q: Разверните односвязный список на месте. Напишите итеративную версию и скажите, во что обходится рекурсивная в Go.

Пройдите список один раз с `prev` и `cur`: сохраните `cur.Next`, направьте `cur.Next` назад на `prev`, затем сдвиньте оба на узел вперёд.

Q: Дедупликация 200 000 адресов этой функцией занимает около 15 секунд. Какова её временная сложность и как довести её до O(n)?

Сложность равна O(n²): `slices.Contains` просматривает всё, что уже собрано, поэтому при почти уникальных адресах k-й адрес сравнивается с k-1 предыдущими, всего около n²/2 сравнений.

Q: Найдите длину самой длинной подстроки без повторяющихся символов за O(n). Как движется окно и что меняется для текста не в ASCII?

Держите окно без повторов и map от каждого символа к позиции, где он встречался последний раз.

Big O, хеширование, два указателя, скользящее окно, стек, бинарный поиск, кучи и графы на Go, а также конкурентные задачи вроде пула воркеров с ограничением

Middle-разработчик · 18 вопросов

01
Что такое нотация Big-O и сколько стоят поиск, вставка и удаление в слайсе Go, в map и в отсортированном слайсе?
Big-O описывает, как время работы или память алгоритма растут с размером входа n, без учёта констант: O(1) не растёт, O(n) удваивается вместе с n, O(n²) растёт вчетверо.
02
Напишите функцию, которая возвращает пересечение двух неупорядоченных слайсов любой длины. Сколько она стоит и что нужно сначала уточнить про дубликаты?
Посчитайте элементы одного слайса в map, затем пройдите по второму и оставляйте каждый элемент, чей счётчик ещё больше нуля, уменьшая его: O(n + m) по времени и O(min(n, m)) дополнительной памяти вместо O(n·m) у двух вложенных циклов.
```
// 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
Проверьте, что строка из скобок вроде ([]{}) сбалансирована. Какую структуру вы используете и на каких входах ломается решение, которое просто считает скобки?
Нужен стек: каждую открывающую скобку кладите в него, на закрывающей снимайте верхнюю и проверяйте, что она того же вида.
```
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
Проверьте, является ли строка палиндромом без учёта регистра, пробелов и знаков препинания, чтобы А роза упала на лапу Азора проходила. Почему сравнение s[i] с s[len(s)-1-i] не работает?
Двигайте два указателя с концов к центру, пропускайте всё, что не буква и не цифра, и сравнивайте остальное через 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
Проверьте за один проход, монотонен ли слайс, то есть целиком неубывающий или целиком невозрастающий. На каких входах ошибаются быстрые решения?
Заведите два флага, up и down, оба true в начале: пара с a[i-1] > a[i] сбрасывает up, пара с a[i-1] < a[i] сбрасывает down, и слайс монотонен, если уцелел хотя бы один флаг.
```
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
Разверните односвязный список на месте. Напишите итеративную версию и скажите, во что обходится рекурсивная в Go.
Пройдите список один раз с prev и cur: сохраните cur.Next, направьте cur.Next назад на prev, затем сдвиньте оба на узел вперёд.
```
type Node[T any] struct {	Val  T	Next *Node[T]} func Reverse[T any](head *Node[T]) *Node[T] {…
```
07
Дедупликация 200 000 адресов этой функцией занимает около 15 секунд. Какова её временная сложность и как довести её до 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}
```
Сложность равна O(n²): slices.Contains просматривает всё, что уже собрано, поэтому при почти уникальных адресах k-й адрес сравнивается с k-1 предыдущими, всего около n²/2 сравнений.
08
Сгруппируйте список слов по анаграммам, чтобы eat, tea и ate оказались вместе. Что вы используете как ключ map в Go и сколько это стоит?
Дайте каждому слову ключ, общий для всех его анаграмм, и добавляйте слово в 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++ {…
```
09
Найдите длину самой длинной подстроки без повторяющихся символов за O(n). Как движется окно и что меняется для текста не в ASCII?
Держите окно без повторов и map от каждого символа к позиции, где он встречался последний раз.
```
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
Объедините пересекающиеся интервалы, например слоты бронирования [1,3] [2,6] [8,10] [9,12]. Зачем сначала сортировать и сколько это стоит?
Отсортируйте по началу и пройдите один раз: если следующий интервал начинается раньше, чем кончается последний объединённый, растяните его конец до большего из двух; иначе начните новый интервал.
```
type Interval struct{ Start, End int } func Merge(xs []Interval) []Interval {	if len(xs) == 0 {		return nil	}…
```
11
Найдите баг: этот бинарный поиск первой метки времени не раньше t на некоторых входах зависает навсегда.
```
// 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}
```
Цикл смешивает два соглашения: hi := len(ts)-1 с lo <= hi задают закрытый диапазон, которому нужно hi = mid - 1, а hi = mid относится к полуоткрытому.
12
Найдите баг: topK на container/heap возвращает k слов, но редко самые частые, и при каждом запуске другой набор.
```
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 и h.Pop здесь собственные методы типа, которые только дописывают и удаляют последний элемент; порядок кучи поддерживают функции пакета heap.Push(h, x) и heap.Pop(h).
13
Реализуйте LRU-кэш с Get и Put за O(1). Какие две структуры вы сочетаете в Go и почему одной map недостаточно?
Нужна map от ключа к узлу двусвязного списка, который хранит записи от самой недавно использованной к самой давней.
```
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
Посчитайте острова в сетке из 0 и 1. BFS или DFS, и почему рекурсивный DFS в Go может упасть на карте 3000×3000?
Пройдите все клетки; каждый раз, встретив ещё не посещённую сушу, засчитайте остров и залейте его через BFS или 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
Два канала отдают числа по возрастанию. Слейте их в один канал по возрастанию. Почему не подходит select по обоим и что меняется для k каналов?
Держите текущую голову каждого входа: прочитайте по одному значению из обоих, отправьте меньшее и дочитывайте только ту сторону, откуда оно взято.
```
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)…
```
16
Даны сервисы и сервисы, от которых зависит каждый из них. Верните порядок их запуска или сообщите о цикле, из-за которого это невозможно.
Задача сводится к топологической сортировке.
```
// 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
Напишите конкурентный краулер: пройти по ссылкам от одного URL до глубины 2, скачать каждый URL один раз, не больше 10 загрузок одновременно. Как он понимает, что закончил?
Скачивайте каждую страницу в своей горутине: множество visited под мьютексом помечает URL до того, как его запланировать, буферизованный канал ограничивает число одновременных загрузок, а sync.WaitGroup считает незаконченные страницы.
```
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
Напишите клиентский балансировщик над ненадёжными бэкендами: распределяйте вызовы по кругу (round-robin), а при ошибке пробуйте следующий бэкенд, пока один не ответит или не истечёт контекст.
Держите бэкенды в слайсе и счётчик atomic.Uint64: каждый вызов берёт свой стартовый индекс через Add(1), перебирает бэкенды по кругу с этого места и возвращает первый успешный ответ.
```
type Backend interface {	Invoke(ctx context.Context, req []byte) ([]byte, error)} type Balancer struct {	backends []Backend…
```

Live coding на Go

Что такое нотация Big-O и сколько стоят поиск, вставка и удаление в слайсе Go, в map и в отсортированном слайсе?

Напишите функцию, которая возвращает пересечение двух неупорядоченных слайсов любой длины. Сколько она стоит и что нужно сначала уточнить про дубликаты?

Проверьте, что строка из скобок вроде `([]{})` сбалансирована. Какую структуру вы используете и на каких входах ломается решение, которое просто считает скобки?

Проверьте за один проход, монотонен ли слайс, то есть целиком неубывающий или целиком невозрастающий. На каких входах ошибаются быстрые решения?

Разверните односвязный список на месте. Напишите итеративную версию и скажите, во что обходится рекурсивная в Go.

Дедупликация 200 000 адресов этой функцией занимает около 15 секунд. Какова её временная сложность и как довести её до O(n)?

Сгруппируйте список слов по анаграммам, чтобы `eat`, `tea` и `ate` оказались вместе. Что вы используете как ключ map в Go и сколько это стоит?

Найдите длину самой длинной подстроки без повторяющихся символов за O(n). Как движется окно и что меняется для текста не в ASCII?

Объедините пересекающиеся интервалы, например слоты бронирования `[1,3] [2,6] [8,10] [9,12]`. Зачем сначала сортировать и сколько это стоит?

Найдите баг: этот бинарный поиск первой метки времени не раньше `t` на некоторых входах зависает навсегда.

Найдите баг: `topK` на `container/heap` возвращает `k` слов, но редко самые частые, и при каждом запуске другой набор.

Реализуйте LRU-кэш с `Get` и `Put` за O(1). Какие две структуры вы сочетаете в Go и почему одной map недостаточно?

Посчитайте острова в сетке из `0` и `1`. BFS или DFS, и почему рекурсивный DFS в Go может упасть на карте 3000×3000?

Два канала отдают числа по возрастанию. Слейте их в один канал по возрастанию. Почему не подходит `select` по обоим и что меняется для k каналов?

Даны сервисы и сервисы, от которых зависит каждый из них. Верните порядок их запуска или сообщите о цикле, из-за которого это невозможно.