Алгоритмы: различия между версиями

Материал из Artem Aleksashkin's Wiki
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 69: Строка 69:
Попробуйте порешать контест
Попробуйте порешать контест
https://contest.yandex.ru/contest/8458/enter/ Здесь задачи, которые очень похожи на те, что мы даем на интервью, первая задача решена, чтобы можно было ознакомиться с самой системой.
https://contest.yandex.ru/contest/8458/enter/ Здесь задачи, которые очень похожи на те, что мы даем на интервью, первая задача решена, чтобы можно было ознакомиться с самой системой.
* [https://www.techinterviewhandbook.org/grind75/]
* [https://coderun.yandex.ru/]
* [https://www.techinterviewhandbook.org/grind75/]
* [https://coderun.yandex.ru/]




Версия от 04:09, 20 ноября 2024

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

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

Гипотезы

  • Какие проблемы уже решали? Попробовать увидеть паттерн, дать поработать интуиции, а потом ее проверить
  • Какие проблемы мы видели, но в другой форме?
  • Переберите все возможные техники и алгоритмы, которые знаете
  • Посмотрите на проблему с разных углов, точек зрения, областей
  • Декомпозиция. Может проблема состоит из комбинации других?
  • Решаем в лоб самым тупым способом - brute force
  • Нарисуйте на бумаге варианты идей
  • Попытка угадать алгоритм, как черный ящик, используя гипотезу - "А что, если оно вот так работает?"
  • Уберите все невозможные варианты из решения
  • Найти все corner(extreme) cases вашей проблемы
  • Используйте инверсию (Что, если все наоборот? Как сделать так, чтобы такие условия точно не сработали? Как сделать наоборот хуже? Если я хочу помочь Индии, то какие есть способы, чтобы навредить Индии?)
  • Используйте backwards thinking
  • Решите самую простую версию по данным
  • Решите самую простую версию по условиям
  • Измените упрощенную версию
  • Представьте ситуацию, когда все условия соблюдены
  • Найдите такую упрощенную версию, которая может быть сведена к более сложной текущей версии, но которую можно решить.
  • Рассмотрите более сложную версию(парадоксально, но может помочь)
  • Изменить условия. Пробовать решить за O(n), O(nlogn), O(n^2), O(n^3)
  • Возможно для решения есть формула. Последовательности и тп
  • Сколько состояний у нас есть? Что меняется в процессе работы алгоритма? Что остается неизменным?
  • Моделируйте, добавляя новые и убирая текущие свойства проблемы.
  • Представьте, что решение уже готово. Можем ли мы как-то это использовать?
  • Итеративное мышление
  • Декларативное решение, рекурсия, divide and conquer
  • Используйте аналогию
  • Используйте ассоциативное мышление
  • Используйте индукцию
  • Решите частные случаи. Specialization
  • Решите в общем виде. Generalization

Яндекс

Высылаю материалы для подготовки: Статья на хабре о том, как проходят наши интервью: 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

sort

heap/hash

two pointers

sliding window

tree

greedy problems

Сортировка

Выборка

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))
}
Источник — http://wiki.aleksashkin.net/index.php?title=Алгоритмы&oldid=3297