Pull to refresh

Comments 457

Пару раз не прошёл интервью в Амазон (они очень активно нанимают), впечатления остались очень положительные — их сотрудники действительно пытаются узнать твои сильные стороны, уважительно и профессионально ведут процесс собеседований (ни какого сравнения с другой известной крупной компанией). Многому научился в процессе подготовки. Рекомендую — полезное и увлекательное занятие, только планку нужно высокую ставить, чтобы не сожалеть, когда ее преодолеете.
Фигасе. Гугл заболел, что-ли? Я андроид разраб — три раза проходил онсайт в гугле в MV и самый приближенный к андроиду вопрос был «а покажите над чем раньше работали», три четверти заданий обычно динамическое программирование и отстаток почему-то простецкие задачки с leetcode.

Скорее уж Mountain View (там главный кампус)

Признаю ошибку, хотя, судя по статье, думал речь идёт о Европе.
Иногда, кстати, сокращают до MTV.
И наверное чаще, чем MV. [citation needed]
MV вполне нормально для обозначения Mountain View.
BTW MTV на автобусах Гугловских написано, которые сотрудников развозят.
Видимо, заболел. Я не так давно переехал в Лондон в тот же самый Android, так по Android ни одного вопроса ни на одном собеседовании не было.
> Но это уже совсем другая история.

А про устройство в другую компанию есть планы написать? Было бы круто.
Да, с удовольствием почитал бы )
Планы есть, но пока мало материала и времени. Так как устройство в другую компанию было связано с переездом в другую страну, надо сначала тут обжиться, а потом можно уже и писать про все сразу.

А почему андроид? После проведённой подготовки произвольный swe же пыщпыщ

Да привык я как-то к андроиду ) Уже как 6 лет в нем ковыряюсь. Ну и допустим что собеседование на произвольного SWE я пройду на ура. А что дальше-то делать? Я же по сути всю жизнь с мобилками ковыряюсь, ничего другого не умею, кроме разве что давно забытых сакральных знаний об ассемблере и микроконтроллерах.
Вот и получается, что Андроид я знаю, а собеседование не прошел.
А то, куда наверное прошел бы, я не знаю.
Такой вот парадокс )
Ну а потом уже свичнуться в андроид :)
Вы ограничиваете себя сами своим отношением. Вы Software Engineer, который в данный момент времени занимается мобильными приложениями. А в принципе можете быстро перейти в любую другую область. Проще всего посмотреть сначала в Backend, ничего сложного там нет. Те же алгоритмы и подходы. Технологии меняются часто и всем приходится постоянно учиться.
Не совсем. Как я уже писал, я всю жизнь занимаюсь мобилками или встраиваемыми устройствами. Занимаюсь потому, что мне это нравится. У меня были офферы от геймдев компании и компании по разработке чего-то вроде биллинговой системы. Но даже имея их я предпочел мобильную разработку. Так что это скорее вопрос желания, а не возможностей.
Когда приходишь в Гугл учишь много нового, потому что все системы и «библиотеки» свои. То есть общие знания о том, как что устроено помогает, но в целом никто не ждет, что ты с первого дня начнешь писать кучу кода. Поэтому интервью так устроены, потому что в основном фундаментальные знания снаружи полезны внутри. И в целом ожидается, что ты сможешь взять любую технологию/язык и сделать что-то с этим. Я уже успел написать код на 6 языках и даже сделать кое-какие изменения в приложении для Андроида, хотя никогда в жизни не прикасался к Андроиду.

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

Я бы попробовал опять, но просто на SWE, а потом, уже поняв что и как устроено внутри, решить куда хочется дальше идти.
Ничего страшного, я даже в небольшие компании интервью, где спрашивают все вот эти заумные алгоритмы и задачки, которые не имеют отношения к реальной работе и проектам, заваливаю, но это не сильно мешает в итоге найти подходящего работодателя.
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
Грузчики, технички и кассиры — тоже люди. Вообще все вокруг люди, за исключением тех, кто не люди.
Грузчики это же физики!
По своему опыту знаете? :)
*ирония*
А не пробовали читать текст прежде, чем искромётно шутить?

По вашей логике, только гуманитарии не могут пройти собеседование в Гугл? Вот вы, например, работаете в Гугл или вы — гуманитарий?

Может, он может, но не хочет. Я, например, довольно долго относился к этой категории.
как сохранить энтузиазм и мотивацию в течение года, изучая алгоритмы и решая задачи, которые не встречаются у тебя в практике?
Один из вариантов — соревнования по программированию. Для меня сработало более чем. Да, я себя и в принципе смог бы заставить, но соревновательный элемент это очень неплохая мотивация. Особенно после того, как начинает получаться )
а где брали свободное время?
Вечерами, на выходных. Иногда на работе выпадало свободное время.
А как к этому относились домашние?
Терпели и поддерживали ) У меня очень хорошие домашние.
очень помогает почитать перед сном какой-нибудь алгоритм, а засыпая пытатся в уме его имплементировать
имплементировать

Скомпилировать

UFO just landed and posted this here
Ох… стоит ли оно того? если такие знания потом на практике не использовать — выветриваются быстро.

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

Но такое упорство заслуживает уважения.

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

Вот прямо то, что хотел ответить )
Откройте мне секрет: тут очень много пишут про нужность всех этих графов, деревьев, матриц, сортировок и преобразований.
Я, правда, в специализированных конторах по разработке ПО не работал — я программы пишу в одиночку (потому что я просто инженер в НИИ, а не в IT-фирме). Пишу программ я много. Самых разных. И игры, и простенькие 3D-движки и чёрт знает, что ещё. Как для себя, так и по работе. Задач требуется решать массу. Кому это просто посчитать, а кому-то сложный комплекс нужен с большущим GUI. И вот никак я не могу понять, чем вы в IT-конторах занимаетесь, что вам нужны все эти деревья и сортировки? Ну правда, я давно заметил, что самое сложное в программе — это обеспечить интерфейс для маленького (по сравнению с обёрткой вокруг) модуля. Этот модуль и есть то, ради чего программа делалась. И в этом модуле могут быть все эти алгоритмы. Но он получает конкретные данные (это как фильтр в фотошопе, а вокруг него весь остальной фотошоп) и часто достаточно прост. Непростая вот вся остальная обвязка с проверкой ошибок, получением данных, реакцией на действия пользователя, автоматика. Есть, правда, «чистые программы» — там почти вся программа такой вот модуль. Но это специфическая задача автоматики. Так вот, я чего не понимаю-то: как так выходит, что у меня в ПО эти алгоритмы встречаются достаточно редко и самым сложным не являются, а послушать вас всех, так у вас кроме алгоритмов в программе, считай ничего и нет — остальное не существенное. И я этого нифига не понимаю. Расскажите, если не сложно, в чём тут фишка.
Спасибо. :)
Я уже приводил в других темах пример. Продублирую тут.
«И пример из личной практики. Человек, явно не понимающий ничего в сортировках, умудрился делать вставку в сортированную коллекцию за O((N^2)*lgN), вместо O(lgN). Что при размере коллекции 1000 элементов дает примерно 7 000 000 (7 миллионов, Карл) операций, вместо 7.»
Графы — поиск пути почти в любой игре. Или на карте.
Деревья — TreeMap из Java. Мне вот один человек на собеседовании доказывал, что это ненужная штука и можно отсортировать HashMap. Шутник.
Матрицы — любая банальная операция в машинном обучении. Там сплошные матрицы.
Т.е. шаг в сторону от GUI, и вот они, алгоритмы )
Всё это замечательно, но мой вопрос не об этом. За всю мою практику мне пару раз потребовалось BSP-дерево (для думоподобного движка) и столько сортировка. Остальные задачи всего этого не требовали. Они требовали управления устройствами, работы с железом, обработки ситуаций автоматики, но никаких графов, деревьев и матриц (я имею в виду работу с разрежёнными матрицами и прочей экзотикой — обычные матрицы и кватернионы я использовал в математике) не требовалось совсем.
Возможно, в вашей практике это так. В практике других людей по-другому. Недавно вот была статья, где люди из Яндекса приводили примеры достаточно простых ситуаций, где им понадобились алгоритмы.
И опять же вопрос не столько в том, что они требуются, а в том, что надо понимать, как что работает.
Я уже упомянул выше про сортировку HashMap. На мой взгляд такой уровень знаний для разработчика неприемлем.
Но многие могут с этим конечно не соглашаться.
Но я ведь и прошу вас всех рассказать о вашей практике. :) Люди из яндекса не интересны — это как и гугл специфическая контора. Меня интересуют обычные программисты. Не с гугла и подобных мегакорпораций.

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


То есть, человек может накатать с нуля операционку (так бывает — не Windows, конечно, но вполне рабочую), сделать систему управления боеголовкой (так тоже бывает), накатать автоматику станка или высоконадёжного устройства с резервированием, но вот HashMap он не использует и не применяет. А уровень знаний почему-то остаётся неприемлем. Почему же? Что помешает открыть книжку и найти требуемое? Почему в инженерной практике не требуется значть вот прямо всё — есть справочники, есть пособия по проектированию. Вот не знаю я, как делать лопасти турбины. Открываю литературу и читаю: все расчёты есть. Так же и со схемотехникой. Нужен мне прецизионный усилитель — открываем, читаем, изучаем, применяем. Тогда что не так с IT? Я не понимаю. :)

Вот, кстати, а где вы эти хэши используете? Я такое максимум в шахматной программе использовал для определения повтора позиций и не более.
Вот, кстати, а где вы эти хэши используете?
Да везде же. В Java всего два варианта Map: HashMap и TreeMap. Остальное завязано на них так или иначе. И если мне надо удобно хранить пару ключ-значение с доступом по ключу (разумно быстрым), то естественно я использую одну из них. И так как в среднем HashMap быстрее (если знать как его готовить), то использую я его. А TreeMap как раз в тех редких случаях, когда нужна сортировка по ключам.
Открываю литературу и читаю: все расчёты есть.
Вот вы читаете. А другой возьмет и запилит на production сервер в «горячее» место HashMap с кастомным объектом в качестве ключа и не переопределенной хэш функцией. Что сервер сделает от такого? Естественно «умрет», так как поиск в мапе деградирует с O(1) до O(N). А зачем ему читать доки? Он же где-то слышал, что HashMap быстрый.
И да, я видел на собеседовании людей, которые не знают что такое хэш и как он используется в HashMap, но при этом HashMap используют.
. И если мне надо удобно хранить пару ключ-значение


Вопрос был в том, для чего вам может понадобиться хранить пару ключ-значение и тем более делать это с хэшем? Два примера (оба связаны с анализом текста для интерпретации/компиляции) тут привели. Но это вряд ли распространённые задачи.

и запилит на production сервер


Давайте всё же без web (я не знаком с web и не занимаюсь им). Меня интересует обычный Си++ и прикладное ПО, запускаемое на ПК пользователей.
С хэшем чтобы быстрее, ибо правильно настроенный HashMap быстрее TreeMap, как минимум асимптотически.
Хранить пару ключ-значение например чтобы из списка в миллион пользователей (или сообщений, или отчетов или чего угодно) можно было быстро выдернуть искомое по ID. Например железяка (мы же не рассматриваем веб, пусть будет прямая связь по bluetooth) говорит, что пользователь 100500 изменил местоположение и присылает новые координаты. Почему не присылает все данные по пользователю? Потому, что они могут быть несколько мегабайт. Нечего забивать канал. Я беру HashMap, в который у меня все пользователи загружены при коннекте к железке, быстро выдергиваю пользователя, меняю данные и уведомляю пользователя через UI. Да, можно было хранить пользователей списком, но тогда бы мне пришлось просмотреть миллион пользователей (в худшем случае). И так каждый раз. А сообщения такого типа могут прилетать от каждого пользователя.

И да, это примерное описание реальной ситуации, с которой я сталкивался.
Судя по всему, мне потребуется несколько переформулировать «без web». Правильнее будет: «без клиент-серверной технологии». Иначе сюда, действительно, сразу попадают все задачи поиска пользователя, а они и так очевидны, но совсем не интересны. Впрочем, может я сильно отстал, и алгоритмы так желанны у соискателей потому, что везде этот самый «web» с подобными задачами поиска пользователей?
Ну, тогда не из моей практики, но в принципе — написание любой IDE и почти любого текстового редактора. В IDE там и графы, и строки с подстроками и все что угодно. В текстовом редакторе соответственно работа со строками/подстроками.
Даже не знаю, что сказать. Вроде как строки все действительно используют, но что-то я сомневаюсь, что часто пишут собственный скоростной поиск подстроки в строке.
Все эти ответы — всё не то. Как бы объяснить…
Вот смотрите: вы пользуетесь всеми этими строками, хэшами, стеками, очередями, деревьями и прочим. Почти всё из этого покрывается stl. Вы будете писать свой алгоритм сортировки только если у вас есть специфика в данных. Всё остальное время вы будете вызывать функцию из библиотеки. Зачем в этом случае вам помнить алгоритмы сортировок? Что это вам даст? Ничего. Та же история со всем остальным. Если вам понадобится балансировать дерево — найдёте и так, как это сделать. Искать подстроку в строке с максимальной скоростью — точно так же.
Далее, в программе всё это перечисленное составляет, наверное, столь малую часть, что непонятно, почему эта часть возведена в абсолют. Я вот об этом и спрашиваю: моя практика показывает, что сложность разработки ПО не связана с тем, что принято называть алгоритмами. Она связана с внутренней организацией, с общими алгоритмами работы ПО, с прозрачным взаимодействием между модулями, с предусматриванием возникающих ситуаций, но никак не с сортировками, поиском и прочим. Именно поэтому я и спрашиваю вас, что такое вы постоянно пишете, что у вас на первое место постоянно вылезает не архитектура ПО, а все эти стандартные алгоритмы? Вы отвечаете — мы ими ищем пользователей, строки и прочее. Неужели у вас вся программа — это бесконечный поиск с минимальной обработкой? У меня почему-то программы выглядят как автоматы с кучей состояний в зависимости от того, что хочет пользователь. Скажем, вот пользователь решил включить режим рисования. Отменяем всё незавершённое в предыдущем режиме, начинаем новый. Пользователь щёлкнул мышкой — запоминаем точку, предварительно пересчитав координаты из экранных координат в мировые с учётом масштаба и смещения системы координат. Пользователь продолжает дальше щёлкать мышкой и перемещать поле зажав другую кнопку мышки. Отслеживаем курсор и отрисовываем линию, соединяющую соседние точки между собой и всё остальное, уже нарисованное пользователем (простой список нарисованного есть). Пользователь замкнул фигуру. Проверяем, выпуклая ли она? Если да, заносим её в список с определением описывающего прямоугольника и позволяем рисовать дальше заново. Алгоритмы до сих пор так и не появились. Это примерно так работает у меня редактор карт. Конечно, можно захотеть странного в данном случае — разбить список готовых объектов на дерево для оптимизации вывода графики, но во-первых, даже если я это сделаю, то это составит крохотную часть программы, а во-вторых, пользователь физически не нарисует столько простых объектов, чтобы оно начало тормозить даже на P-233. Потому что пробежать список и выбросить всё, с координатами описывающего прямоугольника вне экрана очень быстрый процесс.
Именно поэтому я и спрашиваю вас, что такое вы постоянно пишете, что у вас на первое место постоянно вылезает не архитектура ПО, а все эти стандартные алгоритмы?

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


Мне кажется, у нас разные Солнечные системы. :)
Скорее всего, все сводится именно к этому )
Пользователь замкнул фигуру. Проверяем, выпуклая ли она?
А вот кстати и алгоритм. Из раздела Computational Geometry. Неважно, как мы это проверяете, но это алгоритм, готовый или самодельный.
Не-а. :) Потому что, как все знают, вообще-то алгоритм — это просто порядок действий для достижения результата — то есть, абсолютно любая программа и есть алгоритм. А вот то, что понимают под алгоритмами нынче, это вполне чёткие фишки типа фишек из книги Рода Стивенса «Алгоритмы. Теория и практическое применение».
Ну не знаю, когда меня учили алгоритмам, там проверка многоугольника на выпуклость вполне была, в теме «Вычислительная геометрия».
Из моей практики мне несколько раз помогало знание основ алгоритмов. Самое очевидное и частое где это пригождается — народ поголовно не понимает разницу между линейным поиском и поиском по хеш таблице. Только в прошлом году разгонял участок кода, который работал 30 минут из за большого количества линейных поисков (там надо было замапить одну сущность на другую, так вот бралось пооле из сущности 1 и лнейным поиском искалось поле из сущности 2). И после замены на словарик тот участок стал работать 3 секунды. Потому когда я собеседую людей, обязательно задаю вопрос про различие поиска по словарю и по списку.
Другой пример — однажды мы делали систему где важной частью была древовидная сущность — дерево с произвольным количеством дочерних узлов. Нам надо было ходить вверх\вниз, собирать множество и подмножество объектов, и прочее. Это, конечно, не rocket science, но поиск в ширину и глубину пришлось использовать.
Много было более мелких эпизодов, когда ты видишь неэффективный код и правишь его просто чтобы улучшить производительность — как то раз применял сортировку подсчетом, менял проверку наличия цифр в строке с регулярки на линейный поиск (почему все так любят регулярки? Они ж медленные. Откуда я это знаю? — из курса алгоритмов) и тд. Но, конечно, у меня не было ничего настолько сложного, чтобы пришлось прямо изобретать алрогитм. А писать свою сортировку слиянием это вообще зачем? Я не уверен, что олимпиадники в задачах пишут сортировки сами (только если это не смысл задачи), мне кажется это просто трата времени.
Я к тому, что писать алгоритмы каждый день может и не придется, но знание как они работают помогает писать более эффективный код.
Спасибо. :) Да понятно, что кусочки любой использовал.

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


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


Нет, не знаю. Я знаю что есть CORDIC (цифра за цифрой) для быстрых математических операций. А вообще, сопроцессор у нас чем занимается? Электричество только жрёт что ли? А оптический умножитель не хотите применить (да, если бы была задача на скорость и устройство сами бы проектировали, я бы на этапе создания железа бы уже задал ряд вопросов)? :) Есть и такое.

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


Мне кажется, вы шутите. У меня тут сложные вычислительные задачи (да, обсчёт модели гироскопа дорогая штука. А уж если ещё и фильтр Калмана добавить...) на микроконтроллерах работают с крошечным ОЗУ и смешными мегагерцами. А вы мне рассказываете про перерасход аккумулятора и расход времени на мобильнике?! Это которые многоядерные с частотами в пару ГГц? Там подсветка сожрёт больше, чем вы наоптимизируете. Да, собственно, работа сайтов на старом оборудовании прекрасно показывает всю вашу оптимизацию — они не работают на компьютерах, скажем, 2004 года. Не хотят-с. Тормозят вплоть до зависания.

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


Кстати, как вы это решали? Мне приходит в голову хранить поступающие значения в отсортированном связанном списке (сделав его обычной структурой с указателями на предыдущий и последующий элементы — т.е. без stl (чтобы указатели на элементы не менялись) ну и указатели на начало и конец завёл бы), добавляя вставкой элемент куда надо. А в стеке хранить указатель на элемент списка, убирая или вставляя его. Соответственно, начало списка и его конец всегда будут указывать на большее и меньшее число.
> приходит в голову хранить поступающие значения в отсортированном связанном списке

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

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

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

> У меня тут сложные вычислительные задачи (да, обсчёт модели гироскопа дорогая штука. А уж если ещё и фильтр Калмана добавить...)

куда уж мне с 3 миллиардами финансовых операций в сутки 24/7 в swift-е и обязательно не в кластере… написать абы как и пусть банки в очереди ждут пока транзакция досчитается. (и такое в практике было)
только вот как из стека потом вынимать-то… немножко конфуз с правилом FILO выходит.


Так же. В стеке-то указатель на список. Из списка выбросить элемент пара пустяков.

а решается это самым типовым алгоритмом с созданием дублирующего стека.


А подробнее? Вот пришло число — вы его поместили в первый стек. А что со вторым стеком делать?

куда уж мне с 3 миллиардами финансовых операций в сутки 24/7 в swift-е и обязательно не в кластере… написать абы как и пусть банки в очереди ждут пока транзакция досчитается. (и такое в практике было)


И тормозит у вас, конечно, именно умножение чисел, да? ;) Вот эти самые 3 миллиарда финансовых операций в сутки, это сколько умножений в секунду требуется? Неужели, однотактный умножитель в ваш процессор почему-то не завезли? Просто сдаётся мне, вы оптимизировали то, что не требовало оптимизации. Или вам профайлер показал, что программа на умножениях застревает? Но судя по вашей специфике, это будет странно.

вопрос с добавлением в отсортированный список не отпадает. золотое сечение тут использовать не получится — элементы лежат в памяти не подряд.
это не HashMap и ткнуть в нужный элемент не получится. чтобы получить, скажем, 4й элемент придется обратиться к 1му, от него ко второму, от него к третьему и лишь потом получите нужное.
а теперь представим список из 1_000_000_000 элементов и вы добавили какое-то число, равное max-1… можно идти домой — сегодня результата не будет.


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


И тормозит у вас, конечно, именно умножение чисел, да?

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

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


Да, не отпадает.

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


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

но вот после чистки кода от таких вот «типовых» решений


А если умножение вернуть стандартное, быстродействие у вас ухудшается?
А если умножение вернуть стандартное, быстродействие у вас ухудшается?

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


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


Профайлер часто показывает, что такие системы бывают

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

общая идея была «будем считать каждый байт и такт».


До ассемблера с оптимизацией кэшей и оптимизаций предсказаний ветвлений вы, надо полагать, ещё не добрались? :) (шутка :) )

моя практика показывает, что 9 из 10 java-программистов


Я не пишу на java. Только Си и Си++. :) Поэтому проблемы java мне не ведомы.
До ассемблера с оптимизацией кэшей и оптимизаций предсказаний ветвлений вы, надо полагать, ещё не добрались?

ну вообще-то до изучения исходников добрались.


Поэтому проблемы java мне не ведомы.

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

ну вообще-то до изучения исходников добрались.


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

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


От профайлера типа Intel VTune мне (в Си++) нужно просто увидеть, где программа проводит большую часть времени во время работы и какая конкретно операция жрёт процессор больше всего. Что показывает профайлер для java — не в курсе.
у меня не мобильник. всего лишь депозитарная система ЦБ, которые известные медиа ресурсы, банковские сервера… сидя на 1 месте 5 лет только потеряете квалификацию. это был простейший пример с мобильником, но ничуть не надуманный. просто обычно нормальная подготовка такова, что устройство значения особого не имеет.

> полагаю, для написания высокоскоростного приложения java не лучший выбор

предположение не верно. страшно удивитесь, но путем некоторых ухищрений и манипуляций Java может даже обогнать плюсы за счет более качественной оптимизации байт-кода. но это требует опять же знаний. а не книжек уровня 1го курса. плюс уж извините, но плюсы крайне неудобны в крупных проектах. бардак с именованиями, редкие обновления спек, множество велосипедов по причине отсутствия стандартных типовых библиотек для не слишком стандартных вещей. одни утечки памяти чего стоят — в проекте из нескольких тысяч файлов допустить подобное ничего не стоит. посетите что-нибудь из конференций jug.ru (для дотнетовцев тоже есть) — сильно удивитесь подходам в крупных компаниях.
как я вас понял — вы работаете без команды и обмена опытом нет. может быть в этом проблема? сходите на собеседование в крупную компанию — запомните на чем завалите собеседование.

сам лет 7 назад собеседовался в mail на позицию разработчика в skyforge. на вопрос о графах в итоге выдал бред, что «сейчас компьютеры настолько мощные, что знать этого не нужно».
провалил. выпросил книжки для самообучение. прочитал… до сих пор стыдно)))

> и какая конкретно операция жрёт процессор больше всего.

ну в том же Java профайлере операция может быть слишком высокоуровневой. то что там что-то написало — не значит ровным счетом ничего. например. не выйдет заглянуть внутрь for без бубна.
самое смешное, что далеко не все понимают, что профайлер «врет» чтобы программа не повисла из-за слишком пристального внимания.
UFO just landed and posted this here
Как ни странно, я нашёл эту задачу с решением. Понятно, как решается. Там, кстати, есть интересные варианты решения и без дублирующего стека (для целых чисел):

Я нашел решение, которое удовлетворяет всем упомянутым ограничениям (операции с постоянным временем) и постоянное дополнительное пространство.

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

public class MinStack {
    long min;
    Stack<Long> stack;

    public MinStack(){
        stack = new Stack<>();
    }

    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push(0L);
            min = x;
        } else {
            stack.push(x - min); //Could be negative if min value needs to change
            if (x < min) min = x;
        }
    }

    public int pop() {
        if (stack.isEmpty()) return;

        long pop = stack.pop();

        if (pop < 0) {
            long ret = min
            min = min - pop; //If negative, increase the min value
            return (int)ret;
        }
        return (int)(pop + min);

    }

    public int top() {
        long top = stack.peek();
        if (top < 0) {
            return (int)min;
        } else {
           return (int)(top + min);
        }
    }

    public int getMin() {
        return (int)min;
    }
}

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

Но заметьте. Двойной стек также не является лучшим решением в целых числах.
Бывают задачи на несколько минут. Бывают на несколько дней. А бывают и на годы.
да.
я просто к чему это все. я пытаюсь донести простую мысль.
алгоритмы надо знать не для галочки. их надо знать просто для того, чтобы понимать какая работа уже была проделана с максимальной эффективностью.
еще с универа придерживаюсь правила — «страшен не тот. у кого атомная бомба, а тот, кто знает где найти ее чертежи и материалы».
просто зная, что «что-то такое я уже видел» вы можете в пару минут поиска сократить время работы с недели до часов. в условиях бизнеса это очень много значит и самым благотворным образом может сказаться на карьере, освободив уйму времени для более интересного.
Так я и не возражаю: «что-то где-то видел» — это прекрасно. Но помнить все эти реализации — увольте.
а как вы предлагаете проверять, что человек не вызубрил названия алгоритмов, а именно понимает о чем речь? ла еще за каких-то пару часов собеседования. если вы понимаете как работает быстрая сортировка — вы ее хоть спросонья напишете.
Вот три года назад я использовал в своей шахматной программе альфа-бета с амортизацией отказов. Угадайте, смогу я сейчас написать условия работы отсечений этого алгоритма? Не смогу. Потому что за три года я делал и изучал массу других вещей. А мозг, он так устроен, что ему нужно забывать, чтобы развиваться (где-то тут даже статья про это была). Кроме конкретных алгоритмов есть куча всего, что вы можете изучать помимо них. Особенно, если вы не занимаетесь всеми этими алгоритмами постоянно (а я не занимаюсь).
Угадайте, смогу я сейчас написать условия работы отсечений этого алгоритма? Не смогу.
Это как раз и является признаком того, что использовали вы алгоритм без понимания того как он работает.
с натуральными числами вроде работать будет. с отрицательными не уверен, но поверю.
Там подсветка сожрёт больше, чем вы наоптимизируете

Ага, это пока ваше приложение не стоит на миллионах устройств, и люди не спрашивают: "А чего это оно жрёт больше других? А чего это оно проснулось?"

вот пример
Конкретно в этом примере как раз все получится: по запросу в Google «stack with minimum» у меня на первой странице все ссылки по теме. Даже код есть с просьбой провести review.
но вот приведенный выше код, кстати, не надежен.
уложу туда 10 значений -1*max_long и получу переполнение. т.е. теоретически вспомогательный функционал крашит основной.
Это вопрос требований. Разумеется, если соискатель на эту тему порассуждает, это будет большим плюсом.
что там на всероссийской и выше
Здесь есть задачи всероссийской олимпиады.
Задача поиска атрибутов по ключу возникает практически в каждой Enterprise системе неоднократно. Web тут совершенно не причем.
Это все замечательно, только использование HashMap и TreeMap к умению написать алгоритм по памяти имеет весьма далекое отношение. Это примерно, как умение водить машину и умение эту машину спроектировать, понятно без азов понимание как работает мотор машину можно быстро угробить, но не каждому современному водителю нужно уметь разобрать и собрать любой современный двигатель на скорость.

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

Это как вопросы вроде вспомнить восьмую нормальную форму БД — да есть 0.01% программистов, которые без нее работать не смогут, но остальные могут работать с базой не вспоминания о нормальных формах.
Я бы даже сказал, если человек написал относительно сложный типовой алгоритм, ни разу не подсмотрев а что там у хохлов в инет, его следует на первый раз предупредить, а в случае рецидива — выгнать за велосипедирование, звезданутость и неосторожность.
А кто и где требует написания алгоритма по памяти?
Так в статье об этом.
Задача была на графы. Я быстро понял, что надо сделать, но выбрал не тот алгоритм. Когда начал писать код осознал это и переключился на другой вариант, который и дописал. Интервьюер задал несколько вопросов на тему сложности алгоритма, спросил, можно ли быстрее. Я как-то затупил и не смог. На этом время вышло и мы распрощались. Потом, минут через 10 до меня дошло, что вместо алгоритма Дейкстры, который я использовал, конкретно в этой задаче можно было бы использовать поиск в ширину, и это было бы быстрее.


Следовательно, автор сидел и реализовывал сам алгоритм.
Написание алгоритма не отличается от написание кода в целом. Меня попросили решить конкретную задачу. У меня был выбор — написать свой велосипед или использовать что-то готовое. Если знаешь что-то готовое, то это гораздо быстрее. Не обязательно помнить детали. Что есть алгоритм Дейкстры? Обычный жадный алгоритм. Берем точку, смотрим расстояние до соседей и запоминаем. Берем ближайшего соседа, смотрим расстояния от него до соседей и обновляем путь до исследованных точек, если он стал короче. Повторять пока не посмотрим все точки. Написать под это код дело техники.
И где там «написание алгоритмов по памяти»?
Ясно написано, что требование было не «вспомнить и написать», а решить задачу. Не требуется при этом стандартные алгоритмы реализовывать — используй библиотеки. Конечно, понимать устройство этих библиотек надо (хотя бы для сложностной асимптотики), но помнить все тонкости реализации — не надо.
Судя по фрагменту, требовалась именно реализация на доске. Программа. А это означает как раз и тонкости реализации в том числе.
Не уверен, что вообще возможно понимать алгоритм Дейкстры, но не мочь его написать. Как только идею понял, реализация очевидна. Поэтому, поскольку проверить, понял ли автор алгоритм, довольно трудно, вместо этого проверили, может ли он его написать
Не уверен, что вообще возможно понимать алгоритм Дейкстры, но не мочь его написать.

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

Да легко можно, понимается он ведь в предметных терминах, а формулируется — в терминах ЯП
Если будет ±1 ошибка в цикле или еще что-нибудь подобное, или код не скомпилируется из-за опечатки, никто вам ничего не скажет (ну, в нормальной компании, конечно). Опять же, никто не будет просить, чтобы вы заменяли индекс в цикле на указатель по массиву или делали еще какую-нибудь оптимизирующую дичь — асимптотика сходится, и нормально.
А вот если вы не можете выразить алгоритм достаточно подробно, чтобы оно хотя бы отдаленно напоминало код (пусть на псевдокоде, неважно), то я бы не сказал, что вы алгоритм знаете.
Мне, наверное, проще будет рекурсивную схему под дийкстру подобрать
Вот это очень интересно, никогда не видел Дейкстры в таком подходе. Может, статью напишете? Думаю, с заголовком вроде «как я, все забыв, придумывал с нуля алгоритм Дейкстры» пойдет на ура.
никто вам ничего не скажет (ну, в нормальной компании, конечно)

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


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

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

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

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

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


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

UFO just landed and posted this here
Умение переводить алгоритм из предметных терминов в код — очень важная составляющая работы программиста, так что такой вопрос на собеседовании убивает сразу двух зайцев :)
Да, можно было хранить пользователей списком, но тогда бы мне пришлось просмотреть миллион пользователей (в худшем случае).

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

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

И писание кода на доске выглядит дикостью. С хорошей IDE очень многое делается компом.

В общем, ваш материал почитал с удовольствием, но порадовался, что в гугл не собираюсь устраиваться. Ну и мнение о них сложилось специфическое, примерно как об армии РФ…
Мне кажется, с мэпами вы отклонились в сторону. Понять, где и когда надо применять TreeMap и HashMap — можно меньше чем за час, просто прочитав их описание. В статье же речь идет о куче алгоритмических задач, и умении их быстро решать, что уже намного более сложно и никак не достигается прочтением, только практикой.
Вот вы читаете. А другой возьмет и запилит на production сервер в «горячее» место HashMap с кастомным объектом в качестве ключа и не переопределенной хэш функцией.

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


Что сервер сделает от такого? Естественно «умрет», так как поиск в мапе деградирует с O(1) до O(N). А зачем ему читать доки? Он же где-то слышал, что HashMap быстрый.

Вообще, согласитесь, если ваш хеш деградирует на дефолтной хеш-функции до линейного, то это не хеш, а хрень.

Вообще, согласитесь, если ваш хеш деградирует на дефолтной хеш-функции до линейного, то это не хеш, а хрень.
Дак на то она в Java и дефолтная, просто шестнадцатеричный идентификатор объекта.
Так может усилия стоит направить на то, чтобы определить тех людей, которые «читают», а не тех, что знают двадцать вариантов сортировки?
Ну, и то и другое полезно. Каждый ли разработчик Java знает, что при сортировке массивов примитивов используется вариация быстрой сортировки, а при сортировке массивов объектов используется вариация сортировки слиянием. И для скольких из них будет сюрпризом, что быстрая сортировка может деградировать до O(N^2), а при сортировке объектов им понадобится дополнительно O(N) памяти?
А что вы подразумеваете под быстрой сортировкой?
Каноничную сортировку Хоара с одним опорным элементом?
Или все вариации?
Java использует DualPivotQuickSort. Подробнее можно посмотреть тут.
Перечитал ваш пост, перечитал свой вопрос, понял что задал вопрос совершенно не про то, про что надо.
Хотя и ответили вы тоже не на тот вопрос, который я задавал :)
P.S.: Про то, что в Java STL используется быстрая сортировка с двумя опорными элементами знал и так, равно как и про TimSort.
так как в среднем HashMap быстрее
Не оспаривая тот факт, что обычно это так, хочется дополнить. В случае TreeMap нам нужно алфавитное сравнение элементов, которое может работать быстрее, чем вычисление хеш-функции. Например, если у нас не очень большой Map из длинных массивов, то TreeMap будет на случайных данных работать быстрее, поскольку сравниваем мы до первого не совпавшего элемента за O(N), где N — размер Map, а хеш считаем — за O(M), где M — размер массива. Помнится, на каких-то олимпиадах я с этим сталкивался.
Не совсем понял, но отвечу на то, что понял. Если массивы это ключи, то это уже в принципе плохо. Если значения, то без разницы.
В случае идеального HashMap, мы имеем О(1) как на вставку, так и на доставание. Т.е. при вставке мы считаем хэш (если он уже не посчитан для этого объекта) и кладем в пустую ячейку. При доставании считаем хэш (если не посчитан) и делаем 1 вызов equals.
В случае с TreeMap equals будет вызываться в каждом узле, чтобы понять куда идти, т.е. lgN раз.

Итого, если даже массив из М элементов это ключ, а в мапах по N элементов, для HashMap положить это M и достать 2*M + N, а для TreeMap положить это M*lgN, и достать аналогично.

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

Нет, не забыл, я написал «идеальный HashMap». Т.е. коллизий у нас нет. Но это да, сферический конь в вакууме.
А вот в дереве элемент всегда кладется как лист. А уже потом мы начинаем балансировать дерево. Т.е. lgN у нас всегда.
Да, я прекрасно понимают, что если нужна гарантия, то мы берем дерево, так как в случае HashMap гарантия это O(N).
Нет, не забыл, я написал «идеальный HashMap». Т.е. коллизий у нас нет. Но это да, сферический конь в вакууме.

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

В этом примере дело не в коллизиях, см мой коммент чуть ниже.
Хеш считается не за O(1), а за O(M), где M — длина массива. А вот сравнение массивов идет лишь до первого не совпавшего элемента, и, соответственно, в случае случайных данных будет в среднем занимать O(log N), где N — число объектов. Причем основание этого логарифма — число возможных вариантов для элемента массива, скажем, для 32-битного числа это будет больше 4 млрд. По сути, константа, в реальном мире.

IdeOne с кодом на C++ о том, что я имею в виду. Hash set из 1000 случайных массивов длиной 100'000 элементов работает втрое дольше, чем tree set из них же. Для map'ов ничего не поменяется. Я использовал стандартный оператор сравнения векторов, и хеш-функцию из boost. Хеш-функцию, правда, пришлось скопировать, не умею я на IdeOne использовать boost.
Причем основание этого логарифма — число возможных вариантов для элемента массива, скажем, для 32-битного числа это будет больше 4 млрд. По сути, константа, в реальном мире.

Кстати, важный момент, которые многие часто забывают.

Что-то я запутался с массивами ) Что вы с ними пытаетесь сделать? Использовать в качестве ключа для мапы или что-то другое?
Складываю во множество. Это ничем (в контексте рассматриваемого эффекта) не отличается от использования их в качестве ключей в мапах. Можете считать, что каждое insert добавляет в мапу элемент с соответствующим ключом и значением nullptr.
PS: Вот версия с мапами, эффект тот же.
Ну, тогда как я и говорил, это в принципе достаточно порочная практика, по крайне мере при использовании с HashMap.
И в данном случае можно от этого уйти, например используя для хэша 3 элемента массива (начало, середина, конец). Снова получаем константу. Вся суть HashMap сводится к правильному выбору хэш функции, задача которой более менее равномерно размазать данные по ячейкам.
И к тому же хэш объекта можно кэшировать. Это удобно для иммутабельных объектов, например таких, как строки в Java.

Но в любом случае итог не меняется — HashMap в среднем быстрее, но может деградировать. TreeMap в среднем медленнее, но дает гарантию.
Ну да, так делать не надо. И это весьма экзотический случай, который едва ли встречается в реальной жизни. Просто забавный факт, который добавляет еще одну крупицу к пониманию HashMap vs TreeMap.
У вас странное отношение. «Специфичная контора», «мегакорпорация». Мне лично, напротив, ваша контора, где нужно управлять железом, кажется специфичной :) Накатать операционку, сделать систему управления боеголовкой, накатать автоматику станка — очень специфичные задачи! Прикладники же, которые пилят бэкенды к веб-сервисам, сталкиваются с хэшмапами и сортировками постоянно.
А вот если отвлечься от Web?
Вы спрашивали, чем мы занимаемся, что нам нужны алгоритмы и структуры данных. Я вам дал один из ответов: вебом. Зачем отвлекаться? )
Потому что я не занимаюсь web и, уверен, масса людей тоже им не занимается. И мне интересно, для чего всем им эти самые алгоритмы сдались и почему они их возводят в абсолют, словно это самое-самое главное в написании ПО.
Да, в свете нового комментария от nobodyhave, мне следует уточнить, что задача авторизации пользователя любого прикладного ПО не представляет для меня интереса, как очевидная задача поиска. Меня не она интересует. :)
По моему сейчас 90% всех программистов это фронтэнд вебовский, бэкенд какой нибудь, да мобилки. Притом что понимание структур данных и алгоритмов везде желательно.
Ну вот у меня не Web, у меня HFT и всякий онлайн трейдинг. Тоже постоянно поток ордеров, которые надо распихивать по фин. инструментам. Инструменты, соответственно, в хэшмапах.

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


По-моему, это задачи одно уровня: клиент-сервер. :)
У меня таких задач практически нет, потому я про них мало что знаю.
Кроме адаптеров, писал симуляторы рынков — везде то мапы, то сеты и перфоманс. Писал кодеки (с биржевых протоколов) — однажды аж Trie использовать пришлось. Кеширование строчек и т.п. так постоянно. Писал анализаторы биржевого трафика, скрипты для разбора логов и т.п. — тоже постоянно map'ы. Как вообще без hashmap'ов программировать?!
где нужно управлять железом


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

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

Если например взять другую область где надо набросать UI. То там конечно не будет этих алгоритмов. Там другие задачи. Возможно вы решаете другие задачи которые редко требуют алгоритмы. Либо используете нативные средства языка или библиотеки. И вам не сильно важно что бы это был быстро.

Можно пример человека, который может на коленке написать операционку(с пруфами), и не знает концепцию хэш-таблицы?

Простые бинарные деревья на самом деле бывают редко нужны из-за специфики их работы и адресации. Хотя хороший slab allocator может эту проблемку порешать, да. А так hash + vector зачастую оказываются быстрее в реализации, когда внезапно нужно иметь упорядоченный хеш. Знание алгоритмов — это хорошо, бесспорно, но при наличии интернета достаточно умения найти подходящий алгоритм. Другой вопрос — возникнет ли такое умение, если нет базовых знаний этих самых алгоритмов...

А вот зачем вам хэш вообще? :)
Могу привести последний пример из личного опыта: реализация CSE в компиляторе. Все используемые программой выражения хранятся в хэш-таблице, чтобы обнаружить повторное использование одинаковых выражений. Моей задачей было придумать такой хэш, который бы не менял относительный порядок выражений в хэш-таблице при изменениях в неотносящемся к CSE коде; в частности, в хэше не должны были использоваться значения указателей, числовые значения опкодов и т.д.
Годится?
Годится? :) Я, может, ошибаюсь, но мне кажется, что написание компилятора весьма большая редкость. Спишем на вашу уникальность. :)

У меня была такая задача, когда я писал удобный (как минимум для себя) язык конфигов libucl — https://github.com/vstakhov/libucl. И там одним из важных свойств была возможность выводить конфиг после парсинга в как можно более близком к оригиналу виде (в том числе и порядок ключей объекта). Ну и производительность была тоже важна, да. Ну и в моем основном проекте Rspamd такая задача тоже встречалась. Если же нужна сортировка элементов, то такой "хеш с порядком" работает только в случае read-most структуры, иначе, конечно, дерево.

Вы, кажется, упорно пытаетесь доказать, что хэш-таблицы нужны только веб-деву и небожителям?
Потребность в алгоритмах и структурах зависит не только от конечной макрозадачи, но и от архитектурного подхода.
Пример: приложение на дельфи7, которое формирует sql запрос, выполняет его, превращает в файл одним из десятков заложенных способов, отправляет. И таких действий в приложении сотни.
Легаси содержало что-то вроде:
AdoQuery1.sql.add(Format(…
И таких от 3 до 30 строк на запрос. А потом outfile.lines.add('node' + encode(adoqwery1.fieldbyname('foo').asstring) + '/node');
Сопровождаемость отсутствует как класс.
Логично вынести шаблоны запросов в ресурсы. Ресурсы адресовать по имени. И чтобы каждый раз не расшифровывать (запросы в ресурсах зашифрованы) — кэшировать. Самое место для хэш-мэпа строка-строка.
А этапы отдельных операций, настроечные параметры — были в харрррдкоде и дельфи-формах, а теперь объявляются декларативно, в массиве константных объектов, и адресуются по имени.
Приложение, заметьте, не поменялось в смысле цели. Но затраты труда на сопровождение и доработку снизились ну просто феерически. Прежде всего — из за введения абстракций с косвенной адресацией элементов по именам.
А начальник, который создал исходный вариант, фигачит всё по-старому и в ус не дует. Ему-то хеш-мапы ни к чему, да… И даже всё работает, и бизнес-цели реализуются.

UFO just landed and posted this here

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

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

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

Не-не. Это как ездить на велосипеде ) Если научился решать задачки, то это останется. Да, забудутся детали, но общий навык никуда не денется, особенно, если все равно пишешь код каждый день.
И восстановить навык при необходимости займет максимум 1-2 месяца, тогда как получить его с 0 потребовалось 1.5 года.
Не-не. Это как ездить на велосипеде ) Если научился решать задачки, то это останется.

Ну, не знаю. Я не раз ловил себя на том, что помню, что задача Х решается неким хитрым методом, но при этом самого метода — не помню. Потому что дело было года 3 назад.

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

Нет, ни то ни другое хитрым методом не является, т.к. в обоих случаях — это вполне алгоритмизируемая штука.
А вот когда вы ОДУ, при помощи хитрой замены решаете, приводя к некоторому виду, в котором оно уже решается при помощи алгоритма — это как раз то самое. Потому что замена ниоткуда не следует и не выводится (если только вы не придите к разделяемым переменным через группы Ли), никакой логики в ней нет.
Именно в этом смысл хитрости метода — в его логической невыводимости и неалгоритмизируемости. Вы либо его знаете, ну, как наизусть, либо вам везет, и он приходит в голову при переборе.
С-но если он в голову пришел — и вы его потом забыли, то тот факт, что вы его когда-то использовали, вам уже ничем и не поможет. И никакое понимание не поможет, потому что понимать там банально нечего.

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

Вы, видимо, не поняли. Смысл хитрого метода именно в том, что ничего глубокого в его основании не лежит. Иначе бы он не был хитрым.


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

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

Если никто не знает — значит основание отсутствует.

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

Да нет, вопрос был не в том…
Очень часто бывает нужно знать асимптотику работы стандартных алгоритмов и структур данных. Грубо говоря, чтобы не использовать List там, где нужен произвольный доступ, тем самым, сэкономив O(N). Еще раз в сто лет бывает нужно реализовать какой-нибудь алгоритм в местном SDK, причем очень желательно сделать это оптимально и обобщенно (например, многие не знают, что обход в ширину, обход в глубину, алгоритм Дейкстры и алгоритм А* — это, по сути, один и тот же алгоритм). Ну и на каждом собеседовании спрашивают, так что знание алгоритмов позволяет получить больше офферов, из которых проще выбрать более вкусный (особенно если все эти офферы есть одновременно — они могут торговаться между собой, избавляя вас от необходимости торговаться с компанией).
Собеседование — вопрос отдельный. Меня интересовало, что вы все такое программируете (чем занимаетесь), что используете тот же обход дерева в ширину? Вот что? В моей практике гораздо чаще встречаются задачи уровня разобраться с работой с технологией (например, с DirectShow, с сокетами, с портами, с написанием драйвера, да с чем ещё угодно), чем делать обход чего либо.
Правда уточню — я пишу на Си и Си++. И не для Web.
что вы все такое программируете (чем занимаетесь), что используете тот же обход дерева в ширину?
В такой постановке вопроса — в 99.9% случаев ничего. Еще в 0.1% случаев — дописываю во внутреннюю SDK какую-нибудь ранговую эвристику в СНМ или что-нибудь такое. Оно потом будет использоваться везде и всеми.
Но помимо этого, я каждый день решаю, что мне использовать — LinkedList или ArrayList, и мне важно не ошибиться в этих решениях.
PS: А поскольку мне все же своя рубашка ближе к телу, для меня лично в знании алгоритмов и структур данных важнее всего возможность получить более вкусные офферы.
В моей практике гораздо чаще встречаются задачи уровня разобраться с работой с технологией (например, с DirectShow, с сокетами, с портами, с написанием драйвера, да с чем ещё угодно), чем делать обход чего либо.
Правда уточню — я пишу на Си и Си++. И не для Web.
В моей тоже. Я, правда, тоже пишу в основном на C и C++ и не для Web.
PS: А поскольку мне все же своя рубашка ближе к телу, для меня лично в знании алгоритмов и структур данных важнее всего возможность получить более вкусные офферы.


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

Кроме того, не стоит забывать, что лучше всего решается та задача/класс задач, которую ты уже решал или видел её решение. Но когда потребуется решить принципиально новое, решишь ли ты, ещё большой вопрос. А типовые задачи можно и в книжке посмотреть.
Тоже был раньше против алгоритмов.
Если человек смог осилить алгоритмы это говорит о том, что он более менее умен, мотивирован и усидчив.
Так я не против. :)
Но я не вижу прикладной их ценности. Это сродни олимпиаде по математике. И я полагаю, что как шахматы развивают только шахматы, то и алгоритмы только сами себя и развивают в мышлении. Но сложность программы не определяется этими самыми алгоритмами. В ПО Шатта вряд ли есть эти самые алгоритмы, а сложность этого ПО ужасающая.
А есть исследования, что шахматы развивают только шахматы?
Я где-то читал исследования, что люди играющие в шахматы значительно успешнее не играющих. Там было про уровень дохода и образования. Попробую найти вечером.
Как позиционируется — шахматисты развивают способность просчитывать и дисциплину. Для тех кто думает что это легко, попробуйте рассчитать хотя бы на 5 ходов вперед все возможные ходы на каждом ходе. Это несложно, но нужна самодисциплина.
Хотя я лично думаю, что люди играющие в шахматы уже заведомо были умнее других и росли в других условиях.

Да, в случае с шахматами — это явно отношение корреляции, а не причинности.

есть такое исследование, называется «шахматные программы»
сколько ни пытался, не смог в них ни текст набрать, ни таблице посчитать

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

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


Тема развития определенных навыков и влияние этих навыков на все остальные аспекты жизни хорошо раскрыта в книге "Peak: Secrets from the New Science of Expertise". Автор книги является также автором исследования про 10000 часов, и в этой книге он объясняет, что популярная трактовка "10000 часов практики == профессионал" является неверной.

Если человек смог осилить алгоритмы это говорит о том, что он более менее умен, мотивирован и усидчив.

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

Глядя на лаги и тормоза хангаутса, джимэйла, да и андроида в целом, требующего 8 ядерного процессора, чтобы лончер минимально плавно листался, не нахожу подтверждения тезиса о большом внимании гугла и его кодеров к оптимизации алгоритма в своих изделиях.
Если человек рассортировал вручную 1 тонну гречнево-рисовой смеси это говорит о том что он глуп или золушка.
или что у него крестная фея — я бы серьезно задумался о такой возможности и вам советую. Крестная фея была бы куда более крутой фичей, даже при условии ограниченной работоспособности предоставляемых ею карет
А типовые задачи можно и в книжке посмотреть.
Поэтому на собеседованиях любят динамическое программирование — оно, как правило, нарабатывается большим опытом. И, зная динамическое программирование, изобрести алгоритм Дейкстры можно, а вот наоборот — нельзя.
Я вот недавно для себя писал игровой движок гексагональный — намучался с алгоритмами когда делал поиск пути.
Но я правильно понимаю, что этот поиск пути махонькая часть движка?
Я-то ведь чего спрашиваю? Эти алгоритмы подаются как первостепенной важности вещь. Но моя практика показывает, что они применяются в прикладном в очень ограниченных объёмах (если вообще применяются), а основная сложность ПО вовсе не в алгоритмах, а скорее, в архитектуре и обеспечении прозрачного взаимодействия десятков/сотен/тысяч компонентов.
UFO just landed and posted this here
Я половины написанных слов не знаю. :)
UFO just landed and posted this here
Ответы могут быть от традиционных («для нашего устройства выгоднее создать свой контроллер со своей ISA и своим компилятором, чем лицензировать существующие») до хайповых («пишем компилятор для смарт-контрактов в новом блокчейне»).
UFO just landed and posted this here
думаю, как бы поизящнее и повыразительнее выражать запросы по AST и по data flow

Не знаю, какие именно запросы и как именно надо выражать, но вроде же в llvm есть встроенные средства для паттерн-матчинга по поддеревьям?
UFO just landed and posted this here
Серьезно? Обход дерева даже мы в 1с периодически используем, правда из за того что в стандартной библиотеке это не реализовано))
… и этот обход и есть суть всей программы. Так? :) Или этот обход — кусочек вспомогательного кода и только? Поймите, я не говорю, что это не нужно использовать, я не понимаю, почему именно вот эта, на мой взгляд, очень незначительная часть ПО, подаётся как суть всего ПО. Вот почему?
Давайте я отвечу на ваш вопрос)

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

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

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

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

Таким образом, незначительная часть ПО подается как суть всего исключительно за неимением другой, сколько нибудь формализованной, сути, а также в целях повышения эффективности (снижения издержек) бизнеса.
Экий интересный подход )
А человек, который докажет, что P = NP маляр или художник? Он же кроме алгоритмов ничего не знает.
А мяляр, который может снизить стоимость издержек для бизнеса в 10 раз, заменив 100 строчек кода достоин называться художником, или не очень?
Знаете, в моей практике в проекте с реальным устройством участвуют и математики (так как теория работы устройства требует построения математической модели). Думаю, с разработкой быстрого алгоритма та же фигня — для них нужны тоже математики. Доказать N=NP — разве это не математическая головоломка? Сдаётся мне, что там не одну диссертацию по этим алгоритмам защитили.

А мяляр, который может снизить стоимость издержек для бизнеса в 10 раз, заменив 100 строчек кода достоин называться художником, или не очень?


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

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

В сложной системе, если она сделана абы как, точно так же вы просто утонете в концепциях и взаимосвязях между объектами задолго до того, как проект вообще появится. А уж сколько интересных неучтённых ошибок вы получите на этапе отладки — это будет сказка. :) У меня тут есть коллега, решающий задачу автоматизации в лоб — я его программу загоню легко в состояние, в котором она начнёт делать с аппаратурой нечто невменяемое. Потому что он вместо общего заложил частности. Алгоритмов, кстати, это ПО не содержит — оно чисто автоматика.
Ну вот смотрите — при нормально организованных процессах модульность так или иначе поддерживают, крупные архитектурные решения принимают архитекторы (а иногда и мелкие), а вот конкретные задачи решают уже все, а при их решении понимание важно. Плюс при прочих равных знание алгоритмов гарантирует что человек с головой и памятью. И их можно быстро проверить. Плюс странно если нормальный программист не знает алгоритмов, ему же это должно быть просто интересно даже самому узнать.
P.S. Несмотря на то что я топлю за знание алгоритмов программистами у самого знания эти почти отсутствуют, как и в сфере которой приходится заниматься. За что кстати 1сников заслуженно часто ругают.
Это все равно что не понимать хотя бы примерно как работает железо, интерпретаторы, компиляторы, ос (не в деталях, а поверхностно хотя бы знать должны все, чтобы чушь не писать)
Плюс странно если нормальный программист не знает алгоритмов, ему же это должно быть просто интересно даже самому узнать.


Он не то, что не знает, он знает что можно делать и какие бывают структуры данных и чем они удобны. Это не значит, что он напишет балансировку дерева, но это значит, что он знает, что это можно сделать и это что-то даст при обходе дерева.
А интересны ему могут быть совсем не дебри теории стандартных алгоритмов. Алгоритмы всего лишь метод обработки каких-то данных и программа делается вовсе не ради этих алгоритмов. Вот решение задачи, для которой и писалась программа, и может составлять интерес.
А откуда он это знает? Значит же интересовался. А раз интересовался — то и смотрел как это сделать можно. Ну и конкретные задачи — задачами, но ведь всегда интересно что и как внутри устроено.
Ну он как бы книжки-то читает иногда. ;) Но из того, что вы пользуетесь какой-то технологией вовсе не следует, что вы сможете её вывести. Я могу пользоваться законом Био-Савара-Лапласа, но вот вывести его не смогу. Ну или уравнениями Максвелла — я их тоже вывести не смогу. Так и тут. Бесполезно просить сделать быструю сортировку — кандидат может вообще плохо помнить, в каких случаях она не самая быстрая и как она вообще устроена. Но он помнит в целом, что сортировки существуют и есть быстрые алгоритмы.

Ну и конкретные задачи — задачами, но ведь всегда интересно что и как внутри устроено.


Ладно, ладно. Вот у вас есть сотовый? Вы знаете, что это — устройство с использованием радиоволн. А вот знаете ли вы методы модуляции, параметры антенны и сможете всё это реализовать? Очень сомневаюсь. А ведь вам, следуя такой логике, должно было быть интересно, как там оно внутри устроено. Но вот мне преподаватель по вакуумной и плазменной электронике как-то сказал на экзамене «Вы что, хотите понять все курсы? Это невозможно. Максимум — останутся в голове какие-то основы и обрывки». Так и здесь. Прочитал книжку — не факт, что даже понял методики и доказательства — но потребуется, можно найти реализацию и сделать. Так всё инженерное образование построено! Почему программисты должны быть другими?
Вообще я не утверждал что я хороший программист. А хорошему да, должно быть интересно все что связано с программированием. А алгоритмы и подобное уже по идее сами по себе запомнятся.
А если интересно вообще множество вещей? Голова лопнет на этапе ухода в конкретику и нюансы. :)
Но, возвращаясь к ПО: в ПО кроме этих самых стандартных алгоритмов полно ведь других вещей — почему же нужно делать акцент именно на алгоритмах? Я полагаю, что на них свет клином не сошёлся.
А если интересно вообще множество вещей? Голова лопнет на этапе ухода в конкретику и нюансы
Насколько я помню, в agile обычно считается, что лучше всего для работы подходит команда из «T-shaped» специалистов. Это такие специальные люди, которые знают все области средненько, а одну — очень хорошо. Исходя из такой логики, наверное, более или менее всем полезно поверхностное знание алгоритмов и структур данных.
Мне вот много чего интересно как внутри устроено, но время есть ограниченный ресурс. Если потратить все это время на A, то пробелы будут в B,C и D. Как произошло у автора с алгоритмами и разработкой непосредственно под Android
Вот и я об этом. А самое интересное, что «специалист подобен флюсу — его полнота односторонняя». И в результате получаем поразительную вещь: я знал математика, который в математике прекрасно, но во-первых, имеет совершенно никакой кругозор, а во-вторых, у него принципиально отсутствует желание понимать. Например, я не смог объяснить ему, как можно измерять массу не в килограммах, а в метрах и секундах (LT-система единиц — масса измеряется в м^3/с^2). Вот не смог и всё тут. Он не может этого понять. Вообще. Он обзывал меня с коллегой идиотами и тупыми, но понять, что происходит при введении подобной системы единиц и почему это получается он не способен даже с формулами. Потому что инерция мышления и привычки мыслить проторенными категориями столь огромны, что требуется полный слом системы в голове. Это поразительно.
UFO just landed and posted this here
Построили бы аналогию с раскладыванием величин в базис.

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

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

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

Ну, он просто импульсивный. :) Верит во всём статьям из википедии (а там почему-то не написано, что массу можно мерить в метрах и секундах). Что рабство было в США не знал вот… Любит авторитетов. :) Но доказывает теоремы и выводит хорошо и кандидатскую защитил. Сейчас наукой занимается в другом месте.

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


При том что алгоритмов я, наверное, не вспомню по памяти вообще ни одного уже.

Что, впрочем, не совсем правда, забыть бинарный поиск нужно сильно постараться например.
Это, конечно, не значит что алгоритмы сами по себе не нужны — вам накидали множество примеров где они таки нужны. Но в случаях когда нужен алгоритм достаточно уметь это заметить и уметь алгоритм найти. А вот тренированный мозг, который может заметить потенциальную проблему и быстро накидать корректную абстракцию вы на SO уже не найдете. Я этот мозг использую буквально каждый день и очень хорошо вижу разницу с теми, кто алгоритмы и структуры данных всякие не изучал. Время объяснения потенциальной проблемы, например, просто кратно отличается.

До 2005 года я любил писать разные простые игровые и прикладные программы и баловался с 3D-графикой. В 2005 мне пришлось начать работать с аппаратурой. И оказалось, что мышление тут потребуется изменить. Отсюда я заключаю, что тренировка мозга гораздо больше связана с анализом и решением возникающих нестандартных ситуаций, а вовсе не с запоминанием и пониманием стандартных алгоритмов.

Это, конечно, не значит что алгоритмы сами по себе не нужны — вам накидали множество примеров где они таки нужны.


Вот именно, что накидали примеров того, где они нужны. А я разве примеры спрашивал? Я спрашивал вполне конкретную вещь: откуда у вас всех акцент именно на алгоритмах? Я на 100% уверен, что могу поставить задачу вам такую, что вы ни разу не используете ни одного стандартного алгоритма, но при этом задачу провалите полностью и утонете в абстракциях и взаимодействиях между компонентами, просто потому, что никогда такого не делали. Вот подобная задача:
1) Имеются три вычислителя, объединённые шиной CAN.
2) Каждый вычислитель имеет четыре процессора, соединённых в звёздочку через двупортовое ОЗУ.
3) Первый процессор подключён к первой шине CAN, второй ко второй, третий к третьей. Четвёртый является DSP и реализует математическую модель и является центром звёздочки. Вычислители соединенты по первой шине. Вторая идёт на обмен с рядом устройств. Третья тоже идёт на некие устройства.
4) Одно из устройств на первой шине управляет электропитанием всех компонентов системы (и вычислителей). Все устройства вне вычислителей троированы.
5) Имеется система тактирования с частотой 32 Гц. Это — системный такт обмена и по результатам обмена производится вычисление модели в заивисимости от команд по магистральному последовательному интерфейсу.
6) Модели нужно около 27 кБ ОЗУ для расчётов и буферов. Скорость CAN не позволит передавать такой объём в каждом такте.
7) Первые процессоры подключены к магистральному последовательному интерфейсу.
8) Каждый момент времени работает только один вычислитель. Второй в горячем резерве. Третий в холодном (выключен).
9) Имеются два программиста. :) Удачи им в написании ПО с резервированием отказов компонентов (отказать может любой. Перезагрузиться, кстати, тоже — время штатной работы исчисляется годами. Потеря связи — запросто. Зависание — легко. Отказ — это когда перезапуски не помогают восстановить управляемость) и синхронизацией данных между вычислителями (с запоминанием того, что вообще делает устройство в данный момент и чем заняты компоненты комплекса и математическая модель). Ах да, язык — Си99.

Вот такое я понимаю — это у меня тут типовая задача. Возможных ситуаций, которые должна отрабатывать программа — до фига. И алгоритмы в решении никак не помогут.
Фух. :)
До 2005 года я любил писать разные простые игровые и прикладные программы и баловался с 3D-графикой. В 2005 мне пришлось начать работать с аппаратурой. И оказалось, что мышление тут потребуется изменить.

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


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

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


анализом и решением возникающих нестандартных ситуаций

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

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


Я говорю о архитектуре приложения. О методах работы.

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


Я уже в сумме раз пять каждому написал, о чём мой вопрос. Зачем вы пытаетесь отвечать на придуманный вами самими вопрос? Ну вот зачем? Я нигде не говорил, что не нужно хотя бы прочитать стандартные алгоритмы. Я спрашивал, почему вы их поставили на первое месте в разработке ПО. И только.

То есть именно что с анализом и решением возникающих нестандартных ситуаций


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

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


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

А я говорю о навыке построения абстракций и умении работать с алгоритмами.


Я спрашивал, почему вы их поставили на первое месте в разработке ПО.

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


Ох… стоит ли оно того? если такие знания потом на практике не использовать — выветриваются быстро.

Я написал почему стоит. Как вы из этого сделали вывод что я считаю изучение алгоритмов самым важным в разработке ПО для меня — загадка.


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

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


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

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


алгоритмы не являются пупом Земли

следует второе:


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

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

То есть вы считаете, что это — типовая задача для разработчика, а веб/мобильное, любой клиент-сервер, любой комилятор/интерпретатор — нет?

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

Как Вам удается совмещать семью-работу-обучение? Просто я никак не могу найти этот баланс, только два из трех получается совместить. :(
Студенту нельзя жениться. Будет заниматься женой — у него появятся " хвосты". Будет увлекаться учебой — вырастут рога. А попробуй совместить и то другое — отбросишь копыта!
Ну, вот как-то удалось. Я почти не тратил время на дорогу. На Кипре я жил в 15 минутах езды от офиса. Вместо обычной книжки читал книжку по программированию. На работе вместо прокрастинации переключался на решение задачек.
Но как вы сами понимаете, такое возможно только на ограниченном отрезке времени.
Например сейчас, с появлением третьего ребенка я бы уже так не смог.
чувак, да ты герой! проделать такое с двумя детьми… у меня хватает время только на 8 часов работы и остальное время с детьми и семьей…
Чувак, да вы мы в 21 веке разленились просто до ужаса и зажрались.
Тут, говорят, диды по 15 детей рожали, успевая при этом гектары перепахивать на сивой кобыле.
График был: с 3:30 до 17:00, обед в том же поле (без смузи).
Такие дела.
Так и отпрыски «дидов» с 5-ти лет избу мели, с 7-и одежду себе шили, с 12-ти за остальными приглядывали, корову доили, есть готовили, пока родители в поле…
Но это не наше детство… ;)
Так они и мёрли как мухи.
Где-то была статья про таджиков (100 чего-то там про Таджикистан), так у них ребёнок к колыбели привязывается как-то (без подушки под головой), снизу пакетик, а сами в поле.
Неплохо умеете пробиваться. У меня один пока ребёнок — время свободное почти исчезло. Час — погулять в день с ребёнком, потом ещё поиграться, попытаться пообучать чему-нибудь, а на остаток не попрограммируешь, т. к. нужна какая-то сквозная задача, а для её начала требуется как минимум отпуск взять. Остаётся только книжки читать и ещё по мелочи.
Два ребенка играют друг с другом, а один с родителями.

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

UFO just landed and posted this here
Плохого в этом ничего нет, особенно, если это самому интересно и не ухудшает софт скиллы(а то иной раз посмотришь на такого «олимпиадника», жалко беднягу становится). Плохо, что это практикуют те компании, в проектах которых это не нужно, а то, что нужно, особо и не спрашивают. Собсно, комментарии ниже тому подтверждение
Какие-то знания реально потом пригодились? Если да, то какие именно?
Какие-то конкретно наверное нет. В общем и целом да. Ну может из конкретных сложность алгоритмов, начинаешь замечать в коде потенциальные «бомбы».
Вообще это можно сравнить со спортом. Например, я бегаю по утрам. Пригодится ли мне когда-то умение бегать? Возможно нет. Повысит ли это мою выносливость в целом? Скорее да.
Тут я бы сравнил с подготовкой к айрон мену, нежели к бегу по утрам

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

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

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

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

Чувство собственной нужности и полезности (пусть даже лишь как отдельного винтика в крупной корпоративной машине) людям нужно.
Мне кажется, если у тебя нет доли в проекте, то лучше вообще не парится и относится к этому скептически. Если уж душа все равно просит нормального кода, тогда лучше делать что-то дома свое. Во-первых, это приносит моральное удовлетворение, которое не смогла дать работа. Во-вторых, помогает не зачахнуть и быть всегда готовым к решению сложных задач. В-третьих, позволяет развиваться независимо ни от кого.
Речь не о качестве кода, а о его нужности в принципе. Очень тяжело делать работу, которая абсолютно никому не нужна. Можно сделать раз, два, но когда ты понимаешь что в конторе это скорее правило чем исключение (т.е. выбрасывание результатов многомесячного труда в помойку) — пропадает вообще стимул что-то дальше делать.
UFO just landed and posted this here
Некоторые части Google лежат в open source, например, Android. Можно оценить, сколько пишет средний разработчик.
Меня как-то смутило одно интервью с инженером Гугла, которое проводило Бибиси. Ожидал увидеть комфортный футуристический офис, нооо… интервью проводили на лужайке во дворе. Сразу понял, что эти футуристические оффисы — кино-постановка. А что творится реально — лучше никому не показывать, даже такой проверенной конторе, как Бибиси.

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

Смутило то, что это было Бибиси, а не блоггер Пупкин, которого любой может обидеть. Я тоже в филиале большой конторы работаю, чуть меньше гугла. Примерно понимаю о чем речь.
Журналист Пупкин, который работает на Бибиси, договорился взять интервью у знакомого разработчика Гугла. :)

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

Бибиси — это очень хороший ПиАр. Многие сами бы заплатили бы.
Приезжайте ко мне в Лондон, покажу лично вам офис. На мой личный взгляд, он лучше, чем офис Яндекса в Москве (его фото вроде были в сети).
Покажите мне, пожалуйста, если возможно. Мне интересно.

Это не так.


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


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

Менеджерская логика в этом есть. Правда тут столкнулся с противоположным подходом тоже в крупной конторе. При собеседовании ничего особо не спрашивают, просто свободная беседа без особой методы. Мотивировали это тем, что они хотят, чтобы у человека возник обратный эмоциональный импульс — сначала казалось уныло, потом оказалось прекрасно.
Собеседование в Gooogle это олимпиада по программированию. При этом шанс писать какой-то убитый легаси очень велик. Риск не оправдан. Можно сходить ради фана, но не более. Тем более 2-3-5 раз.
Ну, команду все же можно выбирать. Да и сменить потом вполне реально.

Нет, далеко не олимпиада — задачки где-то на уровне leetcode'овского medium, ничего сверхъестественного там нет. Интервью на дизайн тоже ничего сложно не представляет из себя если есть какой-никакой бэкграунд в похожем технологическом стаке. Плюсом оценивают пресловутую коммуникабельность и прочие софт-скиллы. И как тут уже заметили таки да, команду можно выбирать + internal mobility работает очень хорошо. Есть даже внутренний стартап-инкубатор где с бюрократией сильно проще чем в среднем по больнице, и туда также постоянно нужны люди, как и в другие проекты.

// Риск не оправдан
многие не согласятся, потому что
— строка в резюме почетная
— знакомства с новыми людьми из крутой компании
— хорошие бонусы
— возможность клевой релокации
— после такой работы чувствуешь себя реально опытным бойцом
Огромное спасибо за статью и ваш опыт! Очень мотивирует поднять ленивую жопу с дивана и взяться за седжвика (бросил после первой части курса). Поднять уровень до интервью в гугл за 1.5 года это очень крутая цель!
С таким упорством у Вас все получится, удачи!
UFO just landed and posted this here
UFO just landed and posted this here
Расскажете, каким Google был 15 лет назад? Интересно.

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


  1. Медленное рабочее решение лучше быстрого, но плохо работающего. Решение за экспоненциальное время, лучше, чем решение, которое должно было бы работать за линейное время, но работало через раз.
  2. Большинство задач даётся в «открытом» виде, без полного набора критериев и требований. Так что, считается хорошим тоном «Будет ли этот код запускаться в нескольких потоках?», «Есть ли какое-то ограничение по памяти?», «Будет ли это приложение кроссплатформенным?», «Это полностью решается классом X из java.util.concurrent, можно ли использовать его?»
  3. Ну и, конечно же, комментировать. «Тут нужно отлавливать NPE», «Этот код не будет потокобезопасным, если бы нужен был потокобезопасный код, то я бы использовал метод Б»

Как-то так. Я хорошо ответил на алгоритмические и архитектурные вопросы и так себе на объектно-ориентированный дизайн, в итоге сейчас пишу эту простыню из Цюриха.

UFO just landed and posted this here
Я о том, что медленное, но рабочее решение лучше, чем ничего. Само собой, быстрое рабочее решение лучше, чем медленное.
Все сильно зависит от интервьюера. Кому-то описанного вами достаточно, кому-то нет. Кого-то N^3 вместо N*lgN не устраивает как решение, стоящее записи. См. интервью 4.
В вашем случае звезды сложились, в моем нет )
Более того, решить задачу — это вообще не то, что нужно для трудоустройства. Обычно нужно показать, что умеешь думать. Если направление мысли было правильным, ты задавал верные вопросы — это будет в сто раз лучше, чем молча код написать.

Можете привести пример из первого пункта? Вы имеете в виду имба-задачи как Traveling Salesman, которую разные гении начинают оптимизировать путем "а давайте брать ближайшую незанятую точку и идти туда"? (Хотя тут уже все перекопано и есть эвристичестие решения, которые ошибаются на 0.05% от идеального-преидеального варианта)


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

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

Просто если человек решал много задач, у него отпечатывается «неполное решение = вообще не решение», то есть если код не прошел даже самый крайний corner case — может идти лесом.

— мне кажется, от этой привычки избавляются уже после первых месяцев работы и начинают понимать, когда нужно исчерпывающее решение, а когда достаточно сделать всё «в первом приближении».
Ребят, вот все конечно же круто, но остался один вопрос — а работа в гугл реально стоит такого гемора? Ну вот в деньгах не факт что больше чем во многих других компаниях, по опыту тоже самое, не факт что будешь заниматься чем-то серьезным, даже наоборот громадная вероятность что самое крутое что ты напишешь это то что писал на собеседовании. И на сколько я слышал от многих знакомых такая фигня с собеседованиями только у гугла, остальные не доходят до такого маразма с требованиями, особенно когда понимают что гонять по алгоритмам фронтенд разработчика это глупость.
Бывший коллега как-то уехал в одну московскую крутую компанию(имя называть не стану), прошел все круги ада собеседований, что только у него не спрашивали, один из вопросов вообще был «а как вы оптимизировали бы решето аткина»(сам завис, через 10 лет после окончания вуза такие вещи вообще не вспомнишь если не применяешь, а вероятность применения близка к нулю), и в результате коллегу взяли и за три года работы по его словам он не применил ничего о чем спрашивали на собеседовании включая почти всех кто сидел в их здании. От лукавого все это, от лукавого.
Для кого-то это гемор, для меня было интересное увлечение. Когда времени на это не стало, свернул попытки устроиться в гугл и устроился в другую компанию. Но знания все равно пригодились )
Не спорю что это отличное увлечение, и я сам бы с удовольствием прошел бы это, но сильно завидую как очень давно уже не будучи студентом как найти на это время. У меня курс по Go на корсуэре длится уже 5 месяцев потому что все время сжирает работа, семья и тренировки.
И на сколько я слышал от многих знакомых такая фигня с собеседованиями только у гугла, остальные не доходят до такого маразма с требованиями, особенно когда понимают что гонять по алгоритмам фронтенд разработчика это глупость.

Надо же как-то фильтровать миллионы желающих работать в Гугле. Все примерно знают одинаково технологии. Остаётся заставлять решать задачки.
Бывший коллега как-то уехал в одну московскую крутую компанию

Тут нету крутых компаний. Яндекс что ли?
Ну не сказал бы что все знают технологии одинаково, это уж сильное преувеличение.
А что такое крутая компания? Вот если положив руку на сердце — чем для среднестатистического разработчика Гугл отличается от многих других компаний, даже региональных, кроме громкого имени и клевой записи в резюме? От того что компания «крутая» и распиаренная не говорит что именно вам придется там заниматься чем-то действительно интересным.
Я посмотрел что там по деньгам у гугла в Цюрихе — пожалуй, да, стоит.

А потом погроммист проходит в Google, резко прыгает к вершине пирамиды Маслоу и начинается выпендреж: "5 строк за год всего лишь послал", "Ну вот в деньгах не факт что больше чем во многих других компаниях"...

UFO just landed and posted this here

А вы посмотрели, что там по уровню жизни в Цюрихе?

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

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

Смотрел, конечно, всё там отлично. Не Россия, конечно, но и не Долина вовсе, при достаточно сильной социальной защищенности и сверхнизкой преступности.
а работа в гугл реально стоит такого гемора?
Полтора года (это с нуля, я так понял, а так было бы быстрее) интересных занятий, общеразвивающих для мозга, ради того, чтобы получить навыки, позволяющие без проблем получить оффер практически в любой интересующей тебя компании? Плюс, если все-таки пойдешь в Google, строчка в резюме, благодаря которой на тебя будут смотреть не так, как на «еще одного иммигранта»? Ну даже не знаю.
Автор судя по всему проходил собеседование на сеньора, а в гугле это $300-400K в год. Много есть мест в мире где можно столько получать?
Вряд ли (уважаемый nobodyhave, подтвердите?). У меня в свое время интервью было примерно таким же по сложности, только вместо Android были еще алгоритмы. Потом со мной связались и сказали, что на джуна я слишком силен и решили пересобеседовать на регуляра. Вообще, Google практически никогда не нанимает сеньоров, для этого нужно быть суперзвездой. Ну или еще какую-нибудь хитрость применить, например, попасть в компанию не через собеседование, а через покупку твоего стартапа.
Да мне особо никто не сообщал, на кого именно ) В вакансии было написано Android developer. Вакансий синьоров там не было вообще, как и джуниоров кстати. А какие-то градации я думаю применяли бы уже по результатам собеседования.
Да мне особо никто не сообщал, на кого именно
Это известная проблема, пока сам не спросишь, не колются. Я спросил в конце онсайта, когда было уже поздно менять, и был удивлен, что меня с без недели пятью годами опыта и текущей строчкой в резюме «Senior в Deutsche Bank» собеседуют на джуна.
Слышал из дойче банка бегут все — руководители сбежали теперь очередь за девелоперами?
Senior — это не руководитель. И пока я там работал, текучка была небольшая, как везде.
Интересно, спасибо )
Буквально сегодня общался с рекрутером из Google, правда они сами меня нашли. Так же предлагают Цюрих.
На следующей неделе будет первое техническое интервью, тут даже больше интересно попробовать и проверить себя.
Сам рекрутер звонил из Лондона, общались через Hangouts и это действительно было не очень, частые фризы, рассыпание картинки и заикания звука.
UFO just landed and posted this here
С рекрутером задачи не решают, а техническое интервью будет на следующей неделе.
Интересно, кто же у них такой пишет Hangouts, что на него все жалуются. Школьники из Индии на аутсорсе?) /s
Я конечно понимаю, что программист который хорошо знает математику это замечательно. Но не уж то в гугл и тд нужна целая армия таких. Почему нельзя иметь просто штат обычных математиков для разработки сложных алгоритмов и просто грамотных программистов которые смогут это понять и реализовать. Само по себе написание качественного кода задача не простая и требует много времени и опыта… Потом вся эта высшая математика необходима не так часто в проектах, а основная часть работ все равно как правило требует математики не выше школьного уровня.
Математика это математика, а Computer Science все-таки несколько другое. Хотя местами и пересекаются.

В Google тоннами шлют свои биографии со всех стран мира. Шанс что рандомное резюме пробьется, равен std::numeric_limits<double>::epsilon(). Из каждого утюга пишут, что не шлите через сайт pdf, отправьте через знакомого, иначе вам придет "привет, досвидания" автоматом.


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

Это ж просто писец. Человек профессор который бы мог работать в los alamos искать идеальное топливо или искать лекарство от рака — куплен гуглом клепать формочки
Тут выбор такой: работать за гроши в поисках лекарства или получать миллион долларов в год за клепание формочек.

Выше вы же писали про $300-400к в год для сеньора. Клепатель формочек получает за троих сеньоров, что ли?

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

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

Google говорит мне, что зарплата Associate professor в Stanford — около $99k в год. В области залива Сан-Франциско семьи с доходом менее $117k в год считаются малообеспеченными. То есть, чтобы перестать быть малообеспеченным, нужно подняться на высшую академическую ступень — full professorship.

Ну это и не отличается как-то существенно от зарплаты сениоров в Сан-Франциско:


https://www.glassdoor.com/Salaries/san-francisco-senior-developer-salary-SRCH_IL.0,13_IM759_KO14,30.htm


немного выше, но все таки сениор — это как раз, наверное, аналог full professorship, а не associate.


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

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

UFO just landed and posted this here
По крайней мере, синиорство по окончанию вуза у меня было без всяких напрягов (я просто люблю писать код), а построить аналогичную научную карьеру надо очень постараться.

Так это уже дело личных предпочтений.

Востребованность «формочек» и других финтифлюшек обществом гораздо выше, чем у идеального топлива. Вряд ли Google или Apple виноват в этом.
Мир вообще штука несправедливая.
Докажите пжлста что востребованность выше. Вот например google wave. Сколько формочнк и кода было написано докторами компьютерных наук. И всемушло вскорзину. Вот такая востребованность. Stupid waste of resources.
Востребованность обществом можно смотреть по деньгам, которые это общество платит. Оно же не станет платить за что-то ненужное? Так что, если мы хотим, например, понять, что востребованнее — machine learning или создание сайтов, то нужно оценить общий оборот компаний, которые занимаются первым и вторым. Подозреваю, что machine learning победит.
UFO just landed and posted this here
Именно по описанному мной функционалу победит? Сомневаюсь. В ML есть компании, которые, хоть и дергают библиотечки, стоят миллиарды.
UFO just landed and posted this here
Не путайте полезность и востребованность. Множество очень востребованных вещей практически бесполезно.

Я пока вижу, что подавляющее большинство окружающих меня людей с готовностью выкладывают несколько сотен долларов за новый телефончик, но отнюдь не готовы и десятку пожертвовать на научные исследования. А значительная доля так вообще считает ученых бездельниками и верит в плоскую землю.
Ну а то, что куча сделанного выбрасывается в корзину не говорит ни о чём — общество с готовностью оплачивает и эту корзинную деятельность.
Google может себе позволить завышать требования. Да, напрямую знания алгоритмов нужны не часто, но при прочих равных программист хорошо ориентирующийся в алгоритмах обычно способен делать работу лучше или быстрее. Кроме того, такой отбор позволяет поддерживать атмосферу в компании.
Мне кажется есть и другая цель: чтобы эти программисты не пошли к конкурентам. Расходы на зарплату — мелочь, на фоне возможной потери лидерства в поиске и рекламе.
Прям hooli из «кремниевой долины»
После окончания курсов я осознал, что многие знания это многие печали. Если раньше я просто знал, что ничего не знаю, то теперь начал осознавать, что именно я не знаю.


so true. Чем больше материала изучаешь, тем больше знаешь о том, чего не знаешь.
Знания как белый круг во тьме, чем круг шире тем больше область видимого не знания)
иногда хочется его конформно отобразить…
Очень показательная история,
автора можно похвалить за настойчивость и трудолюбие,
2 года готовится к экзаменам это подвиг, серьезно.

Но если подавать заявку в Гугл на разработчика Андроид, то как бы нужно 90% времени читать документацию Андроид! Ведь работа будет связана либо с разработкой/оптимизацией фрагментов новых/старых версий Андроид, либо с реализацией сервисов Гугл на Андроид, не так ли?
У Вас ведь спрашивали именно документацию Андроид
«А дальше начались несколько неожиданные вопросы в духе «а что в классе Х делает метод У»»

Со стороны автора рассказа все выглядит как детский сад, Вы просто отняли время у Гугл, играли в игру «собеседование в Гугл», явно не желая получить положительный результат и работать в Гугл, а просто хотели приключений.
И еще раз, 2 года подготовки вызывают уважение.
Android-разработчик, а не разработчик Android'a или я чего-то не так читаю

Так написано: "работа будет связана либо с разработкой/оптимизацией фрагментов новых/старых версий Андроид, либо с реализацией сервисов Гугл на Андроид", то есть и Android-разработчик, и разработчик Android.


Можно подозревать что сил на разработку всего Android, т.е на оболочку, API, свистелки, сервисы типа Google Play тратится несоизмеримо больше сил, чем на создание клиентов приложений на всем готовом, то есть в сорцы нырять пришлось бы все равно. Точно ничего не утверждаю, в Google не работал Android-девом, где-либо еще тоже.


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

Видите ли, до недавнего момента в гугл спрашивали именно то, к чему я готовился. На любую роль, хоть фронтенд разработчик, хоть кто. И какие-то подвижки начались не так давно. И как заметили выше из Лондона, похоже даже не во всех офисах.
Так же я упоминал в статье, что да, рекрутер мне озвучил то, что будут вопросы с андроид спецификой, но не смог привести пример.
Т.е. готовился я играть по одним правилам, а когда сели за стол, то правила слегка поменялись.
А неожиданность вопросов не в том, что они по андроиду, а в сути. Ну не уровень это гугла, спрашивать, что какой метод делает. А особенно как. Т.е. был вопрос, что написано внутри метода. Может я его 3 года назад смотрел, а они там код переписали.
Вы рассказали интересный случай, как КомпьютерСаэнс для конкретной вакансии оказался важным, но не главным фактором. Конечно, ответственность за неудачное собеседование не только Ваша. Рекрутеры должны были уточнить какие-то требования к вакансии, какие знания Вы должны подтвердить на интервью. Плюс, интервьюер имеет какие-то инструкции, кроме общего впечатления (Комп.Саэнс) он должен проверить кандидата на специфику того департамента/команды, где открыта вакансия.
Интересно, интервьюеры как-то представлялись?
Да, но я уже не вспомню подробностей.
интервьюеры как-то представлялись?
Обычно кратко представляются, вроде «привет, меня зовут Алекс, я из команды Android Z»
В конце беседы они всегда спрашивают, есть ли к ним вопросы, и на вопросы в духе «давно ли здесь, чем занимаешься, как тебе атмосфера» и т.п. — отвечают вполне охотно.
Ну не уровень это гугла, спрашивать, что какой метод делает. А особенно как.
Ну это смотря как сформулировать и как оценивать ответ.
Меня вот в одной компании спрашивали «как реализован std::distance?» Я ответил, что впервые такое название слышу. Интервьювер сказал, что это функция, которая выдает расстояние между двумя итераторами и спросил, как бы я ее реализовывал — ну я и рассказал, как бы я это делал, со всякими std::enable_if, с обсуждением того, логично ли выдавать отрицательный ответ, если на вход даны два RandomAccessIterator в неправильном порядке, и тд. По-моему, неплохой вопрос получился.
По доброму завидую силе воли и целеустремленности автора. Некоторые в тепличных условиях без каких-либо раздражителей не хотят даже десятую часть изучить из того, что он смог с семьей и работой.
Ну и довольно сильно мотивирует на учебу и новые знания, спасибо.
Завидую упорству автора. Реально очень круто. И в очередной раз офигеваю с гугловской моды насиловать мозг кандидатам. (больше всего, конечно, меня добивает написание простыни кода на доске)
А чем плохо код на доске писать? Причем, я подозреваю, доску уважаемый автор выбрал самостоятельно — на собеседованиях дают и ноутбук.
Если ноутбук дают — то без вопросов, просто я слышал только про доски и никак иначе.
Нуу, это выглядит так.
— Напишите нам код на доске.
(Начинаю писать код, исписал доску)
— Ой, знаете, а у нас тут хромбук есть, но я им как-то никогда не пользовался. Хотите?
-Нет, спасибо, давайте не будем отвлекаться

Опять же, хромбук поюзать можно, но писать-то придется в гуглодоке. IDE никто не даст.
Интервьювер не прав, что не обратил ваше внимание на него сразу.
Не в гуглодоке, но и не в ИДЕ. Простенький редактор кода, не помню, есть ли подсветка синтаксиса.
Если память мне не изменяет, а это может быть, так как было давно, на тот момент мне предлагали именно гуглодок. И Hangouts собеседования тоже были в нем.
Хэнгаутс собеседования, к сожалению, еще в гуглодоке пока что. Я не знаю, конечно, всех экспериментов с хромбуками, но последний начался недавно и включает в себя этот спец редактор.
Это новая штука. Там есть подсветка синтаксиса. Правда большинство готовится писать на доске и выбирают доску. Также с языками. Готовят джаву, говоришь, у вас тут питон как главный язык в резюме, может питон, а они всё равно на джаве.
Мне на собеседовании у них в Цюрихе не предлагали ноутбук — только доску и маркер.
Возможно, в других офисах ноутбук действительно предлагают.
Неожиданно. Я слышал, что такое случалось в далекой древности.
Я у них был ровно два года назад.

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

А чем плохо код на доске писать?

Я, например, с детства ненавижу писать на доске. Меня напрягают следующие вещи:

1) надо писать от руки (пишу медленнее раз в 10-20, чем набираю)
2) надо писать от руки на вертикальной поверхности, мне это тупо в разы неудобнее, чем на горизонтальной
3) мало места, мелкими буквами писать не люблю и выйдет ещё медленнее чем нормальными
4) нужно постоянно отходить чтоб окинуть взглядом написанное
5) волнуюсь, оказавшись перед доской под чьим-то пристальным взором, будто в школе будто опять очутился (учился там хорошо, но у доски всегда нервы)
UFO just landed and posted this here
Вас собеседует не воплощение компилятора, проверяющее расстановку скобок и точек с запятыми, а живой человек, которому достаточно обвести блок кода в кружочек и пририсовать стрелочку «его вставляем вон туда».
UFO just landed and posted this here
Ох нет. Помнится, в Яндексе мне как-то раз попался один наглухо упоротый интервьювер, требовавший «чтобы вообще вот без ошибок было».

Вы же не прошли? Ну и радуйтесь, не придется с ним работать :)

Да и в целом, в процессе работы на хоть сколь-нибудь сложным алгоритмом с множеством граничных случаев, этих «стрелочек с кружочками» в итоге может стать столько

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

К этим 20 строчкам еще надо алгоритм привести, из алгоритма на все 200.

Что значит «еще надо алгоритм привести»? Кому и куда его приводить надо?
На алгоритмическом интервью вы должны просто написать код и дать к нему устные комментарии. Объём кода, который ожидает увидеть собеседующий обычно очень невелик (и вряд ли требует более 5 минут на собственно написание). Сколько вы при этом наболтать успеете — дело добровольное.
Что значит «еще надо алгоритм привести»? Кому и куда его приводить надо?

Ну вот вы написали алгоритм "влоб", получилось 200 строк. Его, конечно, можно переписать за 20. Но надо еще переписать.


Сколько вы при этом наболтать успеете — дело добровольное.

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

Естественно, что если человек наперед не знает алгоритма, код будет сильно неэффективен
Нет, это неестественно. Нормальный разработчик сначала немного подумает, а потом начнёт писать. Идеального кода сразу, конечно, не получится. Но и разбухания в 10 раз не будет.
Нормальный разработчик сначала немного подумает, а потом начнёт писать.

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


Но и разбухания в 10 раз не будет.

Ну насчет 200 строк я все же утрировал, да, но раза в 3 — вполне себе. И если 20 строк — это тьфу, мало, то 60 для рукописного кода — уже ощутимо.


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

Дело практики: семестр ассистентом в универе — и уже пишешь на доске со скоростью мысли, под хоть десятком пристальных взоров одновременно.
Кроме того, задачи для собеседований нарочно выбираются так, чтобы простыни кода там не понадобились; скорость письма/набора при их решении — вообще не фактор успеха.
Кроме того, задачи для собеседований нарочно выбираются так, чтобы простыни кода там не понадобились
Попробуйте написать на доске (да даже и на бумажке) код для Андроид. Например Activity + AsyncTask + TextWatcher + пару побочных классов типа таймера. И снабдить это минимальной бизнес логикой.
И вы неприятно удивитесь размеру )
Казалось бы, гуглодок решает все эти проблемы. И предлагается на собеседованиях (судя по всему, не всегда, но почти всегда).
UFO just landed and posted this here
Сомневаюсь, что от уважаемого nobodyhave требовали, чтобы код компилировался.
Напрямую никто не требовал, но во многих устных рекомендациях от рекрутера было написание кода, максимально приближенного к реальности. Так что возможно это как-то оценивается интервьюерами.
В письмах с ходу не нашел, но есть такая строчка
«Be sure to test your own code and ensure it’s easily readable without bugs
Для кого-то баг это ошибка в алгоритме, а для кого-то пропущенная скобочка.
Конечно, если ваш код компилируется, это плюс. Я имел в виду, что написать идейно правильный код гораздо важнее, чем синтаксически корректный.
Я с вами согласен, но боюсь в любой компании могут найтись люди, которые наше мнение не разделяют )
Из всех трат Google напрямую оплачивает только билеты. Отель, еда и проезд оплачиваются кандидатом.

Как-то подозрительно, раньше точно так не было. Даже 2 года назад так вроде не было. Бронируют отель и самолет, за еду потом можно по чекам получить.

Мне кажется, что вы зря пытались пройти именно на Android разработчика. Во-первых, это, имхо, одна из самых неинтересных вещей, которыми можно заниматься в Google. Во-вторых, проще пройти как SWE и потом уже трансфериться, если уж очень хочется именно в Android.

Ну и хочу добавить, что интервью — это несколько рандомный процесс и методы оценивания и вопросы некоторых людей являются, мягко говоря, неоптимальными (и не следуют гайдлайнам. какой нафиг код на System Design?)
Как-то на тот момент над этим не задумывался. Тем более что до момента, как позвали на онсайт, никто не говорил, что интервью будет отличаться от стандартного для SWE.
А то что процесс рандомный я уже понял. Если бы было время — может еще бы покидал кубик, но не сложилось.
Как-то подозрительно, раньше точно так не было. Даже 2 года назад так вроде не было. Бронируют отель и самолет, за еду потом можно по чекам получить.


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

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

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

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

Сам в алгоритмах не силен, просто прочитал пару книг, и иногда напоминаю себе что и такое бывает :)
Проблема в отсутствии свободного времени ) Поэтому надо было себя настроить, чтобы выделить это время из несвободного. Маленький лайфхак.
А если есть свободное время и желание развиваться, то естественно это можно делать и просто так.
Как-то не вяжется: сначала заставляют пройти 5 интервью, а в результате получают
Пробовали общаться через Hangouts, но качество было ужасное, поэтому переключились на телефон.
Подход к подбору кандидатов явно требует перемен. Относится и ко многим российским компаниям.
Ну, тут проблема может быть и не в Hangouts ) Интернет на Кипре он такой, специфический )
Сам однажды пробовал собеседоваться через Hangouts. Минут через 20 браузер вылетел с крэшем. Где-то выше в комментариях другие тоже жаловались. Так что проблема точно в Hangouts.
Подход к подбору кандидатов явно требует перемен.

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

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


Есть еще интересный факт — hangouts официально ПО для видеоконференций внутри гугла (https://www.blog.google/products/g-suite/how-google-went-all-video-meetings-and-you-can-too/), а это значит что сами гугловцы отбивают десятки тысяч видеоконференций в день, соединяя зачастую офисы в разных городах и странах.

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

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

Мне кажется есть два подхода:


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

Какой конкретно подход наверное зависит от самой компании (например очень большие компании имеют бесконечную очередь желающих туда попасть) и области о которой идёт речь (в hardware например имеется куда более глубокая специализация, и часто требуется человек с конкретным skill set и опытом)

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

Мне года четыре назад написал рекрутер из Google на Linkedin, но я ему честно сказал тогда, что проходить собеседование не готов. Просил стажировку, — к сожалению, мест не было. Договорились, что буду готовиться и потом сам свяжусь с ним. Проконсультировался у aml на счёт необходимой глубины знаний в python, но решил, что не готов.


Этой весной, занимаясь подготовкой инфраструктуры для повторного прохождения QSA-аудита для получения сертификации PCI, выяснилось, что у k8s с этим всё очень плохо. Немного подумав, я решил, что если и заниматься k8s, то лучше сразу в Google, о чем и было написано в сопровождающем письме к отклику на вакансию SRE через careers.google.com.


Через несколькой дней позвонил HR с просьбой подтвердить намерения, позадавал уточняющие вопросы (в какой офис хотите? и т.д.), после чего прислал письмо со ссылкой на google calendar, где необходмо было выбрать удобный мне слот для первого телефонного интервью.
В процессе поиска информации о формате данных интервью, я натыкался на типичные вопросы, которые там задают… и назначил интервью через 4 дня, решив, что если не смогу пройти первичную отсеевалку, то явно мне дальше делать нечего. Звонок прошёл хорошо, и меня попросили зарегистрироваться на Coding Coaching Session, для подготовки ко второму телефонному звонку.
На CSS было человек десять: трое не досидело до середины, уточняющие вопросы задавали очень вяло.
Смысл CSS ровно один — у них есть анкета, которую заполняет интервьювер по ходу собеседования и чтобы умозаключения более последовательные, а оценки о них более приближенны к реальности — есть манифест о том, как надо себя вести.


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


Готовиться к интервью с особым усердием я не стал, посмотрел несколько типовых задач, да и только.
Во-первых, вместо обещанной сессии по программированию на 45 минут, я получил сессию по nix internals & programming.
Минут через 10 после начала разговора, когда мы еще не с головой залезли в дебри файловой системы, я уточнил что ожидал вообще-то сессии по python. "Сорян", — сказали с той стороны монитора, и пообещали отметить это в анкете.
30 минут мы общались по теории, после чего перешли к практике.
Сначала я и второй рекрутер не видели текст задачи, потому что основной интервьювер писал не в тот документ, после чего у меня отвалился интернет: 10 минут драгоценного времени потрачены зря, но резервный канал под боком и едем дальше: пытаемся обсудить как можно хранить и процессить данные по задаче. Ок, договорились — наконец-то начинаем писать код… на 45 минуте.
И тут же первая (и последняя) сложность:
— Я не знаю какие параметры принимает функция (из стандартной библиотеки) и что она возвращает
— Да мы тоже не знаем, в гугле стандартную библиотеку не юзают, у нас все своё
— Эээ, давай откроем документацию?
— Нет времени, пофантазируй
— унылая_двухминутная_фантазия_о_возможных_методах_и_функциях.jpg
— Время закончилось


Фидбэк за второй звонок: solid knowlege за unix internals и "больше фокусируйтесь на программировании" за вторую часть.
HR уточнила согласен ли я с оценками, на что я ответил: согласен, ведь задача не решена, но организация интервью была очень странная — я так и не понял чего я не знаю и как готовиться дальше (ха-ха!). "Я ж вам присылала список литературы для подготовки… не получали? Странно."


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

Среднее кол-во попыток для тех кто прошёл — 4.

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

Что предложите нанимателям вместо таких собеседований? Брать каждого соискателя на испытательный срок, чтобы посмотреть, насколько хорошо он справится с решением практических задач на работе?
Что предложите нанимателям вместо таких собеседований?

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


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

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

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

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

Во-первых, чтобы не показывать кишки непубличных проектов каждому встречному. Во-вторых, потому что в компаниях размером даже в 1/10 Гугла любой проект будет завязан на стотыщ внутренних сервисов, и одно только объяснение «чем мы здесь пользуемся» займёт дольше, чем само ревью.

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

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


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

Да никогда не бывает такого, что нету таски, в которой не завязано совсем на все. Если у вас таких нет — значит совсем уж говнокод, да.


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

Алгоритмы я заучивал, чтобы не отвлекаться на их вспоминание на интервью.
А вот решение задачек это как раз творческое их применение. Откройте например Hackerrank и возьмите задачу пусть даже не Expert, а Hard. С 95% вероятностью вы не найдете стандартного алгоритма для ее решения. Решение будет состоять либо из модификации стандартного алгоритма, а для этого надо понимать, что у него внутри, либо из комбинации стандартных алгоритмов, причем комбинации не самой очевидной.
А вот решение задачек это как раз творческое их применение. Откройте например Hackerrank и возьмите задачу пусть даже не Expert, а Hard.

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

Дак задачки из жизни они такие же ) Можно в реальной задаче увидеть знакомый паттерн, и решить путем применения известных вещей. А можно изобрести велосипед.
Опять же, задача обычно разбивается на подзадачи. Каждую из них можно решить каким-то способом. Была вот одна интересная Hard задачка. Там в одной из ее частей надо было делать RangeMinQuery. Стандартная вещь, даже банальная, но ни один из четырех опробованных вариантов не прошел по скорости, так как это было «узкое место» в задаче. В итоге после пары часов раздумий придумался вариант, использующий еще более банальные prefix sum, но сделанные очень нестандартным способом. И взлетело. Помогло ли мне знание стандартных алгоритмов? Скорее нет. Помогли ли мне навыки решения задач с их использованием? Да, я смог взглянуть на проблему с разных сторон, примерить разные решения и найти верное, пусть и не очевидное.
Стандартная вещь, даже банальная, но ни один из четырех опробованных вариантов не прошел по скорости

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


Например вот:
https://www.hackerrank.com/challenges/build-a-string/problem


Понятно что решается динамикой за O(n^3), и интуитивно понятно, что такой вариант не пройдет. Но сколько надо? O(n^2logn)? O(n^2)? меньше?

Для Java по опыту знаю, что в 4 секунды укладывается решение с
5х10^7 — 10^8 операций, зависит от сложности операции.
У нас 3 теста, каждый по сложности в худшем случае 30000, т.е уже получаем примерно 100 000. Т.е. тут вырисовывается что-то в духе O(N*lgN*lgN) или O(N*sqrt(N)).
И опять же — в реальной задаче вам никто не скажет сложность. В лучшем случае ограничение по времени, как и здесь. А уже ваша задача подобрать сложность, чтобы влезть в ограничения.
И опять же — в реальной задаче вам никто не скажет сложность.

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

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

Ну там же время не пишут? Просто говорят, что "нишмогла" за ограничение, так?


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

Но у них же не мой компуктер.

Просто говорят, что «нишмогла»
Это да, потому и пишу тесты.
По многим задачам есть открытые тесты. И пишут, сколько по времени ушло на тест. Возьмите такой тест и прогоните у себя на машине. Теперь вы знаете, насколько ваш комп быстрее.
Мой был в 2-3 раза. Т.е. если я вижу, что решение худшего случая на моей машине 10 секунд, я близок к цели. Считает уже минуту — точно мимо.
Если для решения задачи нужно писать оптимальный в неасимптотическом смысле код — это плохая задача. И таких, на самом деле, на реальных интервью и олимпиадах довольно мало. В подавляющем большинстве случаев у вас есть решение, грубо говоря, за N√N, которое в оптимальной реализации работает за 0.1 с, и решение за N^2, которое в оптимальной реализации работает 20 с. Ограничение по времени — 4 секунды.

Конкретно в задаче, которую вы привели выше — NlogN, Nlog^2N или N√N предполагается, судя по ограничениям. Учитывая, что корень — это, как правило, корневая эвристика, которая, как правило, оптимизируется до логарифма использованием дерева, предположу, что тут все же один из двух первых вариантов. Дальше уже можно смотреть — если применяется какой-то стандартный логлинейный алгоритм плюс в комбинации с чем-то или в задаче у нас двумерные данные, по которым может хотеться построить дерево — то Nlog^2N, иначе NlogN. Но двумерные деревья слишком сложны для интервью, так что я бы сказал, что здесь, скорее всего, NlogN предполагается.
PS: Условия задачи не читал, только ограничения.
UP: Прочитал условие задачи. Честно говоря, не понимаю, как решить ее без применения суффиксных структур данных, а они явно выходят за рамки любого собеседования.
Ну дак это и не задача с собеседования, а с соревнования.
Я лично не знаю людей, которые ее решат вместе с написанием кода за полчаса. Хотя они есть ) Я кстати тоже не решу, на Hard задачки у меня уходило минимум по несколько часов, а иногда и дней.
sqrt(N) могут давать некоторые техники и алгоритмы, и обычно дерево там не помощник. Например square root decomposition и Mo algorithm.
Хотя, возможно вы просто знаете больше меня )
square root decomposition — это как раз то, что я назвал выше «корневой эвристикой». Часто (хотя и не всегда) можно использовать дерево высоты более 2, и, соответственно, получить логарифм ценой усложнения кода.
Спасибо за алгоритм Мо, никогда о нем раньше не слышал. По сути, в нем тоже строится дерево высоты 2, в каждом узле которого мы знаем минимумы. Если это дерево сделать бинарным, получится разреженная таблица, которая проще в реализации, работает всего за O(N) с предподсчетом за O(NlogN) и не требует оффлайновости запросов, лишь неизменный массив.

Правда, с другой стороны, она требует в logN раз больше памяти. Если хочется впихнуть в O(N) памяти, нужна структура Фараха-Колтона-Бендера, которая слишком сложна для написания на собеседовании. Но в подобной задаче упомянуть ее будет не лишним.

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

Дело не в количестве непосредственных зависимостей задачи, а в размере полного графа транзитивных зависимостей. В случае Гугла получается, что ближайшая система, о которой внешний кандидат может иметь хоть какое-то представление, находится в 3-4 шагах от начальной точки. Единственный выход: заменять конкретику на абстрактные расплывчатые описания, что примерно эта подсистема делает и какие у неё ограничения. Но system design собеседования примерно на таком уровне детализации и ведутся.

Судя по тому, что написано в статье, человек готовился скорее именно к простому заучиванию алгоритмов.
Зачем судить по пересказу, если можно посмотреть на реальные задачи с собеседований Google? Сами убедитесь, что они не на заучивание.
А как по другим профессиям людей набирают? :)
Я не знаю как. Кроме как программистом, я работал только дояром в коровнике, но там конкурса на вакансию не было :-)
Если хотите рассказать, как набирают людей по другим профессиям — буду рад.
UFO just landed and posted this here

А если нет гитхаба соискателя — то гитхаб работодателя! :)

UFO just landed and posted this here
А вот зачем личный гитхаб для человека у которого нет личных проектов на энтузиазме? Ну вот мне 37, у меня работа, семья, тренировки, откуда мне взять время на личные проекты? Ну вот правда, завидую тем кто может все это совмещать, но чем больше живу тем больше прихожу к мнению что все это «ложь, пи… шь и провокация», ну не верю я в такие вещи, иначе у человека что-то должно просаживаться, например работа текущая не пыльная, занят часа три, а дальше может своим заниматься, либо с семьей общается на отъ… сь, либо спорт в виде зарядки 10 минут утром. Ну вот как все это совместить хотя бы в 18 часов в день и не свихнуться не представляю.
Ну это же просто портфолио. Вот Вам лениво его делать, а кому-то — нет. То есть, у него того другого больше шансов получить работу там, где изучают портфолио. Может быть лично Вам это и не нужно (текущая работа не пыльная, времени хватает на спорт и на семью), а кому-то поможет найти работу мечты.
Личный гитхаб просто увеличивает шансы.
UFO just landed and posted this here
Подскажите, пожалуйста, на каких по сложности задачах с hackerrank лучше тренироваться (имеется в виду practice, не соревнования на время)? Medium или Hard уже?
На самих интервью какой приблизительно сложности алгоритмические задачи были?
Если смотреть Hackerrank, то интервью ближе к Medium, может между Medium и Hard. Если смотреть Leetcode, то Medium и Hard. Leetcode в принципе полегче
Забыл спросить, насколько сильно вас подтянули курсы на курсере и книги по алгоритмам? До их прохождения/прочтения вы могли решать hard и medium задачи с Hackerrank?
Нет конечно ) До того, как я начал всю эту эпопею, я в лучшем случае мог решить некоторые из Medium задач.
Даже только после курсов ситуация была не сильно отличающейся. Знание только теории не прокатит, нужна практика. Т.е. нужно натренировать мозг разбивать задачи на части, оценивать сложность каждой части и пытаться найти для нее наиболее подходящее решение. А для того, чтобы решение было подходящим, в голове должна быть база того, чем можно пользоваться.
Спасибо большое, буду тренироваться.
Я бы советовал решать те задачи, которые для вас сложны, но решаются. И лишь в последнюю недельку перед собеседованием смотреть такого же уровня, как там. Грубо говоря, если написать свою реализацию кучи, то потом стек сможешь реализовать на ура, а вот наоборот — вряд ли.
Не уверен, что правильно понял, но это, видимо, справедливо, при условии, что уровень_сложности(«для вас сложны, но решаются») > уровень_сложности(«такого же уровня, как там»). У меня пока, к сожалению, всё наоборот — уровень_сложности(«для вас сложны, но решаются») << уровень_сложности(«такого же уровня, как там»).
Так что буду пока потихоньку подтягивать знания.
Ну пока наоборот, на собеседование идти смысла нет. Надо потихоньку качать уровень, а для этого полезнее всего решать задачи, которые решить можешь (смысл пытаться доказать великую теорему Ферма?), но сложно (смысл каждый день считать 2+2?). Когда уровень будет превышать тот, что на собеседованиях, с небольшим запасом, стоит потренироваться именно на задачах с собеседований (грубо говоря, навык «решить сложную задачу» не означает наличия навыка «решить задачу средней сложности быстро и в условиях стресса»).
Ну собственно вопрос про это и был. До какого уровня качаться, до medium или все таки до hard. Выяснилось, что до hard, чудес не бывает )
Hard бывает очень разный. Скажем, вот эта задача, упомянутая в обсуждении выше, судя по всему, требует использования суффиксных структур данных, которые вас точно не спросят на собеседовании.
Ну то есть, я, скорее, сказал бы, что «решать 100% hard и быть в состоянии накодить в рамках типичного времени для интервью 50-75% hard» — это уже то самое «с запасом».
Прошу прощения за наглость, оно уже слегка не в тему статьи, но не посоветуете как правильно подходить к решению задач, про которые на при первом взгляде вообще нет идей решений?
Т. е. читаю условия и вообще не понимаю как решать, известные алгоритмы по теме тоже не понятно как применять.
Что делать в этом случае?
Пытаться решить «в лоб» максимально тупым способом?
Гуглить по условиям задачи, смотреть названия алгоритмов в результатах поиска и пытаться их применить самому?
Какой-то другой способ?
Если задачу реально надо решить:
  • В первую очередь — понять асимптотику, это можно сделать по ограничениям.
  • Потом — выписать все алгоритмы, которые на требуемую асимптотику похожи, и попытаться понять, какие из них могут быть применены в этой задаче.
  • Понять (наверное, тут только большой опыт и gut feeling поможет), относится задача к динамическому программированию, жадным алгоритмам или еще какой-нибудь такой большой группе — в этом случае можно попробовать сформулировать все в терминах соответствующей группы алгоритмов (причем заметьте, эти группы — они вообще довольно обширны и сильно пересекаются, например, разбираясь в динамике, можно придумать с нуля алгоритм Дейкстры).
  • Разумным образом ослабить ограничения — скажем, если вы подозреваете быстрое возведение в степень, сначала решить задачу просто с умножением. Ну или считать, что памяти бесконечно много для начала.
  • Выбросить часть ограничений или требований, или, напротив, ввести новые, чтобы было проще решать — скажем, задачу на графе сначала решить для пустого графа, потом для графа из 1 ребра, потом для дерева, потом для кактуса, потом для связного графа, а уже потом — обобщить на общий случай.
  • Нарисовать на бумажке десяток небольших примеров.
  • Попытаться посмотреть на ту же задачу в других терминах — скажем, если есть матрица, представить себе граф, для которого эта матрица будет матрицей смежности.
  • Для задач на динамику можно «вывернуть задачу наизнанку» — вместо вопроса, скажем, «сколько раз нужно кидать в окно транзистор, чтобы найти самый низкий этаж, с которого он разбивается, в здании из n этажей?» рассмотреть «для какого максимально высокого здания будет достаточно k бросков?», чтобы дальше добавить бинарный поиск по ответу.
  • Возможно, еще что-то, этот список — только то, что сразу в голову пришло.
Вообще, далеко не всегда задачу действительно нужно решать. Если, скажем, вы решаете задачу для подготовки к собеседованиям, то некоторые сайты с такими задачами могут давать подсказки, которые помогут получить как можно больше пользы от слишком сложной для вас задачи. Опять же, на реальном собеседовании гораздо важнее не молчать, чем вообще решить задачу — начните рассуждать, и хороший интервьювер направит ваши мысли в правильном направлении.
PS: Чисто по моему опыту — решите десять тысяч задач, и вы будете заранее знать все или почти все алгоритмические задачи с собеседования в Google.
Отличный ответ ) Добавлю еще от себя один пункт.
— написать брутфорс решение. Самое простое, самое тупое, но рабочее.
Отсюда есть 2 плюса. Во-первых, при написании брутфорса очень часто вырисовывается структура решения. И потом, просто меняя в ней компоненты, можно добиться нужной скорости.
Во-вторых, на маленьких тестах вы сможете проверять ваши следующие решения. Т.е. если умное решение не проходит тесты на платформе, то пишем генератор тестов (обычно 10-20 строчек кода) и запускаем его в бесконечный цикл, в котором тест будет решаться брутом и «умным» алгоритмом. При несовпадении ответов останавливаемся, смотрим на тест и дебажим умный алгоритм.
Спасибо большое, шикарный ответ, буду пробовать следовать алгоритму.
Но в какой момент таки будет иметь смысл погуглить какие-то алгоритмы по теме, которые не знаешь?
И по поводу последней части — мне кажется, на собеседовании в том же гугле вряд ли прокатит «не молчать, чем вообще решить задачу». Вкатят минус и до свидания.
Десять тысяч?? Уровня medium-hard? Сколько времени это у вас заняло, если не секрет??
Вопрос не мне, но отвечу ) У меня 1100 задач (от изи до эксперт, на 3 сайтах) заняли год. Но дальше само собой пойдет быстрее, так как многие задачки будут казаться похожими. После 1000 задач медиум задачу с хакерранка можно решить за 20 минут, с кодом, если это не что-то новое. Хард задачу за пару часов, опять же если она не новая.
Само собой зависит от свободного времени. Допустим, 20 минут на задачу, 2 часа в будний день и 4 в выходной. Примерно 50 задач в неделю. 200 недель, 4 года ) Если брать более сложные задачи, то еще дольше.
Допустим, 20 минут на задачу, 2 часа в будний день и 4 в выходной. Примерно 50 задач в неделю. 200 недель, 4 года

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

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

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

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

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

Задачу я в итоге решил полностью и оптимально.
Я уже писал выше, что само решение задачи не так интересно. Больше интересно именно то, что происходит в процессе. Как человек движется к решению. какие идеи озвучивает.
в какой момент таки будет иметь смысл погуглить какие-то алгоритмы по теме, которые не знаешь?
Перед тем, как решать задачи по теме. Сначала — лекции про Дейкстру, потом — задачи на Дейкстру, иначе не решишь.
мне кажется, на собеседовании в том же гугле вряд ли прокатит «не молчать, чем вообще решить задачу»
Мне кажется наоборот, хотя сам я не пробовал (именно в Google, в Яндексе, скажем, пробовал, помогло). Если ты рассуждаешь, то и самомй проще додуматься получается, и интервьювер может увидеть, что тебя переклинило и ты не можешь заметить маленький очевидный кусочек — он его подскажет, и задача будет решена.
Десять тысяч?? Уровня medium-hard? Сколько времени это у вас заняло, если не секрет??
Большая часть их была проще, наверное (сложно оценить, я на leetcode вообще не зарегистрирован). Более или менее постоянно — 10 и 11 классы. Плюс по три недели летом после 7, 8 и 9 классов. Ну и немного на младших курсах, но там прямо немного. Десять тысяч — это примерная оценка.
Более или менее постоянно — 10 и 11 классы. Плюс по три недели летом после 7, 8 и 9 классов. Ну и немного на младших курсах, но там прямо немного. Десять тысяч — это примерная оценка.

Тут надо, наверное, уточнить, сколько в среднем на одну задачу уходило. Потому что если 30-60 на задачу, то это какие-то совсем безумные сроки, если только не заниматься ежедневно часов по 8+ в день.

Ну это сложно сказать. Оценку в ~10'000 задач я посчитал еще на младших курсах, когда в голове было яснее, что и когда я делал. Но несколько месяцев по 8+ часов в день там были.
Если кому-нибудь интересно, могу написать пост с разбором нескольких задачек с собеседований с точки зрения бывшего олимпиадника, в стиле «как бы я это решал». На самом деле, очень много вещей делается автоматически, еще в процессе чтения условия или в первые секунды после, и только из-за этого кажется, что кто-то «сразу знает, как решать задачу».
Мне было бы интересно, но после фразы про десять тысяч задач, мне кажется, там будет огромное количество этого самого gut feeling + нереальная алгоритмическая база, что сильно повлияет на способ мышления.
Ну база там не нереальная, все алгоритмы, которые нужны, вполне можно за неделю-две запомнить, если у вас эйдетическая память =)
Gut feeling попытаюсь частично формализовать, частично искоренить подбором задачи, в котором оно не очень нужно. В общем, посмотрим, как зайдет.
UFO just landed and posted this here

Странно мне всегда казалось что там ищут креативных людей, а не "доводить до автоматизма". Ну его этот гугл

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

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

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

Я бы хоть FizzBuzz спрашивал, если бы его не все знали. Проблема в том, что вопросы часто утекают и их запрещают спрашивать. Поэтому интервьюерам приходится придумывать новые задачи, которые не популярны и не такие сложные. Несложные задачи, которые не сводятся тривиально к известным всем, не так просто придумать, поэтому некоторым попадаются замудренные.
Привет сосед, спасибо за статью! А хорошую работу в Швейцарии веб-разрабом из ЕС легко найти? Сам живу в Греции, на след год планирую в Швейцарию.Если получится.
Привет. За ЕС не скажу, у меня нет паспорта/гражданства какой-нибудь из ЕС стран.
А хорошую работу в Швейцарии веб-разрабом из ЕС легко найти

Зависит есть ли уже гражданство в ЕС (или может постоянное резиденство ЕС, не блю карта). Если нет, то почти нереально, ИМХО (если не в гугл). Я пробовал — первый вопрос граэданство ЕС или право на работу в Швейцарии есть, нет — увы, вы нам не подходите… Местным фирмам, чтобы взять не гражданина ЕС нужно куча сил, времени и денег, а очередь граждан десятки и сотни человек на место, т.к. зарплата сильно выше. Хотя может я не сильно мотивирован был.

P.S. Подавайтесь, к нам, в Люксембург, проще, а уровень жизни тоже высокий. Ну, или в Германию.
Не знаю насчет Люксембурга, но в Берлине в Google зарплаты, с учетом цен и налогов, едва ли не вдвое ниже, чем в Цюрихе.
Ну сьем квартиры, еда, садики и прочее тоже раза в 2 будут больше (в Берлине даже по Германии зарплаты меньше, чем скажем в Кёлне или Дюссельдорфе, но траты тоже меньше).

Да, в итоге денег оставаться все равно в Цюрихе будет больше, но именно поэтому конкурс туда большой, грубо говоря для любого программиста в ЕС переехать в Цюрих, как правило, выиграть в деньгах, поэтому желающих… дох… фига.

Поэтому гугл чуть ли не единственная компания готовая нанимать не граждан ЕС в Швейцарию.

P.S. Люксембург где-то посередине между Германий и Швейцарией, зарплаты после налогов раза в 1,5 выше, чем в Берлине, а траты явно меньше чем в Швейцарии (и Бельгия, Франция и Германия в часовой доступности на общественном транспорте). При этом нет таких заморочек как в Швейцарии с наймом иностранцев.
У меня в свое время получилась разница почти в два раза с учетом цен и налогов.
Я рад за вас. А в гугле в США может быть еще в несколько раз выше. тут вопрос другой где хочется жить и куда сможешь попасть за вменяемое время и усилия.
При расчетах как раз получается, что в США и в Цюрихе примерно одно и то же, с учетом цен и налогов, заметно больше, чем во всей остальной Европе.

Согласен, что стоит смотреть только на достижимые варианты. А еще крайне желательно считать разницу налогов и цен для своей потребительской корзины, а не для средней.
@vedenin1980P.S. Подавайтесь, к нам, в Люксембург, проще, а уровень жизни тоже высокий. Ну, или в Германию.

Спасибо за ответ) С резидентским гражданством ЕС все норм. Люксембург — как второй и уже последний для меня сейчас вариант. Тоже за. Благодарю что просветили, а то были сомнения. Гуглил много, но лучше услышать «по опыту». Подписался, думаю придется когда-нибудь посоветоваться. Заранее спасибо!
Если кому-то вдруг лень искать материалы для подготовки, то вот здесь есть очень крута подборка. Может быть немного слишком для подготовки для собеседований, но для развития — то, что надо

github.com/jwasham/coding-interview-university
Не могу голосовать голосовать.) Спасибо!
Я бы автору порекомендовал так же попробовать свои силы в ФБ, линкидин или тот же спланк компании ни чем не хуже Гугла и возраст там помоложе и денег вполне могут дать побольше. Пинтерест так же активно нанимает… В гугл я обычно заказываю интервью перед тем как искать работу для разогрева и прощупать общий тренд за то время пока работал. За последние 10 лет было толи три, толи четыре интервью. Судя по статье набор задач не сильно изменился.
Такие собеседования, такие вопросы, сложности алгоритмов, как быстрее, как меньше памяти, 100500 этапов интервью…
а по факту:
1) выпиливал некоторые моменты использования гуавы, потому что жрёт памяти как не в себя
2) заканчивался пул коннектов, потому что их использование из какой-то другой гугловой библиотеки было настолько НЕ ОЧЕНЬ очевидным(да, потом нашли пример в доках, да, разработчик не посмотрел)
3) вы видели gmail?), больной ублюдок вообще интерфейс придумывал

Но тем не менее, осадочек остался, ожидаешь-то большего.

Articles