Задачи на собеседованиях в Яндексе

[Chijikson]

Жаль на хабре не придумали заметки :(

[barmaley_exe]

Какие заметки? Заметки есть для пользователей, а ещё Вы можете добавить статью в избранное и указать собственные теги.

[Suvitruf]

Проходил собеседование в Yandex на вакансию Android-разработчика. Целый час все разговоры были только теоретические: контейнеры, сложность алгоритмов и т.д. Вопросов по синтаксису или по компонентам, собственно, самой платформы задано не было.
По истечению часа прервали собеседование, мол «на собеседование отводится не более часа».

Пара неприятных моментов:
1) По прошествии какого-то времени пришла стандартная отписка. Такая же практика и в mail и других подобных компаниях, которые не могут по-нормальному написать письмо с отказом. В небольших компаниях HR или тех. специалист даже сам может позвонить и сообщить о решении. Видимо, в больших компаниях людей не особо ценят.
2) На мои вопросы о том, чем придётся заниматься, какая команда, какие условия, какая з/п, ответа не получил. Отнекивались мол «мы не имеем права разглашать эту информацию». Выходит, хотите нанять хорошего разработчика, который в итоге получает кота в мешке.
3) То что, на собеседовании не спрашивают про саму платформу/язык, а задают какие-то абстрактные теоретико-алгоритмические вопросы, для меня навсегда останется загадкой.

[iSheeZ]

И не только в Я. Практически во всех компаних (по моему опыту) спрашивают только теорию (которая, как правило, не особо полезна на практике)

[eastig]

Странная у вас практика. В моей практике сплошные NP-hard задачи, а тут без теории не обойтись.

Да ведь спрашивают ведь не что-то навороченное, а базовые вещи которые должен знать разработчик. Про Яндекс могу сказать, что у них объемы данных такие, что даже классические алгоритмы пробуксовывают. Вот тут вы почувствуете разницу между O(n*log(n)) и O(n^2).

[AccessGranted]

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

[eastig]

Думаю разрабоку компиляторов можно отнести к производственной сфере.
У меня есть опыт создания и Web-приложений, и библиотек, то есть того что используется в продакшене. Во всех случаях знание алгоритмов и структур данных требовалось. Почему-то все с кем я работал хотели, чтобы их приложения работали быстро.

[philpirj]

Почему-то все, с кем я работал, хотели, чтобы их приложения были быстро написаны. Avoid premature optimization.

[eastig]

Avoid premature optimization.
Это немножко из другой области. При разработки архитектуры приложения у нас принято проводить анализ предметной области. Например, если количество данных не больше 2^32, мы спокойно используем битовый вектор. Если данные равномерно распределны, то хэшь таблицу. Знаем какие у нас данные и соотвественно выбираем алгоритмы и структуры данных. Где здесь преждевременная оптимизация?

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

[jcmvbkbc]

Под преджевременной оптимизацией обычно понимают любые изменения кода «чтобы было быстрее/меньше по размеру» без предварительной оценки, где тормозит/где толсто, и, порой, вообще без насущной необходимости.

То, что вы перечислили, при определённых условиях, вполне может выступать в роли реальной оптимизации.

[deilux]

Программистов вокруг много и готовых результатов, которым можно пользоваться — тоже. Одну и ту же задачу разные фреймворки\утилиты решают по-разному. И не зная теоретических основ, можно легко выбрать неподходящее в вашем случае решение. Так что вопрос очень и очень спорный.

[xaoc80]

Мне как-то девушка позвонила их HR Яндекса из Питерского офиса и тоже на позицию Андроид разработчика. Сказала, что вышлет мне тестовое задание. Если мне не изменяет память, надо было написать архиватор аля gzip за 1 час (ну я так задание это понял и выглядело оно именно так) и это в рабочий день. Само собой я за это время на работе врядли смог бы что-то сделать, кроме предполагаемых интерфейсов класса…

[Suvitruf]

Почитайте эту статью (http://habrahabr.ru/post/178037/). ZeptoLab просит написать игру в тестовом задании.

Я тоже подумывал к ним устроиться, но когда ты только переехал в чужой город и ищешь работу, то тратить недели/месяцы на тестовое задание не видится возможным. К тому же, судя по истории zagayevskiy, шансы туда устроиться даже с готовым заданием малы.

[zagayevskiy]

Кстати, они все еще ищут девелоперов, начали поднимать базы претендентов годовой давности.

[Zverik]

Вдруг кто-нибудь за год написал эту чёртову игру.

[zagayevskiy]

Я написал пакмана, и чуть-чуть не дописал их текущую хотелку — Астероиды. =)

[alexkirichkov]

На сайте теперь нормально указывают, что нужен человек, который напишет за 10-12 часов.

И что нужны строго плюсы, а не Obj C

где — то год назад я написал, так что даже позвали на собеседование, но требования высоковаты оказались — нужно было польше опыта именно работы, а я скорее для себя программирую

[dapi]

Обычно на собеседованиях спрашивают то, что сами недавно узнали.

[xaoc80]

Я с Вашего позволения это затвиттил. Само собой, с указанием копирайта.

[xaoc80]

Чем хорошь хабр так это тем, что никогда не угадаешь за что могут слить карму.

[Badevlad]

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

[esir_pavel]

Ну как сказать, с цифровыми вычислителями разные случаи встречаются.
habrahabr.ru/company/intel/blog/205970/

[lkern]

А также тем, что непонятно за что её добавляют.

[Zverik]

Если кармой дорожишь, до такой степени, что изливаешь свою боль публично, — потеряешь. Пиши хорошие статьи, карма после перехода границы в 20-30 уже не важна.

[xaoc80]

Дело не в этом. Дело в непредсказуемости что ли. Карма здесь (ну мне лично) нужно лишь для возможности публикации. Есть штук пять работ, которые оформляю в виде статей. У меня, если честно первый раз так — комментарий и слитая карма. Ведь важна не карма, а понимание того, что, если кто-то слил, значит твой коммент кого-то обидел или покоробил. А это приводит к непониманию и самокопанию. Наверное, не надо быть таким мнительным, да.

[anatolix]

На самом деле есть еще более продвинутая концепция, нужно на собеседования задавать вопросы, на которые вообще ответа никто в компании не знает и уже несколько месяцев все ищут :)

Часто так делаем на собеседованиях людей уровня эксперта.

Если что, это не на случай, что вдруг сейчас скажут правильное решение решение, так ни разу не было(хотя каждый раз надеемся). А просто если человек придет он тоже будет искать ответ на этот вопрос, и будет круто проверить, что он на одной волне, в смысле понимает тему и может в команде работать над поиском ответов.

[bachin]

В двух местах (я сейчас говорю не о яндексе) мне предложили в качестве «домашнего задания» довольно сложные алгоритмические задачи. Обе задачи весьма «синтетические». Я думаю 95% кандидатов просто берут самоотвод, увидев условие. Особенно обидно, когда решаешь задачу (пусть не идеально, но тратишь на нее какое-то весьма ненулевое время, а в ответ потом тишина)

Хотите испытать себя? Могу продиктовать условие.
На вход алгоритму дается последовательность беззнаковых 48-битных чисел.
Программа должна отбросить все составные (то есть не простые) числа и найти наидлиннейшую возрастающую последовательность из простых чисел. ( 2, 12, 3, 4, 11, 5, 7 -> ответ: { 2, 3, 11 } )
Размер исходных данных неизвестен. Естественно, числа там большие, так что проверять на простоту каждое встреченное число скорее всего долго. Ограничение по памяти — программа 32-битная. Должна использовать несколько ядер проца.

На вторую подобную задачу сейчас жду ответа. Честно говоря, в третий раз подобным аниматься не захочется

[Pastafarianist]

Можно найти все простые до sqrt(2^48)=2^24 решетом Эратосфена на битовом массиве, понадобится 2^24 / 8 = 2^21 байт, каких-то жалких 2 метра. Потом классический алгоритм для поиска наидлиннейшей возрастающей подпоследовательности. Только фиг знает, куда здесь запихать многоядерность.

[anatolix]

В результате прогона решета у вас будет все простые числа до 2^24, но между 2^24 и 2^48 тоже наверняка встречаются простые числа и их тоже будет нужно найти, для этого достаточно будет поделить их на все простые числа из решета. «Вот тут то мышка и пригодилась....» (с) анекдот. В смысле куда деть несколько CPU теперь понятно(да и решето на них можно считать, если аккуратно).

Ход мыслей imho очень правильный, хотите к нам в Яндекс?

[Pastafarianist]

Вы приглашаете? )
А если серьёзно, мне бы выучиться сначала. Злобный физтех не пускает переводников посередине года, но если преуспею в Хитром Плане™ попасть туда через семестр, то ждите через пару-тройку лет :)

[Lol4t0]

Да можно просто исключать в несколько потоков.

[alexfetisov]

По-моему, решето даже не нужно. Можно просто параллельно каждое число факторизовывать за O(sqrt(N)) (то есть если мы нашли делитель до корня, то грустно — число не подходит, иначе оно простое). Потом да, классика за O(n*logn), так как итак есть O(n*sqrt(N) / ядра), то возрастающая последовательность не даст крутой вклад в производительность.

Вообще, я бы из задачи убрал возрастающую последовательность и получил бы неплохую задачу. Так как про проверку на простоту кандидат по идее знать должен, а вот про поиск последовательности — это уже число олимпиадная фишка :)

[leonid-lapidus]

а почему ответ в вашем примере не {2, 3, 5, 7}? я что-то невнимательно прочёл?

[bachin]

потому что 11 нельзя выбросить. это же простое

[Strepetarh]

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

[Mrrl]

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

[bachin]

Я прошу прощения за то, что написал условие задачи несколько невнятно. Писал по памяти, как раз в примере отразил особенность — нельзя игнорировать простые числа. Иначе задача сводилась бы к тривиальной — проходим последовательность «с конца», находим в ней простые числа меньше предыдущего найденного

[Mrrl]

Задача «найти самый длинный монотонно возрастающий фрагмент» на порядок проще, чем «найти самую длинную монотонно возрастающую подпоследовательность с возможными пропусками». Если первая легко решается за линейное время и за один проход, то для второй нужна дополнительная память O(N), и не удивлюсь, если в худшем случае потребуется квадратичное время (O(n*sqrt(n)) уж точно бывает).

[Mrrl]

А, там возможен бинарный поиск по длине. Тогда конечно.

[anatolix]

Мы аккуратно обращаемся с объемными задачами на дом, ровно потому, что понимаем что хорошие разработчики обычно более-менее заняты.

Могу вам посочувствовать, и предложить мне мне anatolix@yandex[-team].ru заслать вашу реализацию про поиск 48-битных простых чисел, на которую вам не ответили, если хорошо написано мы вам ее зачтем ее в карму на собеседовании.

[kit]

Придерусь к «Программа должна отбросить все составные (то есть не простые)».
Единицу надо отбрасывать?

[bachin]

это несущественно. единицу и ноль (буде таковые встретятся) можно считать как угодно.
в условии это явно не было указано, но на сложность и структуру алгоритма это не повлияет

[winger]

Проверять на простоту можно вероятностным тестом за O((log n)^3) битовых операций.

[bolk]

Ха, мы тоже так делали во внутренних сервисах :) Например, спрашивали верстальщика как бы он сверстал сетку занятости переговорок, которая ехала в «Опере». Самый кайф был, когда один верстальщик подсказал идею как это можно было сделать!

[Gero]

Взяли его хоть?

[Stas911]

Зачем, если он и так все выболтал?

[bolk]

Взяли, вроде :) Не помню, несколько лет прошло :)

[keslo]

Самоутверждение за счет претендентов? :-)

[anatolix]

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

Надо понимать, что Яндекс очень технократичная компания, вон менеджеры auto_ptr-ы используют :), и значительную, часть собеседований проводят хорошие программисты, но вообщем не очень хорошие HR-ы (но как вы наверное знаете обычные HR-ы не программисты обычно еще хуже).

Собственно, мы сейчас пытаемся в компании некие более-менее унифицированные собеседования, обучать людей их проводить и должно постепенно стать лучше.

p.s. Если мне в anatolix@yandex[-team].ru напишите ФИО, email и примерную дату собеседования, могу поузнавать подробности и попробовать что-нибудь в косерватории починить, не смотря на то android от меня совсем далеко.

p.p.s Предложение, кстати относится не только к вам лично, но и вообще ко всем кто по какой-то причине остался недоволен собеседованием в Яндексе.

[sphinks]

Расскажу свой опыт собеседования в Я. Собеседовался 2 раза за 2 года — 1 раз очно, 1 раза удаленно. 1 раз все закончилось оффером, 1 раз — отказом. В целом очень не равномерно получилось, первое собеседование было очное, достаточно живо прошло с обоюдным интересом. Два человека меня собеседовали четыре часа, вопросы, задачи и прочее.
Второе собеседование было достаточно печально, 4 собеседования по 1 часу на скайпе, все испортило первое собседование (по профилю вакансии — Java, т.к. на java-developer`а шел), где три анонимных собеседователя (знал только их имена), весело и довольно не сдержанно, смеялись над моими решениями задач, это задело, я задал вопрос, что такого смешного, пускай в возможно неверном решении. Такое замечание видимо их задело, и дальше разговор не сложился :) Оставшиеся 3 собеседования и собеседники были на уровне, но я понимал, что уже нет смысла, основное завалилось, ну и настроения было уже ниже не куда. Закономерный результат — отказ.
Понимаю, что раз на раз не приходится, но случай засел в памяти, видимо до тех пор, пока не наткнусь на еще более «интересный» способ проведения собеседования.

[eastig]

Зря вы свой HR ругаете :). Нормальный он у вас. Менеджерам за auto_ptr нужно сказать «ая-яй-яй».

В качестве примера, идеального собеседования, могу привести собеседование в Амазон. HR занимался организацей процесса собеседования, отвечал на все возникающие вопросы, запрашивал feedback на собеседующих. Кроме того HR задавал воросы нетехнического характера: почему Амазон, про опыт и т.п. Когда в ответе было много технической информации, честно говорили, что они не специалисты в данной области. Люди, которые проводили собеседования, были вежливы. Вопросы задавали по существу, а не с целью завалить.

[anatolix]

Я не свой ругаю, а вообще, HR без программиста не может рекрутить. Да вот мы сейчас пытаемся такую же систему сделать как вы описали в amazon.

Ну вот я менеджер использовавший auto_ptr, скажите мне «ая-яй-яй», за что кстати?

[eastig]

:) Использование auto_ptr в ответе на тестовую задачу не проблема. Использование в продакшен коде — проблема. Вы создаете новые типы. Где гарантия, что у другого разработчика не возникнет желание воспользоваться ими. А если возникнет, то ему нужно будет знать об опасности и значит о внутренней реализации.

Ну а если вернуться к тестовому заданию, то с человеком дополнительно можно поговорить на тему почему auto_ptr опасен.

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

[anatolix]

> Вы создаете новые типы.
Где это, std::auto_ptr это очень даже стандартный тип, плюс по-моему это почти единственный способ их функции что-то вернуть по указателю а не значением, и не уточнять кто теперь главный за освобождение этого указателя.

Можно сравнить чем голый указатель опасен, или shared_ptr опасен.

Такие задачи мы тоже даем. В основном устно.

[encyclopedist]

В новом стандарте auto_ptr объявлен deprecated из-за ряда проблем. Вместо него теперь unique_ptr.

[anatolix]

Да, это в старом стандарте написано.

[eastig]

typedef struct auto_ptr<Expression> ExpressionPtr;
class Operation;
class BracketExpression;

Вот новые типы, использующие auto_ptr.

Современные компиляторы умеют делать RVO, что уменьшает накладные расходы возврата значения.

[anatolix]

И что чем это плохо? Плохо плодить сущности, в которых надо разбираться(если их бояться надо писать на plain C), в те которые устроены стандартным способом и все знаю как не вызывают проблем.

[eastig]

Если это локализовано внутри одного файла и гарантировано, что используется только внутри и не является публичным API, то проблем никаких. Иначе гарантировано найдеться умник, который отстрелит себе ногу или даже две :). Ведь люди начинают вчитываться в документацию только после того, как что-то не работает или же перестает работать.
С auto_ptr придется раскрывать детали внутренней реализации, описывать это в документации, причем очень большими буквами. А потом может получиться что поменяли внутренную реализацию, а документацию не проапдейтили.
Работа в большом проекте научила, что нужно быть крайне осторожным с тем, что делать публичным API. К сожалению в головы многих разработчиков вбито: не пиши свое, переиспользуй что есть. При этом как-то забывают заострить внимание, что нужно проверять будет ли то, что написано работать в 100% случаев твоей задачи. И в итоге получается, что время тратится не на написание кода, а на разбор багов. Причем багов нетривиальных. А переиспользованный код обрастает кучей неочевидных костылей. А потом тот кто саппортит исходный модуль очень удивляется этим костылям, в его картине мира эти случаи не возникают. Тут ему объясняют, что это костыли, чтобы поддержать корректную работу другого модуля.

[anatolix]

Как я уже писал мне кажется что неопределенность с тем кто должен освобождать то что из программы вернули сильно хуже чем неочевидность autoptr. Новым типом его не считаю то такой non-syntax sugar
Понятно что move semantics и uniqptrв cxx11 наверное более лучшее решение той же проблемы

[BelBES]

auto_ptr не рекомендуется использовать т.к. он может покрашить память где не надо. Простой пример:

std::vector<std::auto_ptr<int>> vec;
...
std::auto_ptr<int> tmp = vec[0];

Вот в этом месте среда отдает все права владения куском памяти в котором хранится vec[0] переменной tmp, при этом элемент вектора становится невалидным. А это довольно сложно отлавливаемая ошибка. В стандарте C++11 вместо него рекомендуется использовать std::unique_ptr… в мне пофиксили проблему с неявным изменением прав владения, т.к. в нем нет конструктора копирования. А для явной передачи прав владения надо использовать std::move…
Т.ч. за std::auto_ptr в продакшене надо делать ай-яй-яй)

[anatolix]

не делайте так ©

[BelBES]

вы сейчас серьезно?:)

[anatolix]

чуть-чуть серьезно. Смысле в том что в том контексте как был использован auto_ptr он использован правильно и по делу. Аргументация, что вы его можете случайно положить в vector она очень странная, сроду что вы зря взяли язык C++ на нем программа может упасть.
При этом недостатки auto_ptr-а я конечно понимаю.

[ZloyHobbit]

Я как-то писал тестовое задание на стажировку (честно признаюсь, что желания устраиваться у меня не было, область все-таки другая, да и на программиста я не учился. Но нужны были относительно простые задачки для изучения языка). Так вот там была задача пропарсить кучу исходников на предмет глобальных переменных, я тогда решил загнать их в компилятор и посмотреть вывод, однако задумка провалилась, в куче исходников использовались всякие функци вроде printf без включения библиотеки stdio, компилятор плевался. Я спросил, можно ли включить в таких файлах библиотеку, или ее выпилили специально для поиска иного решения, на что получил пространный ответ, что это задание построенно на основе проблем, с которыми часто сталкиваются программисты, и что все исходники проверялись на компиляцию. Все с тех пор хочу спросить (как не программист, конечно), чем вы там компилируете?
А еще одна задачка была на переформатирование списка файлов/директорий между разными форматами. Я ее решил, скормил вебморде автотестера, код прошел пару десятков тестов, потом сломался, причем вебморда мне сообщила, что на вход было подано больше текста, чем она может вывести, ну и на выходе соответсвенно тоже. Как дебажить — непонятно, ну и на этот вопрос сопровождающий мне так и не ответил…

[Monnoroch]

Дебажить — вдумчиво и зорко :)
Вам еще повезло, я делал эти же три задания когда-то давно, и два из них были на тестовом сервере неправильно реализованы, мне пришлось писать длинные поэмы в саппорт, какие у них баги и как их, скорее всего, можно починить.

[khim]

Все с тех пор хочу спросить (как не программист, конечно), чем вы там компилируете?

Любым нормальным компилятором C (не C++!). По стандарту функции типа printf объявлять, как ни странно, не обязательно.

Хотя это, конечно, и бардак.

[anatolix]

Без указания подробностей кто и когда выдал сложно ответить на этот вопрос точно. Как вам написали скорее всего если нет include <stdio.h> это была C программа, а не C++, там это делают сплошь и рядом.

[darkdimius]

О собеседованиях в Яндексе у меня и знакомых такой опыт:
Если собеседование на C++-позицию то впечатление о собеседовании достойное.(человек 10)
Если собеседование на Java-позицию то не очень.(человек 5).

На моей памяти только один Java-ист который нашел общий язык с Java ребятами на собеседовании в Яндексе. Но в Яндекс он так и не пошел.

Мне же было очень неприятно, когда Яндекс до последнего не озвучивал сумму предложения, и в итоге назвал сумму в 2.5 раза меньше моей текущей зарплаты.

Замечу что все Java-исты были не-Android. Все ребята из Москвы и речь о очных собеседования(5 часов вопроса + задача на месте в следующий раз)

[darkdimius]

На последней встрече с Java -командой, инициированной ими, вообще разговор не завязался. Они с трудом понимали что за задачи они хотят мне предложить, и не могли ответить на простые вопросы по постановке задачи.

Через час бессмысленного разговора прервала присутствовавшая на нем HR, и сообщила размер компенсации. Был крайне удивлен суммой в 2.5 раза меньшей чем моя зарплата на тот момент. При том что на HH была ясна указана сумма, с которой я начинаю рассматривать предложения.

[anatolix]

можешь pls мне написать подробности на anatolix@yandex[-team].ru, хочу узнать в чем прикол был.

[vitalets]

На мои вопросы о том, чем придётся заниматься, какая команда, какие условия, какая з/п, ответа не получил

Когда я устраивался — получил ответы на все эти вопросы. А команда собственно была на собеседовании.

[alexeykuzmin0]

Обычно собеседование проводит тимлид

[anatolix]

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

[elgordo]

Правильно, они оценивают ваши способности к алгоритмическому мышлению — основной навык программиста. Знание конкретной платформы или языка программирования не является ценностью — «правильный» программист, обложившись книжками и конкретными задачами, сможет освоить любую платформу/язык за пару недель.

[Suvitruf]

И они будут ждать, пока этот человек будет с 0 осваивать новую платформу/язык?

[EuroElessar]

В Яндексе, как и любой другой крупной IT компании, есть несколько уровней собеседований. На первом этапе, как правило, отсеиваются все, кто не знает алгоритмы и самого языка.

А далее, на очных, уже отсеиваются люди с недостаточными знаниями конкретных платформ и по другим более узким критериям.

[khim]

Да, будут. Специфика крупных компаний такова, что у них у всех своя платформа. Да, разумеется готовые механизмы они тоже используют, но и чисто своих велосипедов хватает.

Так как что-то придётся осваивать всё равно, так что знание вами готовых систем — всего лишь небольшой плюс, неумение достаточно быстро осваивать новое — профнепригодность.

[anatolix]

Ну в чем проблема, освойте язык и приходите, мы пару недель то уж собеседования подождем :)

p.s. Глобально вы конечно правы. Для хорошего программиста знание языка программирования ничто. Проблема в том что есть много людей которые за много лет вообще ни одного языка не освоили хорошо, и чтобы их отсечь про язык надо таки спрашивать.

[bachin]

Мое мнение (не исключаю, что оно в корне неправильное) заключается в том, что главное — это умение решить прикладную задачу, а не знание различия между static_cast и reinterpret_cast (хотя это тоже не вредно знать). В реальной жизни у нас возникают задачи с нечеткими условиями. Или даже если сегодня условие задачи звучит четко — надо понимать, что завтра мир немного изменится и задача изменится вместе с миром. Умение написать код так, что он будет работать завтра и послезавтра в изменившихся условиях (ну или хотя бы чтобы его можно было бы поправить не переписывая с нуля) важнее, imho, споров о безопасности auto_ptr.

Допустим, надо в исходную задачу добавить вычисления синуса, косинуса, логарифма и квадратного корня. Чей код (разработчика или манагера) вы возьмете а основу если вам надо решить теперь эту задачу? Или напишете свое решение?

[anatolix]

Мое мнение, что хороший программист должен уметь и то и другое, и если он не умеет это подозрительно. можно любой взять.

[Viacheslav01]

Освоить можно, а вот насколько правильно он смоет ее использовать после такого экспресс освоения?

[VlaZ]

Смутно представляю, как можно обложившись книжками за пару недель стать спецом по Java или .Net. Или начать сколько-нибудь качественно писать на C++.
Надеюсь, что ваше сообщение — это ирония над «правильными» программистами, а не искренняя убежденность в том, что исключительно алгоритмическое мышление делает человека ценным разработчиком.

[FINTER]

Ну понятно, что если человек всю жизнь на Java писал, то, например, Erlang он за пару дней не освоит. Но обычно у хорошего программиста есть хороший кругозор. Скажем тот же Java программист наверняка пробовал Python или Ruby. Скорее всего использовал JS и Bash.

Проблема в другом. Программисты нужны для чего? Чтобы создавать ПО. У ПО есть сроки и критерии качества. Если программист может создать ПО с этими критериями качества за установленное время, то не всё ли равно как он знает язык программирования?

[VlaZ]

Согласен. Но качество ПО больше зависит от знаний фреймворков, архитектуры приложений и их принципов их взаимодействия.
Математические алгоритмы нужны гораздо реже, большинство из них уже оформлены в библиотеки, и изобретение велосипеда не требуется.
В Яндексе и подобных компаниях, могут быть свои особенности, но даже у них 90% разработчиков заняты в совсем не «творческих» задачах.

[Cancel]

Кстати, Erlang как раз и освоит.

[bolk]

Разгадка в том, что в разных группах собеседование проводится по-разному, никакого общего стиля нет.

[mynameco]

Мне кажется они не разработчиков ищут а натаскивают интервьюверов. С таким колличеством желающих копаться с легасикоде крупной компании можно организовывать платные тренинги для интервьюверов.

[FINTER]

Ну это получается как в том анекдоте:
Приходит профессор домой и говорит жене: «Я сегодня лекцию прочитал так хорошо, что даже сам понял»

[sphinks]

1) К сожалению, обычная практика, кстати, хорошо хоть отписка была, многие вообще никакой обратной связи не дают.
2) В таких случаях, я думаю можно не рассматривать это собеседование, как возможность устроится на работу, жаль времени, но это не дело. Я обычно начинаю задавать вопрос по Д. Спольски и подсчитывать количество набранных баллов, в данном случае это 0 баллов.
3) Это дань уважения традициям для 80% вакансий, не более того.

[kibergus]

Disclaimer: я не знаю, в какой отдел вы собеседовались, когда и кто это делал. И я не могу ничего сказать по первым двум вопросам т.к. с этой областью не связан. Но могу предположить про «теоретико-алгоритмические вопросы» на собеседовании. Возможно в вашем случае ситуация была следующей:

Разработку мобильного приложения перевели в отдел, занимающийся разработкой серверной части того же сервиса. В итоге множество людей, обладающих должным опытом собеседования и представляющих кого им надо нанять, мало пересекается с множеством людей умеющих писать под android. Собеседующим остается спрашивать достаточно общие вопросы из теории программирования, чтобы оценить как вы мыслите и насколько владеете общими концепциями, понять сможете ли вы писать архитектурно сложные приложения. В то, что вы умеете писать под android они готовы поверить. Если не совсем умеете — то научитесь т.к. способность усваивать новый материал собеседующие тоже оценивают.

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

[Coffin]

Когда ты уверен в себе и знаешь сколько ты стоишь, то собеседование обычно начинается с того, что они могут предложить тебе. А уже потом, если тебя это устроит, то ты уже рассказываешь, что ты можешь предложить им.

Чем это хорошо? Да тем, что на первом этапе может тебя не устроит что-то, а может их и смысла узнавать о твоих знаниях уже не имеет. Ну или же услышав от тебя, что ты хочешь 100500млн денег, они уже зададут вопросы тебе на эти деньги, а не вопросы, которые стоят 100 денег :)

[VlaZ]

Полностью согласен.
Как-то странно получается — человек приходит, тратит свое время, что-то доказывает, а ему даже не готовы сообщить, для чего он нужен и на какую сумму может рассчитывать.
Пора формулировать встречные вопросы для HR:
1. Кто вам нужен?
2. Зачем?
3. Сколько вы готовы за это платить?
Имхо, после ответа на эти вопросы будет гораздо проще разобраться с требованиями к кандидату.

[anatolix]

Я не совсем HR, но попробую ответить. Проблема в том, что дать вот эти 3 конкретных ответа можно на одну конкретную вакансию, и нельзя дать про весь Яндекс, в котором сейчас вакансий наверное штук 300.

Ну т.е. если бы в Яндексе была всего одна вакансия все бы формулировалось просто, но т.к. их много то человека который для какой-то вакансии оверквалифицирован всегда можно передать куда-то в другое место, где высокая квалификация только достоинство (и это кстати некий skill собеседующего вовремя это понять и человека куда-то передать если он подходит там лучше, который не всегда срабатывает)

На практике есть некое ограничение уровня подготовки снизу без которого просто не возьмут никуда(и он как-то тот в статье раскрыт), и особо нет проблем с крутыми людьми, ну т.е. высокие пожеления к зарплате, при должном уровне квалификации и отвественности не являются проблемой, много людей в компании которые получают сильно больше рынка(правда замечу обычно не за скиллы, а за то что они для компании делают).

На самом деле не очень понятно, только, что делать с людьми которые хотят 100500, а по квалификации тянут на 100, ну да тут обычно договориться не удается.

[VlaZ]

Да, согласен. В больших компаниях, где куча открытых вакансий такая проблема есть. Ищут не на конкретное место, а просто определенных специалистов, которые могли бы пригодиться.
Я имел в виду, что если есть серьезные разногласия между ожиданиями претендента и компании, то лучше прояснить их как можно раньше, не тратя ни чьего времени.
Например, пришел человек, претендует на позицию D3, заявляет какие-то навыки в резюме. Было бы здорово, если бы ему еще до собеседования сообщили вилку зарплаты, на которую он может рассчитывать, и хотя бы примерный круг ответственности.
Дело в том, что уровень зп и обязанностей разработчиков одного грейда между разными компаниями сильно отличается.
Возможно, что у вас другой подход и разброс по зп и обязанностям в рамках грейда очень большой в самой компании. Тогда было бы очень интересно почитать, отчего так получается и какие преимущества это дает.

[anatolix]

Это кажется все лечится указанием желаемой зарплаты в резюме или на сайте типа HH, где это резюме лежит.

[Viacheslav01]

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

[mekegi]

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

[Viacheslav01]

Я и не связываюсь, но время и силы уже потрачены, а мне было куда их тратить и без них, к сожалению в последний раз когда искал работу несколько раз натыкался на такой подход.

[Hixon10]

Добрый день.
А собеседования на позицию стажёра проходят по этой же схеме?

[alexeykuzmin0]

Да, только задание не одно, а больше

[anatolix]

Скажем так, эта схема это примерно, то что мы хотим от разработчика базового уровня. Поэтому вопросы обычно все те же(но возможно сложных не спросят, задачу дадут попроще), но по ответам обычно предполагается скидка за отстутствие опыта.

[Firsto]

Поделюсь опытом — у меня было три тестовых задачи и две недели времени. Задачи вроде бы несложные на первый взгляд, но прежде чем решение пройдёт все тесты, приходится достаточно долго думать над оптимизацией.

Потом по результатам смотрят, рассматривать дальше кандидатуру или нет.

[Hixon10]

Понятно, спасибо за ответ.

[mynameco]

Очень приятно работать зная как закодить синтаксичекий парсер разгребая кучу легаси кода в авральном режиме.

[anatolix]

можете пояснить мысль, пожалуйста.

[just_prepod]

Вы не знаете, что такое Legacy-code? Устаревший код, который более не поддерживается и не обновляется, но используется (ну, либо левый код от каких-то сторонних разрабов).

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

Собственно, разрабу, который знает что такое LR-парсер, и как можно вашу задачу решить вообще без построения деревьев, очень грустно и печально интегрировать в систему код десятилетней давности, купленный у каких-то индусов. О чём и писал автор предыдущего комментария.

[anatolix]

Я знаю что такое legacy код. Я попросил автора комментария уточнить, что он имел ввиду, вдруг это как-то касается Яндекса. Код у индусов мы вроде не покупаем, весь код в рабочем состоянии.
Если вы можете написать синтаксический парсер, зачем работать над кодом который написали люди которые не могут?

[mynameco]

Во время работы над каким то большим проектом львиную долю времени отнимает рутинная работа и очень мало — написание нового кода. А уж разработка алгоритма, решающего какую-то сложную и нетривиальную задачу (проектирование) — просто как манна небесная.

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

Отдаю должное тем интервьюверам, которые на собеседовании рассказывают — чем предстоит заниматся, какие отношения между отделами, какие подходы используются при разработке. В больших фирмах это редкость (имел опыт только с мейлру, в начала коментариев есть похожий опыт с Вами).

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

[philpirj]

В условиях задачи же написано «в авральном режиме». Извините, вы не проходите.

[VlaZ]

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

[love5an]

Аплодирую стоя!

[symbix]

Мне код менеджера больше нравится. Дело не в классах, просто он понятнее :-)

[leanid]

+1, я вообще приятно удивлен кодом менеджера. А вот код разработчика мне не нравится ни разу, я бы подумал что это джуниор.

[anatolix]

Спасибо за комплимент менеджеру, код на самом деле мой :)
Я в меру условно менеджер с 10 годами бекграунда в C++ просто долго не тренировался

На самом деле с точки зрения практики код программиста мне нравится больше, в задаче парсинга классы это некий оверкилл, прочитать его все-таки не проблема, он просто такой более «конкретный» без архитектурного рассусоливания. Если посмотреть канонические примеры этих алгоритмов в wikipedia они примерно так же выглядят.

[asis]

Вы простите конечно, у вас замечательный код, но вот только «из пушки по воробьям».
Объясню почему: у вас грамматика из четырех элементов, без возвратов. Даже для людей которые на помнят таблицу конечного автомата на память для мат. операций, все равно ее записать — 10-15 минут потратить + 3 минуты в коде массив набить. Далее простая машина состояний которая переходит в нужную ячейку в зависимости от входного символа — линейно. Далее обход листьев с созданием ОПЗ — линейно. Ну а потом уже стек машина для вычисления результата — опять же зависимость только от длины цепочки.
А вы на пару с программистом чуть ли не целый парсер пишите :(

[anatolix]

> у вас грамматика из четырех элементов, без возвратов.
с возвратом конечно, там есть peek это на самом деле то же самое, что вытащить элемент и его вернуть потом.

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

Я в статье перечислил правильные способы это сделать, но сам не сделал т.к. для меня это означало бы сначала почитать теорию.

[asis]

Нет. В данной грамматике нет возвратов. При очередном входном символе у вас не может создаться ситуация, что вам нужно вернуться на N шагов назад и перестроить дерево. Парсинг входной последовательности состоящей из скобочек, бинарных операций и констант — линейно однопроходной по определению.

[anatolix]

Вообщем давайте терминологию уточним, я в русской не силен. Если под парсером с возвратом вы имеете только LL(*), т.е. парсеры с бесконечным возвратом, то вы правы, если все которые вообще иногда выполняют lookahead(он же возврат), то приведенный это LL(1) т.е. с возможностью вернуть не больше 1 токена.

[anatolix]

p.s. стандарный комментарий для всех кто написал умную вещь: приходите к нам в гости :)

[sys_int64]

лучше через абстрактное синтаксическое дерево делать, мне кажется, и код проще и быстро работает.

[zagayevskiy]

Лучше вообще без дерева, использовать алгоритм рекурсивного спуска.

[anatolix]

кажется с точки зрения реализации нет особой разницы строить дерево или считать сразу. Дерево лучше тем что если будет поддержка переменных это можно один раз разобрать а потом подставлять.

[zagayevskiy]

При спуске естественным образом строится полиз. Переменные поддерживаются на раз-два.

[anatolix]

Да так тоже можно

[sys_int64]

ну по сути с АСД так и получается, парсящие процедуры взаимно вызываются и возвращают узел дерева, но правда при генерации кода например нужно будет сделать обход этих узлов, чтобы сгенерировать код.

[BelBES]

Какие смелые у вас манагеры, через пару лет отсутствия практики использовать std::auto_ptr не боясь случайно покрашить где-нибудь память)
А к списку литературы я-бы еще посоветовал книгу Дракона прибавить — тоже стоящая вещь для алгоритмистов.

[alexeykuzmin0]

А у меня есть целая коллекция задач с собеседований в Яндекс. Ребята, вы классные!

[andymitrich]

Поделитесь же :)

[alexeykuzmin0]

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

[WraithOW]

«У меня для вас посылка, только я вам её не отдам.»

[Funcraft]

По поводу примера задания: извиняюсь за тавтологию, но лично мне, как визуалу, не хватает примера, наглядного. Надеюсь, на собеседованиях он (пример) есть, иначе визуал лишается возможности использовать одну из своих сильных сторон — визуальное восприятие.

[VlaZ]

Кстати, первое, что подумал, прочитав задачу: Взять пример, нарисовать по нему дерево на листе бумаги, а потом уже думать над алгоритмом.

[t13s]

Если Яндексу интересны самостоятельные разработчики, то, думаю, он вполне может ожидать, что кандидат сам сочинит для себя необходимое окружение.
А то кому-то картинки показать, кому-то — песенку спеть, кого-то тоннами тестовых примеров завалить…

А в статье бы, да, картинки не помешали, соглашусь.

[Funcraft]

Вы не поняли, но ладно.

[anatolix]

На самом деле визуальное изображение это некий способ решения, т.е. промежуточный этап который где-то есть а где-то нет. Если вам поможет, то «код менеджера» рисует текстовое представление синтаксического дерева, просто скомпилируйте и запустите.

[medvoodoo]

Я не очень хорошо знаю си, может проглядел это решение в коде, но не проще ли использовать алгоритм выделения отдельных действий, когда каждому действию выделяется приоритет. Мы перемещаемся по строке и отслеживаем 3 действия, идущих подряд.
В случае, если у второго действия приоритет больше или равен третьему и первому- заменяем эту пару на число.
Так преобразуем строку пока не получится конечное число.
Со скобками решается тем, что первая скобка и закрывающая(если стоит третьей) имеют нулевой приоритет, закрывающая с действием(когда стоит в середине) -тоже нулевой
И когда в скобках остается конечное число -они убираются.

[alexeykuzmin0]

Скорее всего, то, что Вы предлагаете, будет работать за квадратичную сложность

[anatolix]

Да так и будет.

[alexfetisov]

По-моему, смотря как написать. Если добавить просчет парных скобок (обычный стек) и неявно писать ответ на внутрискобочном выражении в левой скобке (то есть не сжимать ничего явно), то будет линия. С другой стороны, это намного сложнее сделать, чем обратно польскую нотацию (если я правильно понял задачу, то это вроде бы классика решения).

[anatolix]

Не понял если честно, проще напишите по коду или вы поймете что где-то квадрат или я что так можно.

[alexfetisov]

Странно, что сложность проще оценивать по коду…
Давайте я попробую объяснить еще раз.
1) У нас есть выражения. Для простоты пока есть только +, -, *, / и (). Допустим, что скобок нет. Тогда понятно как за 2 прохода вычислить результат? На всякий случай, поясню. Сперва за линию считаем все * и / (проще идти с конца и кидать все в левую переменную. После этого останутся равноранговые операции + и -. Это тоже линейно считается. Кстати я не посмотрел, но вы заставляете кандидатов думать о переполнении? Пара операций умножений может быстро усложнить жизнь.
То есть мы умеем линейно решать выражения вида А, где А = (А) | B, где B — выражение без скобок.
2) Теперь добавим скобки. Сперва сделаем линейный прекальк — для каждой скобки определим парную. Это делается с помощью стека. (Надеюсь пояснять не нужно как).

Теперь имея все это делаем так: сканируем рекурсивно слева. Видим скобку — идем вглубь (имеется в виду начинаем независимо сканировать выражение внитри скобок. Допустим, мы пришли к тому, что скобок нет. Тогда за линию считаем ответ. Кладем его «на левую скобку» и возвращаемся из рекурсии. Легко видеть что каждое подскобочное будет просканированно линейно и независимо. Это линия в сумме.

[seegester]

Угу. Моё «решение программиста» примерно так и устроено. Только операции вычисляются сразу по мере считывания очередного токена до тех пор, пока это возможно. Суммарно должно получиться О(N), насколько я понимаю.
На самом деле там даже стек для поиска парных скобок не очень нужен.

[alexfetisov]

Точно, не нужно. Я просто привык эти данные сразу принимать как имеющиеся, когда думаю о решении. Задача и правда неплохая на собеседование! Особенно в формате, в котором вы просите — то есть оставить кандидата — пусть пишет.

[anatolix]

Да я понял. Неплохое решение, оно не за один проход, но линейное. Наверное действительно проще в реализации. Принимается.

[alexfetisov]

Ну количество проходов ни о чем не говорит :)
Вообще, это решение по-моему в разы сложнее, чем обратно польская нотация, которая как раз за один проход :)

[anatolix]

Ну в теории, на практике количество проходов может например удвоить железо в кластере, и стоить 100M$

Да, но обратная польская это то что за 2 часа уже не изобретешь.

[alexfetisov]

Не говорит в плане понятия сложности. Все таки обычно решения кандидатов на такие задачи не мерят размером константы. По крайней мере я так не делаю, если у вас так, тогда извините :)

Не изобретешь, да. Лучше знать :)

[anatolix]

Да не для тестового задания очень даже ок.

[alexfetisov]

То есть вы хотите сказать, что если кандидат напишет вам верное решение за 3 прохода, то вы его не возьмете, из-за гипотетической формулы длиной километр, чтобы почувствовать разницу в производительности?

Мне просто интересно еще, где в реальности вы найдете такие данные, на которых константа 3 стоит 100М$ (для конкретной задачи про формулу, конечно, ведь мы ее спрашиваем), если мы уж пытаемся привести жизненный подход?

[anatolix]

Можно спросить как вы из моего ответа сделали подобный вывод, помоему написано ровно наоборот.

В нашей реальности у нас много где такие данные :)
про формулу конечно нет, мы в реальности вообще формул кодом на C++ не парсим.

[alexfetisov]

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

Ну да, поэтому и подчеркнул, что говорю о формуле :) В общем стоящая задача на собеседование. Спасибо за статью, интересная!

[alexhemp]

Вообще это задания на уровне второго курса, кажется дисциплина называлась «Теория алгоритмов».
Примером к разделу формальных грамматик является как раз грамматика разбора арифмитических выражений.
Архиваторы писали там-же на втором курсе, семестром позже — причем сразу и арифметическое кодирование и хаффмена и LZ.
RLE-архиватор девочки на лабах даже писали, сам видел :-)

Но за час в рабочий день — это да, как-то странно.

[anatolix]

Ну да, вообще в идеальном мире любой человек получивший обучение по специальности Computer Science умеет программировать, в том числе и простые алгоритмы. Наша вселенная к сожалению не идеална, поэтому приходится проверять, а не просто в диплом смотреть.

[anatolix]

Дается ноут, на котором есть все разумные среды разработки. На бумажке это надо застрелиться чтобы написать.

[SkorKNURE]

На онсайт-собеседованиях в Гугл весь код пишется маркером на доске. А бедный интервьювер его следом переписывает как раз на бумажку — для отчетности :-)

[khim]

У вас устаревшие сведения! Сейчас код пишется… на Chromebook'е в Google Docs. Что помогает интервьюверу, но вряд ли — собеседуемому.

[SkorKNURE]

Если они и устаревшие — то не более, чем на 5 недель. Справедливо, как минимум, для офиса в Цюрихе — лично проверял :) Может не везде ввели еще новую практику. Но не согласен с вами — печатать код в редакторе, по сравнению с писанием на доске — большой шаг вперед. Пару программ занимали целую доску, и все они были в стиле данного топика.

[geka]

код разработчика неверно работает на тестах типа: «1-2+3», выдает -4 :(

[anatolix]

facepalm. Подтверждаем, поправили.

[aavezel]

вербуйте geka в тестеры яндекс.диска :)

[anatolix]

geka, пришлите пожалуйста резюме на anatolix@yandex[-team].ru

[SVolkov]

Ну и как это помогает написать деинсталятор…

[aml]

Вот например так: habrahabr.ru/post/206338/

[mejedi]

Если вы знаете о существовании каких-нибудь классических алгоритмов в этой области, то задача становится проще… Также помимо Recursive descent parser популярными является LR-парсер.

LR парсер управляется таблицами (фактически это машина состояний с возможностью поместить текущее состояние в стек и извлечь состояние со стека). Способность посчитать таблицы для LR -парсера вручную требует выдающегося уровня задротства.

[anatolix]

Тут на самом деле та же машина на функциях, чтобы 4-5 состояний определить кажется не нужно особого задротства

[mejedi]

В принципе да, но! Класс грамматик LR(k) эквивалентен LL(k). Если мы реализуем LR парсер на рекурсивных функциях, это также будет реализация эквивалентной LL(1) грамматики рекурсивным спуском (формально это можно показать так: для каждого состояния создаем свой нетерминал, для каждого перехода S₁→^cS₂ добавляем продукцию S₁:cS₂).

Код будет дословно такой же, как если бы мы привели грамматику к пригодному для LL анализа виду и реализовали рекурсивный спуск.

Резюме: LR грамматику проще составить чем LL, но без генератора парсеров реализацию создать сложно. Можно побыть самому в роли генератора, и исполнить соответствующий алгоритм при помощи ручки и бумажки (keyword: задротство). Либо можно интуитивно составить код так, чтобы реализовать LR процесс. Для этого нам понадобиться привести грамматику к LL виду (явно или не явно). И парсер будет LL.

[ZyXI]

По условию задачи у вас есть формула с цифрами, операциями +-*/ и скобками. Нужно написать программу, которая ее вычисляет. Формула может быть большой. Хочется, чтобы программу можно было легко дорабатывать, вводя функции, параметры и т.д.

Я как‐то писал такое на фортране. Без рекурсии, без деревьев, без сложных структур данных вообще. Способ простой

1. Преобразуем выражение в обратную польскую нотацию. Просто переносим операции, начиная с наименее приоритетных и расположенных правее всего, через их правый операнд. Операции для переноса выбираются справа налево (по позиции), снизу вверх (по уровням); сначала проходятся позиции, потом уровни. Последним шагом удаляются все скобки.
2. Результат выполняется в простейшей стёковой виртуальной машине, состоящей на 90% из копипасты.
3. Вершина стёка возвращается как результат.

O(N) по памяти (на хранение формулы. Вы так же не можете получить стёк больше, чем имеется в формуле токенов, т.к. есть только токены‐значения (+1 значение в стёке) и токены‐функции/операторы (+1−(арность) значение в стёке: т.е. +0 в худшем случае)). Если я не ошибаюсь, то O(N²) по времени (перенос операций проходит формулу два раза: в обратном (для нахождения операций) и прямом (для переноса через операнды) порядках; число уровней — константа; исполнение на стёковой виртуальной машине — O(N)). (N — длина формулы.)

Число выделений памяти минимально: если вы знаете длину формулы можно обойтись одним (в моей программе их 0, но длина формулы жёстко ограничена на этапе компиляции).

При записи всего этого на более удобном языке, чем fortran, добавить пользовательские функции и функции с переменным числом аргументов (лучше (легче) в стиле Haskell f (a) (b)) довольно легко (переменные у меня уже есть). Хотя до того, как я поставил себе задачу написать такой «калькулятор» именно на фортран, я бы тоже делал синтаксический парсер. Сейчас бы использовал имеющееся в голове решение.

Интересно, это считалось бы допустимым ответом?

[anatolix]

Да считалось бы. Более того это помоему каноническое решение и самое быстрое.
Собственно выше про него было написано: en.wikipedia.org/wiki/Shunting-yard_algorithm
Его ограничение то, что нужно знать про обратную польскую нотацию, соответственно оно не обладает свойством что его может написать любой кто умеет программировать. Но как я говорил, если знаешь теорию то становится проще.

[ZyXI]

Нет, это не моё решение. У меня выражение в инфиксной записи проходит через {число уровней приоритета} преобразований, в промежутках выдавая выражение в частичной обратной польской нотации, а здесь однопроходной парсер. У меня асимптоматика по времени хуже, по памяти так же (честно говоря, мне сложно написать такой калькулятор с более чем O(N) по памяти).

[Quilin]

На самом деле, такую же задачку давали на первом коллоквиуме по программированию на мехмате в МГУ, у тов. Борисова. Только разве что (с учетом мощности местных компьютеров), были какие-то очень добрые ограничения на ввод. Но это же рандом, нет? Или для выпускников мехмата у вас другие задачки?)

[anatolix]

Нет зачем, какая разница почему человек умеет программировать, потому что в ВУЗ-е научили(как кстати и должны были) или потому что сам научился.

[relgames]

Увидел код ваших решений и поразился — неужели все настолько плохо в Си?
В Java, например, есть ANTLR (да и для C он тоже есть). А вот ваша задача на Scala
Или совсем просто stackoverflow.com/questions/3422673/evaluating-a-math-expression-given-in-string-form

[tangro]

Не волнуйтесь, всё настолько плохо только на собеседованиях. Для всего есть библиотеки (хотя и не входящие в стандартную библиотеку языка). Никто в реальном коде не будет писать своих лексических и синтаксических парсеров. Ну разве кроме разработчиков компиляторов других языков или чего похожего.

[relgames]

Ну вот и я удивился — зачем спрашивать то, что в реальной жизни не используется.

[anatolix]

На самом деле все люди которые учатся в университете, делают задания на coursera.org пишут много вещей которые в реальной жизни не используются. Притом иногда несколько лет подряд. Кажется в том, чтобы поделать это еще пару часов нет ничего страшного.

Нам хочется увидеть что человек умеет писать код, это можно попросить сделать написав маленький кусочек кода. Найти что-то что при этом можно куда-о применить на практике достаточно сложно, плюс еще применить на практике это все равно нельзя если только с кандидатом не подписывать контракт о правах на код.

Но вообще если вам задача конструктивно не нравится, т.е. вы готовы предложить что-то еще, что интересней написать — с удовольствием послушаем — мы открыты к предложениям.

[relgames]

Ну мне не нравится тем, что я в университетах не обучался :) Если я почитаю вики и потрачу 4 часа, я этот алгоритм напишу, конечно. И в будущем буду его писать уже за час.

Мне кажется что умение написать алгоритм — это только один из критериев. Понятно, это зависит от компании. Например, мы просим написать задачу, которая в принципе похожа на то, что мы делаем. При этом мы смотрим на тесты, на использование стандартных библиотек, на простоту кода, на документацию. Это же не ACM, тут люди будут потом разгребать твой код.

По поводу задачи, наше задание я не могу привести по понятным причинам. Ну вот примерный аналог: разработать веб-сервис, который позволяет узнать курсы валют на определенную дату, плюс нужно сделать простой сервис статистики — сколько раз веб-сервис использовали, какую валюту запрашивают чаще всего. Даны файлы данных в каком-либо формате, ну и в принципе все. Дальше уже кандидат решает, как лучше это сделать. Очень хорошо видно, кто как привык писать. Кто-то начинает мастерить мега-фреймворк, кто-то пишет на чистой Java. Кто-то тупо кидает исключение, кто-то обрабатывает ошибки. У кого-то нет документации вообще, кто-то документирует каждую строку. Ну и так далее.

Еще мы задание даем домой и не ограничиваем явно время, чтобы убрать стресс. Опять же, это специфика нашей области — лучше медленно, но хороший понятный код с документацией и обработкой ошибок, чем быстро, но как тут уже писали, ваше решение работает неверно.

[anatolix]

Ну просто «разработать веб-сервис, который позволяет узнать курсы валют» это тоже не практическая задача, в смысле вы ее так же викинете, если вам только не нужно 50 разных сервисов которые отдают курсы валют.

Что касается нас, то у нас специфика в том, что мы хоть и интернет компания, у нас почти нет web разработчиков в нормльном понимании. Т.е. человек будет решать практические проблем уже в некоем стандартном окружении и поднимать web сервис самому ему наврядли пригодится. А вот уметь разбираться в алгоритмах средней сложности — вполне.

[relgames]

Ага, понятно. Просто у нас критерии немного другие. В вашем решении нет ни тестов, ни документации, ни единого коммента :) Не описано, каким образом вы туда добавите функции — а это ведь часть задания, расширяемость.

[anatolix]

если что то в моем решении как раз тест с длиннющей генеренной формулой вместо ввода данных, и комментарии(но комментарии я скорее для хабра написал, если бы сам делал задание не стал бы)

[relgames]

Да, я видел :) Я о втором решении. В общем, придираюсь я. Уже понятно, что у вас критерии другие немного, чем в проклятом энтерпрайзе :)

[relgames]

«У вас» — я тут имею ввиду компанию.

[just_prepod]

Нам хочется увидеть что человек умеет писать код, это можно попросить сделать написав маленький кусочек кода.

Вот это-то и раздражало всегда на собеседованиях. Для теста дают интересную задачу, ты её решаешь, а потом на работе говорят «ну, вот тебе база данных, нужно из неё данные вытащить и на сайте(форме) показать. Это и будет твоей работой. Зато у нас соцпакет и бесплатные печеньки».

Ребята, какого рожна вы даёте писать на собеседованиях парсеры, если вы не занимаетесь разработкой компиляторов? Зачем просите показать скилы во внешних сортировках, если потом всё равно нужно будет использовать фунцию GetExtraLargeChunkFromFile, которая уже есть в вашем фрейворке лет пять?

Разрабов это и раздражает в HR. Хотя теперь, кажется, вы объяснили почему HR так поступают. Из-за этих самых идиотских многоступенчатых собеседований, когда HR даже не знает, что за человек нужен в команде.

Вместо того, чтобы искать сотрудника на конкретную должность «нужен кодер на дохрена денег, умеющий вытаскивать JSON и отображать на странице», вы собеседуете разраба, который в универе пять лет читал книгу дракона и «алгоритмы» Сейджвика.

Это примерно как «нам нужен опытный водитель-механик, способных водить фуры в сложных метеоусловиях, желателен опыт участия в Париж-Дакар. Зачем? А сельский автобус между колхозами гонять». ИЧСХ, вы, похоже, не понимаете, что дело тут даже не в деньгах…

[anatolix]

Это на самом деле правильный филосовский вопрос.

Тезисы ответа на него такие:
1) Мы технологическая компания. (Под этим имеется ввиду, что вот макдональдс не технологическая компания, может у них есть программисты которые занимаются внутренними системами, но на бизнес компании они не влияют. У нас если программист сделал алгоритм ранжирования лучше чем у гугла или ускорил программу работающую на 20000 серверах на 10% это на бизнесе уже очень конкретно отражается)
2) К сожалению все простые способы технологически повлиять на бизнес компании уже сделаны, остались сложные. Для их реализации нужны очень умные люди. Да этих людей нужно не много, но сейчас их у всех компаний сильно меньше, чем надо.
3) Нанять этих людей почти нельзя, но их можно вырастить, люди которые сейчас руководят разработкой ранжирования пришли 8-10 лет назад студентами, и наверное в своей карьере писали json-о подобное что-то.
4) Так вот, чтобы у тебя через 5-10 лет были люди которые двигают бизнес компании вперед надо прямо сейчас нанимать людей у которых их потолок сильно выше написания json файлов. Даже если сейчас нужно в том числе и json делать.
5) Да часть из этих людей свой потолок не реализуют, по разным причинам(в сильной мере от них зависящих) и останутся недовольны, зато другая часть будет делать реально клевые штуки.
6) Если же нанять людей которые ничего кроме генерации json-а делать не смогут, то тягаться с ребятами типа Гугла будет достаточно грустно.

Я ответил на ваш вопрос?

[olegdunkan]

Те задачи о которых вы говорите, они скорее всего в плоскости разработки очень специализированных алгоритмов над гибридными структурами данных, более того эти структуры данных далеко не те, которые на устах здесь у программистов. В моем понимании если вы хотите конкурировать с google, то вам нужно в том числе искать математиков, и людей занимающихся исследовательскими задачами, алгоритм Укконена например, не возникает в процессе решения программистких задач, он возникает и исследовательских задач, программисты в большей массе это люди умеющие понимать и использовать уже имеющиеся алгоритмы и технологии, в вашем случае мне кажется необходимо вообще иметь исследовательский отдел с людьми, имеющими глубокое математическое абстрактное мышление, только такие люди могут составлять конкуренцию мировым гигантам.

[anatolix]

Практика(и наша и гугла) показала, что математики, которые не могут написать код чтобы проиллюстрировать свою идею почти совсем бесполезны(production код они могут не писать, но прототипы обязаны). Двигают прогресс все-таки программисты-математики.

Ну вот у меня есть мнение что через 5 лет исследовательскими задачами будут заниматься люди которые сейчас только, что закончили вуз и возможно пишут генераторы json-а и задачки по machine learning на coursera.org

[olegdunkan]

Я бы написал, математики-программисты.
Очень забавно слышать, что математики не могут свои мысли изложить в алгоритмическом ключе, но вам виднее. Думаю все современные выпускники математических институтов должны иметь прекрасное представление о языках программирования и проблемы здесь не будет. Но я все же хотел акцентировать внимание на исследовательских задачах, решение которых не должно быть непосредственно связано с реализацией ее на том или ином языке с использованием тех или иных архитектур вычислений и технологий. На выходе этого отдела будет математическая модель, которую потом можно реализовать с использованием тех или иных способов, но уже непосредственно связанных с тем, чем занимаются программисты. Грубо говоря я не считаю, что исследователи должны заниматься вопросами реализации, они создают модель, а программисты ее реализуют, вот такое четкое разделение должно быть у гигантов, у них должны быть на это средства, понимание и самое главное доверие. И последнее, у математиков в моем понимании, должен быть инструмент программирование, для решения исследовательских задач, на выходе которых будут новые модели и алгоритмы (инструмент для программистов), поэтому я пишу математики-программисты, а не на программисты-математики — вот это как раз те, которые используют математику как инструмент. Хотя конечно и те и те могут быть в одном лице, но это уже вопросы организации труда и экономики.

[khim]

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

И откуда же, чёрт побери, возьмутся такие задачи?

На выходе этого отдела будет математическая модель, которую потом можно реализовать с использованием тех или иных способов, но уже непосредственно связанных с тем, чем занимаются программисты.

Я вам умный вещь скажу, только ты не обижайся: моделей можно нагенерить за один день 100500 штук. Вопрос в применимости модели к реальному миру. И как ваш отдел будет оценивать применимость модели, если он неспособен прогнать через неё реальные данные?

Да, прототип может быть написан не на C++, а, скажем, на Java (или вообще на Python'е), он может работать в 100 медленнее, чем нужно, но он должен работать с реальными данными и выдавать реальные результаты.

Вы, конечно, правы: для гениального математика с сотней опубликовынных статей и, скорее всего, профессорским званием могут и сделать исключение и нанять его, несмотря на то, что он не умеет программировать, но сколько таких нужно на фирму? Один человек на тысячу? Или на две тысячи? Ну где-то примерно в этой районе.

[olegdunkan]

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

[anatolix]

На самом деле если бы эратосфен не придумал бы свое решето, его бы придумал сейчас какой-нибудь школьник из 9 класса, алгоритм то очень простой.

Сейчас в софтверных гигантах нет институтов, но например в области задач machine learning они сильно впереди всяких институтов типа standford-а, просто потому как у них больше данных и больше вычислительной мощности, и больше мотивации заниматься этой частью науки. У них просто сильно меньше мотивации в научной среде что-то публиковать.

[anatolix]

> они создают модель, а программисты ее реализуют
это работает в системе разработки waterfall, когда заранее можно сказать что надо реализовать и осталось только это сделать. Когда это никто раньше не делал, R&D это плод скорее проб и ошибок, и человек который сам может попробовать становится сильно более эффективен.

из примеров задач: если можете сформулировать как сделать ранжирование в турции лучше чем у гугла, при количестве данных в 30 раз меньше чем у гугла, можете сформулировать, и мы закодируем :)

[bachin]

> из примеров задач: если можете сформулировать как сделать ранжирование в турции

Я не знаю что такое ранжирование и почему у Я оно в 30 раз меньше, чем у Г, поэтому эту задачу не решу. Могу лишь предложить свой подход к подобным проблемам — сначала убрать из условия задачи Турцию. Взять любой другой регион, где данных можно достать больше чем есть у Г. Добиться приемлемого результата. А потом уже постепенно экстраполировать на Турцию и другие «сложые регионы» :)

[anatolix]

Пользователи кликают на результаты поиска и этим дают сигнал, у нас в турции 3% рынка, у гугля остальное — сигнала сильно меньше чем в россии, или там украине.

В других регионах типа России у нас и так уже ранжирование лучше, проблема в том что просто экстраполировать на турцию по причине отсутствия пользовательских данных не получится.

> поэтому эту задачу не решу
вот поэтому математики и не помогают, т.к. тут 15% математики, 35% разработки и 50% понимания предметной области.

[tavel]

… как сделать ранжирование в турции лучше чем у гугла, при количестве данных в 30 раз меньше чем у гугла

При исходных данных — никак. Даже если весь гугл заставить решать эту проблему — ничего не получится. Потому что задача стоит совсем другая: как собрать данных столько же, сколько у гугла.

[anatolix]

Ну вот, а люди делают. И вообщем-то уже почти сделали. Данные тоже конечно собираем, но столько все равно не собрать.

[relgames]

Да пожалуйста stackoverflow.com/questions/304268/getting-a-files-md5-checksum-in-java
Или даже вот www.golubev.com/hashgpu.htm + www.jocl.org/

А вы, как я погляжу, сторонник старого мифа что «Java медленно работает».

[elgordo]

Так радостно читать все эти вещи, когда работаешь сам на себя. :-D

Собеседования — это как тесты на IQ. Нужно не просто найти правильные ответы на вопросы, а угадать ход мыслей в голове того, кто их придумывал.

[tangro]

По поводу последней задачи — единственный фактически возможный вариант, который может быть реализован в продакшене, это «грамматика + (lex&yacc || boost.spirit || аналог)». Именно так должен будет поступить нормальный программист в серьёзном продукте. А человека, ответившего это, я так понял, Яндекс пошлёт нафиг?

Каким образом написание глупого и ненужного кода показывает подготовку к решению практических задач?

[anatolix]

Не пошлет, попросит все же написать самому.
А что вы предлагаете написать, чтобы показать способность решать практические задачи?

[tangro]

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

Если человек хоть раз писал парсер на чём-то из вышеуказанного — вполне реальная задача на 2-4 часа работы. При этом получится на порядок более надёжный код.

[pyatigil]

Цель же не в том, чтобы проверить умеет ли человек использовать конкретные инструменты, а в том, чтобы проверить помнит ли он как пишут код.

Хотя, надо признать, в конкретном случае с lex/yacc скорее всего умеет

[tangro]

А мне вот чего-то всегда казалось, что работа программиста — создавать работающий продукт, а не уметь набивать километры букв.

Если я решу задачу в 50 строк, прицепив к продукту нужные библиотеки, а кто-то напишет 1000 строк кода лексического и синтаксического анализаторов, потратив на них в 3 раза больше время и оставив в коде пяток ошибок (а на 1000 строк их точно не меньше будет после первого захода) — то кто же более ценен для компании?

На счёт «конкретный инструменты vs писать код» — суть в том, что о конкретных инструментах может знать только человек с опытом. Я бы составлял задачи так, чтобы у человека была возможность продемонстрировать знание всего: алгоритмов, парсеров, параллельного\асинхронного кода, сети, паттернов.

Вот вам навскидку такое задание: веб-сервер на С++, способный решить предыдущую задачу — получить по HTTP через POST формулу и вернуть её результат в теле ответа. Вот тут можно разгуляться! Что человек выберет для сети? Сокеты? boost.asio? Poco? Касабланку? Чем будет парсить POST? Напишет ли хоть простенькую фильтрацию «левых» данных? Как сделает обслуживание нескольких клиентов — в разных потоках или в одном, синхронно или асинхронно? Чем разберёт формулу? Вынесет ли грамматику в отдельный файл? Сделает ли генерацию парсеров частью билда или сгенерит один раз и включит в код? Напишет ли хоть пару тестов?

Реальная задача — реальные инструменты — реальный результат. Вот это всё скажет о разработчике многое. А то, умеет ли он скобочки выкусывать из входящей строки, да дерево строить — ну, фигня какая-то.

[anatolix]

> Если я решу задачу в 50 строк, прицепив к продукту нужные библиотеки
На само деле в больших проектах прицепление библиотек — по талонам. В смысле большая часть таго что вроде как есть работающее на самом деле на наших данных ломается, есть некоторое количество проверенных.

> веб-сервер на С++, способный решить предыдущую задачу
а чем не подойдет консольную программу в init.d вписать добавив заголовок? web сервер на C++ чтобы написать это более менее объемное решение, в простом варианте сравнимое с самой задачей. Т.е. можно но это эффективно увелдичение времени на разработку в 2 раза.

[khim]

По моему вы тупо спорите мимо друг друга.

Давайте я попробую вас помирить, а?

Вот тут можно разгуляться! Что человек выберет для сети? Сокеты? boost.asio? Poco? Касабланку?

Первое — недоступно в production'е, второе — запрещено style guide'ом, третье — вылетает по той же причине, что и вариант номер 1.

Чем будет парсить POST?

Чем бы он там его не парсил у себя дома у Yandex'а (как и у Google, кстати), есть свой корпоративный стандарт, и ничего другого вам использовать не дадут.

Напишет ли хоть простенькую фильтрацию «левых» данных?

См. выше.

Как сделает обслуживание нескольких клиентов — в разных потоках или в одном, синхронно или асинхронно?

Опять-таки есть готовые framework'и, являющиеся «корпоративным стандартом», выход за которые, мягко говоря, не приветствуется.

Чем разберёт формулу?

Опять-таки: какая, нафиг, разница, если в работе у него выбора не будет? Будет несколько готовых инструментов, которые security team допускает — или писать руками.

Вынесет ли грамматику в отдельный файл?

Ну здесь хоть сколько-нибудь осмысленный вопрос. Но, опять-таки, какая разница, если он не знает даже возможных вариантов ответа на этот вопрос? У нас, скажем, есть штук 10 мест куда можно, в принципе, засунут эту конфигурацию (и не всегда «оставить в коде» будет самым плохим вариантом), но ни про одну из этих технологий «снаружи» ничего не известно. Что дальше?

Сделает ли генерацию парсеров частью билда или сгенерит один раз и включит в код?

И сможет ли он это проделать с той билд-системой, которую использует Яндекс.

Напишет ли хоть пару тестов?

А здесь, опять-таки, копроративные политики рулят.

Реальная задача

Ну… почти.

Реальные инструменты

Которые при этом интервьюеру придётся специально изучать и про которые всё равно придётся забыть сразу после приёма на работу.

Реальный результат

Который столь же похож на то, с чем придётся делать, как и исходная задача. Только на 90% состоящий из демонстрации знаний, которые уж точно никому не понадобятся в дальнейшем.

Дальше что?

Вот это всё скажет о разработчике многое.

Угу. Станет ясно: можно его брать в стартап из 3 человек или нет. Но тут вроде речь идёт о собеседовании на работу в Яндекс?

А то, умеет ли он скобочки выкусывать из входящей строки, да дерево строить — ну, фигня какая-то.

И тем не менее только работа, подобная этой «фигне» может встретится в его дальнейшей работе.

Остальное же… остальное тоже будет делаться. Теми инструментами, которые принято использовать для этого в Яндексе, Facebook'е или Google.

Вы всё ещё не можете понять чем большая компания отличается от маленького стартапа. А она отличается. И очень сильно. Тем, что у неё много (действительно много) своих инструментов.

Грубо говоря вы предлагаете при приёме на работу плотника дать ему возможность сделать целый дом. И посмотреть на то, как он может решать много интересных задач: как он сделает окна, двери, вытяжную трубу для печи. Но при этом его берут в домостроительный комбинат, где уже есть есть чёткие правила, описывающие какие окна, двери и трубы допустимы, какие — рекомендуются, а какие — «только в крайнем случае».

[tangro]

Ага, а ещё тут где-то недавно пробегала статья о том, что из Гугла разработчики уходят не из-за маленькой зарплаты или плохого соцпакета (там это всё ок), а потому что Гугл не ленится нанимать к себе лучшие умы текущего поколения и… садит их на вторую линию техподдержки, или на тестирование, или на багфиксинг легаси, или на конвеерное ревью.

Так и Вы — вместо попытки распознать опытного и квалифицированного в решении практических задач разработчика предлагаете выбирать тех, кто способен «стоять у конвеера», тестируя максимум тот факт, что ему роста и длины рук хватит, чтобы за этим конвеером стоять.

[anatolix]

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

[just_prepod]

Ух. Сколько лет мне потребовалось, чтобы это понять.

Поправочка: уметь выкусывать скобочки из входящей строки очень нужно тем, кто пишет asio и poco — чем лучше умеют выкусывать, тем они круче. Просто это разные уровни стека технологий.

Собственно, в ветке выше я и пытался объяснить эффективному менеджеру, что для каждого уровня стека технологий нужны свои компетенции, и тому, кто будет юзать готовые либы нет смысла давать тесты на алгоритмы сортировок. И наоборот — тому самому «математику-программисту» ни о каких бустах знать по-крупному счёту и не нужно.

[anatolix]

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

[anatolix]

Возможно вы правы, если задачку как-то модифицировать, чтобы в ней нужно было что-то и руками написать то это наверное вполне решение.

[relgames]

Как вариант — генерить тестовые данные для этой задачи :) Т.е. дается парсер, который умеет решать, надо написать генератор по заданным параметрам (количество скобок, количество операций умножения, сложения и т.д.) :)

Не знаю, есть ли стандартное решение, но идея такова, что надо дать что-то на «придумать самому», а не «вспомнить алгоритм».

[humbug]

Не пошлет, попросит все же написать самому.

facepalm.jpg

[tym32167]

Если честно, мне бы в голову не пришло юзать грамматики, так как на память написать LL парсер лично для меня неподъемная задача. Я бы попробовал, к примеру, двухстековый алгоритм Дейкстры. Хотя у меня когда то была похожая задача (с доп условиями), но я её решил чисто в лоб :)

[tangro]

(del)

[chuprakov]

Всегда был против синтетических тестов. Мне, как тимлиду, важнее было то, насколько человек обучаем и адекватен. Не во всех случаях, но очень часто для этого достаточно часовой беседы в спокойной обстановке без мозголомающих абстрактных задач.
Многие кандидаты часто слишком нервничают, чтобы сосредоточится и написать код (программисты, как правило, интроверты разной степени замкнутости). Если нужно проверить на знание конкретных умений/языка, гораздо правильнее будет дать серию заданий «на дом», а потом их обсудить лично с кандидатом. Если задания делал не он — это выявляется сразу. Стиль и уровень программирования кандидата, а также уровень его алгоритмического мышления тоже будет понятен после выполнения заданий.
Кстати, есть вполне опытные разработчики, которые могут при этом путаться в синтаксисе. Просто они слишком привыкли к IDE и наличию хелпа, чтобы помнить всё до мелочей. Я, конечно, исключаю клинические случаи, когда человек не знает, что строка в С++ заканчивается точкой с запятой. Но если эйчар такого захантил — это скорее проблема эйчара и в самом эйчаре.
В общем, программистов все же нужно оценивать по их программам прежде всего. И еще по адекватности поведения, если это получится оценить конечно. А абстрактные тесты, решения которых находятся минутным загугливанием, могли бы иметь смысл только при отсутствии у человечества Интернета как такового. В этом случае они хотя бы демонстрировали общий уровень эрудиции.

[Tutufa]

а как у вас проходит собеседование на исследователя по анализу данных?

[Stas911]

Думаю, банально просят показать профиль на Kaggle ;)

[alpust]

Это ж задача калькулятора, собрать Польскую нотацию, решают студенты на 3-ьем курсе.

[anatolix]

именно. просто почему-то это 90% людей решить не могут.

[funca]

Код HRa

#include <string>
#include <cstdlib>

int main ()
{
  // I do not hope that the empoyee will write a LL-parser. But we still have a vacancy web developer.
  std::string const formula = "1 + 2 * (3 + 4)";
  std::string const cmd = std::string("php -r 'echo ") + formula + ";'";
  std::system (cmd.c_str());
  return 0;
}

[anatolix]

код hr-а это sms/jabber: ", можешь мне прислать, пожалуйста код калькулятора на C++"

[phoenix367]

Наверное немножко не в тему комментарий. Не очень давно ваш HR присылал вакансию что-то типа разработчика в области компьютерного зрения. Чтобы добраться до собственно собеседования предлагалось заполнить анкету с вопросами из которых собственно к компьютерному зрению относился только один — назовите три последние статьи по компьютерному зрению, которые вы прочитали или что-то в этом духе. Т.е. вопрос ни о чем. Почесал я репу и понял, что Яндекс — это не та компания, где я хотел бы работать :)

[tvv]

Посмотрел код разработчика, всегда интересно смотреть, как пишут специалисты крупнейших компаний… Правильно ли я понял, что у вас допускается и считается нормальным, когда конструкции типа str.end() многократно вызываются в циклах, включая вложенные циклы?

for (std::string::const_iterator cit = str.begin(); cit != str.end(); ++cit) {
    ...
    int curnum = 0;
    while (cit != str.end()) {
        curnum = 10*curnum + (*cit - '0');
        if ((cit + 1) == str.end() || !isdigit(*(cit+1))) {
            break;
        }
        ++cit;
    }
    ...
}

P.S. То, что я написал выше, это не в упрек программисту. Сам я, с нуля, прямо на собеседовании, такую задачу за два часа скорее всего не решу на C++ (по крайней мере без ошибок и ляпов, и чтобы мне было не стыдно такой код показывать). Попросил бы часа четыре, но при этом написал бы множество юнит-тестов, и доку под доксиген. Хотя тогда проводящие собеседование скорее всего меня назвали бы медленным программистом, и не взяли бы. Жаль.

[tvv]

Думаю, то, что получится, очень сильно зависит от выбранного компилятора, а также реализации std::string. Прошу прощения, какой компилятор Вы имеете в виду, и с какими опциями компиляции? Хотелось бы посмотреть, какой генерируется код (на ASM).

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

Eсли посмотреть имплементацию basic_string.h, то, в зависимости от реализации, будет что-то типа:

iterator end() {
    return iterator(_M_data() + this->size());
}

По крайней мере описание именно такое:

The past-the-end character is a theoretical character that would follow the last character in the string. It shall not be dereferenced.

Because the ranges used by functions of the standard library do not include the element pointed by their closing iterator, this function is often used in combination with string::begin to specify a range including all the characters in the string.

[anatolix]

Ну и будет инлайн, плюс вынесение вычисления неизменяемых в цикле переменных за пределы цикла, 2 самые простые оптимизации которые компиляторы годах в 90 еще делали.

Отвечая на оригинальный вопрос:
1) Да считается нормальным.
2) Если это случится в проходе по кишкам поиска(самая дорогая операция) и компилятор ошибется то найдут профайлером и поправят. там как бы и cache miss-ы ищут профайлером.

[tvv]

Ясно, спасибо за ответ, принимается. Хотя я бы не доверял во всех случаях компилятору (включая данный случай), так как реальные результаты часто отличаются от того, что ожидается по теории, но я понимаю, что, возможно, это лишь моя личная программерская паранойя. Кстати, если не секрет, какой компилятор Вы в данном случае использовали, и с какими ключами компилировали этот код? Было бы интересно проверить.

[seegester]

Привет!
Я — автор «кода разработчика». Попробую прокомментировать свой вариант, вернее то, как и почему я его писал.

Disclaimer 0: я на самом деле тоже уже не совсем разработчик, скорее, какая-то странная смесь из маленького начальника/менеджера/админа/тестировщика/ну и разработчика, да. Но код пишу по большим праздникам, и уже начал немного отвыкать.

Вообще, как тут где-то отвечал anatolix, основная цель заключалась в проверке, может ли обычный программист «с улицы» написать такое задание за приемлимое время, — чтобы на нас не посыпалась волна упрёков, что задания слишком сложные. Вот я и попробовал — в первую очередь для себя — воспроизвести условия, как они бывают на собеседованиях. В основном это касалось временных рамок и ограничений по использованию справочных ресурсов. Если поискать, то легко можно найти и алгоритмы и даже готовые программы, но так не интересно. Теорию последний раз вспоминал лет 10 назад, тогда же и читал Dragon book.

Но полностью воспроизвести условия не получилось — в первую очередь временные: конец года, как всегда некоторая запарка + личная жизнь. семья и всё такое. В результате пришлось разбить всё на два куска — 40 минут и 1:10 где-то — в нерабочее время, разумеется.

Тем не менее это во многом оказалось полезным в контексте данной статьи, и вот почему. Понимая, что я очень ограничен по времени, я старался сделать минимально простое решение задачи. Чем меньше кода, тем проще его и писать и отлаживать. И вроде как это получилось.

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

В общем, повторюсь, я старался сделать всё как можно проще. Зачем? А затем, что

Disclaime 1: моё мнение может не совпадать с мнением других коллег, проводящих собеседования в Яндексе, и даже с автором этой статьи.

… затем что, в действительности практически всегда интервьюер в конце такого собеседования хочет увидеть работающую программу, а не красивый «канонический», но не работающий код. Для «канонического» кода эта задача или слишком маленькая или, наоборот, слишком большая, если делать всё совсем-совсем правильно. И да, для неё есть уже много готовых инструментов. Если бы можно было или воспользоваться, ими надо было обязательно пользоваться. Это же относится и к другим задачам, которые предлагаются на собеседованиях.

Соответственно, давая кандидату написать на собеседовании код, хочется увидеть не только то, насколько кандидат знает те или иные особенности языка/компилятора/whatever, а может ли он решить заданную ему задачу. Некрасивое работающее решение лучше красивого неработающего. Как тут уже писали, в реальной работе есть множество ограничений: и на используемые библиотеки и style guide, да и сами задачи не все и не всегда носят характер rocket science. Я бы даже сказал, что настоящий rocket science — это объединение сотен и тысяч таких маленьких кусочков, написанных десятками, а то и сотнями людей. Этот процесс может длиться не один год — и как-то странно пытаться интерполировать маленькую тестову/ задачу до такого уровня.

Disclaimer 2: да, бывают люди, способные в одиночку сделать что-то охрененно крутое. Но таких единицы на миллион, и уж по ним обычно и так всё понятно.

Вернусь к исходному вопросу о допустимости того или иного говнокода сомнительного кода в «крупнейших компаниях». Конечно, в идеале надо было бы всё причесать, написать тесты, прогнать через профайлер. И так обычно и делается — в крупных командах даже есть специальные позиции для этого. И у нас (я говорю про поисковый отдел Яндекса) тоже. Но весь код действительно большого проекта не может быть идеальным — это экономически не выгодно.

Единственное, не стоит судить по моему наколеночному решению о том, что происходит внутри нашего репозитория. А что там в действительности творится — подражая anatolix'у, скажу: есть простой способ это узнать.

ЗЫ. Прошу прощения за простыню текста. Я отвечал не только на коментарий выше, а скорее по совокупности всему этому треду.

[tvv]

Спасибо за развернутый ответ, позиция понятна, принимается. Повторюсь, написать такое за два часа, с нуля, без интернета, это уже отличный уровень. Но в любом случае, не мне судить. Меня просто некоторые детали реализации зантрересовали, у вас они, как оказалось, позволительны, а в некоторых других компаниях строго запрещены. Но это мелочи, в принципе.

[tvv]

#0. Код программиста, приведенный на данный момент в статье, не обрабатывает унарный оператор перед скобками. То есть на выражение -(1+1) будет выдана ошибка, хотя это вполне допустимое выражение с точки зрения математики.

#1. Код программиста на выражение -1*0 выдаст -0. Вряд ли это хорошо. Или это так было задумано?

[anatolix]

особо не считаю нужным придираться к тестовому заданию.

[tvv]

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

[anatolix]

В задании не оговаривались унарные минусы, и проверять я бы их не стал. Можно было оговорить и проверить.

[Dremkin]

Был раз на собеседовании в Яндексе. Самым важным вопросом, который мне задали был про названия кабинетов/переговорок. Мое предложение нумеровать их в виде простых натуральных и всем понятных чисел, типа 1,2,3,4 и тд., было воспринято как очень недостойное предложение, унижающее креативный потенциал всей компании в целом :)

[Mrrl]

в виде простых натуральных и всем понятных чисел, типа 1,2,3,4

Наверное, после слов «простых натуральных...» ожидали услышать 2,3,5,7… А 4 — какое же оно простое?

[AraneusAdoro]

Да с нуля надо было нумеровать просто :)

[bachin]

— Как вас зовут?
— Василий.
— Дети есть?
— Да, сын Василий и дочь Василиса!
— А животные дома есть?
— Кот Васька!
— К сожалению, мы не можем вас принять на должность креативного менеджера…

[anatolix]

У переговорок есть нумерация помимо с названием, нумерация выглядит как 5-1, т.е. 5 этаж первая переговорка, номера переговорок на этаже зависят от географии, это чтобы не думать куда вообще идти в переговорку 26.
Тем не менее названия всем нравятся больше.

[jcmvbkbc]

Ожидал, что код разработчика будет хотя бы на флексо-бизоне, разочарован.

%option noyywrap

Whitespace [ \t\v\n]
Op [-+*/()]
Number [0-9]+

%%
{Whitespace}
{Op}            { return *yytext; }
{Number}        { return 'd'; }

%%

%{
#include <stdio.h>
int yylex (void);
int yyerror(const char*);
extern char *yytext;
%}

%error-verbose

%%
Input: /**/
    | Expression { printf("%d\n", $1); }
    ;

Expression: Sum
    ;

Sum: Sum '+' Product { $$ = $1 + $3; }
    | Sum '-' Product { $$ = $1 - $3; }
    | Product
    ;

Product: Product '*' Unary { $$ = $1 * $3; }
    | Product '/' Unary { $$ = $1 / $3; }
    | Unary
    ;

Unary: '+' Trivial { $$ = $2; }
    | '-' Trivial { $$ = -$2; }
    | Trivial
    ;

Trivial: 'd' { $$ = atoi(yytext); }
    | '(' Expression ')' { $$ = $2; }
    ;

%%

int yyerror (char const *s)
{
        return 0;
}

int main()
{
        yyparse();
}

[funca]

<занудамод> это код сишного разработчика. у флексо-бизона есть морда ведь и для с++ </занудамод>

[jcmvbkbc]

Хм. А с таким make-файлом что вы скажете?

calc: calc.lpp calc.ypp
        flex calc.lpp 
        bison calc.ypp 
        g++ calc.tab.cpp lex.yy.c -o calc

[anatolix]

Естественно весь код в production на bison, тут хотелось посмотреть как человек пишет на C++

[mejedi]

Я бы сделал проще, неоднозначности разруливаются приоритетами / ассоциативностью.

Expr: 
    NUMBER | 
    '(' Expr ')' | 
    '-' Expr |
    Expr '+' Expr |
    Expr '-' Expr |
    Expr '*' Expr |
    Expr '/' Expr |
    Expr EXPONENTIATION Expr;

[jcmvbkbc]

Мне кажется, приоритеты и ассоциативность — это какой-то ненужный костыль в бизоне, превращающий грамматику в непойми что.

[mejedi]

ИМХО костыль этот здорово упрощает грамматику, хотя это дело вкуса. Костыль всего-лишь позволяет разрешить shift-reduce конфликты.

[Mrrl]

Я бы написал так

enum{
      ERR_NO_RPAR=1,
      ERR_INVALID_UNARY=2,
      ERR_INVALID_BINARY=3,
      ERR_EXTRA_RPAR=4,
      ERR_ZERO_DIVIDE=5
};


double ReadDouble(char *&s){
    double val=0;
    for(;*s>='0' && *s<='9';s++) val=val*10+(*s-'0');
    return val;
}

int lpri(char c,int &err){
	switch(c){
	    case '+':
	    case '-': return 2;
	    case '*':
	    case '/': return 4;
 	    case 0:
            case ')': return -1;
	}
	if(err==0) err=ERR_INVALID_BINARY;
	return -1;
}

double ReadExpr(char *&s,int pri,int &err){
    double val=0,val1;    
    char c=*s;
    if(c>='0' && c<='9'){
        val=ReadDouble(s);
    }else{
	s++;
        if(c=='('){
	    val=ReadExpr(s,0,err);
            if(*s++!=')' && err!=0) err=ERR_NO_RPAR;
        }else if(c=='+'){
            val=ReadExpr(s,3,err);
        }else if(c=='-'){
            val=-ReadExpr(s,3,err);
        }else{
            err=ERR_INVALID_UNARY;
            s--;
        }
    }
    while(!err){
        char c=*s;
	if(c<=' '){ s++; continue; }
	if(lpri(c,err)<pri) return val;
	s++;
        switch(c){
            case '+': 
		val+=ReadExpr(s,3,err);
                continue;
            case '-':
		val-=ReadExpr(s,3,err);
                continue;
            case '*':
		val*=ReadExpr(s,3,err);
                continue;
            case '/':
                val1=ReadExpr(s,5,err);
                if(val1==0 && err==0) err=ERR_ZERO_DIVIDE;
                else val/=val1;
                continue;
        }
    }
    return val;
}

double CalcExpr(char *s,int &err){
    err=0;
    double res=ReadExpr(s,0,err);
	if(*s!=0 && err==0) err=ERR_EXTRA_RPAR;
	return res;
}

И завалился бы на примере с 10^8 скобок — не хватило бы глубины стека вызовов.
Зато никакого синтаксического разбора, хоть сейчас переписывай на ассемблер.

[Joshua]

Компилятора под рукой нет, но не нравится строчка if(c<=' '){ s++; continue; }
Не свалится ли на выход за границы массива например, на таком примере: "(3+1"

[Mrrl]

Свалится, конечно. В следующем варианте я уже написал c>0 && c<=' ', но исправлять этот было поздно.

[lesha_firs]

Если мне дали отказ по собеседованию на вакансию python, когда я могу попробовать еще раз пройти собеседование, если важно для ответа в моем городе нету филиала Яндекс. и на что следует сделать упор? может что-то особенное спрашивают по старому собеседованию?

Что посоветуете прочитать для python?

[andymitrich]

Смотря на какую позицию вы собеседовались :) Насколько я знаю, там несколько вакансий для Python.

[lesha_firs]

При собеседование мне сказали что на все подходящие вакансии связанные с Python!
Это было полгода назад, может больше, их тогда было меньше :)

Да и знаний у меня было меньше!

[TimeCoder]

Проходил в Яндексе собеседование на С++-разработчика, было интересно проверить себя. Не прошел, попросил дать обратную связь, и мне скинули примерный список вопросов, где я плавал. Это очень и очень специфичные вещи, типа алгоритма удаления в красно-черном дереве, на каких процессорах встречается big-endian, как внутри устроен boost'овый smart_ptr и пр.

Помнить как можно больше алгоритмов сортировок, помнить тонкости деревьев — может либо вчерашний студент, либо человек, кто с этим постоянно работает (но таких единицы). Вот и получается парадокс: у вчерашнего студента шанс ответить правильно выше, чем у меня, разработчика с 10-летним стажем, за который мне ни разу не пригодились эти специфичные вещи. Даже если бы понадобились: подобные моменты легко гуглятся, являясь по сути справочными данными.

По поводу того, что нагуглить невозможно, не было задано ни одного вопроса, я о реальном опыте разработки. Как строится архитектура высоконагруженных Enterprise-систем, как организуется корпоративная шина данных, отказоустойчивая синхронизация данных от множества систем и многое другое. Нужны годы реальной коммерческой разработки чтобы все это узнать, но Яндексу важнее знания специфических технических деталей, чем опыт разработки. Не осуждаю конечно, это право компании, решать, по какому критерию вести найм, просто был искренне удивлен таким подходом.

[Monnoroch]

Возможно, вы просто не дошли до момента, когда переходят к вопросам про построение архитектуры сложных систем. Интервьюер совершенно закономерно подумал, что если вы не знаете базовых вещей, то спрашивать о сложных не имеет смысла, ведь если вы даже ответите верно, то, скорее всего, вы просто умеете (выучили наизусть, или «со словарем»), а не разбираетесь, как устроено внутри.

[TimeCoder]

Помнить алгоритм удаления в красно-черном дереве — вы считаете это базовым?

Поясните пожалуйста, каким образом это так, если это изучают на СДиА (на 3-м курсе ВУЗа), и потом за много лет разработки подавляющему числу программистов ни разу не приходится реализовывать красно-черное дерево, покуда быстрее и правильнее (особенно в бизнес-разработке) использовать готовые решения (STL в C++, generics в C#).
Чтобы правильно выбрать контейнер мне не нужно дотошно знать все его алгоритмы реализации, достаточно знать сложность всех его операций (выраженную в О-нотации).

[Monnoroch]

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

[TimeCoder]

Сложно сказать, какую степень подробности они от меня ждали, поскольку вопрос исчерпал себя почти сразу: я просто не помню шаги этого алгоритма. У нас с вами разное видение того, что считать базовыми знаниями, и я не претендую на то, чтобы как-то вас переубеждать. Просто поясню, по какому критерию я определяю что базовое знание, а что нет.
Если разработчик много лет успешно решает задачи в рамках тех проектов, над которыми работает его компания, к качеству его кода, архитектуре выбранных решений, и производительности в готовом продукте нет претензий у его коллег и тимлида — он обладает базовыми знаниями.
Для тех задач, которые мне приходилось решать в своей жизни (например, это проекты в сфере разработки 3D игр с искусственным интеллектом, Enterprise-системы для обработки геоданных) — мне ни разу не пригодилось знание алгоритмов работы красно-черного дерева.

[Monnoroch]

Да, только вы приходите в Яндекс и внезапно оказывается, что вам надо обрабатывать петабайты данных, и, если ваш код работает на одной сущности на 1ms дольше, потому, что вы не самым оптимальным образом выбрали дерево, не зная его внутреннего устройства, то это примерно 3 лишних часа работы свободного кластера, а на нем ведь еще 400 таких человек, как вы, работает, и у каждого по дофига задач считается, что даст гораздо больше времени, ушедшего в никуда из за вашей оплошности — и это на каждый вычислительный таск.

[TimeCoder]

Я и не спорю, что для специфических задач такое знание нужно, мы говорили о другом: что базовое, а что нет. Это не базовое) В том проекте, куда я собеседовался, нет кластерных вычислений, но видимо в Яндексе общие для всех проектов требования.

[Monnoroch]

Тут где-то уже писали, что сначала собеседуют «в общем», это да, это политика компании, не мне ее обьяснять, так что аргументов нет больше :)

[Monnoroch]

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

[TimeCoder]

Понимаете в чем дело, есть большие сомнения, кто такие эти суперспецы. Поясню.

С ходу помню как минимум два случая, в разных компаниях, когда человек был очень грамотен, но не умел самого главного — работать. Эти люди делали крутейшие технические презентации своих идей, заваливали названиями ультрасовременных технологий, и я уверен, что на все вопросы Яндекса про деревья и пр. ответили бы без запинки. Проходило время, а прогресса по задачи нет. В итоге в обоих случаях эти суперспецы, знающие всё, так и не доделали свои задачи, запутавшись в сложности своих реализаций, пытаясь решить задачу такими крутыми решениями и алгоритмами, что в итоге это все просто не заработало. Это чуть не завалило весь проект, и мне приходилось выкашивать их код и с нуля делать рабочее решение.

[TimeCoder]

Дополнение к комменту выше:

а чтобы отличить спецов-теоретиков от реальных спецов, нужно не просто спрашивать теорию, а смотреть на опыт. И давать тестовые задачки. Спрашивать академическую теорию имеет смысл для junior-вакансий, когда есть знания, нет опыта. После нескольких лет работы все, что не используется на практике — выветривается напрочь… Зато появляется опыт.

[Monnoroch]

Я имел ввиду спецов в CS. Теоретик спокойно научится прогать, обратное — неверно, по моему опыту. Гугл вон, вообще высшее образование требует, слава богу, Яндекс такой фигней не страдает, лишь бы знания были соответствующие оному образованию.

[khim]

После нескольких лет работы все, что не используется на практике — выветривается напрочь…

С чего вдруг? Да, те знания, которые у вас висят «с краю» карты могу и выветрится, но такие базовые вещи, как RB-деревья или AVL-деревья у вас в мозгах должны быть на кучу других вещей завязаны, как они могут «выветриться»? Я понимаю как Фибоначчевы кучи могут выветрится или даже ассимптотики работы хеш-мапа (сам hash-map участвует в куче проектов, но когда он начинает ухожить от O(1) обычно это означает что пора что-то рефакторить), но RB-деревья???

Зато появляется опыт.

После чего в «нормальных» компаниях человек переходит в менеджеры и гордится тем, что код он больше писать не может. Ни в Яндексе, ни в Google таких орлов не берут ибо там новый проект какой-нибудь Staff Software Engineer зачастую начинает один, без всяких подчинённых. После того, как есть прототип, да, команда расширяется, но это уже потом. А на первых порах — нужны люди и со знанием и с опытом, а не или-или.

[Monnoroch]

Немного подробнее: вам совершенно не нужно уметь реализовывать красно-черное дерево (хотя это будет плюсом), но что это такое знать важно.
А что это такое? Самобалансирующееся дерево поиска. Что значит самобалансирующееся? У которого высота не превышает какой-то оценки (log(N)). Но постойте, таких много деревьев, чем отлично красно-черное? Определенным способом самобалансировки. Вот этот способ и хотел выведать интервьюер: вводится аттрибут цвета (для доказательства оценки), а дальше при добавлении и удалении делают повороты, которые сохраняют оценку высоты. Что за повороты? Тут на бумажке проще нарисовать кусок дерева и как поддеревья передвигаются. Там их два всего: короткий и длинный, плюс симметрия. Минимум такое описание должен уметь дать каждый, кто претендует на какой-то программистский умственный труд.

[TimeCoder]

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

Наша беседа ушла из конструктивного русла. Я описал критерий, по которому определяю, какие знания для программиста считать базовыми. Вы пишите

Минимум такое описание должен уметь дать каждый, кто претендует на какой-то программистский умственный труд.

-никак это не обосновывая. Почему это должен знать каждый программист? А кто-то скажет, что каждый программист должен знать алгоритм .........(вставить нужное)...., лишь описание которого занимает пол книги. А кто-то скажет «достаточно знать что такое int». Если нет критерия, все очень субъективно, все эти «должен-не должен».

[Monnoroch]

Прошу прощения, я чуть выше обосновал.

[khim]

Вам кажется это очевидным, просто потому что вы уже знаете этот алгоритм — смогли бы додуматься до него самостоятельно?

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

Примерно следующая цепочка:
С одной стороны у нас есть двоичное дерево поиска, но в нём есть беда: оно может стать «рыхлым», потому что в нём будет много вершин только с одним потомком.
С другой стороны у нас есть дерево, которое по какой-то причине называют красно-чёрным. С чего вдруг?
Ну, наверное, в нём помечены вершины.
Зачем они помечены?
Чтобы «хорошие» вершины или рёбра отличать от «плохих».
Ok, пусть будут рёбра. И пусть хорошие… ну пусть «красные»… рёбра организуют «костяк» дерева… а тогда «чёрные» будут их разбавлять.
Ну и, наверное, стоит сделать так, чтобы воды уж очень много не было, то есть чёрные рёбра не шли подряд.
А поскольку у нас «плохих» («красных») рёбер мало, то вот на них мы и наложим ограничения: пусть они всегда ведут в два «хороших» («чёрных») ребра.

Всё — мы восстановили структуру красно-чёрных деревьев. Только вместо чёрных вершин у нас красные рёбра, ну и фиг с ним, какая, нафиг, разница? Этого уже вполне достаточно для того, чтобы писать процедуру удаления и доказывать свойства нашего дерева (высота не более 2 * log₂N, etc).

Почему это должен знать каждый программист?

А как он без этих знаний сможет работать? Запомнит назубок, что AVL-деревья медленно добавляют, а RB-деревья медленно ищут? Ну так эти знания у него рано или поздно из головы выветрятся, если он паковщик всё равно, а если он картостроитель, то он и другую информацию у себя из головы вытащить сможет.

[just_prepod]

Меня порой поражает как люди считают вещи базовыми, на том основании, что их изучают на первом курсе института (или в школе). Вот вы грамотно пишете. А вы сейчас, не заглядывая в словарь, скажете определение термина «склонение», сколько склонений в русском языке, и к какому склонению относятся слова «ель», «дуб», «берёза»? Из моего опыта на такие вопросы могут ответить один из десяти (профессиональных лингвистов я из выборки исключу). А ведь между тем эти вещи изучались в шестом классе!

Я сам, например, помню, что склонения три, и там как-то можно по окончанию определить, к какому склонению относится слово. Типа, «ель» это женский род с нулевым окончанием, значит, 3е склонение. В то же время я хоть убей не вспомню какие из окончаний "-ать", "-ить", "-еть" относятся к какому спряжению. Но -ВНЕЗАПНО! — я знаю что это вообще такое — склонения и спряжения, и знаю где найти подробности.

Так вот с этими вашими графами и деревьями то же самое. Делал лабы в универе (сам делал, не из книжки перепечатывал), но вот щас не вспомню чем алгоритм Крускала отличается от алгоритма Прима.

Поэтому все эти «базовые вещи» существуют только в головах девочек-HR, которые открывают книжку по программированию за второй курс, и считают темы из оглавления теми «базовыми вещами», которые прямо-таки невозможно забыть.

[TimeCoder]

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

[TimeCoder]

Ну на самом деле, если бы я прошел собеседования, у меня был бы повод задуматься, не факт, что я бы отказался. Просто не было прям сильного рвения (и возможности, если честно) потратить значительное время на подготовку. Почитал Рихтера, GoF и Скиену 4 вечера, освежил в памяти, что-то новое открыл для себя, и пошел.

Как мы уже выше в обсуждениях выяснили, тут срабатывает единый подход к собеседованиям в Яндексе, т.е. спрашивают про хитрые тонкости даже на те вакансии, где это особо не нужно. Если бы я шел на проект поиска или Крипты — безусловно, там без мощных знаний математики и СДиА даже делать нечего. Но для разработки desktop-приложений, плагинов к браузеру — вряд ли нужно обладать таким же багажом.

[khim]

Но для разработки desktop-приложений, плагинов к браузеру — вряд ли нужно обладать таким же багажом.

А если вдруг проект свернут — куда вас потом девать? Один мой знакомый, когда-то занимавшийся Google Toolbar под Firefox сейчас вполне себе в отделе, занимающемся оптимизацией поиска работает. В Яндексе, насколько я знаю, примерно та же картина.

[TimeCoder]

Тоже верно. С другой стороны, вы же понимаете: человек не может знать все одинаково хорошо. Как ни крути, computer science — слишком широкая область, и у каждого разработчика есть та или иная специализация. Смена профиля по необходимости, или по желанию — штука полезная. Другое дело, кому это сделать проще, какой бэкграунд этому способствует — но тут мы рискуем начать холивар «насколько программисту нужно знать математику».

[anatolix]

Не могу ответить за ваше собеседование без подробностей, но вообще говоря эти вопросы предполагают что кандидат вообще знает, что бывают big endian и little endian архитектуры, и что тут есть грабли. И что человек знает что такое balanced search tree(у него 2 свойства) как его балансировать обычно не спрашивают.

Если про существование ни того ни другого вообще не знать, то да до архитектуры собеседование не дойдет.

[OlolondiyOloloev]

Если Яндексу нужны математики-программисты, а не программисты, то у меня возникает ряд встречных вопросов HR:

1. Насколько вы готовы поделиться бизнесом с человеком, который должен двигать бизнес вперёд?
2. Какое отношение к математикам-программистам имеют выпускники ВУЗов, если серьёзный математик это как правило магистр или профессор того же математического ВУЗа?
3. Где гарантия, что специалист, которого вы так долго будете «выращивать», не сбежит в Гугл спустя 5 лет работы?

Просто у меня сложилось впечатление, будто на самом деле вакансия (с вышеприведёнными заданиями, которые в реальности уже никто давно не решает), существует не для выполнения конкретной работы, а для поиска математически-одарённых студентов. Которые по собственной наивности и желанию себя зарекомендовать будут «за зарплату» разрабатывать инновационные проекты. И пока они не сообразили, что свой талант можно продать в Гугл за перспективу мигрировать, с них можно вытянуть интересные идеи.

Абстрактное «нам надо увидеть, как человек умеет писать алгоритмы», не более чем попытка защитить свою компанию от индусского кода, чем поиск математически одарённых кандидатов.

Либо HR менеджер попросту выгораживает своё тёплое место, изображая «бурную деятельность».

[anatolix]

А что заминусовали то — хороший вопрос:
1) Готовы, делимся. У 25% топовых разработчиков акции компании. У совсем топовых совсем много.
2) Магистр=выпускник. У нас есть и выпускники, и кандидаты и доктора наук. От выпускников больше пользы сейчас, из них много кто становится кандидатом работая в Яндексе.
3) Это же наша проблема, в сумме получается, в конкретных случаях иногда нет.

> чем поиск математически одарённых кандидатов.
поиск математически одаренных кандидатов кстати нельзя сделать через собеседования и резюме. Яндекс наверное больше всех в россии вкладывается в академические программы.

[OlolondiyOloloev]

> От выпускников больше пользы сейчас, из них много кто становится кандидатом работая в Яндексе.

Согласен. Молодые люди, едва вышедшие с порога ВУЗа, обладают некоторым скиллом переработки. У них пока ещё не появилась семья с малыми детьми, нет ипотечной кабалы. Не испытывая серьёзных стрессов, они готовы усердно работать над поставленной задачей, а вопрос денег их особо не напрягает, им нужен опыт.

Да и это во всём мире так. Более старшее поколение, за 30 лет, скажем так, более инертно.

У меня тогда такой вопрос: каковы шансы у потенциального сотрудника, если он старше тимлида? Просто я сам сталкивался с такой особенностью. «Молодая бурно развивающаяся компания» получила ряд интересных встречных вопросов, и после этого интервьювер потерял свой запал задора и весёлости. В компании Яндекс в заданной команде разработчиков, ведётся ли подбор специалистов одной возрастной планки?

[anatolix]

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

Про деньги это как раз не вопрос, есть мнение что компании экономят деньги, это в массовом масштабе конечно так, но вообще для начальника деньги это самый простой способ мотивации, надо просто чтобы было за что их дать.

На самом деле в совершенно научной математике есть некая тенденция, что много открытий математики совершали будучи молодыми, все-таки мозг видимо стареет. Со старостью приходит опыт но в инновационной сфере возможно он не так важен.

[Monnoroch]

Интересно, что, судя по комментариям, недовольны те, кто не прошел, а со стороны прошедших недовольства не видно, никто не жалуется, мол, я прошел, но интервью мне не понравилось.
По-моему, довольно показательно.
Может, я пропустил подобные комментарии, конечно, так что извиняйте, если что, вполне мог.

[TimeCoder]

Так устроена человеческая психика, что поделать. То, что вызвало недовольство, стимулирует к поиску недостатков. Но это не означает само по себе, что недостатков нет, тут уже нужно конкретно рассматривать.

[Monnoroch]

Ну да, в себе-то недостатки ох как тяжело искать, в интервьюере гораздо проще.

[TimeCoder]

Не буду минусовать ваш комментарий, просто отмечу: я ни слова не сказал о недостатках интервьюера, речь шла о подходе к собеседованию в целом. Мне было по чему судить, т.к. я прошел 4 этапа собеседования, все с разными интервьюерами. И еще раз скажу: я не зол на Яндекс, не призываю их сменить подход к найму. У них это работает, результат налицо — это главное. Просто мне непонятно как, вот и все:)

[Suvitruf]

Хотелось бы увидеть тех, кто прошёл собеседование. Вернее, совпало ли всё с их ожиданиями.

Лично я не жалею, что не прошёл. Скорее даже рад, ибо нашёл куда лучшее место работы с хорошими условиями и хорошей командой)

p.s. мой комментарий сверху был вызван не недовольством, а банальным непониманием подобной методики проведения собеседований

[RainM]

Собеседование абсолютно не понравилось.
P.S. Собеседование прошел. Но в итоге отказался.

[kashey]

Я такую задачу в институте на олимпиаде решал. B-tree и все такое. Не больше 300 строк кода. Заняло минут 20.
Лет через 5 на работе понадобилось — делал неделю, и еще месяц баги находил.
И по коду почему-то получилось очень очень сильно больше, ну почти как в варианте менеджера.

[IrixV]

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

Кстати, когда специалист был действительно нужен и интересен, несколько уровней собеседований легко объединялись в один. Совершенно несложно 3-м специалистам из соседних кабинетов придти в одно место и провести общее собеседование (если им это нужно). Более того, соискатели, которые просят объединить собеседования вызывают больший интерес.

Про уловки с тестами… Допустим вы подходите и нужны компании, но заявленая зп более высокая, чем компания хотела бы вам платить. Тут на помощь компании приходит ваш тест. Наверняка, многие вещи там буду сделаны не оптимально, либо будут неправильные ответы на какие-то специфичные вещи. Вы услышите что-то вроде: «Тест ваш так-себе, мы бы могли вас взять… но не на ту зарплату».

[anatolix]

угу, большие компании все имитируют, и поиск сотрудников, и разработку, и рост выручки, на самом деле никто ничего не делает, а все пишут 3 инопланетянина в подвале.

Самая страшная тайна Яндекса, что его создают не тысячи его номинальных сотрудников, а трое инопланетян, спасенных когда-то Воложем от смерти в казахских степях, в теперь хранящиеся в охраняемой бронированной барокамере на его даче. К инопланетянам припаяны кнопочки: «еще сервис», «еще дизайна», «еще релевантности». Все остальные тысячи сотрудников — лишь ширма. Они лишь бессмысленно слоняются по бескрайним просторам очередного бизнес-центра. Конечно, посвященным топам не так уж просто удается поддерживать видимость деятельности — но и платят за этот адский труд им не мало. Новые сотрудники охреневают от того, что они ничего не делают, а все происходит «само», но через полгода перестают замечать и втягиваются. Отсюда столь разнообразная активность «сотрудников» Яндекса на всех фронтах — конференции, блоги, roem. Код пишут трое в шкафу, а остальные — лишь Санта-Барбара с приходами-уходами, отношениями, игрою в эффективность, слияниями, поглощениями, открытиями-закрытиями офисов.

roem.ru/2010/02/05/addednews13544/index.php/firrma.ru/data/insides/779/?c#com58268

[KvanTTT]

Интересная точка зрения, которая никогда не приходила мне в голову (к Яндексу никаких претензий, я в общем).

[anatolix]

Мы вот тут с seegester сидим в курилке, и рядом с нами человек на спор решил написать это за полчаса, то что мы писали 2 и 4. Написал за 14 минут квадратичную версию и в сумме за 29 не квадратичную. Сейчас запостит код.

[ProgrammerAlias]

#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <ctime>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <math.h>
#include <queue>
#include <memory.h>
#include <iostream>
#include <fstream>
#include <stack>
#include <complex>
#include <list>

using namespace std;

void ASS(bool bb)
{
    if (!bb)
    {
        ++*(int*)0;
    }
}

#define FOR(i, x) for (int i = 0; i < (int)(x); ++i)
#define CL(x) memset(x, 0, sizeof(x))
#define CLX(x, y) memset(x, y, sizeof(x))

#pragma comment(linker, "/STACK:106777216") 

typedef vector<int> vi;

typedef long long LL;

string s;
vi next;

int op[256];

int Parse(int L, int R) {
    int c = 0;
    int pos = 0;
    int pr = -1;
    for (int i = L; i < R; ++i) {
        if (s[i] == '(') {
            i = next[i];
            continue;
        }
        if (s[i] == ')')
            ASS(0);

        if (c == 0 && i > L && pr <= op[s[i]]) {
            pr = op[s[i]];
            pos = i;
        }
    }
    if (pr > 0) {
        switch (s[pos]) {
            case '+': return Parse(L, pos) + Parse(pos + 1, R);
            case '-': return Parse(L, pos) - Parse(pos + 1, R);
            case '*': return Parse(L, pos) * Parse(pos + 1, R);
            case '/': return Parse(L, pos) / Parse(pos + 1, R);
        }
    }
    if (s[L] == '(')
        return Parse(L + 1, R - 1);
    if (s[L] == '-')
        return -Parse(L + 1, R);
    int x = 0;
    ASS(s[L] >= '0' && s[L] <= '9');
    while (s[L] >= '0' && s[L] <= '9') {
        x = x * 10 + s[L] - '0';
        ++L;
    }
    return x;
}

int main() {
    op['+'] = 2;
    op['-'] = 2;
    op['*'] = 1;
    op['/'] = 1;
    string t;
    while (cin >> t)
        s += t;

    int last = (int)s.size();
    next.resize(s.size(), 0);

    vi v;
    for (int i = last - 1; i >= 0; --i) {
        if (s[i] == ')')
            v.push_back(i);
        if (s[i] == '(') {
            ASS(v.size() > 0);
            next[i] = v.back();
            v.pop_back();
        }
    }
    cout << Parse(0, s.size());

    return 0;
}

[jcmvbkbc]

$ echo '1 - -2' | ./test
1
$ echo '--1' | ./test
0

… и где здесь с++?

[Monnoroch]

Нет же унарных операторов!

[jcmvbkbc]

Привет, а это что?:

    if (s[L] == '-')
        return -Parse(L + 1, R);

[Monnoroch]

В постановке изначальной не было :)

[jcmvbkbc]

Разработчик встроил неправильно работающую недокументированную возможность в тестовое задание. Хорошее начало. Думаю его возьмут.

[jcmvbkbc]

А ещё отличное обращение мимо массива вот в этом фрагменте:

        if (c == 0 && i > L && pr <= op[s[i]]) {
            pr = op[s[i]];

s[i] — это же char. Когда char знаковый символы из верхней половины таблицы ascii имеют отрицательный код. Результаты забавные:

$ echo '5 А 1' | ./test
5

[encyclopedist]

И переменная с нигде не изменяется, и её можно выкинуть. Автор торопился же.

[ProgrammerAlias]

Допустимые символы имеют неотрицательные коды, никаких обращений мимо. Писалось в курилке просто чтобы показать что это возможно написать быстро. Унарный минус небыло цели обрабатывать.

[jcmvbkbc]

Конечно всё так. Но цель же была на С++ посмотреть, а С++-то тут г.

[ProgrammerAlias]

Цель была показать, что это можно быстро написать. Речь о разговоре в курилке.

[jcmvbkbc]

Как будто возможность написать что угодно быстро и некачественно не вызывает сомнений?

[seegester]

Вообще говоря, вызывает.

Понятно, что некорректно сравнивать условия на собеседовании (явный стресс) и трёп в курилке, где все свои, и фейл ни к чему нехорошему не приведёт, но тем не менее.

Имея рабочую программу, привести её к красивому виду довольно легко. Написать простые тесты, «причесать» код и т.д. — допустим, на это уйдёт ещё полчаса. Неплохой результат в любом случае. Тут с самого начала речь шла о скорости, а не о том, чтобы написать код, который можно выдавать за эталон.

[encyclopedist]

Это квадратичная версия, ведь так? Тогда хотелось бы и на линейную взглянуть.

[encyclopedist]

Поясню: проблема в цикле поиска операции с максимальным приоритетом. Для длинного выражения без скобок (например 1+2+3+....), этот поиск всегда будет сканировать весь диапазон.

[ProgrammerAlias]

int Parse(int L, int R, vi* ops = 0) {
    vi* opsV = ops;
    vi v;
    if (!opsV || opsV->empty()) {
        opsV = &v;
        for (int i = L; i < R; ++i) {
            if (s[i] == '(') {
                i = next[i];
                continue;
            }
            if (s[i] == ')')
                ASS(0);
            if (opsV->empty() || op[s[opsV->back()]] <= op[s[i]]) {
                if (!opsV->empty() && op[s[opsV->back()]] < op[s[i]])
                    opsV->clear();
                opsV->push_back(i);
            }
        }
    }
    if (!opsV->empty()) {
        int pos = opsV->back();
        opsV->pop_back();
        switch (s[pos]) {
            case '+': return Parse(L, pos, opsV) + Parse(pos + 1, R);
            case '-': return Parse(L, pos, opsV) - Parse(pos + 1, R);
            case '*': return Parse(L, pos, opsV) * Parse(pos + 1, R);
            case '/': return Parse(L, pos, opsV) / Parse(pos + 1, R);
        }
    }
    if (s[L] == '(')
        return Parse(L + 1, R - 1);
    if (s[L] == '-')
        return -Parse(L + 1, R);
    int x = 0;
    ASS(s[L] >= '0' && s[L] <= '9');
    while (s[L] >= '0' && s[L] <= '9') {
        x = x * 10 + s[L] - '0';
        ++L;
    }
    return x;
}

[encyclopedist]

Спасибо.

[makc3d]

> 100 миллионов вложенных скобок
ад и fml

[Mrrl]

Нерекурсивная версия получилась не длиннее рекурсивной. Но она использует stl::stack :(

typedef pair<double,char> spear;

enum{
	NOERR=0,
	ERR_ILLEGAL_UNARY=1,
	ERR_ILLEGAL_BINARY=2,
	ERR_NO_RPAR=3,
	ERR_EXTRA_RPAR=4,
	ERR_ZERO_DIVIDE=5
};

double CalcExpr(char *s,int &err){
	stack<spear> ops;

	int mode=0;
	double val=0;
	ops.push(spear(0,0));  // hard '('

	for(;;){
		char c=*s++;
		if(c>0 && c<=' ') continue;
		err=ERR_ILLEGAL_UNARY;
		if(mode==0){   // unary
			if(c>='0' && c<='9'){
				val=c-'0';
				while(*s>='0' && *s<='9') val=val*10+(*s++-'0');
				mode=1;
			} else if(c=='+' || c=='-' || c=='('){
				ops.push(spear(0,c));
			} else return val;
		} else{
			int lpri=
				c==0 ? 0 :
				c==')' ? 2 :
				c=='+' || c=='-' ? 4 :
				c=='*' || c=='/' ? 6 : -1;
			err=ERR_ILLEGAL_BINARY;
			if(lpri<0) return val;
			double ccont=true;
			while(ccont){
				char last=ops.top().second;
				int rpri=
					last==0 ? 1 :
					last=='(' ? 3 :
					last=='+' || last=='-' ? 5 : 7;
				if(lpri>rpri) break;
				double lastval=ops.top().first;
				ops.pop();
				err=NOERR;
				switch(last){
				case 0: return val;
				case '(':
					err=ERR_NO_RPAR;
					if(c!=')') return val;
					ccont=false;
					break;
				case '+':
					val+=lastval;
					break;
				case '-':
					val=lastval-val;
					break;
				case '*':
					val*=lastval;
					break;
				case '/':
					err=ERR_ZERO_DIVIDE;
					if(val==0) return lastval;
					val=lastval/val;
					break;
				}
			}
			if(c==')'){
				err=ERR_EXTRA_RPAR;
				if(ccont) return val;
			} else {
				ops.push(spear(val,c));
				mode=0;
			}
		}
	}
}

[anatolix]

1. Примерно про все крупные компании есть жалобы. Яндекс набрал 6000 сотрудников, и отказал примерно вдесятеро раз большему количеству, жалобы вы можете по пальцам пересчитать, по-моему процент не очень плохой, но мы его пытаемся улучшать.
Кстати, попробуйте найти хоть один отзыв «я работал в Яндексе и мне не понравилось», что кажется сильно больше говорит о компании, чем отзывы «Меня не взяли и мне не понравилось».

2. Угу, вот тут кажется пишут сколько получают люди уровня Дейкстры в Яндексе.
ria.ru/technology/20110527/380674438.html

У нас хорошие зарплаты вполне соответствующие рынку(просто это более менее конфеденциальная информация поэтому, к сожалению с цифрами сложно ответить) и к ним еще в дополнение акции. Миллионов долларов как до IPO там прямо сейчас нет(если компания не вырастет еще в 10 раз) но даже если стоимость яндекса будет примерно такой же как сейчас, они все равно в объеме которые могут вывести зарплату например на вдвое больше рыночной(но не со старта, не всем). Stock based compensation сейчас покрывает 25% разработчиков.

[kibergus]

Мне было бы очень интересно почитать отзывы от программистов поработавших у вас, а затем ушедших.

Попробую вспомнить, из-за чего увольнялись коллеги. Числа даю точные, но за какой период и из скольки человек выборка, не скажу. Отсортировал по-убыванию.

4 человека уехали из России. Двое принципиально уехали из страны, один ради нового жизненного опыта, а еще один уже вернулся обратно, но в минский офис, а не в московский.

2 человека уходили на более высокие зарплаты. Один из них поработал полгода в стартапе, пока там были интересные задачи, а потом вернулся обратно в Яндекс.

1 человек ушел в Гугл. Про причины я не спрашивал.

1 человек решил сменить область деятельности и ушел писать компиляторы. Но отношения в коллективе ему там не очень понравились. Вернулся к нам в другой отдел.

[anatolix]

> По ссылке у вас 270 сотрудников в штате, и 6000 нанятых.
2700. Статья времени IPO прошло года 3. Тогда в компании работало 2700 человек, сейчас 6000 с копейками. Просто рост органический. Текучка есть но имхо очень маленькая, в сумме кажется из Яндекса в российские компании почти не уходят, есть некоторое количество людей которые уезжают из России/Москвы. Очень большой уровень возвратов, в смысле ушел — вернулся в Яндекс.

> Ключевые разработчики с улицы не приходят.
Приходят и потом становятся ключевыми.

> 10% сотрудников вполне могут быть приближенными к руководству людьми
Угу, человек который жжет в работе очень быстро замечается руководством и становится ключевым. Это классический пример корелляции когда ключевость зависит от успехов в работе, карьера зависит от успехов в работе, зарплата зависит от успехов в работе и количество акций тоже от успехов в работе.

> а не подходящим людям прямо говорить, что вам нужны лучшие из лучших.
1) Нам нужны лучшие из лучших, их немного, мы их целенаправленно хантим, большими зарплатами. просто по объявлениям их редко удается набрать, да и лучшие из лучших это не набор скиллов, скиллы там необходимое условие, но на таком уровне они дают только 10% вклада.
2) Нам так же нужны люди которые могут стать лучшими, почти все кто сейчас жжет не пришел готовым, а научились всему внутри. Если что в России почти нет индустрии где есть люди с готовой нужной нам специализацией, почти всему люди учатся внутри.
3) Нам так же нужны просто квалифицированные разработчики.

[anatolix]

На должность серьезного разработчика можно, нужно просто быть серьезным разработчиком. Ну в смысле например вот Яндекс постоянно конкурсы разные по machine learning проводит — выступите хорошо и поймете, что к вам относятся очень серьезно.
Или в компании в нашей сфере сделайте что-то хорошее — тоже отнесутся.
Написание в резюме любого количества слов о своей серьезности к сожалению очень слабый фактор.

[Phoen]

Фидбеки такого плана встречал не раз: www.linux.org.ru/forum/job/9501598/page1#comment-9605776

p.s. Сам решил попробоваться на младшего системного администратора ради интереса, скоро собеседование, посмотрим что выйдет.

[oleksiivinogradov]

Я у себя в callsfreecallsделаю так:
1. Четко формулирую ЗП, навыки и опыт мне необходимый для HR
2. Собеседование проходит в четыре этапа:
а) кандидат рассказывает последовательно по резюме об опыте работы и показывает (если хочет) участки кода или рассказывает интересные решение которые он там придумал
б) я даю ему свой ноутбук и показывают определенные участки кода которые он должен прокомментировать
в) на основании кода который дал я даю тестовое задание
г) рассказываю о будущем компании, что можно заработать в процессе и какие ждут задачи

Таким образом я избегаю нескольких проблем:
а) относительной неопределенности как в яндексе (ну мы же большая компания вы же понимаете что все будет круто)
б) слишком сложных задач для всех кандидатов (чем больше он расскажет об опыте работы и раскроет себя тем легче будет тестовое задание)
в) необходимость подгребать всех под одну гребенку, каждое собеседование уникально по сути

Такой подход оправдывает себя при поиске талантов, которые ищут большой самореализации, а не винтиков большой машины. Перевернуть мир нелегко внутри большой компании.

[anatolix]

> Четко формулирую ЗП, навыки и опыт мне необходимый для HR
если это можно сформулировать, что обычно всегда можно если компания не занимается чем-то наукоемким это конечно решает все проблемы.
Но просто и вы скоро поймете что для разработчиков с одинаковыми навыками и опытом продуктивность иногда различается в десятки раз и их под одну гребенку не получится.

[oleksiivinogradov]

У меня как раз очень наукоемкие задачи. И для соискателя очень важно знать что он должен глубоко разбираться и любить алгоритмы и математику что я и пишу сразу. Есть масса хороших программистов которые лучше сделают стиль приложения чем кодирование сложного математического алгоритма и им наверное ваша задача не очень будет в радость.
Я конечно знаю про еффективность. Для этого я и провожу собеседование по описанной методике, чтобы определить эффективность в будущем. Я сам кодирую и понимаю много просто по тому как человек написал или прокомментировал небольшую задачу. Надо внимательно смотреть на то как он работает.
Конечно в ваших условиях приходится ставить процесс на относительный «поток» тогда как я могу себе позволить более персонализированные вещи. В этом наверное и есть разница большой и небольшой компании.

[dendibakh]

Я тоже нашел время и написал свою версию этого парсера. Вот: github.com/dendibakh/LLParser.
Потратил около 3-4 часов на разработку и 1-2 часа на рефакторинг. Но по-моему вышло очень красиво!

[Maccimo]

Исходники в кодировке CP866 нечасто встретишь в 2014 году.

[samo-delkin]

Бросился в глаза вот этот фрагмент из кода разработчика

Код

int main() {
    std::string line;
    while (!std::cin.eof()) {
        std::getline(std::cin, line);

        if (line.length() > 0) {
            try {
                std::cout << process(line) << std::endl;
            } catch (std::exception &e) {
                std::cout << "error: " << e.what() << std::endl;
            }
        }
    }

    return 0;
}

Тут смоделировал, что может из этого получиться

Код

#include <iostream>

double process(const std::string &str)
{
    std::cout << "string: " << str << std::endl;
    return 0.0;
}

int main()
{
    std::string line;

    while (!std::cin.eof()) {
        std::getline(std::cin, line);
        if (line.length() > 0) {
            try {
                std::cout << process(line) << std::endl;
            } catch (std::exception &e) {
                std::cout << "error: " << e.what() << std::endl;
            }
        }
        std::cout << "cin.good(): " << std::cin.good() << std::endl;
        std::cin.seekg(0);
    }
    return 0;
}

Это вывод

...
cin.good(): 0
string: a
0
cin.good(): 0
string: a
0
cin.good(): 0
string: a
0
cin.good(): 0
string: a
0
cin.good(): 0
string: a
...

В общем, пусть getline() вставляет прямо в условие.