- Что такое структура данных?
Структура данных — это способ организации и хранения данных в памяти компьютера для эффективного доступа и модификации. Примеры: массивы, списки, стеки, очереди, деревья, графы, хэш-таблицы. Выбор структуры данных напрямую влияет на производительность алгоритмов.
- Чем массив отличается от среза?
Массив в Go имеет фиксированную длину, задаваемую при создании. Срез — динамическая обёртка над массивом, может изменять размер (через append).
arr := [3]int{1, 2, 3} // массив длиной 3
slice := []int{1, 2, 3} // срез
slice = append(slice, 4) // [1,2,3,4]
- Как реализован slice внутри Go?
Указатель на подлежащий массив
Длина (количество элементов)
Ёмкость (максимально возможное число элементов до перевыделения памяти)
slice := make([]int, 3, 5)
fmt.Println(len(slice)) // 3
fmt.Println(cap(slice)) // 5
https://stepik.org/lesson/1939232/step/3?unit=1965970
- Что такое связанный список?
Связанный список — структура данных, где каждый элемент (узел) хранит значение и указатель на следующий элемент. В отличие от массива, элементы могут находиться в разных местах памяти.
type Node struct {
value int
next *Node
}
func main() {
n1 := &Node{value: 1}
n2 := &Node{value: 2}
n1.next = n2
fmt.Println(n1.value, “->”, n1.next.value) // 1 -> 2
https://stepik.org/lesson/1939232/step/4?unit=1965970
- Какие бывают виды списков (односвязный, двусвязный)?
Односвязный список: каждый узел хранит указатель только на следующий элемент. Двусвязный список: у каждого узла два указателя — на следующий и предыдущий элемент. Это упрощает удаление и вставку, но требует больше памяти.
- Чем список отличается от массива?
Массив — фиксированный размер, быстрый доступ по индексу (O(1)), дорогостоящая вставка/удаление.
Список — динамический размер, вставка/удаление O(1) при известном месте, но доступ к элементу O(n).
- Что такое стек и как он работает?
Стек — структура данных LIFO (last in, first out). Последний добавленный элемент извлекается первым.
type Stack []int
func (s *Stack) Push(v int) {
s = append(s, v)
}
func (s Stack) Pop() int {
l := len(s)
if l == 0 { panic(“empty stack”) }
v := (*s)[l-1]
s = (s)[:l-1]
return v
}
func main() {
var st Stack
st.Push(10)
st.Push(20)
fmt.Println(st.Pop()) // 20
}
https://stepik.org/lesson/1939232/step/7?unit=1965970
- Что такое очередь и чем она отличается от стека?
Очередь — структура данных FIFO (first in, first out). В отличие от стека, элементы извлекаются в порядке добавления.
type Queue []int
func (q *Queue) Enqueue(v int) {
q = append(q, v)
}
func (q Queue) Dequeue() int {
if len(q) == 0 { panic(“empty queue”) }
v := (*q)[0]
q = (q)[1:]
return v
}
func main() {
var q Queue
q.Enqueue(1)
q.Enqueue(2)
fmt.Println(q.Dequeue()) // 1
}
https://stepik.org/lesson/1939232/step/8?unit=1965970
- Что такое очередь с приоритетами?
Очередь с приоритетами возвращает элементы не в порядке вставки, а по приоритету (обычно — наибольшему или наименьшему значению). В Go можно реализовать через container/heap.
import (
“container/heap”
“fmt”
)
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } // min-heap
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { h = append(h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func main() {
h := &IntHeap{3, 1, 4}
heap.Init(h)
heap.Push(h, 2)
fmt.Println(heap.Pop(h)) // 1 (минимум)
}
https://stepik.org/lesson/1939232/step/9?unit=1965970
- Что такое хэш-таблица и как она работает?
Хэш-таблица хранит пары «ключ-значение». Ключ пропускается через хэш-функцию, которая вычисляет индекс в массиве. Для разрешения коллизий используют метод цепочек или открытую адресацию.
m := make(map[string]int)
m[“alice”] = 25
m[“bob”] = 30
fmt.Println(m[“alice”]) // 25
https://stepik.org/lesson/1939232/step/10?unit=1965970
- Чем отличается открытая адресация от метода цепочек?
Оба метода решают проблему коллизий в хэш-таблице.
Метод цепочек: каждая ячейка хранит список (цепочку) элементов с одинаковым хэшом. Просто реализуется, но требует выделения памяти под списки.
Открытая адресация: все элементы хранятся в массиве. При коллизии ищется следующая свободная ячейка (линейное/квадратичное пробирование или двойное хэширование). Экономит память, но таблица должна быть неплотной (load factor < 0.7).
- Как устроены map в Go?
В Go map реализован как хэш-таблица с открытой адресацией и использованием бакетов. Каждый бакет хранит до 8 пар «ключ-значение». При переполнении создаётся новый бакет, связанный со старым. При высоком коэффициенте загрузки выполняется rehash (увеличение размера таблицы). Пример:
m := make(map[string]int)
m[“apple”] = 5
m[“orange”] = 10
fmt.Println(m[“apple”]) // 5
- Что такое бинарное дерево?
Бинарное дерево — иерархическая структура, где каждый узел имеет не более двух потомков: left и right. Используется для поиска, сортировки и представления данных.
type Node struct {
value int
left *Node
right *Node
}
func main() {
root := &Node{value: 10}
root.left = &Node{value: 5}
root.right = &Node{value: 15}
fmt.Println(root.left.value) // 5
}
https://stepik.org/lesson/1939232/step/13?unit=1965970
- Чем отличается бинарное дерево поиска от обычного?
В обычном дереве нет строгих правил расположения узлов. В бинарном дереве поиска (BST) выполняется условие:
Все значения в левом поддереве < корня
Все значения в правом поддереве > корня
Это позволяет выполнять поиск за O(log n) в сбалансированном дереве.
- Что такое сбалансированные деревья (AVL, красно-чёрные)?
Сбалансированные деревья автоматически поддерживают высоту ~O(log n), чтобы избежать деградации в линейный список.
AVL — поддерживает разницу высот поддеревьев ≤ 1. Быстрый поиск, но дорогие вставки/удаления.
Красно-чёрные — менее строгое балансирование, но более быстрые вставки/удаления.
- Что такое B-дерево и где оно используется?
B-дерево — сбалансированное поисковое дерево, где каждый узел может содержать несколько ключей. Глубина минимальна, так как узлы широкие. Используется в базах данных и файловых системах, где важно минимизировать количество обращений к диску.
- Чем отличается граф от дерева?
Дерево — частный случай графа без циклов, связный и имеет n-1 ребро при n вершинах.
Граф — обобщённая структура: может быть направленным/ненаправленным, содержать циклы.
- Какие бывают виды графов?
По направленности: ориентированные (digraph) и неориентированные
По весу: взвешенные и невзвешенные
По плотности: плотные и разреженные
По наличию циклов: ациклические и циклические
Специальные: дерево (связный ациклический граф), DAG (ориентированный ациклический граф)
- Как работает BFS?
BFS (поиск в ширину) обходит граф слоями от стартовой вершины. Использует очередь. Применяется для поиска кратчайшего пути в невзвешенных графах.
func BFS(start int, graph map[int][]int) {
visited := make(map[int]bool)
queue := []int{start}
for len(queue) > 0 {
v := queue[0]
queue = queue[1:]
if visited[v] {
continue
}
visited[v] = true
fmt.Println(v)
for _, nei := range graph[v] {
if !visited[nei] {
queue = append(queue, nei)
}
} }https://stepik.org/lesson/1939233/step/3?unit=1965971
- Как работает DFS?
DFS (поиск в глубину) идёт вглубь по каждому пути, пока возможно. Реализуется рекурсией или стеком. Применяется для топологической сортировки, поиска компонент связности.
func DFS(v int, graph map[int][]int, visited map[int]bool) {
if visited[v] {
return
}
visited[v] = true
fmt.Println(v)
for _, nei := range graph[v] {
DFS(nei, graph, visited)
}
}
https://stepik.org/lesson/1939233/step/4?unit=1965971
- Что такое алгоритм Дейкстры?
Алгоритм Дейкстры находит кратчайшие пути от стартовой вершины до всех остальных в графе с неотрицательными весами. Использует жадный подход и очередь с приоритетами.
func Dijkstra(graph map[int]map[int]int, start int) map[int]int {
dist := make(map[int]int)
for v := range graph {
dist[v] = 1«31 - 1 // бесконечность
}
dist[start] = 0
visited := make(map[int]bool)
for len(visited) < len(graph) {
u := -1
minDist := 1<<31 - 1
for v, d := range dist {
if !visited[v] && d < minDist {
u = v
minDist = d
}
}
if u == -1 {
break
}
visited[u] = true
for nei, w := range graph[u] {
if dist[u]+w < dist[nei] {
dist[nei] = dist[u] + w
}
}
}
return disthttps://stepik.org/lesson/1939233/step/5?unit=1965971
- Что такое алгоритм Беллмана–Форда?
Алгоритм Беллмана–Форда ищет кратчайшие пути от одной вершины до всех остальных, работает даже с отрицательными весами рёбер (но не с отрицательными циклами). Сложность — O(V·E). Также он позволяет обнаружить наличие отрицательного цикла.
Пример реализации:
type Edge struct {
from, to, weight int
}
func BellmanFord(edges []Edge, V, start int) []int {
dist := make([]int, V)
for i := range dist {
dist[i] = 1«31 - 1 // “бесконечность”
}
dist[start] = 0
for i := 0; i < V-1; i++ {
for _, e := range edges {
if dist[e.from] != 1<<31-1 && dist[e.from]+e.weight < dist[e.to] {
dist[e.to] = dist[e.from] + e.weight
}
}
}
return dist }https://stepik.org/lesson/1939233/step/6?unit=1965971
- Как работает алгоритм Флойда–Уоршелла?
Алгоритм Флойда–Уоршелла ищет кратчайшие пути между всеми парами вершин графа. Он основан на динамическом программировании и имеет сложность O(V³).
Пример реализации:
func FloydWarshall(matrix [][]int) [][]int {
n := len(matrix)
dist := make([][]int, n)
for i := range dist {
dist[i] = make([]int, n)
copy(dist[i], matrix[i])
}
for k := 0; k < n; k++ {
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if dist[i][k]+dist[k][j] < dist[i][j] {
dist[i][j] = dist[i][k] + dist[k][j]
}
}
}
}
return dist }https://stepik.org/lesson/1939233/step/7?unit=1965971
- Что такое минимальное остовное дерево?
Минимальное остовное дерево (MST) — это подмножество рёбер связного графа, которое соединяет все вершины при минимальной сумме весов. Используется, например, в сетевых топологиях, задачах оптимизации и маршрутизации.
