Не говорит в плане понятия сложности. Все таки обычно решения кандидатов на такие задачи не мерят размером константы. По крайней мере я так не делаю, если у вас так, тогда извините :)
Ну количество проходов ни о чем не говорит :)
Вообще, это решение по-моему в разы сложнее, чем обратно польская нотация, которая как раз за один проход :)
Точно, не нужно. Я просто привык эти данные сразу принимать как имеющиеся, когда думаю о решении. Задача и правда неплохая на собеседование! Особенно в формате, в котором вы просите — то есть оставить кандидата — пусть пишет.
Странно, что сложность проще оценивать по коду…
Давайте я попробую объяснить еще раз.
1) У нас есть выражения. Для простоты пока есть только +, -, *, / и (). Допустим, что скобок нет. Тогда понятно как за 2 прохода вычислить результат? На всякий случай, поясню. Сперва за линию считаем все * и / (проще идти с конца и кидать все в левую переменную. После этого останутся равноранговые операции + и -. Это тоже линейно считается. Кстати я не посмотрел, но вы заставляете кандидатов думать о переполнении? Пара операций умножений может быстро усложнить жизнь.
То есть мы умеем линейно решать выражения вида А, где А = (А) | B, где B — выражение без скобок.
2) Теперь добавим скобки. Сперва сделаем линейный прекальк — для каждой скобки определим парную. Это делается с помощью стека. (Надеюсь пояснять не нужно как).
Теперь имея все это делаем так: сканируем рекурсивно слева. Видим скобку — идем вглубь (имеется в виду начинаем независимо сканировать выражение внитри скобок. Допустим, мы пришли к тому, что скобок нет. Тогда за линию считаем ответ. Кладем его «на левую скобку» и возвращаемся из рекурсии. Легко видеть что каждое подскобочное будет просканированно линейно и независимо. Это линия в сумме.
По-моему, смотря как написать. Если добавить просчет парных скобок (обычный стек) и неявно писать ответ на внутрискобочном выражении в левой скобке (то есть не сжимать ничего явно), то будет линия. С другой стороны, это намного сложнее сделать, чем обратно польскую нотацию (если я правильно понял задачу, то это вроде бы классика решения).
По-моему, решето даже не нужно. Можно просто параллельно каждое число факторизовывать за O(sqrt(N)) (то есть если мы нашли делитель до корня, то грустно — число не подходит, иначе оно простое). Потом да, классика за O(n*logn), так как итак есть O(n*sqrt(N) / ядра), то возрастающая последовательность не даст крутой вклад в производительность.
Вообще, я бы из задачи убрал возрастающую последовательность и получил бы неплохую задачу. Так как про проверку на простоту кандидат по идее знать должен, а вот про поиск последовательности — это уже число олимпиадная фишка :)
Хм… В каждом алгоритме мы пройдем все ребра один раз. Сложность одинаковая. O(E). Много раз мы ничего не проходим. Везде все тоже самое. Перепутать два варианта с учетом названий сложно. Но это мое субъективное мнение. Я поверю, что возможно это сложно.
Вообще можно без терминологии жить и разрабатывать что-то с помощью чего-то при помощи какого-то там. Но без терминов вас не поймут. Неужели так сложно выучив и поняв новый алгоритм еще заодно запомнить как он называется? В математике вы учили теоремы с названиями. Тоже зачем? Ну чтобы вас понимали и понимали о чем вы говорите. Почему я должен поверить на интервью, что кандидат знает алгоритм, но не знает название? Особенно таких стандарных вещей, как обходы графов. Это, к сожалению, уже проблемы кандидата. И то, что какой-то компании повезет — может быть, но я лучше перестрахуюсь и не поверю.
Я уже говорил выше, что я не люблю терминологию в интервью. Но не знание, что такое сложность алгоритма — это сразу отказ (не термина сложность, а сути).
А что такое быстрая или медленная компонента динамики обхода? Вообще обход в глубину и в ширину сами как бы в названии говорят как они работают. Если вы знаете как они работают, то перепутать их сложно.
Вообще по-моему вы сейчас больше придираетесь, так как ясно, что интервью гибкий процесс со множеством подсказок. Я очень рад, если кандидат начинает диалог — например, «хм… я знаю обходы графа, но совершенно не помню термины. Обход с использованием очереди, когда мы проходим граф слой за слоем, как он называется?» Тогда я отвечу: «В ширину!» и даже не подумаю, что это минус. А если вопрос будет: «Граф? А что это?». Тут сложнее что-то ответить.
«Algorithm Complexity» или «Big-O notation» — то что я знаю и использую и меня всегда понимали на работе, на интервью, на формах и т.д. С «Worst time» я бы не согласился. К тому же я сделал скидку на волнение кандидата и свой кривой английский, и переформулировал вопрос несколько раз. Другому работодателю не повезет.
Вообще давать задачу на Топологическую сортировку не хорошо — я согласен. То есть с первым пунктом я полностью согласен. И частично не согласен со вторым. Понимаете, когда я, собеседуя человека, на вопрос о сложности алгоритма получаю ответ, что алгоритм не сложный… Мне кажется это сразу отказ! Это основа. Если вы хотите работать в Google или компании такого рода — это нужно знать. Вопросов почему здесь быть не может. Потому что это Google. DFS, BFS — тоже. Так как просто понимать что такое граф — необходимо. Значит базовую работу с ними нужно уметь делать. DFS помогает в понимании рекурсии, что очень важно. BFS в знании очереди, то есть базовой структуры данных, которые тоже знать необходимо. А вот алгоритм Дейкстры, Форда-Беллмана, потоки и т.п. спрашивать на интервью не нужно — это и правда спец знания. Хотя… Если вы допустим хотите работать с графами (ну например в ФБ в соц. графе) наверное спросить про алгоритмы путей можно.
Готовиться к собеседованию можно, но даже если вы видели задачу, то каков шанс, что вы мне ее объясните и напишите без ошибок? Я спрашивал задачу, которая была во многих местах для эксперимента. Мне говорили ответ. Но когда я слегка ее модифицировал (просто добавил размерность) — почти никто не мог ответить. Те, кто жалуются на вопросы, просто не понимают альтернативы. Проектировать сложнее, чем решать. На вопросы дизайна ответить сложнее, чем накодить задачу.
Теперь про СП.
Я все еще участвую в контестах, так как это помогает мне думать быстрее. Я стал намного продуктивнее в разработке (не кодировании, а именно в разработке — то есть дизайн, проектирование, организация и т.д.), когда снова стал решать. Может быть это только у меня так. Не знаю.
Но еще небольшой момент. У меня много знакомых программистов олимпиадников. И я, если честно, затрудняюсь сказать, кто из них не устроился работать в крутую компанию. Кто не захотел уехать — те в Яндексе или в самых лучших местах в родном городе. И все они работают хорошо — то есть получают повышения, интересные проекты. Я ни в коем случае не говорю, что СП — это единственное. У меня также много знакомых, которые прекрасно работают, не занимаясь СП. Это ответ на ваши вопросы. Как измерить? Я просто вижу живые примеры.
Пока практика показывает, что этот метод работают. У нас работают крутые инженеры и фейлов не много. Метод не идеален, однако лучше нет. Почему Вы думаете, что что-то изменится, если будете писать на компе? Он Вам решение нашепчет? Время интервью хотите экономить? Так Вам же хорошо, если дольше будете писать одну задачу. Вопросы не нравятся? Что тогда спрашивать? Как реализовать систему? Так это тоже спрашивают. Если откроете книгу «Cracking coding interview», то увидите, что про это есть глава. Только кандидатам хуже от этих вопросов — они намного сложнее. Спрашивать про язык? А зачем? Допустим Вы спец по с++. «Надрочились», так сказать. А завтра надо будет на python писать, и вы скажете — я не умею… Не хорошо. Может быть спрашивать про технологии? Про SDK? Про инструменты? Ну совсем странно. Хм… А можно ли спрашивать что-то не требующее специальных знаний, чтобы кандидат показал, что он может учиться, что у него есть соображалка? Ах да, мы это и спрашиваем.
Я провел много интервью, и почему-то «надрочившихся» не видел. Зато видел, как люди думают, умеют ли писать код, а не жать «Generate method». Свои задачи я придумываю сам. Мои коллеги тоже. Но проблема в том, что я спрашивал «из пула» — не ответили…
Вас не спрашивают олимпиадные задачи! Почитайте задачи с финала Mail.Ru, или с opencup.ru. Вот это олимпиадные задачи. Там надо тренироваться, знать алгоритмы, оценивать время работы, знать хаки языка, быстро придумывать, строить из заготовок и многое другое.
Эта задача не сложная. Я не полагаю, я знаю, что вас спросят не одну это задачу, а 3-4. И они в сумме покажут много чего. Знание гита, с++ или предыдущий опыт мне ничего не скажут. Я не работал с Вами, я не буду в шоке от того, как вы круто манипулируете клавиатурой со скоростью набора 200 символов в минуту. Я скажу — этот кандидат решил поставленную задачу, задал верные вопросы, знает как оценивать сложность решения и пишет код умно (то есть не сажает тупых ошибок, которые потом не найти).
Я не занимаюсь штангой, но перед каждым занятием Muay Thai я должен прыгать на скакалке. Кстати видел как разминаются штангисты на днях :) догадаетесь?
Реалии таковы, что именно такие задачи задают на собеседованиях. И если честно, на них пройти шанс выше, чем на задачах проектирования. Эта задача хороша, потому что она не требует от Вас умения писать что-то «олимпиадное», просто логика, тесты и умение кодировать. На работе очень много кода будет строиться из таких маленьких задачек.
По своему опыту собеседований, люди не отвечают на серьезные вопросы дизайна. Да и после этих вопросов мне очень сложно оценить кандидата. Я трачу все собеседование на один вопрос. И это может быть очень плохо для кандидата, так как он может затупить и тогда все, второго шанса нет. С маленькими задачами лучше, так как их можно сделать 2-3 за интервью. (Когда я проходил в Фейсбук я успевал сделать 3). И если у кандидата возникли проблемы с одной задачей, вторая может его реабилитировать. Плюс, если кандидат не может написать решение в 30-50 строк, тогда простите, почему я должен поверить, что он способен написать большую работающую систему? Если человек не придумал решение, тогда почему я должен поверить, что он может их придумывать? В Твиттере решаются сложные задачи на всех уровнях. Говорить, что какая то задача плохо отражает скилл… Просто нужно решать их и все.
Эти задачи не идеальны, но компании уровня Твиттера просто нет времени проводить собеседование по 10 часов с каждым. Ведь каждое интервью — это время одного инженера, которое стоит денег. Однако, по-моему, спрашивать про фишки языка — вот это глупость, или про то, кто такой Дейкстра и что он сделал для мира программирования. Или что такое Mock тестирование? (Это вопросы реальные и мне их задавали). Эти вопросы вообще бесполезны, так как если вы напишете решение задачи, предложенной выше с верной асимптотикой и проходящее все тесты, тогда, с большое долей вероятности, вы способны освоить технологии быстро и качественно.
Совет неплохой — мы так и сделали в этот раз — не помогло :) Акклиматизация настала потом — когда работать начал — так как сил меньше намного отсается :) Но ничего страшного — все люди, все все понимают. Да и страховка есть — так что в больницу сходить можно и даже не накладно
Не изобретешь, да. Лучше знать :)
Вообще, это решение по-моему в разы сложнее, чем обратно польская нотация, которая как раз за один проход :)
Давайте я попробую объяснить еще раз.
1) У нас есть выражения. Для простоты пока есть только +, -, *, / и (). Допустим, что скобок нет. Тогда понятно как за 2 прохода вычислить результат? На всякий случай, поясню. Сперва за линию считаем все * и / (проще идти с конца и кидать все в левую переменную. После этого останутся равноранговые операции + и -. Это тоже линейно считается. Кстати я не посмотрел, но вы заставляете кандидатов думать о переполнении? Пара операций умножений может быстро усложнить жизнь.
То есть мы умеем линейно решать выражения вида А, где А = (А) | B, где B — выражение без скобок.
2) Теперь добавим скобки. Сперва сделаем линейный прекальк — для каждой скобки определим парную. Это делается с помощью стека. (Надеюсь пояснять не нужно как).
Теперь имея все это делаем так: сканируем рекурсивно слева. Видим скобку — идем вглубь (имеется в виду начинаем независимо сканировать выражение внитри скобок. Допустим, мы пришли к тому, что скобок нет. Тогда за линию считаем ответ. Кладем его «на левую скобку» и возвращаемся из рекурсии. Легко видеть что каждое подскобочное будет просканированно линейно и независимо. Это линия в сумме.
Вообще, я бы из задачи убрал возрастающую последовательность и получил бы неплохую задачу. Так как про проверку на простоту кандидат по идее знать должен, а вот про поиск последовательности — это уже число олимпиадная фишка :)
Вообще можно без терминологии жить и разрабатывать что-то с помощью чего-то при помощи какого-то там. Но без терминов вас не поймут. Неужели так сложно выучив и поняв новый алгоритм еще заодно запомнить как он называется? В математике вы учили теоремы с названиями. Тоже зачем? Ну чтобы вас понимали и понимали о чем вы говорите. Почему я должен поверить на интервью, что кандидат знает алгоритм, но не знает название? Особенно таких стандарных вещей, как обходы графов. Это, к сожалению, уже проблемы кандидата. И то, что какой-то компании повезет — может быть, но я лучше перестрахуюсь и не поверю.
А что такое быстрая или медленная компонента динамики обхода? Вообще обход в глубину и в ширину сами как бы в названии говорят как они работают. Если вы знаете как они работают, то перепутать их сложно.
Вообще по-моему вы сейчас больше придираетесь, так как ясно, что интервью гибкий процесс со множеством подсказок. Я очень рад, если кандидат начинает диалог — например, «хм… я знаю обходы графа, но совершенно не помню термины. Обход с использованием очереди, когда мы проходим граф слой за слоем, как он называется?» Тогда я отвечу: «В ширину!» и даже не подумаю, что это минус. А если вопрос будет: «Граф? А что это?». Тут сложнее что-то ответить.
Готовиться к собеседованию можно, но даже если вы видели задачу, то каков шанс, что вы мне ее объясните и напишите без ошибок? Я спрашивал задачу, которая была во многих местах для эксперимента. Мне говорили ответ. Но когда я слегка ее модифицировал (просто добавил размерность) — почти никто не мог ответить. Те, кто жалуются на вопросы, просто не понимают альтернативы. Проектировать сложнее, чем решать. На вопросы дизайна ответить сложнее, чем накодить задачу.
Теперь про СП.
Я все еще участвую в контестах, так как это помогает мне думать быстрее. Я стал намного продуктивнее в разработке (не кодировании, а именно в разработке — то есть дизайн, проектирование, организация и т.д.), когда снова стал решать. Может быть это только у меня так. Не знаю.
Но еще небольшой момент. У меня много знакомых программистов олимпиадников. И я, если честно, затрудняюсь сказать, кто из них не устроился работать в крутую компанию. Кто не захотел уехать — те в Яндексе или в самых лучших местах в родном городе. И все они работают хорошо — то есть получают повышения, интересные проекты. Я ни в коем случае не говорю, что СП — это единственное. У меня также много знакомых, которые прекрасно работают, не занимаясь СП. Это ответ на ваши вопросы. Как измерить? Я просто вижу живые примеры.
Я провел много интервью, и почему-то «надрочившихся» не видел. Зато видел, как люди думают, умеют ли писать код, а не жать «Generate method». Свои задачи я придумываю сам. Мои коллеги тоже. Но проблема в том, что я спрашивал «из пула» — не ответили…
Эта задача не сложная. Я не полагаю, я знаю, что вас спросят не одну это задачу, а 3-4. И они в сумме покажут много чего. Знание гита, с++ или предыдущий опыт мне ничего не скажут. Я не работал с Вами, я не буду в шоке от того, как вы круто манипулируете клавиатурой со скоростью набора 200 символов в минуту. Я скажу — этот кандидат решил поставленную задачу, задал верные вопросы, знает как оценивать сложность решения и пишет код умно (то есть не сажает тупых ошибок, которые потом не найти).
Я не занимаюсь штангой, но перед каждым занятием Muay Thai я должен прыгать на скакалке. Кстати видел как разминаются штангисты на днях :) догадаетесь?
По своему опыту собеседований, люди не отвечают на серьезные вопросы дизайна. Да и после этих вопросов мне очень сложно оценить кандидата. Я трачу все собеседование на один вопрос. И это может быть очень плохо для кандидата, так как он может затупить и тогда все, второго шанса нет. С маленькими задачами лучше, так как их можно сделать 2-3 за интервью. (Когда я проходил в Фейсбук я успевал сделать 3). И если у кандидата возникли проблемы с одной задачей, вторая может его реабилитировать. Плюс, если кандидат не может написать решение в 30-50 строк, тогда простите, почему я должен поверить, что он способен написать большую работающую систему? Если человек не придумал решение, тогда почему я должен поверить, что он может их придумывать? В Твиттере решаются сложные задачи на всех уровнях. Говорить, что какая то задача плохо отражает скилл… Просто нужно решать их и все.
Эти задачи не идеальны, но компании уровня Твиттера просто нет времени проводить собеседование по 10 часов с каждым. Ведь каждое интервью — это время одного инженера, которое стоит денег. Однако, по-моему, спрашивать про фишки языка — вот это глупость, или про то, кто такой Дейкстра и что он сделал для мира программирования. Или что такое Mock тестирование? (Это вопросы реальные и мне их задавали). Эти вопросы вообще бесполезны, так как если вы напишете решение задачи, предложенной выше с верной асимптотикой и проходящее все тесты, тогда, с большое долей вероятности, вы способны освоить технологии быстро и качественно.