Алгоритмы
Перейти к навигации
Перейти к поиску
Яндекс
Высылаю материалы для подготовки: Статья на хабре о том, как проходят наши интервью: 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) по памяти 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:
https://leetcode.com/problems/valid-parentheses/
dfs/bfs:
https://leetcode.com/problems/number-of-islands/ https://leetcode.com/problems/remove-invalid-parentheses/
sort:
https://leetcode.com/problems/merge-intervals/
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/
НОД и НОК
// 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 {
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))
}