Здравствуйте, El Camino Real, Вы писали:
ECR>Здравствуйте, CreatorCray, Вы писали:
CC>>В больших компаниях совсем без предварительно поговорить с кучей народа не берут вообще никого. ECR>Очень редко, но берут. Знаю точно про яблочников и гугль. Но там были спецы уровня "извините, а почему вы спрашиваете у меня вопросы из моей же книги?".
Они с кучей народа уже заочно поговорили, все соглачны. Несогласные уволены
Здравствуйте, lintik, Вы писали:
L>Не пытаться "поразить" интервьюера своим знанием некоторых алгоритмов сортировки, не применимых в общем случае.
radix sort прекрасно применим в любых случаях, где применим любой другой алгоритм сортировки. Признавайся — ты HR?
L>Очевидно, что по результатам этого интервью вы с интервьюером не смогли найти общий язык даже в такой общеизвестной области как алгоритмы сортировки.
Учитывая, что я — совсем не тот из нас двоих, кому платят зарплату за болтологию, не совсем понятно, почему в этом виноват я.
L>Именно поэтому, компании, где на входе громадный поток кандидатов, предпочитают дальше не рисковать и переключаться на тех, кто способен без дополнительных проблем ответить на базовый набор вопросов. L>Я думал, что за последние 10-15 лет все уже выяснили, что телефонный скрининг это просто проверка на адекватность. Не нужно "блистать", нужно просто стандартно и правильно отвечать на задаваемые стандартные вопросы. Если интервьюер захочет деталей и нюансов, он всегда задаст follow up по более продвинутым темам.
Ключевые слова — "стандартный", "ожидаемый", "ты чо самый умный чё ли?"
Ой, это кажется музыкой навеяло.
L>Кроме этого, нужно помнить что на стадии телефонного интервью, вы в Google заинтересованы гораздо больше чем они в вас. Поэтому вы должны давать на этой стадии ожидаемые ответы, а не собеседующий из вас вытаскивать детали.
Честно говоря — я довольно мало заинтересован в работе в Гугле. Понтов очень много, а работа, на самом деле — не фонтан. Просто было интересно, что из этого выйдет. Я не разочарован в результатах
Но отношение "работать у нас — охренительно большая честь, всем сделать ку три раза, надеть намордник и радоваться" таки присутствует, да.
L>P.S. Мне кажется что у людей которым позвонили из Google, Amazon, Facebook и т.п. складывается какое-то странное мнение о собственной исключительности и о том, что офер практически у них в кармане, осталось только согласиться.
Здравствуйте, 0xCAFEDEAD, Вы писали:
CAF>А как то определил, молчание недоуменно-возмущенное??? Он вообще ничего не сказал? Мычал? CAF>Может полез в инет проверять или связб отключилась? Или ты вызвал сбой в программе биоробота?
Недовольно пробурчал что-то в духе "очень интересно".
CAF>Ну ты напиши, каков итог. Может ты просто прошел этот тур досрочно
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, 0xCAFEDEAD, Вы писали:
CAF>>А как то определил, молчание недоуменно-возмущенное??? Он вообще ничего не сказал? Мычал? CAF>>Может полез в инет проверять или связб отключилась? Или ты вызвал сбой в программе биоробота?
CM>Недовольно пробурчал что-то в духе "очень интересно".
Значит сбой в программе.
CAF>>Ну ты напиши, каков итог. Может ты просто прошел этот тур досрочно
CM>Сказал "позвоню завтра". Не позвонил.
Вообще странно. Крупные конторы людей обычно собеседуют пачками, готовы к разнообразным ответам, и развести ля-ля по любому поводу.
Здравствуйте, 0xCAFEDEAD, Вы писали:
CAF>Вообще странно. Крупные конторы людей обычно собеседуют пачками, готовы к разнообразным ответам, и развести ля-ля по любому поводу.
CAF>А что группа, направление?
По моему — ничего странного, кадровики всегда так делают
Site Reliability Engineering или что-то типа того.
Здравствуйте, CoderMonkey, Вы писали:
CM>radix sort прекрасно применим в любых случаях, где применим любой другой алгоритм сортировки.
Вам дали файл JSON 120Gb, у вас 8gb памяти в системе, нужно сортировать по произвольному полю, построчно в порядке возрастания. Как будете сортировать radix sort-м?
Здравствуйте, Тёмчик, Вы писали:
Тё>Вам дали файл JSON 120Gb, у вас 8gb памяти в системе, нужно сортировать по произвольному полю, построчно в порядке возрастания. Как будете сортировать radix sort-м?
Для начала — сортировать что? Что значит "построчно"?
Здравствуйте, CoderMonkey, Вы писали:
Тё>>Вам дали файл JSON 120Gb, у вас 8gb памяти в системе, нужно сортировать по произвольному полю, построчно в порядке возрастания. Как будете сортировать radix sort-м?
CM>Для начала — сортировать что? Что значит "построчно"?
Что непонятно? "построчно" имеется в виду, результат удовлетворяет условию что strcmp(r[n-1].field, r[n].field) >= 0 для всех n 1..N-1.
Здравствуйте, Тёмчик, Вы писали:
Тё>Что непонятно? "построчно" имеется в виду, результат удовлетворяет условию что strcmp(r[n-1].field, r[n].field) >= 0 для всех n 1..N-1.
Непонятно — что конкретно сортировать? У тебя есть файл JSON, а в нем что?
Здравствуйте, CoderMonkey, Вы писали:
CM>Имел собеседование со "специалистом" из Гугла. На вопрос "какова лучшая сложность для алгоритмов сортировки", ответил ему, что O(n).
А вопрос точно был задан как "Какова лучшая сложность алгоритмов сортировки"? Потому что он сам по себе сфрмулирован неточно и ответ "у них сложность O(n)" выдает в отвечающем неадеквата, который дает конкретный ответ на нечетко сформулированый вопрос, подразумевающий уточнение вопроса перед ответом.
Я попробую включить тепелата и предположить что в вопросе упоминались алгоритмы сортировки, сравнивающие элементы попарно. Для этих алгоритмов есть математическое доказательство того, что лучше чем в O(NLogN) они работать не могут, это видимо и был предполагаемый ответ на вопрос. А объяснять это вам не стали, потому что целью собеседующего не является вас просвещать.
Здравствуйте, ylp, Вы писали:
ylp>А вопрос точно был задан как "Какова лучшая сложность алгоритмов сортировки"? Потому что он сам по себе сфрмулирован неточно и ответ "у них сложность O(n)" выдает в отвечающем неадеквата, который дает конкретный ответ на нечетко сформулированый вопрос, подразумевающий уточнение вопроса перед ответом.
Гениально, просто гениально. Рекрутер?
Я тебе задам уточняющий вопрос. Какие другие осмысленные варианты "лучшей сложности алгоритма" ты знаешь, кроме этой?
ylp>Я попробую включить тепелата и предположить что в вопросе упоминались алгоритмы сортировки, сравнивающие элементы попарно.
Здравствуйте, CoderMonkey, Вы писали:
CM>Гениально, просто гениально. Рекрутер?
не-а, собеседующий. Нет, не из гугла
CM>Я тебе задам уточняющий вопрос. Какие другие осмысленные варианты "лучшей сложности алгоритма" ты знаешь, кроме этой?
Уточнять нужно было не определение слова "лучший", а какие именно алгоритмы сортировки и сортировки чего именно имеются в виду.
Потому что есть алгоритмы сортировки, сортирующие массив из N чисел за O(logN), есть алгоритмы, сортирующие за O(K), где K зависит от структуры исходных данных и т. д.
ylp>>Я попробую включить тепелата и предположить что в вопросе упоминались алгоритмы сортировки, сравнивающие элементы попарно. CM>Нет, не упомянались.
а, ну значит он сформулирован был так, чтобы сразу на него отвечали только неадекватные люди
Здравствуйте, ylp, Вы писали:
ylp>не-а, собеседующий. Нет, не из гугла
Сочувствую твоим коллегам.
ylp>Потому что есть алгоритмы сортировки, сортирующие массив из N чисел за O(logN)
Да правда что ли? И где же есть такой волшебный алгоритм?
ylp>а, ну значит он сформулирован был так, чтобы сразу на него отвечали только неадекватные люди
Всякого бреда я насмотрелся, но ты бьешь буквально все рекорды.
Здравствуйте, CoderMonkey, Вы писали:
Тё>>Что непонятно? "построчно" имеется в виду, результат удовлетворяет условию что strcmp(r[n-1].field, r[n].field) >= 0 для всех n 1..N-1.
CM>Непонятно — что конкретно сортировать? У тебя есть файл JSON, а в нем что?
В каждой записи есть некое поле field1, field2 ..., дается произвольное поле (скажем fieldCoderMonkey) и по нему сортировать.
Здравствуйте, CoderMonkey, Вы писали:
ylp>>Потому что есть алгоритмы сортировки, сортирующие массив из N чисел за O(logN) CM>Да правда что ли? И где же есть такой волшебный алгоритм?
в разделе "сортирующие сети" и "параллельные вычисления". Могу, правда, ошибаться и там будет квадрат логарифма от размера массива, а не логарифм размера массива.
Эти алгоритмы работают не сравнивая попарно элементы, а обрабатывая весь массив целиком (т.е. предполагается не стандартная фон-неймановкая архитектура, а другая модель вычислений). На практике такого полно — GPU, ASIC и т. д.
ylp>>а, ну значит он сформулирован был так, чтобы сразу на него отвечали только неадекватные люди CM>Всякого бреда я насмотрелся, но ты бьешь буквально все рекорды.
и вам не хворать!
Здравствуйте, ylp, Вы писали:
ylp>в разделе "сортирующие сети" и "параллельные вычисления". Могу, правда, ошибаться и там будет квадрат логарифма от размера массива, а не логарифм размера массива. ylp>Эти алгоритмы работают не сравнивая попарно элементы, а обрабатывая весь массив целиком (т.е. предполагается не стандартная фон-неймановкая архитектура, а другая модель вычислений). На практике такого полно — GPU, ASIC и т. д.
1. Если ты разобьешь алгоритм на несколько ядер или других вычислительных элементов, то количество операций от этого не уменьшится — уменьшится только время выполнения. Соответственно, величина О-фактора останется абсолютно той же.
2. Отсортировать массив, не сравнив каждый элемент с каким-либо другим как минимум раз — невозможно.
3. Размер любого ASIC или GPU ограничен, а это значит, что и логарифмического времени там тоже не будет — будет оно все равно линейным
Звон ты где-то услышал, но смысл — вообще не понял.
Здравствуйте, Тёмчик, Вы писали:
Тё>В каждой записи есть некое поле field1, field2 ..., дается произвольное поле (скажем fieldCoderMonkey) и по нему сортировать.
Что из себя представляет запись? Это атрибут, элемент в массиве, что-то еще?
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
CM>1. Если ты разобьешь алгоритм на несколько ядер или других вычислительных элементов, то количество операций от этого не уменьшится — уменьшится только время выполнения. > Соответственно, величина О-фактора останется абсолютно той же.
о, пошли философские разговоры. Люблю такое. Что такое "О-фактор", расскажИте? А то у меня тут общепринятое понимание — оно про время выполнения и про дополнительную память
CM>2. Отсортировать массив, не сравнив каждый элемент с каким-либо другим как минимум раз — невозможно.
гениально, браво, спасибо. КО! Если сравнивать элементы массива не по два за один шаг алгоритма, а параллельно группами, можно успеть сделать сравнения быстрее, улавливаете?
CM>3. Размер любого ASIC или GPU ограничен, а это значит, что и логарифмического времени там тоже не будет — будет оно все равно линейным CM>Звон ты где-то услышал, но смысл — вообще не понял.
я смотрю, вам нравится выставлять себя идиотом. продолжим: https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort
Worst-case performance {O(log^{2}(n))} parallel time
Здравствуйте, mgu, Вы писали:
mgu>Здравствуйте, The Passenger, Вы писали:
TP>>бодрым уверенным голосом рассказываете все на пальцах как дебилу ... это только умных оскорбляет а дебилы это любят
mgu>Когда меня впервые спросили про лучшую сортировку (их как раз канонизировали, а я не следил за новостями вселенских соборов), то я искренне ответил: "домЕнная". Слив был засчитан -- не спрашивать же, что это такое? Так что можно смело называть алгоритм Гогенфишмана-Макакагавы и получать три раза ку.
Мы для этой цели придумали куст Лапласа. Применяется в контексте "Ну как же можно не знать таких простых вещей как куст лапласа" или "Или ну этот алгоритм сводится к правильному использованию куста лапласа" к людям которые любят именами разбрасываться. Что интересно почти ссегда работает. Чтобы вызывать у пациента смутное подозрение, что его развели, можно в конце разговора упомянуть пень гамильтона.
Здравствуйте, ylp, Вы писали:
ylp>о, пошли философские разговоры. Люблю такое. Что такое "О-фактор", расскажИте? А то у меня тут общепринятое понимание — оно про время выполнения и про дополнительную память
Общепринятое понимание — про число операций и память.
ylp>гениально, браво, спасибо. КО! Если сравнивать элементы массива не по два за один шаг алгоритма, а параллельно группами, можно успеть сделать сравнения быстрее, улавливаете?
