19.md

XIX Задача о поиске элемента ⭐⭐

Дан упорядоченный массив чисел размером N Нужно реализовать алгоритм поиска вхождения упорядоченного подмассива размера M, где M << N

func isInclude(array int[], subarray []int) bool

assert(isInclude([1, 2, 3, 5, 7, 9, 11], []) == true) 
assert(isInclude([1, 2, 3, 5, 7, 9, 11], [3, 5, 7]) == true) 
assert(isInclude([1, 2, 3, 5, 7, 9, 11], [4, 5, 7]) == false) 

Что хочется увидеть:

1. Алгоритм со сложность быстрее чем O(N) по времени

2.md

II Задача о парковке ⭐⭐

Дана последоватльность пар вида {start, end}

start - время заезда автотранспорта на парковку
end - время выезда автотранспорта с парковки

Нужно найти максимальное количество автотранспорта, находящихся одновременно на парковке

Что хочется увидеть:

1. Алгоритм с оптимальной реализацией по памяти

21195.md

I Задача о длиной цепочке единиц ⭐⭐

Дана последоватльность 0 и 1
Нужно найти самую длинную последовательность из 1 (единиц) после удаления любого элемента

func maxOnesAfterRemoveItem([]byte) uint

assert(maxOnesAfterRemoveItem[0,0] == 0)
assert(maxOnesAfterRemoveItem[0,1] == 1)
assert(maxOnesAfterRemoveItem[1,0] == 1)
assert(maxOnesAfterRemoveItem[1,1] == 1)
assert(maxOnesAfterRemoveItem[1, 1, 0, 1, 1] == 4)
assert(maxOnesAfterRemoveItem[1, 1, 0, 1, 1, 0, 1, 1, 1] == 5)
assert(maxOnesAfterRemoveItem[1, 1, 0, 1, 1, 0, 1, 1, 1, 0] == 5)

Что хочется увидеть:

• Алгоритм со сложностью O(N) по времени и O(1) по памяти

21285.md

III Задача об удаление лишних пробелов ⭐⭐

Дана строка с избыточным количеством пробелов Нужно удалить лишние пробелы

before: _On__my___home_world
after:  On_my_home_world

Что хочется увидеть:

• Inplace алгоритм со сложность O(N) по времени и O(1) по памяти

21645.md

X Задача о строительстве газового трубопровода ⭐⭐

Дана последовательность расстояний расположения домов от шоссе.
Нужно рассчитать расположение газового трубопровода, чтобы стоимость подключения всех домов была минимальна.
Все дома находятся по одну сторону от шоссе. Возможен случай, когда расстояние от дома до шоссе равно 0.

Газовый трубопровод будет строиться параллельно шоссе

func calculateLocation(houses []uint) float

Что хочется увидеть:

• Алгоритм со сложностью O(N) по времени

21960.md

XVII Задача о поиске не отсортированного подмассива ⭐⭐

Дана коллекция частично отсортированных целых неотрицательных чисел
Нужно реализовать алгоритм поиска не отсортированного подмассива

func findUnsortedSubarray(array []uint) (left uint, right uint)

Что хочется увидеть:

• Алгоритм со сложностью по времени не большей, чем O(N)

7.md

VII Задача о поиске отрезка с максимальной суммой ⭐⭐

Дана последовательность из целых чисел Нужно найти закрытый интервал с максимальной суммой

assert(findSubarrayWithMaxSum([10, -3, -12, 8, 42, 1, -7, 0, 3]) == {3, 5})