Алгоритмы

• Как решать задачи на Leetcode

Яндекс

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

   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:

   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/

НОД и НОК

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