Здравствуйте, CoderMonkey, Вы писали:

CM>Имел собеседование со "специалистом" из Гугла. На вопрос "какова лучшая сложность для алгоритмов сортировки", ответил ему, что O(n). Нет, говорит, это неправильно — должно быть O(n * log n). Правильно, говорю, именно O(n). Есть такой radix sort, у него сложность именно такая. В ответ — недоуменно-возмущенное молчание. Похоже, не поверил.
CM>Кажется, никакое продолжение мне не светит
Все верно. Т.к. один из проверяемых на интервью навыков это умение четко доносить свои мысли.
В данном случае человек скорее всего ждал от вас рассказа какие ограничения radix sort накладывает на сортируемые сущности (knowledge of internal structure) и почему этот чудо алгоритм не является выбором по умолчанию для библиотечных функций сортировки.

P.S. Вы бы ему еще сортировку подсчетом в качестве примере привели.

Здравствуйте, CoderMonkey, Вы писали:

CM>Имел собеседование со "специалистом" из Гугла. На вопрос "какова лучшая сложность для алгоритмов сортировки", ответил ему, что O(n). Нет, говорит, это неправильно — должно быть O(n * log n). Правильно, говорю, именно O(n). Есть такой radix sort, у него сложность именно такая. В ответ — недоуменно-возмущенное молчание. Похоже, не поверил.
CM>Кажется, никакое продолжение мне не светит
Все верно. Т.к. один из проверяемых на интервью навыков это умение четко доносить свои мысли.
В данном случае человек скорее всего ждал от вас рассказа какие ограничения radix sort накладывает на сортируемые сущности (knowledge of internal structure) и почему этот чудо алгоритм не является выбором по умолчанию для библиотечных функций сортировки.

P.S. Вы бы ему еще сортировку подсчетом в качестве примера привели.