Имел собеседование со "специалистом" из Гугла. На вопрос "какова лучшая сложность для алгоритмов сортировки", ответил ему, что O(n). Нет, говорит, это неправильно — должно быть O(n * log n). Правильно, говорю, именно O(n). Есть такой radix sort, у него сложность именно такая. В ответ — недоуменно-возмущенное молчание. Похоже, не поверил.
Кажется, никакое продолжение мне не светит
Здравствуйте, CoderMonkey, Вы писали:
CM>Имел собеседование со "специалистом" из Гугла. На вопрос "какова лучшая сложность для алгоритмов сортировки", ответил ему, что O(n). Нет, говорит, это неправильно — должно быть O(n * log n). Правильно, говорю, именно O(n). Есть такой radix sort, у него сложность именно такая. В ответ — недоуменно-возмущенное молчание. Похоже, не поверил. CM>Кажется, никакое продолжение мне не светит
Все верно. Т.к. один из проверяемых на интервью навыков это умение четко доносить свои мысли.
В данном случае человек скорее всего ждал от вас рассказа какие ограничения radix sort накладывает на сортируемые сущности (knowledge of internal structure) и почему этот чудо алгоритм не является выбором по умолчанию для библиотечных функций сортировки.
P.S. Вы бы ему еще сортировку подсчетом в качестве примера привели.
Здравствуйте, lintik, Вы писали:
L>В данном случае человек скорее всего ждал от вас рассказа
Для этого открывается рот и издаются звуки вопросительных интонаций.
L> какие ограничения radix sort накладывает на сортируемые сущности (knowledge of internal structure) и почему этот чудо алгоритм не является выбором по умолчанию для библиотечных функций сортировки.
Это отличный повод побеседовать и выяснить понимает ли кандидат все эти нюансы.
Здравствуйте, CoderMonkey, Вы писали:
CM> radix sort, у него сложность O(n)
Вообще-то у него этот логарифм в константе спрятан. Для чисел в два раза шире понадобиться в два раза больше операций. А рост n предполагает рост ширины данных иначе сортировка счетом
Здравствуйте, lintik, Вы писали:
L>В данном случае человек скорее всего ждал от вас рассказа
А не надо высасывать из пальца. Я программист, а не гадалка. Ты, я надеюсь — тоже.
L>какие ограничения radix sort накладывает на сортируемые сущности (knowledge of internal structure)
Ну расскажи мне, для каких таких данных в IT нет никакой возможности разбить их на части.
L>и почему этот чудо алгоритм не является выбором по умолчанию для библиотечных функций сортировки.
Здравствуйте, CoderMonkey, Вы писали:
CM>Имел собеседование со "специалистом" из Гугла. На вопрос "какова лучшая сложность для алгоритмов сортировки", ответил ему, что O(n). Нет, говорит, это неправильно — должно быть O(n * log n). Правильно, говорю, именно O(n). Есть такой radix sort, у него сложность именно такая. В ответ — недоуменно-возмущенное молчание. Похоже, не поверил. CM>Кажется, никакое продолжение мне не светит
Не "силь", а "сол"! (с)
Лучшая сложность -- O(n^2). А O(n) -- это худшая сложность, зато лучшая производительность.
Здравствуйте, mgu.
CM>>Имел собеседование со "специалистом" из Гугла. На вопрос "какова лучшая сложность для алгоритмов сортировки"...
mgu>Лучшая сложность -- O(n^2).
Здравствуйте, CreatorCray, Вы писали:
CC>Здравствуйте, lintik, Вы писали:
L>>В данном случае человек скорее всего ждал от вас рассказа CC>Для этого открывается рот и издаются звуки вопросительных интонаций.
Сейчас это так не работает, а говорит о том, что вы не умеете продавать себя — я это уже проходил
Здравствуйте, kov_serg, Вы писали:
_>Вообще-то у него этот логарифм в константе спрятан. Для чисел в два раза шире понадобиться в два раза больше операций. А рост n предполагает рост ширины данных иначе сортировка счетом
А сравнение двух чисел не предполагает O(ширины_числа)? А то тогда надо пересматривать сложность всех алгоритмов.
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, The Passenger, Вы писали:
TP>>Сейчас это так не работает, а говорит о том, что вы не умеете продавать себя — я это уже проходил
CM>А как это сейчас работает? Детали, пожалуйста.
бодрым уверенным голосом рассказываете все на пальцах как дебилу ... это только умных оскорбляет а дебилы это любят
уверенность в голосе говорит о том что вы разбираетесь в вопросе а количество незначащих деталий говорит о том что глубоко
если при этом еще нарисовать диаграмму или график какой — то вообще фонтан
хотя мои сегодняшние посты не стоит рассматривать серьезно, я походу заболеваю, а когда я это делаю я злой как сволочь
Здравствуйте, The Passenger, Вы писали:
TP>бодрым уверенным голосом рассказываете все на пальцах как дебилу ... это только умных оскорбляет а дебилы это любят
Дебилы, как правило, железно уверены, что именно они — это самые умные и есть.
Здравствуйте, CreatorCray, Вы писали:
CC>Для этого открывается рот и издаются звуки вопросительных интонаций. CC>Это отличный повод побеседовать и выяснить понимает ли кандидат все эти нюансы.
Я могу только еще раз повторить
один из проверяемых на интервью навыков это умение четко доносить свои мысли
Не пытаться "поразить" интервьюера своим знанием некоторых алгоритмов сортировки, не применимых в общем случае.
А, например, пойти одним из двух путей
1) Уточнить что из себя представляет множество сортируемых сущностей, какие операции допустимы и после этого заявить про то, что конкретно в этом случае radix sort даст O(n).
2) Сказать что для сортировки сравнением теоретически возможный минимум это O(nlogn), но для некоторых типов данных доступны дополнительные операции и поэтому есть алгоритмы дающие лучшие результаты.
Очевидно, что по результатам этого интервью вы с интервьюером не смогли найти общий язык даже в такой общеизвестной области как алгоритмы сортировки.
Именно поэтому, компании, где на входе громадный поток кандидатов, предпочитают дальше не рисковать и переключаться на тех, кто способен без дополнительных проблем ответить на базовый набор вопросов.
Я думал, что за последние 10-15 лет все уже выяснили, что телефонный скрининг это просто проверка на адекватность. Не нужно "блистать", нужно просто стандартно и правильно отвечать на задаваемые стандартные вопросы. Если интервьюер захочет деталей и нюансов, он всегда задаст follow up по более продвинутым темам.
Кроме этого, нужно помнить что на стадии телефонного интервью, вы в Google заинтересованы гораздо больше чем они в вас. Поэтому вы должны давать на этой стадии ожидаемые ответы, а не собеседующий из вас вытаскивать детали.
Это у вас интервью с Google одно единственное в год, а у каждого интервьюера таких собеседований 60-100 в год, а то и больше.
Вот когда вы перейдете к offer negotiation, вот тогда уже можете быть уверены, что вы для компании представляете какой-то интерес (в рамках той суммы, которая в офере).
P.S. Мне кажется что у людей которым позвонили из Google, Amazon, Facebook и т.п. складывается какое-то странное мнение о собственной исключительности и о том, что офер практически у них в кармане, осталось только согласиться.
Нужно как можно скорее гнать от себя такие мысли. Если вам назначили технический скрининг, то вы никто.
Вот если вас сразу ведут в ресторан обсуждать возможные варианты сотрудничества и компенсации, тогда другое дело и вы действительно звезда.
Здравствуйте, The Passenger, Вы писали:
TP>бодрым уверенным голосом рассказываете все на пальцах как дебилу ... это только умных оскорбляет а дебилы это любят
Когда меня впервые спросили про лучшую сортировку (их как раз канонизировали, а я не следил за новостями вселенских соборов), то я искренне ответил: "домЕнная". Слив был засчитан -- не спрашивать же, что это такое? Так что можно смело называть алгоритм Гогенфишмана-Макакагавы и получать три раза ку.
Здравствуйте, lintik, Вы писали:
L>Очевидно, что по результатам этого интервью вы с интервьюером не смогли найти общий язык даже в такой общеизвестной области как алгоритмы сортировки.
Гм, ты уверен что тому человеку отвечаешь?
L>Кроме этого, нужно помнить что на стадии телефонного интервью, вы в Google заинтересованы гораздо больше чем они в вас.
Я в гугл не собеседовался вообще никогда.
L>Нужно как можно скорее гнать от себя такие мысли. Если вам назначили технический скрининг, то вы никто.
В больших компаниях совсем без предварительно поговорить с кучей народа не берут вообще никого.
Здравствуйте, CoderMonkey, Вы писали:
CM>Имел собеседование со "специалистом" из Гугла. На вопрос "какова лучшая сложность для алгоритмов сортировки", ответил ему, что O(n). Нет, говорит, это неправильно — должно быть O(n * log n). Правильно, говорю, именно O(n). Есть такой radix sort, у него сложность именно такая. В ответ — недоуменно-возмущенное молчание. Похоже, не поверил.
А как то определил, молчание недоуменно-возмущенное??? Он вообще ничего не сказал? Мычал?
Может полез в инет проверять или связб отключилась? Или ты вызвал сбой в программе биоробота? CM>Кажется, никакое продолжение мне не светит
Ну ты напиши, каков итог. Может ты просто прошел этот тур досрочно
Здравствуйте, CreatorCray, Вы писали:
CC>В больших компаниях совсем без предварительно поговорить с кучей народа не берут вообще никого.
Очень редко, но берут. Знаю точно про яблочников и гугль. Но там были спецы уровня "извините, а почему вы спрашиваете у меня вопросы из моей же книги?".
