Алгоритмы: различия между версиями
Artem (обсуждение | вклад) (Новая страница: «= НОД = <pre> </pre>») |
Artem (обсуждение | вклад) |
||
(не показано 39 промежуточных версий этого же участника) | |||
Строка 1: | Строка 1: | ||
= | * [https://www.youtube.com/watch?v=ugGT4T5HcsI Как решать задачи на Leetcode] | ||
* [https://www.youtube.com/watch?v=6h-blOjL43s Почему ты все еще не выучил алгосы? С чего вообще начать? RoadMap для разноса собесов!] | |||
= Сбор информации = | |||
* Читаем задачу | |||
* Понять проблему | |||
* Пересказать своими словами | |||
* Какие данные есть? | |||
* Что нужно найти? | |||
* Какие ограничения? | |||
* Нарисовать проблему | |||
* Нужно ли найти еще данные? | |||
* Уточняйте. Так много и часто, как возможно, пока не наступит момент, что вопросов больше нет. (Как? Почему? Где? Зачем? А здесь? Что, если?) | |||
* Ищите примеры (простые, средние, сложные) | |||
* Где применяется? | |||
* Что решает проблема? | |||
* Кто связан с ней? | |||
* Можно ли менять условия? | |||
* Чего мы не знаем? | |||
* Валидные ли условия? | |||
* Нет ли противоречий? | |||
* Разделить условия на составные части | |||
= Гипотезы = | |||
* '''Какие проблемы уже решали? Попробовать увидеть паттерн, дать поработать интуиции, а потом ее проверить''' | |||
* Какие проблемы мы видели, но в другой форме? | |||
* '''Переберите все возможные техники и алгоритмы, которые знаете''' | |||
* Посмотрите на проблему с разных углов, точек зрения, областей | |||
* Декомпозиция. Может проблема состоит из комбинации других? | |||
* '''Решаем в лоб самым тупым способом - brute force''' | |||
* '''Нарисуйте на бумаге варианты идей''' | |||
* Попытка угадать алгоритм, как черный ящик, используя гипотезу - "А что, если оно вот так работает?" | |||
* '''Уберите все невозможные варианты из решения''' | |||
* '''Найти все corner(extreme) cases вашей проблемы''' | |||
* '''Используйте инверсию (Что, если все наоборот? Как сделать так, чтобы такие условия точно не сработали? Как сделать наоборот хуже? Если я хочу помочь Индии, то какие есть способы, чтобы навредить Индии?)''' | |||
* '''Используйте backwards thinking''' | |||
* '''Решите самую простую версию по данным''' | |||
* Решите самую простую версию по условиям | |||
* Измените упрощенную версию | |||
* Представьте ситуацию, когда все условия соблюдены | |||
* Найдите такую упрощенную версию, которая может быть сведена к более сложной текущей версии, но которую можно решить. | |||
* Рассмотрите более сложную версию(парадоксально, но может помочь) | |||
* Изменить условия. Пробовать решить за O(n), O(nlogn), O(n^2), O(n^3) | |||
* '''Возможно для решения есть формула. Последовательности и тп''' | |||
* '''Сколько состояний у нас есть? Что меняется в процессе работы алгоритма? Что остается неизменным?''' | |||
* Моделируйте, добавляя новые и убирая текущие свойства проблемы. | |||
* Представьте, что решение уже готово. Можем ли мы как-то это использовать? | |||
* '''Итеративное мышление''' | |||
* '''Декларативное решение, рекурсия''' | |||
* '''divide and conquer(разделяй и властвуй)''' - В информатике разделяй и властвуй — это парадигма разработки алгоритмов . Алгоритм разделяй и властвуй рекурсивно разбивает задачу на две или более подзадач одного и того же или связанного типа, пока они не станут достаточно простыми для непосредственного решения. Затем решения подзадач объединяются, чтобы дать решение исходной задачи. | |||
* '''Используйте аналогию''' | |||
* '''Используйте ассоциативное мышление''' | |||
* Используйте индукцию(Способ рассуждения от частных фактов, положений к общим выводам.) | |||
* Используйте дедукцию(Способ рассуждения, при к-ром новое положение выводится чисто логическим путём от общих положений к частным выводам.) | |||
* Решите частные случаи. Specialization | |||
* Решите в общем виде. Generalization | |||
* Inventor's paradox(Парадокс изобретателя — это явление, возникающее при поиске решения проблемы. Вместо того, чтобы решать проблему определённого типа, может оказаться, что проще найти решение более общей проблемы, которое охватывает специфику искомого решения.) | |||
* Можно ли изменить данные? | |||
* Можно ли рекомбинировать проблему и элементы? | |||
* Можно ли трансформировать проблему? | |||
* Можно ли трансформировать похожую проблему? | |||
* Вернуться назад и проверить, все ли мы использовали из условий? | |||
* '''Визуализируйте.''' Представьте, как оно работает. Оживите вещи в задаче | |||
* '''Важен ли порядок?''' | |||
* Какие есть инварианты? (Инвариант — свойство, остающееся неизменным при преобразованиях определённого типа.) | |||
* '''Гуглите идеи''' | |||
* Спрашивайте у других | |||
* Найдите похожую проблему или отдаленно похожую и решите ее | |||
* Придумайте похожую проблему, если не помните ни одной | |||
* '''Какая связь между данными и неизвестным?''' | |||
* '''Brainstorming''' | |||
* '''Reduction to an absurdity''' (представляет собой форму аргументации, которая пытается обосновать утверждение, что противоположный сценарий привел бы к абсурду или противоречию) | |||
* Proof by contradiction (В логике доказательство от противного — это форма доказательства, которая устанавливает истинность или действительность предложения, показывая, что предположение, что предложение ложно, приводит к противоречию) | |||
* '''Создайте всевозможные тестовые данные для проверки''' | |||
* Используйте автоматические fuzzy тесты | |||
* '''Фиксируйте промежуточные решения тестами или отдельными блоками''' | |||
* '''Перечитать условия еще раз''' | |||
* '''Используйте симметрию''' | |||
* '''Рассмотреть разные области знаний''' | |||
* Попробовать смоделировать | |||
* '''Отложить задачу на потом и сменить контекст''' | |||
= Проба гипотез = | |||
* Одну за один проход | |||
* Вовремя понять, если она не работает | |||
* Не бояться оставить ее, если она не работает и искать другую | |||
* Фиксируйте этапы письменно | |||
* Если нужно, be agile, и откатитесь на пару этапов назад | |||
* Не долбитесь головой об стену, если нет прогресса. | |||
= Обдумайте решение = | |||
* Как у вас получилось решить проблему? | |||
* Как еще можно решить? | |||
* Где можно применить в будущем? | |||
* Какие есть похожие проблемы? | |||
* Как можно было сделать это лучше? | |||
* Как можно сделать красивее? | |||
* Проверьте каждый шаг. | |||
* Что мешало вам решить проблему? | |||
* Как избежать этих помех в будущем? | |||
* Как делать это быстрее в будущем? | |||
* О чем вы думали? | |||
* Что вас отвлекало? | |||
* Мы нашли новый паттерн? Стоит запомнить? | |||
= Black Box = | |||
'''Чтобы применять технологию или алгоритм, необязательно знать его устройство.''' | |||
* Используйте готовые решения, структуры и алгоритмы для решения | |||
* Если нужно или интересно, можно изучить их потом | |||
* Как и когда их применять - отдельный навык | |||
* Соберите себе решение из нескольких черных ящиков. | |||
= Яндекс = | |||
Высылаю материалы для подготовки: Статья на хабре о том, как проходят наши интервью: | |||
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/ Здесь задачи, которые очень похожи на те, что мы даем на интервью, первая задача решена, чтобы можно было ознакомиться с самой системой. | |||
* https://www.techinterviewhandbook.org/grind75/ | |||
* https://coderun.yandex.ru/ | |||
* https://old.mccme.ru//free-books//shen/shen-progbook.pdf | |||
Темы и ссылки, где можно лучше подготовиться к алгоритмам: | |||
== 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) по памяти | |||
<pre> | |||
def single_number(nums): | |||
result = 0 | |||
for i in nums: | |||
result ^= i | |||
return result | |||
</pre> | |||
* 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 == | |||
<pre> | |||
# Depth-first search | |||
def search_depth(node, level): | |||
if visited.check(node): | |||
return | |||
visited.add(node) | |||
print(" " * level, "Узел", node.data) | |||
for child in node.links: | |||
search_depth(child, level+1) | |||
</pre> | |||
<pre> | |||
# Breadth-first search | |||
def search_wide(node): | |||
queue = MyQueue() | |||
queue.add(node) | |||
while not queue.is_empty(): | |||
r = queue.remove() | |||
print("Узел", r.data) | |||
visited.add(r) | |||
for n in r.links: | |||
if not visited.check(n): | |||
visited.add(n) | |||
queue.add(n) | |||
</pre> | |||
* 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 == | |||
Жадный алгоритм (англ. Greedy algorithm) — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным. | |||
* 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/ | |||
= Массивы и строки = | |||
= Связные списки = | |||
<pre> | |||
class Node(object): | |||
def __init__(self, data): | |||
self.next = None | |||
self.data = data | |||
def append_to_tail(self, data): | |||
self.get_tail().next = Node(data) | |||
def get_tail(self): | |||
current = self | |||
while current.next is not None: | |||
current = current.next | |||
return current | |||
</pre> | |||
<pre> | |||
class Node(object): | |||
def __init__(self, data): | |||
self.next = None | |||
self.prev = None | |||
self.data = data | |||
def append_to_head(self, data): | |||
current = Node(data) | |||
current.next = self.get_head() | |||
def append_to_tail(self, data): | |||
current = Node(data) | |||
self.get_tail().next = current | |||
def get_head(self): | |||
current = self | |||
while current.prev is not None: | |||
current = current.prev | |||
return current | |||
def get_tail(self): | |||
current = self | |||
while current.next is not None: | |||
current = current.next | |||
return current | |||
</pre> | |||
= Стеки и очереди = | |||
<pre> | |||
class MyQueue(object): | |||
def __init__(self): | |||
self.first = None | |||
self.last = None | |||
def add(self, data): | |||
current = Node(data) | |||
if self.last is not None: | |||
self.last.next = current | |||
self.last = current | |||
if self.first is None: | |||
self.first = self.last | |||
def remove(self): | |||
if self.first is None: | |||
return None | |||
data = self.first.data | |||
self.first = self.first.next | |||
if self.first is None: | |||
self.last = None | |||
return data | |||
def peek(self): | |||
if self.first is None: | |||
return None | |||
return self.first.data | |||
def is_empty(self): | |||
return self.first is None | |||
</pre> | |||
<pre> | |||
class Stack(object): | |||
def __init__(self): | |||
self.top = None | |||
def pop(self): | |||
if self.top is None: | |||
return None | |||
data = self.top.data | |||
self.top = self.top.next | |||
return data | |||
def push(self, data): | |||
current = Node(data) | |||
current.next = self.top | |||
self.top = current | |||
def peek(self): | |||
if self.top is None: | |||
return None | |||
return self.top.data | |||
def is_empty(self): | |||
return self.top is None | |||
</pre> | |||
= Деревья и графы = | |||
<pre> | <pre> | ||
class Node(object): | |||
def __init__(self, data): | |||
self.parent = None | |||
self.children = set() | |||
self.data = data | |||
def append(self, node): | |||
node.parent = self | |||
self.children.add(node) | |||
return self | |||
</pre> | |||
= Операции с битами = | |||
= Головоломки = | |||
= Сортировка = | |||
== Выборка == | |||
<pre> | |||
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)) | |||
} | |||
</pre> | |||
== Пузырек == | |||
<pre> | |||
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)) | |||
} | |||
</pre> | |||
= Bin Search = | |||
<pre> | |||
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 | |||
</pre> | |||
= НОД и НОК = | |||
<pre> | |||
// 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) | |||
} | |||
</pre> | |||
= np_random_choice = | |||
<pre> | |||
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 | |||
</pre> | |||
= merge intervals = | |||
<pre> | |||
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, right := input[0][0], 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, right = input[i][0], 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)) | |||
} | |||
</pre> | </pre> |
Текущая версия от 17:21, 21 ноября 2024
- Как решать задачи на Leetcode
- Почему ты все еще не выучил алгосы? С чего вообще начать? RoadMap для разноса собесов!
Сбор информации
- Читаем задачу
- Понять проблему
- Пересказать своими словами
- Какие данные есть?
- Что нужно найти?
- Какие ограничения?
- Нарисовать проблему
- Нужно ли найти еще данные?
- Уточняйте. Так много и часто, как возможно, пока не наступит момент, что вопросов больше нет. (Как? Почему? Где? Зачем? А здесь? Что, если?)
- Ищите примеры (простые, средние, сложные)
- Где применяется?
- Что решает проблема?
- Кто связан с ней?
- Можно ли менять условия?
- Чего мы не знаем?
- Валидные ли условия?
- Нет ли противоречий?
- Разделить условия на составные части
Гипотезы
- Какие проблемы уже решали? Попробовать увидеть паттерн, дать поработать интуиции, а потом ее проверить
- Какие проблемы мы видели, но в другой форме?
- Переберите все возможные техники и алгоритмы, которые знаете
- Посмотрите на проблему с разных углов, точек зрения, областей
- Декомпозиция. Может проблема состоит из комбинации других?
- Решаем в лоб самым тупым способом - brute force
- Нарисуйте на бумаге варианты идей
- Попытка угадать алгоритм, как черный ящик, используя гипотезу - "А что, если оно вот так работает?"
- Уберите все невозможные варианты из решения
- Найти все corner(extreme) cases вашей проблемы
- Используйте инверсию (Что, если все наоборот? Как сделать так, чтобы такие условия точно не сработали? Как сделать наоборот хуже? Если я хочу помочь Индии, то какие есть способы, чтобы навредить Индии?)
- Используйте backwards thinking
- Решите самую простую версию по данным
- Решите самую простую версию по условиям
- Измените упрощенную версию
- Представьте ситуацию, когда все условия соблюдены
- Найдите такую упрощенную версию, которая может быть сведена к более сложной текущей версии, но которую можно решить.
- Рассмотрите более сложную версию(парадоксально, но может помочь)
- Изменить условия. Пробовать решить за O(n), O(nlogn), O(n^2), O(n^3)
- Возможно для решения есть формула. Последовательности и тп
- Сколько состояний у нас есть? Что меняется в процессе работы алгоритма? Что остается неизменным?
- Моделируйте, добавляя новые и убирая текущие свойства проблемы.
- Представьте, что решение уже готово. Можем ли мы как-то это использовать?
- Итеративное мышление
- Декларативное решение, рекурсия
- divide and conquer(разделяй и властвуй) - В информатике разделяй и властвуй — это парадигма разработки алгоритмов . Алгоритм разделяй и властвуй рекурсивно разбивает задачу на две или более подзадач одного и того же или связанного типа, пока они не станут достаточно простыми для непосредственного решения. Затем решения подзадач объединяются, чтобы дать решение исходной задачи.
- Используйте аналогию
- Используйте ассоциативное мышление
- Используйте индукцию(Способ рассуждения от частных фактов, положений к общим выводам.)
- Используйте дедукцию(Способ рассуждения, при к-ром новое положение выводится чисто логическим путём от общих положений к частным выводам.)
- Решите частные случаи. Specialization
- Решите в общем виде. Generalization
- Inventor's paradox(Парадокс изобретателя — это явление, возникающее при поиске решения проблемы. Вместо того, чтобы решать проблему определённого типа, может оказаться, что проще найти решение более общей проблемы, которое охватывает специфику искомого решения.)
- Можно ли изменить данные?
- Можно ли рекомбинировать проблему и элементы?
- Можно ли трансформировать проблему?
- Можно ли трансформировать похожую проблему?
- Вернуться назад и проверить, все ли мы использовали из условий?
- Визуализируйте. Представьте, как оно работает. Оживите вещи в задаче
- Важен ли порядок?
- Какие есть инварианты? (Инвариант — свойство, остающееся неизменным при преобразованиях определённого типа.)
- Гуглите идеи
- Спрашивайте у других
- Найдите похожую проблему или отдаленно похожую и решите ее
- Придумайте похожую проблему, если не помните ни одной
- Какая связь между данными и неизвестным?
- Brainstorming
- Reduction to an absurdity (представляет собой форму аргументации, которая пытается обосновать утверждение, что противоположный сценарий привел бы к абсурду или противоречию)
- Proof by contradiction (В логике доказательство от противного — это форма доказательства, которая устанавливает истинность или действительность предложения, показывая, что предположение, что предложение ложно, приводит к противоречию)
- Создайте всевозможные тестовые данные для проверки
- Используйте автоматические fuzzy тесты
- Фиксируйте промежуточные решения тестами или отдельными блоками
- Перечитать условия еще раз
- Используйте симметрию
- Рассмотреть разные области знаний
- Попробовать смоделировать
- Отложить задачу на потом и сменить контекст
Проба гипотез
- Одну за один проход
- Вовремя понять, если она не работает
- Не бояться оставить ее, если она не работает и искать другую
- Фиксируйте этапы письменно
- Если нужно, be agile, и откатитесь на пару этапов назад
- Не долбитесь головой об стену, если нет прогресса.
Обдумайте решение
- Как у вас получилось решить проблему?
- Как еще можно решить?
- Где можно применить в будущем?
- Какие есть похожие проблемы?
- Как можно было сделать это лучше?
- Как можно сделать красивее?
- Проверьте каждый шаг.
- Что мешало вам решить проблему?
- Как избежать этих помех в будущем?
- Как делать это быстрее в будущем?
- О чем вы думали?
- Что вас отвлекало?
- Мы нашли новый паттерн? Стоит запомнить?
Black Box
Чтобы применять технологию или алгоритм, необязательно знать его устройство.
- Используйте готовые решения, структуры и алгоритмы для решения
- Если нужно или интересно, можно изучить их потом
- Как и когда их применять - отдельный навык
- Соберите себе решение из нескольких черных ящиков.
Яндекс
Высылаю материалы для подготовки: Статья на хабре о том, как проходят наши интервью: 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/ Здесь задачи, которые очень похожи на те, что мы даем на интервью, первая задача решена, чтобы можно было ознакомиться с самой системой.
- https://www.techinterviewhandbook.org/grind75/
- https://coderun.yandex.ru/
- https://old.mccme.ru//free-books//shen/shen-progbook.pdf
Темы и ссылки, где можно лучше подготовиться к алгоритмам:
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
# Depth-first search def search_depth(node, level): if visited.check(node): return visited.add(node) print(" " * level, "Узел", node.data) for child in node.links: search_depth(child, level+1)
# Breadth-first search def search_wide(node): queue = MyQueue() queue.add(node) while not queue.is_empty(): r = queue.remove() print("Узел", r.data) visited.add(r) for n in r.links: if not visited.check(n): visited.add(n) queue.add(n)
- 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
Жадный алгоритм (англ. Greedy algorithm) — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.
- 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/
Массивы и строки
Связные списки
class Node(object): def __init__(self, data): self.next = None self.data = data def append_to_tail(self, data): self.get_tail().next = Node(data) def get_tail(self): current = self while current.next is not None: current = current.next return current
class Node(object): def __init__(self, data): self.next = None self.prev = None self.data = data def append_to_head(self, data): current = Node(data) current.next = self.get_head() def append_to_tail(self, data): current = Node(data) self.get_tail().next = current def get_head(self): current = self while current.prev is not None: current = current.prev return current def get_tail(self): current = self while current.next is not None: current = current.next return current
Стеки и очереди
class MyQueue(object): def __init__(self): self.first = None self.last = None def add(self, data): current = Node(data) if self.last is not None: self.last.next = current self.last = current if self.first is None: self.first = self.last def remove(self): if self.first is None: return None data = self.first.data self.first = self.first.next if self.first is None: self.last = None return data def peek(self): if self.first is None: return None return self.first.data def is_empty(self): return self.first is None
class Stack(object): def __init__(self): self.top = None def pop(self): if self.top is None: return None data = self.top.data self.top = self.top.next return data def push(self, data): current = Node(data) current.next = self.top self.top = current def peek(self): if self.top is None: return None return self.top.data def is_empty(self): return self.top is None
Деревья и графы
class Node(object): def __init__(self, data): self.parent = None self.children = set() self.data = data def append(self, node): node.parent = self self.children.add(node) return self
Операции с битами
Головоломки
Сортировка
Выборка
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)) }
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
НОД и НОК
// 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) }
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, right := input[0][0], 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, right = input[i][0], 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)) }