Алгоритмы — easy LeetCode для собеса

На скрининге дают 1–2 простых задачи. Не нужно знать 500. Нужно уметь выбрать паттерн, проговорить сложность и написать чистый код с тестами.

Категории и эталонные задачи

Хэш-таблицы

• Two-Sum — leetcode.com/problems/two-sum
• Contains Duplicate — leetcode.com/problems/contains-duplicate
• Unique Occurrences — leetcode.com/problems/unique-number-of-occurrences

Паттерн: один проход + lookup в map за O(1) → O(n) общая.

Два указателя

• Reverse String — leetcode.com/problems/reverse-string
• Valid Palindrome — leetcode.com/problems/valid-palindrome
• Move Zeroes — leetcode.com/problems/move-zeroes
• Squares of Sorted Array — leetcode.com/problems/squares-of-a-sorted-array

Паттерн: два индекса с разных концов или один отстаёт от другого.

Префиксная сумма

• Range Sum Query — leetcode.com/problems/range-sum-query-immutable
• Pivot Index — leetcode.com/problems/find-pivot-index
• Highest Altitude — leetcode.com/problems/find-the-highest-altitude

Паттерн: накапливаем сумму, считаем диапазон через разность.

Стек

• Valid Parentheses — leetcode.com/problems/valid-parentheses

Паттерн: открывающую скобку → push, закрывающую → проверить top + pop.

Строки / Математика

• Roman to Integer — leetcode.com/problems/roman-to-integer
• Reverse Integer — leetcode.com/problems/reverse-integer
• String to Integer (atoi) — leetcode.com/problems/string-to-integer-atoi

Шаблон решения на Go

// solution.go
package twosum

func TwoSum(nums []int, target int) []int {
    seen := make(map[int]int, len(nums))
    for i, n := range nums {
        if j, ok := seen[target-n]; ok {
            return []int{j, i}
        }
        seen[n] = i
    }
    return nil
}

// solution_test.go
package twosum

import (
    "reflect"
    "testing"
)

func TestTwoSum(t *testing.T) {
    cases := []struct {
        name   string
        nums   []int
        target int
        want   []int
    }{
        {"basic", []int{2, 7, 11, 15}, 9, []int{0, 1}},
        {"reorder", []int{3, 2, 4}, 6, []int{1, 2}},
        {"dup", []int{3, 3}, 6, []int{0, 1}},
        {"none", []int{1, 2}, 5, nil},
    }
    for _, tc := range cases {
        t.Run(tc.name, func(t *testing.T) {
            got := TwoSum(tc.nums, tc.target)
            if !reflect.DeepEqual(got, tc.want) {
                t.Errorf("got %v, want %v", got, tc.want)
            }
        })
    }
}

Что прорешать

В рамках финального задания спринта — 5 задач:

1. Two-Sum (хэш)
2. Valid Parentheses (стек)
3. Move Zeroes (два указателя)
4. Squares of Sorted Array (два указателя)
5. Pivot Index (префиксная сумма)

В каждой папке: solution.go + solution_test.go (минимум 5 кейсов). В README.md — паттерн и сложность по времени и памяти.

Совет на интервью

1. Проговори сначала что понял из условия.
2. Скажи паттерн и сложность ДО написания кода.
3. Пиши, обсуждая каждый шаг.
4. После решения — обсуди edge case'ы (пустой массив, отрицательные, overflow для Reverse Integer).

Это ценится больше, чем «слепить решение по памяти».