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)
Что хочется увидеть:
O(N) по времениII Задача о парковке ⭐⭐
Дана последоватльность пар вида {start, end}
start - время заезда автотранспорта на парковку
end - время выезда автотранспорта с парковки
Нужно найти максимальное количество автотранспорта, находящихся одновременно на парковке
Что хочется увидеть:
I Задача о длиной цепочке единиц ⭐⭐
Дана последоватльность 0 и 1
Нужно найти самую длинную последовательность из 1 (единиц) после удаления любого элемента
func maxOnesAfterRemoveItem([]byte) uintassert(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)Что хочется увидеть:
X Задача о строительстве газового трубопровода ⭐⭐
Дана последовательность расстояний расположения домов от шоссе.
Нужно рассчитать расположение газового трубопровода, чтобы стоимость подключения всех домов была минимальна.
Все дома находятся по одну сторону от шоссе. Возможен случай, когда расстояние от дома до шоссе равно 0.
Газовый трубопровод будет строиться параллельно шоссе
func calculateLocation(houses []uint) floatЧто хочется увидеть:
XVII Задача о поиске не отсортированного подмассива ⭐⭐
Дана коллекция частично отсортированных целых неотрицательных чисел
Нужно реализовать алгоритм поиска не отсортированного подмассива
func findUnsortedSubarray(array []uint) (left uint, right uint)Что хочется увидеть:
X Задача о строительстве газового трубопровода ⭐⭐
- Как я понял шоссе - это прямая, не окружность, кривая и т.д. и т.п. Соответственно газопровод тоже. Это так?
да
- На стоимость газопровода влияет только его длинна?
да
Добрый день, есть не большее уточнение по задаче "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)?
Доброе утро, да 🙂
Добрый день! Есть пара вопросов по задаче "XVII Задача о поиске не отсортированного подмассива". Уточните, пожалуйста
вариант 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)