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

По задаче "XVII Задача о поиске не отсортированного подмассива" - вы уж как то определитесь в формулировкой: либо результат это начальный и конечный индекс подмассива, который нужно убрать чтобы остался отсортированный массив, или результат начальный и конечный индекс подмассива который изменит индексы при сортировке!! Например мою функцию, которая возвращает {1,2} для массива array: []int{2, 1, 0, 3, 4, 5, 6, 7, 8, 9}, объявили неверной, хотя: {2, [1, 0,] 3, 4, 5, 6, 7, 8, 9} -> {2,3,4,5,6,7,8,9}

цитата:
"...К сожалению, тестовое задание решено неверно: не проходят тесты, пример
array: []int{2, 1, 0, 3, 4, 5, 6, 7, 8, 9},
expected: []int{0, 2}..."
и еще:
"...В ответ должны быть включены элементы, которые при сортировке поменяют свой индекс:

{[2, 1, 0], 3, 4, 5, 6, 7, 8, 9} -> {[0, 1, 2], 3, 4, 5, 6, 7, 8, 9}..."

Исходная формулировка

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

@hoopershooch, не ясно откуда у вас появилась данная формулировка

... нужно убрать чтобы остался отсортированный массив

Корректные тестовые данные

array: []int{2, 1, 0, 3, 4, 5, 6, 7, 8, 9},
expected: []int{0, 2}..."

Здесь большинство задач с неполными данными. Советую уточнять ТЗ с тест кейсами. Возможно в этом и была задумка авторов, всё как в реальном мире.

Да. Один из лучших индикаторов для middle+ специалистов. При этом в описание все же присутствует необходимый набор формулировок для правильного решения.

Добрый вечер! В XIX задаче о поиске элемента у нас могут быть повторяющиеся элементы в обоих массивах (array, subarray)?

Доброе утро, да 🙂