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-3-44-46-5-6-7-8-34-3-4-5] => [3,4] , [3,9] или [3,12]

Добрый день!

Вопрос по заданию II Задача о парковке : в формулировке сказано Дана последовательность пар вида {start, end}.

1. Каким образом задается эта последовательность? Устроит, если это будет файл, внутри которого JSON?
2. Каков формат даты? Это Timestamp или более человекочитаемый вид, к примеру "2021-01-12 20:00:00"?

Добрый день 👋

1. Это может быть и массив пар в памяти. Важен алгоритм.
2. Это может быть timestamp

Добрый день, подскажите пожалуйста по задачке "XVII Задача о поиске не отсортированного подмассива"
Нужно вернуть первый не отсортированный подмассив? или нужно брать пересечение всех не отсортированных?
[1-2-3-44-46-5-6-7-8-34-3-4-5] => [3,4] , [3,9] или [3,12]

Добрый день 👋

Посмотри пожалуйста вторую формулировку той же задачи:
https://gist.github.com/rusdevops/d85340e26aeac720c338874492adf637#gistcomment-3799156

Добрый день!

Просьба уточнить условия по задаче https://gist.github.com/rusdevops/d85340e26aeac720c338874492adf637#file-21285-md

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

before: _On__my___home_world
after: On_my_home_world

В задаче нужно удалить лишние пробелы, но в примере знак нижнего подчеркивания. В примере это просто для наглядности? Удалять всё-таки нужно пробелы?

Добрый день, есть не большее уточнение по задаче "XIX Задача о поиске элемента".
Алгоритм со сложность быстрее чем O(N) - не может быть, так как в задаче используется поиск подмассива в массиве. Решение в лоб даст сложность O(N*M)

Добрый день! Есть пара вопросов по задаче "XVII Задача о поиске не отсортированного подмассива". Уточните, пожалуйста

1. Известно ли, что массив отсортирован по возрастанию, либо надо учитывать возможность обоих вариантов сортировки?
2. Как интерпретировать условие задачи для такого входного массива: [1, 2, 3, 101, 4, 5]?
   вариант 1) удаляем элемент с индексом 3, получаем отсортированный массив [1, 2, 3, 4, 5]
   вариант 2) сортируем массив по возрастанию, получаем [1, 2, 3, 4, 5, 101], сравниваем с исходным и оставляем в итоге только первые три элемента [1, 2, 3] (этот вариант следует из формулировки задачи в комментарии https://gist.github.com/rusdevops/d85340e26aeac720c338874492adf637#gistcomment-3799156)

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

1. Как я понял шоссе - это прямая, не окружность, кривая и т.д. и т.п. Соответственно газопровод тоже. Это так?

да

2. На стоимость газопровода влияет только его длинна?

да

Добрый день, есть не большее уточнение по задаче "XIX Задача о поиске элемента".
Алгоритм со сложность быстрее чем O(N) - не может быть, так как в задаче используется поиск подмассива в массиве. Решение в лоб даст сложность O(N*M)

Массивы упорядочены в одном направление

Добрый день!

Просьба уточнить условия по задаче https://gist.github.com/rusdevops/d85340e26aeac720c338874492adf637#file-21285-md

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

В задаче нужно удалить лишние пробелы, но в примере знак нижнего подчеркивания. В примере это просто для наглядности? Удалять всё-таки нужно пробелы?

Нужно удалить пробелы, и да, для наглядности используется знак _ 🙂

Добрый день!

Просьба уточнить условия по задаче https://gist.github.com/rusdevops/d85340e26aeac720c338874492adf637#file-21285-md

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

before: _On__my___home_world
after: On_my_home_world

В строке могут быть знаки пунктуации? Например, точка, запятая, знак вопроса, восклицательный знак? Нужно ли их тоже учитывать при реализации алгоритма?

Добрый день!

Просьба уточнить условия по задаче https://gist.github.com/rusdevops/d85340e26aeac720c338874492adf637#file-21285-md

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

В строке могут быть знаки пунктуации? Например, точка, запятая, знак вопроса, восклицательный знак? Нужно ли их тоже учитывать при реализации алгоритма?

Добрый 👋
Не нужно, удаляем только пробелы 🙂

Добрый день!

Есть пара вопросов по задаче "XVII Задача о поиске не отсортированного подмассива". Уточните, пожалуйста
Известно ли, что массив отсортирован по возрастанию, либо надо учитывать возможность обоих вариантов сортировки?
Как интерпретировать условие задачи для такого входного массива: [1, 2, 3, 101, 4, 5]?
вариант 1) удаляем элемент с индексом 3, получаем отсортированный массив [1, 2, 3, 4, 5]
вариант 2) сортируем массив по возрастанию, получаем [1, 2, 3, 4, 5, 101], сравниваем с исходным и оставляем в итоге только первые три элемента [1, 2, 3] (этот вариант следует из формулировки задачи в комментарии https://gist.github.com/rusdevops/d85340e26aeac720c338874492adf637#gistcomment-3799156)

Добрый 👋
Считаем, что оба массива отсортированы по возрастанию.
Для входного массива: [1, 2, 3, 101, 4, 5] результатом будет {3, 5}
А именно считаем, что не отсортированный подмассив это [101, 4, 5]

Добрый день!

У меня вопрос по задаче "II Задача о парковке". Мне не понятно что имеется ввиду под словом одновременно?!
Например, есть 3 машины с интервалами [3,8] [4, 6] [5, 7]. Все они пересекаются на [5,6]. Можно ли считать это одновременно?

Спасибо заранее за ответ :)

Добрый день!

У меня вопрос по задаче "II Задача о парковке". Мне не понятно что имеется ввиду под словом одновременно?!
Например, есть 3 машины с интервалами [3,8] [4, 6] [5, 7]. Все они пересекаются на [5,6]. Можно ли считать это одновременно?

Спасибо заранее за ответ :)

Добрый 👋 Можно.

Здравствуйте!
Задача о строительстве газового трубопровода.
Правильно ли я понимаю, что массив значений расстояний домов от шоссе неотсортирован?
Если нет, то сложность может быть O(N*M)?

Здравствуйте!
Задача о строительстве газового трубопровода.
Правильно ли я понимаю, что массив значений расстояний домов от шоссе неотсортирован?
Если нет, то сложность может быть O(N*M)?

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

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

По задаче "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}..."

как в известной поговорке: "чувствую, что где то нае*али но не пойму где"

По задаче "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}..."

как в известной поговорке: "чувствую, что где то нае*али но не пойму где"

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

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

По задаче "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)?

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