Как стать автором
Обновить

Комментарии 106

«Дано: массив из N рандомных чисел.»
Отсортировать по убыванию и взять первые K чисел?
НЛО прилетело и опубликовало эту надпись здесь
Почему не оптимальное? Проверил на нескольких миллионах чисел, выполняется очень быстро
НЛО прилетело и опубликовало эту надпись здесь
К раз пройти по массиву из N чисел, каждый раз отыскивая меньшее предыдущего?
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Сложность будет еще хуже: O(N*K)
НЛО прилетело и опубликовало эту надпись здесь
Ну, если K раз пройти по массиву N, как предлагалось выше.
НЛО прилетело и опубликовало эту надпись здесь
А тут N раз пройти по K, не так ли?
Пока что лучший и самый очевидный вариант — O(N*log(N)). При этом я таки в упор не вижу, как сделать быстрее :-(
Проходим по N элементам за O(N), если число больше минимального из отсортированного списка K наибольших, делаем вставку за log(K) (бинари сеч + откидывание минимального элемента).
Тоесть, в хужшем случае (числа идут в возрастающей последовательности) получим оценку O(N*log(K)).
НЛО прилетело и опубликовало эту надпись здесь
Если не ошибаюсь есть сортировка с O(N * log(log N) )
Сортировать N чисел уже умеют за O(N*\sqrt(log(log N))).
Можно получить O(N) для этой задачи:
держим результат в хеше (вставка/удаление за амортизированные O(1)), дополнительно храним минимальное значение элемента в результате
проходим 1 раз по массиву, сравниваем текущий элемент с минимальным — если больше, то кладем в хеш и удаляем минимальное оттуда.
а как в хэше найти минимальное значение?
Да, тоже об этом подумал… минимальное находится за log(K), т.е. будет в худшем случае O(N*log(K))
Я может быть вообще на необитаемом острове живу, но где все берут хеши с O(1)? Это средняя оценка. А в таких задачах интересует худший случай — O(n), для хранения коллизий списком.
Худший случай — это когда все N элементов одинаковые.
В данном случае если диапазон возможных значений рандома намного больше чем N можно пренебречь коллизиями. Если же это не так, то можно в хеше хранить ссылки на кольцевой список номеров элементов, и получить в итоге O(1) на вставку.
Согласен. Про вставку погорячился. Просто последнее время постоянно слышу мнение, что хэш это панацея и все операции в нём за O(1). А чудес не бывает.
Если K = N / 2, то O(N log K) = O(N log N).
НЛО прилетело и опубликовало эту надпись здесь
Да, действительно, вы правы. Выбор k штук описан тут: en.wikipedia.org/wiki/Partial_sorting. Время O(N). Алгоритм является слегка модифицированной версией нахождения k-го наименьшего(наибольшего)
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Priority Queue/Heap (fixed size). O(N * log(K)). Очень часто встречается на StackOverflow, да и на собеседованиях тоже.
НЛО прилетело и опубликовало эту надпись здесь
Отличный способ кстати, в одном проекте так делали показ баннеров с весовыми коэффициентами :)
НЛО прилетело и опубликовало эту надпись здесь
Можно не хранить каждое по N раз, достаточно заранее просчитать «границы» на промежутке от 0 до суммы весов и хранить только их. То есть, если у нас 100 элементов с весами по 2, то можно сохранить просто сотню значений 0, 2, 4,… 198
И генерить равномерно распределенный рандом из этого промежутка, вероятность будет та же.
НЛО прилетело и опубликовало эту надпись здесь
Ну да. Думаю на собеседовании было бы плюсом оба варианта осветить)
Можно посчитать сумму коэффициентов, выбирать значение случайно от 0 до этой суммы, потом пробегать по массиву и суммировать коэффициенты до тех пор, пока они меньше этого числа, и «выдавать» то, на чем остановились. Вроде бы должно работать :)
Вы готовы платить столько своего времени на каждого кандидата? Вы эти вопросы задаёте по телефону или очно? Если очно то вы уверены что кандидата под руками его любимая ide и окружение? Имхо многовато для собеседования.
по телефону
НЛО прилетело и опубликовало эту надпись здесь
Я тоже отвечал. Или их не предлагается делать а предлагается только лишь озвучить варианты? Просто сделать сходу прям тут по телефону не всегда получится быстро.
НЛО прилетело и опубликовало эту надпись здесь
Smart & Gets things done — Сообразительный и доводит начатое до завершения — у Спольски много раз упоминаеться, насколько это важное качество, умение завершать начатое
Резонный вопрос: почему телефон, а не скайп? Даже если скайпиться в наушниках, это не так утомительно, как с трубкой + есть возможность какие-то вещи передавать текстом.

Немного порадовался за себя — практически все вопросы не вызывают, кхе-кхе, вопросов… хороший выдался год, видимо.
1. Многие выходят на улицу для собеседования — шифруются.
2. Корпоративные стандарты.
НЛО прилетело и опубликовало эту надпись здесь
Мне же очень понравилась задача по php, хоть и ужасно проста:

$a = 'I am `a` string';
$b = ' and I am `b` string';
if($a == $c)
echo $a;
if($b == $c)
echo $b;
Найти, чему равна переменная $c, чтобы на экране было написано «I am `a` string and I am `b` string»
Сходу, $c = true;
Браво!
Я же говорю, чрезмерно проста.
Решал недавно похожую задачу. Тут просто — строится граф, в котором ищутся компоненты связности.
Спасибо, хорошее интервью, годное.

Единственное, вопросы по TreeMap/LinkedList/ArrayLis задают все, кто ищет разработчиков под Java, соответственно, если соискатели не глупы, то к ответам на эти вопросы они уже подготовились.

По поводу задачи k из n случайных чисел, действительно, «интуитивное», но не самое быстрое решение, это отсортировать и взять первые k чисел.

Самое быстрое, имхо, это пройти весь массив, и вставлять элементы по мере обработки в новый упорядоченный массив (или дерево), удаляя из него при вставке к+1 самое маленькое значение, действительно, верхняя оценка сложности будет N * log(K). По поводу вероятности, можно сказать что с ростом N, сложность вставки в новый массив будет стремиться к 1 (если мы перед вставкой проверяем минимальное значение в массиве).

Надо подумать над такой идеей: на следующих этапах (во время интервью с Project Manager), спрашивать те вопросы, на которые кандидат не ответил во время ТИ. И если он не сделал попытки погуглить ответы на них, то делать соотвествующие выводы.
Какие выводы?
Понимает ли человек что жизнь слишком коротка чтобы тратить её на ерунду (поиска ответов на ненужные вопросы) ?)
Всего знать невозможно, а само по себе ответы на эти вопросы мало-полезны.
НЛО прилетело и опубликовало эту надпись здесь
Не сочтите за грубость, но это будет или студент или джуниор.

Как пример: Знание о том что внутри Integer живет пул этих самых Integer некоторого размера — достаточно бесполезное знание. Тысячи таких «секретиков» регулярно попадают в поле зрение и так же бесследно исчезают. Не оставив следа ни в одном проекте. И только начинающим разработчикам кажется, что знание таких «секретиков» «важно», и сделает из них настоящего «профессионала». Но это не так)
НЛО прилетело и опубликовало эту надпись здесь
«Как пример:» должно было натолкнуть на мысль причем здесь пул.
Если вы спросили человека про этот пул, а он не знает. Нет ничего страшного в том, что он и не узнает ко второму собеседованию — в работе не пригодится
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
что такое axis в xpath — ничего страшного если человек не поинтересовался ко второму собеседованию если его работа не связана с этим «языком».

про алгоритмы — совсем смешно.
Если у нас работа действительно связана с алгоритмами (комп.графика, комп. лингвистика, неокторые другие области) — то действительно человеку нужно будет ознакомиться с тем что твориться в этой области.
В остальных случаях — все вопросы про алгоритмы — не более чем тешат чсв спрашивающего.
1)Всех алгоритмов знать не получится
2)Сейчас даже ответить на вопрос какой быстрее становится сложно:
Во первых — с распространением многоядерности алгоритмы которые «раньше» были медленными но лучше паралелятся начинают выигрывать на больших объёмах данных.
Во-вторых — все т.н. «оценки сложности» живут в мире «бесконечности». В реальном мире алгоритм, который медленней «в бесконечности», на реальных данных может оказаться быстрей.
НЛО прилетело и опубликовало эту надпись здесь
Почему автор пишет Java вместо JavaScript? Это не одно и тоже.
Вероятно потому что имеются в виду серверные технологии на Java?
Минусующим: про jsp не слышали и иные технологии? Таки да, на Java можно писать и веб-приложения. К тому же TreeMap/LinkedList/ArrayLis явно отсылает именно к Java, а не JavaScript.
Задался таким же вопросом
общий уровень знаний веб программиста, в моем случае на java
Ну а потом действительно общий уровень знаний веб-программиста, без привязки к Java. В конце на вопросах про списки/деревья только пришли к языковым особенностям.
И я. Особенно вопрос про <span> vs <div> убил. Я вот web-программист на Java, но вёрсткой под браузеры ну вот совсем не занимаюсь. Зачем, если мои RESTful API возвращают удобные всем JSON и каждый клиент обработает их как ему удобнее?
Я так подозреваю, что это все исходит из концепции «человек-оркестр».
Все никак не могу понять, почему телефон не заменить на скайп, как во многих конторах, сами же говорите, ухо отваливается за час, в наушниках значительно легче, да и руки свободные для рисования/кодинга.

P.S. Сталкивался с вашими HR, очень агрессивный поиск кандидатов, практически спам. Часто еще на этом этапе отбивают желание продолжать общение.
Я тоже сталкивался с их HR-ми, не скажи, что они были очень любезны, но обещали «до $1000» за голову приятеля, если я приведу.
Я так понимаю внутри компании тоже есть бонус за успешного кандидата. Если кто-то привел, ему часть премии, а если HR сам нашел, то вся премия ему. Это как-то объясняет такой агрессивный хантинг.
>Все никак не могу понять, почему телефон не заменить на скайп

Может быть потому, что далеко не все разработчики имеют возможность работы в отдельном кабинете или выйти с ноутом в безлюдное место и тд и тп. Если я на рабочем месте, где ещё 5 человек работают, буду в течении 2 часов отвечать на вопросы интервью, меня побьют палками и будут правы.
Если вы говорите с позиции человека, который проходит интервью (я так понял что вы именно про этот случай), вы абсолютно правы (в этом случае обычно, спрашивают удобно ли говорить и если нет, то когда будет удобно, можно ли через скайп и т.д.), а если с точки зрения человека, который проводит интервью, то нет. Топик рассказывает как раз о втором случае. Если в компании нет возможности для интервьюера спокойно провести собеседование в удобной обстановке для обеих сторон, то это немного странно.
>а если с точки зрения человека, который проводит интервью, то нет

«То нет» — что? Если собеседник (соискатель) говорит по телефону, то интервьюер, конечно, может позвонить ему и со скайпа. Особенно, если у него есть нормальная обратная переадресация (не знаю бывает ли такое у скайпа). Чтобы соискатель мог куда-то перезвонить при случае. Ну, из соображений элементарной вежливости, что ли… Из замечания про отваливающееся ухо я понял заботу топикстартера скорее о соискателе, нежели чем о себе :).

И… это… вы же говори про свободные руки для кодинга. Это очевидная ссылка на соискателя — интервьюеру-то что кодить? :)

А так, да, — если интервьюеру нет возможности всякое такое проделать, то это, конечно, странно.
Я так подозреваю, что сфинкс, как и я, обратил внимание на то, что разговор по скайпу даже не рассматривается luxoft'ом (хотя не спрашивал, м.б. по желанию «клиента» и согласились бы). Ибо даже час по телефону — для меня это грустно. По скайпу тоже не всегда приятно, но много легче. Понятно, что это не должно быть единственным вариантом, но отсутствие выбора тоже не гут.
Да, вы абсолютно верно поняли мою точку зрения.
«То нет» — это, если у человека который собеседует, нет возможности найти спокойное место для собеседования (как вы написали выше) и его коллеги побьют палками, если он будет проводит собеседование по скайпу и поэтому, соискатель будет вынужден беседовать с ним по телефону, то это по меньшей мере странно. Я все рассматривал исходя из того, что написал автор топика, что собеседование он проводит по телефону. То есть мне странно почему именно по телефону, почему не по скайпу, если есть возможность — ведь при обоюдном согласии это значительно легче и для одной и для другой стороны. Я вот про что.
Вообще-то к почти всем предлагаемым задачам нужно указывать критерии — одноразовая ли это задача («надо сделать сейчас, как можно быстрее и забыть») или регулярная («это надо делать 20 раз в секунду с разными наборами данных»). Решения серьёзно отличаться будут.
Поддерживаю. А то меня тут недавно не взяли в одну контору потому, что я при выполнении тестового задания не комментировал каждую строчку кода и не раскидал «подсистемы» по файлам. А задача-то была сделать долбаный салют (система частиц), что вылилось в 428 строк кода, включая копирайт и лицензию BSD (меньше, чем у других соискателей, между прочим). Зачем размазывать «физику» среднешкольного уровня и отрисовку по нескольким классам и файлам для одноразовой работы? Развивать этот шмат кода никто не будет — нормальный программист возьмёт готовую библиотеку систем частиц с редактором, заодно и задумается над структурой проекта (файловой и классовой). Комментировать очевидные вещи, как это делали другие, принятые на работу соискатели (у одного комменты были почти на каждую строчку), я тоже смысла не видел — проще давать понятные имена функциям и переменным.

Фактически, меня не приняли в компанию просто потому, что я отнёсся к тестовому заданию, как к тестовому заданию, а не как к заготовке для полноценного проекта. Я для разных задач пишу разный код, и считаю это правильным. Не вижу смысла городить огород, если это не нужно, и если никто специально не просил.
Да, очень легко забыть сказать, что именно этой задачкой проверяется — умение структурировать код под большие проекты, умение писать понятные комментарии или умение быстро и эффективно решить одноразовую задачу.
Структурирование кода — задача архитектора.
Нужно уметь писать не понятные комментарии, а понятный код.
Эффективность решения одноразовой задачи только одна — чем быстрее, тем лучше.
6. Транслировать числа в адреса памяти, записать по адресу единицу. Читать адреса с конца, пока не наберется К чисел. :D Попутно можно использовать принцип ассоциативного кэша, чтобы минимизировать чтения.
6. Каждый коэффициент представить в виде интервала. Начальное значение — 0 или значение конца предыдущего интервала. Конечное значение — начальное + сам коэффициент. Можно заменить сам коэффициент конечным значением. Рандомом выбирать число от 0 до нового значения последнего коэффициента. Потом найти первый коэффициент больше полученного рандома.
Много спорного. «Технические блоги» пестрят статьями про «Hello world» и «как преобразовать строку в int». Половина «правильных» решений про эксель файл будет работать до первой даты, времени, разделителя_в_виде_запятой и прочих локалей. Регэксп я и практически все коллеги исспользуют в лучшем случае раз в три года. Я разбираюсь в нём и тут-же забываю до следующего раза.

И так далее и так далее…
Про регэкспы, пожалуй, поддержу. Действительно, наиболее востребованные для меня регэкспы это имейл, фио, номер телефона — для этих случаев у меня записаны нужные регэкспы, их просто скопипастить, даже вникать уже не нужно. Экзотика встречается заметно реже, тогда я снова гуглю регэкспы, разбираюсь и… да, снова забываю до следующего раза.

Конечно, если бы я ими постоянно пользовался, я бы их помнил и мог очень быстро составить нужный, но из за редкости применения этого не происходит, тупо забываю. Нет, могу сходу составить регэксп для простого случая — настолько я этот инструмент помню, но если сложный случай — приходится снова разбираться.
Поддержу, меня не меньше удивляет, когда всерьез не воспринимают ответ на собеседовании: «Работал, на память не помню, обычно гуглю».
Поток мыслей насчет задачи 5:

Если N очень большое и значения действительно рандомны, то K верхних с большой вероятностью будут больше (1-K/N) для случая, когда рассматривается диапазон (0; 1), или больше (Xmin+(Xmax-Xmin)(1/K/N) для произвольной базы рандома. Необходимость дальнейшей проверки это не снимает, но позволяет ее минимизировать. Один раз (сложность N) проходим по массиву и отбираем множество значений, которые больше (1-K/N). Далее в зависимости от их количества (Q): Q=K — задача решена, Q>K — отбираем (Q-K) наименьших, Q<K — перебираем (N-Q) на предмет (K-Q) наибольших. Таким образом, сложность будет приближаться к N(1+abs(Q-K))/2 с нормальным распределением (Q-K) вокруг нуля с вероятностью 146%:) В общем, идея в том, чтобы отталкиваться от свойств рандомности как таковой без лишних сортировок.
А я подумал взять небольшой сабсет, выяснить характеристики распределения по нему, и посчитать границу. Потом пойти по всему массиву отбирая всё, что выше этой границы. Сложность будет O(M + N) (где M — размер начальной выборки).

Но если сразу предположить, что распределение равномерное (как у Вас), то ещё проще получается, конечно.
Ну да, если допустить, что изначально Xmin и Xmax неизвестны. (Как-то по умолчанию сразу подумал, что рандомные значения будут находиться в диапазоне (0; 1), поэтому этот шаг пропустил.)
Спасибо за статью.
Почерпнул несколько хороших мыслей.
Кстати, а что будет быстрее на миллионе записей ArrayList или LinkedList? Минусы каждой из структур данных описаны в статье. Насколько помню, попадавшиеся на глаза тесты — ArrayList побыстрее будет. Но здесь вопрос наверное требует уточнения: важна ли нам на фоне общей скорости скорость вставки одного элемента или нас интересует только общая скорость. Если общая, то судя по всему ArrayList, если важная скорость вставки каждого элемента, то LinkedList, т.к. на вставка будет происходить всегда за O(1), а у ArrayList вставка некоторых элементов будет предваряться увеличением и копированием ArrayList, соотвественно будет значительно O(n). Я бы так наверное ответил.
в 5-той задаче оптимальное решение такое — найти N/2-ую порядковую статистику за O(N) и за один проход найти все числа меньшие ее.
Доказательство что оптимальнее нельзя основано на том что «вход нужно дочитать»
Только не N/2, а K-ую. N/2 — будет худшим случаем(максимальная константа).
для 6-той задачи оптимального решения тоже еще не увидел.
Пусть n — длина массивов.
Оптимальное решение — предобработка за O(n) и создание случайных чисел за O(log(n))
Предобработка состоит в подсчете префикс сумм массива весов. Образованные числа соответствуют концам интервалов соответствующим элементам массива на числовой прямой. Важно заметить что эти концы уже отсортированы.
Выбор конкретного числа производится так — создаем случайное число из интервала от 0 до суммы всех чисел(формально это тоже создание минимум log(n) бит) и бинарным поиском по массиву префикс-сумм ищем интервал куда попало образованное число. Число соответствующее интервалу и будет ответом.
Решение оптимально на основании того что из соображений теории информации нам нужно разрешить не менее log(n) энтропии чтобы выбрать конкретное число.
НЛО прилетело и опубликовало эту надпись здесь
В случае равных весов выбор элемента определяет однозначно число в интервале 1..n и наоборот.
Что однозначно определяет log n бит его записи и наоборот.
Вывод — в случае равных весов выбор элемента равноправен фиксации log n бит.

Потому да, я утверждаю что, в случае если единичной операцией будет создание константного числа случайных бит, невозможно выбрать случайный элемент быстрее чем за O(log n). Потому что это означало бы что можно быстрее чем за O(log n) создать O(log n) случайных бит. Что противоречит тому, что мы можем за единичную операцию создавать лишь константное число случайных бит.
Мне понравилось как в «Докторе Хаусе» набирают персонал — после предварительного отсеивания набирается больше специалистов, чем нужно, они работают испытательный срок и там уже становится ясно кто как работает, индивидуальная совместимость и пр. Конечно, это требует больше времени и средств, но:
1) меньше шансов отбросить хорошего кандидата, а на собеседовании многие не в состоянии нормально думать )
2) отсутствует психологический барьер, когда вы выбрали кандидата, а он в итоге не очень-то хорош, но увольнять не хочется, потому что придётся опять искать и собеседовать новых кандидатов.
3) может оказаться, что новички работают получше некоторых старичков и в итоге могут занять больше мест, чем планировалось.
4) ну и даже если вам придётся распрощаться с неплохими кандидатами, если позже появится вакансия, вы можете сэкономить время и обратиться напрямую к ним, если они ещё не нашли работу и не обиделись )
Да доктор Хаус, по моим наблюдениям, вообще очень неглупый мужик. :)
Мне показалось, что это у них распространённая практика, не подошедших специалистов, вроде, даже определяют в другие, менее крутые клиники, интересно, у нас где-нибудь такое практикуют?
Такие кандидаты могу начать пакостить друг другу, вместо того чтобы работать сообща.
Если напакостить другим не удастся, и с ними попрощаются, то они могут оставить backdoor или слить конфеденциальную инфу.
Если кандидаты все были нормальные, то трудно выбрать кого оставить, а уволенный может перетащить за собой старичков, с которыми успел сработаться.
Новичку требуется достоточно много времени чтобы вкатиться и показать реальную эффективность, и он не будет работать бесплатно все это время, это будет очень дорого.
Уволенные могут подать коллективный иск в суд.
И наконец, это очень рискованно с точки зрения кандидата, я бы сам на такой вариант не пошел.
Новичку требуется достоточно много времени чтобы вкатиться и показать реальную эффективность

то есть на собеседовании за пару часов он покажет свою эффективность лучше, чем за несколько недель работы?
, и он не будет работать бесплатно все это время, это будет очень дорого.
Уволенные могут подать коллективный иск в суд.

Про испытательный срок не слышали? Дорого — это нанять плохого работника, а пара лишних специалистов на испытательном сроке много не съедят. Если хотите сэкономить ещё больше — никого не нанимайте, а деньги себе оставьте.
Такие кандидаты могу начать пакостить друг другу, вместо того чтобы работать сообща.
Если напакостить другим не удастся, и с ними попрощаются, то они могут оставить backdoor или слить конфеденциальную инфу.

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

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

В большинстве случаев всё равно сначала берут на испытательный срок, если только не докажете, что действительно крутой специалист и не поставите вопрос ребром. Так что риски одинаковые.
Судя по фото, мы говорим о специалисте, которого боятся проблемы. Который убивает проблемы быстрее, чем те об этом подумают. Собеседование с ним — понятие вырожденное, это не он хочет устроиться работать, это вы мечтаете его заполучить :)
Вопросы лучше тщательнее формулировать.
Например, по задачкам 4 и 5. Почему-то подразумевается, что импорт из Excel — одноразовая операция, а поиск наибольших K чисел из N — часто повторяющаяся. Но явно об этом не говорится.
А в жизни обычно наоборот: Excel приходится загружать ежедневно, а искать K наибольших чисел — лишь для какого-то одноразового отчета. И в этом случае оптимальными становятся решения, получившие наименьшую оценку автора )
Все, я подготовился к встрече с вами )

А на самом деле хочу поинтересоваться, больше всего интересует меркантильная часть ваших поисков. Судя по вопросам вы подбираете человека, который достаточно опытен, но еще далек от профессионала. Сколько вы готовы ему предложить, как вы в дальнейшем планируете человека мотивировать?
Все эти вопросы, тесты только чтобы найти, а как удержать, заинтересовать?
я не выполняю никаких управленчиских функций, единственное что я могу — хорошо относится к людям чтобы им было комфортно работать
Еще бы давались ответы на вопросы. Нашел парочку на которые ответить не смогу.
Погуглить конечно можно и нужно, но хотелось бы узнать какие ответы ожидает сам автор.
Так же можно решить насколько объективно автор судит.

Автор, создавай интерактивный тест где можно проверить себя :)
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.