Алгоритмы

• Как решать задачи на 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

• https://leetcode.com/problems/valid-parentheses/

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

• 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/

Связные списки

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))
}