Алгоритмы: различия между версиями
Перейти к навигации
Перейти к поиску
Artem (обсуждение | вклад) Нет описания правки |
Artem (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
* [https://www.youtube.com/watch?v=ugGT4T5HcsI Как решать задачи на Leetcode] | * [https://www.youtube.com/watch?v=ugGT4T5HcsI Как решать задачи на Leetcode] | ||
* [https://www.youtube.com/watch?v=6h-blOjL43s Почему ты все еще не выучил алгосы? С чего вообще начать? RoadMap для разноса собесов!] | * [https://www.youtube.com/watch?v=6h-blOjL43s Почему ты все еще не выучил алгосы? С чего вообще начать? RoadMap для разноса собесов!] | ||
= Сбор информации = | |||
* Читаем задачу | * Читаем задачу | ||
| Строка 21: | Строка 23: | ||
* Разделить условия на составные части | * Разделить условия на составные части | ||
= Гипотезы = | |||
* Какие проблемы уже решали? Попробовать увидеть паттерн, дать поработать интуиции, а потом ее проверить | |||
* Какие проблемы мы видели, но в другой форме? | |||
* Переберите все возможные техники и алгоритмы, которые знаете | |||
* Посмотрите на проблему с разных углов, точек зрения, областей | |||
* Декомпозиция. Может проблема состоит из комбинации других? | |||
* Решаем в лоб самым тупым способом - brute force | |||
* Нарисуйте на бумаге варианты идей | |||
* Попытка угадать алгоритм, как черный ящик, используя гипотезу - "А что, если оно вот так работает?" | |||
* Уберите все невозможные варианты из решения | |||
* Найти все corner(extreme) cases вашей проблемы | |||
* | |||
= Яндекс = | = Яндекс = | ||
Версия от 03:24, 20 ноября 2024
- Как решать задачи на Leetcode
- Почему ты все еще не выучил алгосы? С чего вообще начать? RoadMap для разноса собесов!
Сбор информации
- Читаем задачу
- Понять проблему
- Пересказать своими словами
- Какие данные есть?
- Что нужно найти?
- Какие ограничения?
- Нарисовать проблему
- Нужно ли найти еще данные?
- Уточняйте. Так много и часто, как возможно, пока не наступит момент, что вопросов больше нет. (Как? Почему? Где? Зачем? А здесь? Что, если?)
- Ищите примеры (простые, средние, сложные)
- Где применяется?
- Что решает проблема?
- Кто связан с ней?
- Можно ли менять условия?
- Чего мы не знаем?
- Валидные ли условия?
- Нет ли противоречий?
- Разделить условия на составные части
Гипотезы
- Какие проблемы уже решали? Попробовать увидеть паттерн, дать поработать интуиции, а потом ее проверить
- Какие проблемы мы видели, но в другой форме?
- Переберите все возможные техники и алгоритмы, которые знаете
- Посмотрите на проблему с разных углов, точек зрения, областей
- Декомпозиция. Может проблема состоит из комбинации других?
- Решаем в лоб самым тупым способом - brute force
- Нарисуйте на бумаге варианты идей
- Попытка угадать алгоритм, как черный ящик, используя гипотезу - "А что, если оно вот так работает?"
- Уберите все невозможные варианты из решения
- Найти все corner(extreme) cases вашей проблемы
Яндекс
Высылаю материалы для подготовки: Статья на хабре о том, как проходят наши интервью: 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))
}