Здравствуйте, CoderMonkey, Вы писали:
CM>Что из себя представляет запись? Это атрибут, элемент в массиве, что-то еще?
Какая разница? Это подстрока, вычисляемая за пренебрежимо малое время из элемента линейной коллекции.
Более того, JSON-файл можно тупо заменить на обычный текстовый с требованием отсортировать строки по алфавиту. QuickSort с сегментацией и объединением справится, Radix — забуксует.
Здравствуйте, alpha21264, Вы писали:
CM>>>radix sort прекрасно применим в любых случаях, где применим любой другой алгоритм сортировки. Тё>>Вам дали файл JSON 120Gb, у вас 8gb памяти в системе, нужно сортировать по произвольному полю, построчно в порядке возрастания. Как будете сортировать radix sort-м?
A>Да в общем-то как обычно в пределах 8Гигов. Потом, разумеется сортировка слиянием. А ты как думал?
А подробнее?
PS Думаю, что ты не понимаешь ограничения radix sort и не знаешь сложность merge sort.
Здравствуйте, CreatorCray, Вы писали:
L>>В данном случае человек скорее всего ждал от вас рассказа CC>Для этого открывается рот и издаются звуки вопросительных интонаций.
Кандидат сморозил дичь и замолчал. Можно попытаться тянуть его, давать подсказки- но в данном случае он с апломбом. Такие не нужны.
L>> какие ограничения radix sort накладывает на сортируемые сущности (knowledge of internal structure) и почему этот чудо алгоритм не является выбором по умолчанию для библиотечных функций сортировки. CC>Это отличный повод побеседовать и выяснить понимает ли кандидат все эти нюансы.
О чём беседовать?
CM>>Сказал "позвоню завтра". Не позвонил. CAF>Вообще странно. Крупные конторы людей обычно собеседуют пачками, готовы к разнообразным ответам, и развести ля-ля по любому поводу.
Ни в Гугл, ни в Яббл, собеседующие перезванивать не будут, т.к. им запрещено. Этим занимаются HR. Стало быть, тредстартер беседовал с HR, поэтому уже одно то, что HR знает про N * log(N), уже неплохо. И то, что HR отсекает бестолковых выпендрежников, это тоже очень хорошо. Потому как если такого возьмут ненароком, кому-то придется с ним в одной команде работать.
Здравствуйте, CoderMonkey, Вы писали:
CM> ответил ему, что O(n). Нет, говорит, это неправильно — должно быть O(n * log n). Правильно, говорю, именно O(n). Есть такой radix sort, у него сложность именно такая.
А теперь представь такой же разговор на реальном проекте. И вот вы, как два барана, сидите и про*бываете деньги работодателя вместо того, чтобы быстро договориться и фигачить дальше. И если собеседующего ещё как-то можно оправдать — не у всех есть наывыки оцевать специалистов, то тебя никак не оправдать — открывать с ноги дверь в контору, у которой спрос в стопицот раз превышает предложение, это профнепригодность сразу же, ибо программист должен не только в алгоритмах разбираться, но и в аналитику уметь децл.
Чтобы не было обидно, могу сказать, что в молодости я тоже так переодически поступал к предсказуемым результатом, и меня так же переодически тыкали носом. Это совершенно нормальный процесс взросления и получения опыта, но нюанс в том, что кому-то хватает сил переступить через свою гордость и идти дальше, а кто-то так и остаётся "непризнанным гением". Кстати, с высоты лет хочу заметить, что воспринимать себя как среднячка и постоянно перечитывать учебники и учить новое гораздо выгоднее, чем тягаться с топами, потому что "топы" сами по себе, во-первых, явление уникальное — кто-то вот просто так может спать по 4-5 часов в день, а, во-вторых, часто субъективное. Быть среднячком проще, и можно прокачивать навык переговоров по зарплате совершенно независимо.
Здравствуйте, cppguard, Вы писали:
C>И вот вы, как два барана, сидите и про*бываете деньги работодателя вместо того, чтобы быстро договориться и фигачить дальше.
Pzz>Radix sort'ом нельзя сортировать гномиков. Для гугля это существенное ограничение. С такими ограничениями для них этого алкогоритма считай, что нет.
И хешировать гномиков тоже нельзя, это будет воспринято как discriminatory behavior.
Здравствуйте, MaximVK, Вы писали:
Pzz>>Radix sort'ом нельзя сортировать гномиков. Для гугля это существенное ограничение. С такими ограничениями для них этого алкогоритма считай, что нет.
MVK>И хешировать гномиков тоже нельзя, это будет воспринято как discriminatory behavior.
Получается, единственный способ их отсортировать — это призвать в армию, и "раз-два-три, по росту становись!".
Здравствуйте, CoderMonkey, Вы писали:
CM>Имел собеседование со "специалистом" из Гугла. На вопрос "какова лучшая сложность для алгоритмов сортировки", ответил ему, что O(n). Нет, говорит, это неправильно — должно быть O(n * log n). Правильно, говорю, именно O(n). Есть такой radix sort, у него сложность именно такая. В ответ — недоуменно-возмущенное молчание. Похоже, не поверил. CM>Кажется, никакое продолжение мне не светит
Интересно, конечно, послушать другую сторону.
Вдруг, при цитировании вопроса "какова лучшая сложность для алгоритмов сортировки" вы забыли слово "сравнением"?
SLR>Глубинная причина успеха гугля вовсе не в линейной сортировке. SLR>Она заключается во внедрении SCRUM во все бизнес-процессы начиная с момента появления компании и по сей день.
А вот и сектанты подтянулись!
Но вам сначала с сектой инклюзивности нужно договориться, у них отличный от вас взгляд на причину успеха гугла.
Здравствуйте, Quebecois, Вы писали:
Q>Более того, JSON-файл можно тупо заменить на обычный текстовый с требованием отсортировать строки по алфавиту. QuickSort с сегментацией и объединением справится, Radix — забуксует.
Здравствуйте, cppguard, Вы писали:
C>А теперь представь такой же разговор на реальном проекте.
Тут есть один важный нюанс. Кто-то прав, а кто-то нет. Возможно даже, оба неправы. Но такие вопросы очень желательно прояснять, чтобы потом не пришлось горевать, что повысили дурака с длинным языком. И плохо от этого будет всем — и ниже, и выше по карьерной лестнице.
Здравствуйте, Quebecois, Вы писали:
Q>Более того, JSON-файл можно тупо заменить на обычный текстовый с требованием отсортировать строки по алфавиту. QuickSort с сегментацией и объединением справится, Radix — забуксует.
Здравствуйте, Codealot, Вы писали:
Q>>Более того, JSON-файл можно тупо заменить на обычный текстовый с требованием отсортировать строки по алфавиту. QuickSort с сегментацией и объединением справится, Radix — забуксует. C>Так все же, почему? Очень интересно.
Потому что в общем случае (с произвольным длинами строк) у радикса получится дерево ВСЕХ строк, которое надо будет проходить при добавлении каждого элемента. Т.е. тот же NlogN, только по медленному диску вместо быстрой RAM.
QuickSort позволит тупо побить файл на фрагменты по размеру RAM, отсортировать их в памяти с тем же NlogN, и потом объединить в один проход. RAM для этого нужно ровно столько, чтобы одновременно туда влезло по самой длинной строке из каждого фрагмента.
Здравствуйте, Quebecois, Вы писали:
Q>Потому что в общем случае (с произвольным длинами строк) у радикса получится дерево ВСЕХ строк, которое надо будет проходить при добавлении каждого элемента.
Здравствуйте, lintik, Вы писали:
L>скорее всего ждал от вас рассказа какие ограничения radix sort накладывает на сортируемые сущности (knowledge of internal structure) и почему этот чудо алгоритм не является выбором по умолчанию для библиотечных функций сортировки.
Все равно сортируют обычно числа и строки, а также наборы чисел и строк. Причина совершенно другая.
