Алгоритмы
Перейти к навигации
Перейти к поиску
- Как решать задачи на Leetcode
- Почему ты все еще не выучил алгосы? С чего вообще начать? RoadMap для разноса собесов!
Яндекс
Высылаю материалы для подготовки: Статья на хабре о том, как проходят наши интервью: https://habr.com/ru/company/yandex/blog/449890/
В ней дана ссылка на два видео на youtube с разборами задач (одна легкая, вторая сложная): https://youtube.com/watch?v=0yxjWwoZtLw и https://youtube.com/watch?v=zU-LndSG5RE
Попробуйте порешать контест https://contest.yandex.ru/contest/8458/enter/ Здесь задачи, которые очень похожи на те, что мы даем на интервью, первая задача решена, чтобы можно было ознакомиться с самой системой.
Темы и ссылки, где можно лучше подготовиться к алгоритмам:
linked lists
- https://leetcode.com/problems/merge-k-sorted-lists/
- https://leetcode.com/problems/linked-list-cycle/
- https://leetcode.com/problems/add-two-numbers/
- https://leetcode.com/problems/reverse-linked-list/
binary search
- https://leetcode.com/problems/binary-search/
- https://leetcode.com/problems/guess-number-higher-or-lower/
- https://leetcode.com/problems/search-a-2d-matrix/
- https://leetcode.com/problems/search-in-rotated-sorted-array/
- https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
- https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
hash table
- https://leetcode.com/problems/single-number/ - решить за O(1) по памяти
def single_number(nums):
result = 0
for i in nums:
result ^= i
return result
- https://leetcode.com/problems/two-sum/
- https://leetcode.com/problems/4sum/
- https://leetcode.com/problems/group-anagrams/
- https://leetcode.com/problems/valid-anagram/
- https://leetcode.com/problems/find-all-anagrams-in-a-string/
queue/stack
dfs/bfs
- https://leetcode.com/problems/number-of-islands/
- https://leetcode.com/problems/remove-invalid-parentheses/
sort
heap/hash
- https://leetcode.com/problems/top-k-frequent-words/
- https://leetcode.com/problems/top-k-frequent-elements/
two pointers
- https://leetcode.com/problems/container-with-most-water/
- https://leetcode.com/problems/partition-labels/
sliding window
- https://leetcode.com/problems/sliding-window-median/
- https://leetcode.com/problems/sliding-window-maximum/
- https://leetcode.com/problems/longest-repeating-character-replacement/
tree
- https://leetcode.com/problems/same-tree/
- https://leetcode.com/problems/symmetric-tree/
- https://leetcode.com/problems/balanced-binary-tree/
- https://leetcode.com/problems/path-sum-ii/
greedy problems
- https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
- https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
- https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
- https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
Сортировка
Выборка
package main
import (
"fmt"
)
func selectionSort(input []int) []int {
if len(input) <= 1 {
return input
}
for i := 0; i < len(input); i++ {
min := i
for j := i + 1; j < len(input); j++ {
if input[j] < input[min] {
min = j
}
}
if min != i {
input[i], input[min] = input[min], input[i]
}
}
return input
}
func main() {
input := []int{-2, 5, 10, 17, -45, 44, 21, 2, 1, 4}
fmt.Println(input)
fmt.Println(selectionSort(input))
}
Пузырек
package main
import (
"fmt"
)
func bubbleSort(input []int) []int {
if len(input) <= 1 {
return input
}
for {
moved := false
for i := 0; i < len(input)-1; i++ {
if input[i] > input[i+1] {
input[i], input[i+1] = input[i+1], input[i]
moved = true
}
}
if !moved {
break
}
}
return input
}
func main() {
input := []int{-2, 5, 10, 17, -45, 44, 21, 2, 1, 4}
fmt.Println(input)
fmt.Println(bubbleSort(input))
}
НОД и НОК
// fast!
func gcd(a uint, b uint) uint {
for a != 0 && b != 0 {
if a > b {
a = a % b
} else {
b = b % a
}
}
return a + b
}
func gcd2(a uint, b uint) uint {
for a != b {
if a > b {
a = a - b
} else {
b = b - a
}
}
return a + b
}
func lcm(a uint, b uint) uint {
return (a * b) / gcd(a, b)
}
Bin Search
def search(arr, value):
if not arr:
return False
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == value:
return True
elif arr[mid] < value:
left = mid + 1
else:
right = mid - 1
return False
np_random_choice
import random
def np_random_choice(size, probes):
cumsum = [sum(probes[:i+1]) for i, p in enumerate(probes)]
result = []
for probe in range(size):
rnd = random.random()
i = -1
while rnd > 0:
i += 1
rnd = rnd - cumsum[i]
result.append(i)
return result
merge intervals
package main
import (
"fmt"
"sort"
)
func mergeIntervals(input [][2]int) [][2]int {
if len(input) <= 1 {
return input
}
sort.Slice(input, func(i, j int) bool {
return input[i][0] < input[j][0] || input[i][1] < input[j][1]
})
var result [][2]int
left := input[0][0]
right := input[0][1]
for i := 0; i < len(input); i++ {
if right >= input[i][0] {
right = input[i][1]
} else {
result = append(result, [2]int{left, right})
left = input[i][0]
right = input[i][1]
}
}
result = append(result, [2]int{left, right})
return result
}
func main() {
input := [][2]int{{2, 8}, {2, 6}, {1, 3}, {8, 10}, {15, 18}}
fmt.Println(input)
fmt.Println(mergeIntervals(input))
}