Задачи для IT интервью

[mikeG]

а коробки как расположены в помещении? (т.е. стоят ли одни на других)

Нет, просто в ряд стоят, нужно по порядку переставить.

Отсортировать по весу? По цвету? Размеру? По ценности содержимого в оных?

Не важно. Можно считать, что на каждой номер написан.

ну если силы есть и оплата почасовая, то и таскайте их по одной, хоть бабл сортом переставляя, в чем вопрос?

Оптимальный алгоритм переставления коробок, естественно.
Бабл сорт будет одну и ту же коробку много раз двигать. В частности, если коробка уже на своем месте стоит, то двигать не нужно.

[3DD]

Нет, просто в ряд стоят, нужно по порядку переставить.

Отсортировать по весу? По цвету? Размеру? По ценности содержимого в оных?

Не важно. Можно считать, что на каждой номер написан.

ну если силы есть и оплата почасовая, то и таскайте их по одной, хоть бабл сортом переставляя, в чем вопрос?

Оптимальный алгоритм переставления коробок, естественно.
Бабл сорт будет одну и ту же коробку много раз двигать.

Тогда нужно уточнение - наличие доп пространства куда коробки временно выносить, если сортировать, скажем, quick sort - выбираем pivot, сортируем, разделяем надвое, в каждой половине выбираем свой pivot и тд

https://www.alphaux.com?id=1772526509715135

[mikeG]

Тогда нужно уточнение - наличие доп пространства куда коробки временно выносить, если сортировать, скажем, quick sort - выбираем pivot, сортируем, разделяем надвое, в каждой половине выбираем свой pivot и тд

Доп пространства нет.

[M. Ridcully]

Прежде чем искать "оптимальное" решение нужно выяснить модель (ну или cost function, которую минимизуруем), по которой эта самая оптимальность считается. Одна возможная модель - минимизируется суммарное расстояние, на которое переносятся коробки. Тогда решением будет то, что предложила Lisa выше - сначала для каждой коробки определяется её правильное конечное место. Затем берётся любая (ближайшая?) коробка, сразу переносится на своё место. При этом берётся коробка, которая занимает это место и переносится на своё правильное место. Ну и т.д. Довольно очевидно, что для этой модели решение оптимальное - каждая коробка переноситмя кратчайшим путём на своё место.

Либо скажите точнее вашу модель - быть может, нужно ещё минимизировать операции поднять / поставить коробку, или передвижение "порожняком" без коробки и т.д. Если несколько таких операций, то, наверное, это задача минимизации пути в графе - BFS?

[mikeG]

Чтобы сначала отсортировать, потом носить, нужно место (даже если физические коробки не носим, то память нужна).

Да, оптимизировать можно разные вещи - количество поднятий коробок или суммарное расстояние.
Соответственно, решения будут разные.

Минимизация поднятий - это сортировка в EEPROM/FLASH, когда нужно количество writes минимизировать.
На интервью можно все эти варианты обсуждать.

[KVA]

Про EEPROM/FLASH надо было бы сразу сказать, а то при заданных условиях (уточненных и некоторых недосказанных) задача вообще может не иметь решения на практике.

Места дополнительного нет. Носит человек. А коробки со стиральными машинами.

Но поговорить сойдет.

[fruit6]

Про EEPROM/FLASH надо было бы сразу сказать, а то при заданных условиях (уточненных и некоторых недосказанных) задача вообще может не иметь решения на практике.

Места дополнительного нет. Носит человек. А коробки со стиральными машинами.

Но поговорить сойдет. :)

Ожидается, что кандидат начнет задавать уточняющие вопросы и в итоге выйдет на EEPROM!
А такой перец пойдет работать туда, где работают технически подкованные люди и могут эффективно общаться.

[valchkou]

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

вы случаем не в амазоне работаете

[mikeG]

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

вы случаем не в амазоне работаете

Не в Амазоне, но для них актуально...

[ALV00]

Прежде чем искать "оптимальное" решение нужно выяснить модель (ну или cost function, которую минимизуруем), по которой эта самая оптимальность считается. Одна возможная модель - минимизируется суммарное расстояние, на которое переносятся коробки. Тогда решением будет то, что предложила Lisa выше - сначала для каждой коробки определяется её правильное конечное место. Затем берётся любая (ближайшая?) коробка, сразу переносится на своё место. При этом берётся коробка, которая занимает это место и переносится на своё правильное место. Ну и т.д. Довольно очевидно, что для этой модели решение оптимальное - каждая коробка переноситмя кратчайшим путём на своё место.

Тут есть один маленький гиморрой: за один цикл коробки могут не переставиться.
Например, первоначально было
2,1,4,3
передвинули коробки 2<->1, цикл закончился, 4 и 3 остались на своих местах.
Как дальше с этим быть? Надо каждый раз сканировать массив с начала и проверять, все ли коробки стоят на своих местах.
Либо придумать как бысто определять с какого номера начинать следующий цикл.

[3DD]

Тут есть один маленький гиморрой: за один цикл коробки могут не переставиться.

Так он может за один проход все по одной взвесить (i.e. create Set), а за второй проход расставить по весу. O(n)

[ALV00]

Тут есть один маленький гиморрой: за один цикл коробки могут не переставиться.

Так он может за один проход все по одной взвесить (i.e. create Set), а за второй проход расставить по весу. O(n)

А подробней, как расставлять? O(n) это понятно, только понадобится два прохода в худшем случае.