Задачи с собеседований. Три адекватные задачки на «подумать»
Комментарии (15)
NYMEZIDE
1 июля 2017 в 21:52
+2↑
↓
Дана упорядоченная последовательность чисел от 1 до N. Из нее удалили одно число, а оставшиеся перемешали. Найти удаленное число.
В первой странная постановка задачи. Нигде не говорится, что оригинальная коллекция доступна.
Вначале думаешь что доступна только измененная коллекция. И ни про какие суммы и вычитания не думаешь.1 июля 2017 в 21:59
+1↑
↓
Кому как, я сразу про сумму подумал. Формулировка похожа на школьные задачки, там такого было полно.1 июля 2017 в 22:10
+1↑
↓
Согласен с Вами.
1 июля 2017 в 21:52
+2↑
↓
Вторую задачу можно решить и другим способом.1. Наполнить пятилитровый кувшин водой
2. Из пятилитрового кувшина наполнить трёхлитровый кувшин (в пятилитровом останется 2 литра воды)
3. Вылить всю воду из трёхлитрового кувшина и перелить 2 литра воды из пятилитрового кувшина.
4. Наполнить пятилитровый кувшин водой
5. Наполнить заполненый на 2 литра трёхлитровый кувшин водой из полного пятилитрового кувшина (потребуется 1 литр воды)В итоге, в пятилитровом кувшине останется 4 литра воды.
square
1 июля 2017 в 22:33
+2↑
↓
Я точно так же решил и у нас с вами 6 действий, а не 8, как у автора :)
Hydro
1 июля 2017 в 22:43
+1↑
↓
И я почему-то тоже сразу по такому пути пошел
wzrd
1 июля 2017 в 22:01
+1↑
↓
В Задаче 1, если обе последовательности доступны, то, как вариант, можно решить линейно. Пробежаться по отсортированному списку и сравнивать с i-1 — ым элементом отсортированного. По идее это должно получиться оптимальнее решения предложенного автором.-
square
1 июля 2017 в 22:10
+1↑
↓
Оптимальнее? Вы шутите? Т.е. сначала потратим время на сортировку, потом умножим на два занятую память, а потом проведем N сравнений, это оптимизация? Вместо того, чтобы взять n (n+1)/2 и вычесть из него все имеющиеся числа, и в остатке получить ответ.-
wzrd
1 июля 2017 в 22:16
+1↑
↓
Нет, оптимальнее того, что было предложено изначально как решение. Но и тут я не прав. Мне почему-то показалось, что у нас доступна отсортированная последовательность и хотел предложить как вариант.
1 июля 2017 в 22:10
+1↑
↓
Вы забываете что она ещё и пермешана так что не выйдет
aliencash
1 июля 2017 в 22:27
+1↑
↓
где оптимальнее-то? в решении автора всего один цикл от 1 до n и единичные арифметические операции. У вас — вложенные циклы и n^2 операций сравнения. или я не понял что вы предлагаете.-
wzrd
1 июля 2017 в 22:56
+1↑
↓
В решени автора логарифм и линейный обход. А у меня только линейный. Но я ошибься, последовательность даётся только одна, неотсортированная, поэтому мой вариант отпадает.
1 июля 2017 в 22:07
+3↑
↓
Вторую задачу решает Брюс Виллис
EmmGold
1 июля 2017 в 22:40
+1↑
↓
Мне для первой задачи первым всплыло решение брутфорсом. Берём 1 — ищем в последовательности; Берём 2 — ищем; Берём 3 — ищем… берём 34234 — не находим.1 июля 2017 в 23:11
0↑
↓
задачки очень простые и легко решаемы, особенно если прорешивали кучу подобных задач в школьные/университетские годы
Мне пока самое сложное, что попалось — это задачка посчитать количесво вагонов в составе
Условие: есть состав вагонов, закольцованный, можно переходить от вагона к вагону, в обоих направлениях. Скажем, что окна закрыты и видите только текущий вагон.
В каждом вагоне определено понятие света — горит или нет
У Вас, при заходе на очередной вагон, есть две возможности: посмотреть, горит ли в этом вагоне свет, и включить/выключить свет (без ограничений)
Вопрос: как посчитать точное количесто вагонов с наименьшим количеством их посещений?
