Алгоритмы

Материал из Artem Aleksashkin's Wiki
Перейти к навигации Перейти к поиску

Сбор информации

  • Читаем задачу
  • Понять проблему
  • Пересказать своими словами
  • Какие данные есть?
  • Что нужно найти?
  • Какие ограничения?
  • Нарисовать проблему
  • Нужно ли найти еще данные?
  • Уточняйте. Так много и часто, как возможно, пока не наступит момент, что вопросов больше нет. (Как? Почему? Где? Зачем? А здесь? Что, если?)
  • Ищите примеры (простые, средние, сложные)
  • Где применяется?
  • Что решает проблема?
  • Кто связан с ней?
  • Можно ли менять условия?
  • Чего мы не знаем?
  • Валидные ли условия?
  • Нет ли противоречий?
  • Разделить условия на составные части

Гипотезы

  • Какие проблемы уже решали? Попробовать увидеть паттерн, дать поработать интуиции, а потом ее проверить
  • Какие проблемы мы видели, но в другой форме?
  • Переберите все возможные техники и алгоритмы, которые знаете
  • Посмотрите на проблему с разных углов, точек зрения, областей
  • Декомпозиция. Может проблема состоит из комбинации других?
  • Решаем в лоб самым тупым способом - 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/ Здесь задачи, которые очень похожи на те, что мы даем на интервью, первая задача решена, чтобы можно было ознакомиться с самой системой.

Темы и ссылки, где можно лучше подготовиться к алгоритмам:

linked lists

binary search

hash table

def single_number(nums):
    result = 0
    for i in nums:
        result ^= i
    return result

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)

sort

heap/hash

two pointers

sliding window

tree

greedy problems

Жадный алгоритм (англ. Greedy algorithm) — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.

Массивы и строки

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

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 j := len(input) - 1; j > 0; j-- {
		moved := false
		for i := 0; i < j; 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))
}
Источник — http://wiki.aleksashkin.net/index.php?title=Алгоритмы&oldid=3386