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

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

Follow the white rabbit green droid, Neo.
То самое чувство, когда провалил важное собеседование из-за того, что переволновался, перетрудился при подготовке, и сфейлил первый же простейший вопрос.
Знакомо. :(
Для меня вообще собеседования — это жуткий стресс. Поэтому я по ним не хожу и опыта прохождения не имею :) Я могу по пальцам одной руки перечислить все свои собеседования в жизни.
Но я бы и в спокойной обстановке не выдал Base64, просто потому что понятия не имел как он работает и всю жизнь воспринимал его как данность. А ведь это так, только цветочки перед 5 ягодками настоящего очного собеседования.
Мне процесс собеседования показался очень сложным, и я бесконечно далек от этого уровня. Не знаю, зачем Гуглу нужны все эти гении-олимпиадники, но им виднее.
Не знаю, зачем Гуглу нужны все эти гении-олимпиадники, но им виднее.

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

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

Оптимизации — вещь полезная, но их надо уметь преподносить.


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


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

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

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

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

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

То есть да, вы можете подменить этот API и убедить программу, что она общается с настощим Facebook'ом и настоящим GMail'ом и эти фейковые Facebook и GMail верят ей… дальше что? Греть воздух?

Для этого более простые способы есть…
Неа, не понимаю.

Устройство грузит (обфусцированный с использованием одноразовой ВМ) код для валидации. Выполняет его.
Что делается с результатом выполнения этого кода?
Сохраняется локально для использования приложениями «соцсетей и прочего»? (Тогда что мешает его подменить локально?)
Отправляется на сервер гугла? (Тогда что мешает вместо него отправить гуглу эталонный результат, полученный на настоящем устройстве?)
Вам нужно убедить в том, что вы не бот, не локальное приложение, а сервер. Именно поэтому результат выполнения DroidGuard отправляется гуглу.
Тогда что мешает отправить гуглу эталонный результат, полученный обфусцированным кодом на настоящем устройстве? Для этого в обфускации разбираться не требуется.

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


Для обхода защиты надо раз в несколько недель перереализовывать ВМ, понять, какие АПИ и как оно может дергать и эмулировать их все, как на реальном устройстве.

Может быть то, что любой «эталонный» результат Гугл принимает ровно один раз?
Читайте внимательно:
«Байт-код каждый раз новый возвращается с сервера.»
Поэтому и ответы ожидаются каждый раз новые.
Виртуальная машина DroidGuard пользуется системными функциями для получения информации из системы? Если они заранее известны и их количество ограничено, то что мешает эмулировать эти функции, если они вызываются в контексте обычного процесса?
Не совсем так. Например, в виртуальной машине есть команды: загрузить строку, загрузить через reflection класс с определенным именем, выполнить через reflection метод с определенным именем. Вот откуда это имя берется — это логика байт-кода. Чтобы узнать имя класса и имя метода, надо интерпретировать команды байт-кода, которые работают со строками.
Вопрос несколько в другом: если DroidGuard работает в контексте стандартного Linux-процесса, то к железу за данными он пойдёт через системные вызовы, которые наверняка можно локализовать и идентифицировать? Я к тому, что может быть не надо разбирать, что делает внутри себя конкретная инкарнация виртуальной машины, может достаточно поместить её в окружение, которое предоставит ей все нужные для прохождения проверки данные?
Во-первых, у меня не было цели обмануть DroidGuard, я просто решил хорошо провести время :)
Во-вторых, защиту SafetyNet вполне успешно обходят, и это совсем не новость. Есть даже опенсорс реализация всех проприетарных гугловых сервисов microG Project.
Спасибо за информацию. Со времён книжек Криса Касперски я знал, что виртуалки используются для защиты приложений, но даже не догадывался, как их может использовать Google в Android.
Судя по ответу andrei_mankevich чуть выше — список возможных системных вызовов теоретически не ограничен, т.е. эмулировать придётся все поддерживаемые системой. Плюс нужно разгадать, какой результат для каждого вызова проверка ожидает получить.
Если там нет криптопротоколов, то конкретная железка всегда будет отвечать то же самое, если BRAND, ABI, DEVICE не меняются. Если парни из Google знают, что Samsung A10 всегда выдаёт «bar» на вызов foo(), то на этом могут строить свою проверку. Соответственно, достаточно один раз прогнать на живом A10 виртуалку DroidGuard, записать всё, что система ей отдавала, и в дальнейшем всегда успешно проходить проверку.
Системных вызовов меньше 400 ;) И не удивлюсь, если Google под каждую железку, которая проходила у них сертификацию, уже сгенерила набор виртуалок, которыми пользуется.

Но это всё чисто теоретические измышлизмы, без конкретной цели монетизации этого взлома можно даже не начинать разбираться, слишком много работы :)
А представляете какие возможности открываются у «корпорации добра» когда постоянно все устройства загружают и безусловно выполняют некий никем не контролируемый код… каждые 10 секунд…
А если кто-то дискредитирует канал связи с «корпорацией добра»?
Опасненько… ;)
Каждый раз, когда мне приходит push-уведомление, я вспоминаю Google Play Services, которые постоянно в онлайне ;)

Весь мир строится на доверии, и надежды на то, что «нас-то всяко пронесёт». Иначе как ездить на машине, ходить по улице и писать на Хабр? :)
А если кто-то дискредитирует канал связи с «корпорацией добра»?
Опасненько…
человек посередине начнёт майнить.
хм, провайдеры не хило так могут зарабатывать майнингом на своих пользователях.
или можно такой не хилый отечественный ботнет поднять, что вся западная сеть встанет и нас точно отрубят от международных каналов связи))
Помимо системных вызовов, вероятно, нужно также идеально сэмулировать процессор, включая всякие экзотические команды, периферийные устройства, возможно, даже, тайминги, ведь любую информацию можно использовать для поиска отличий. Если вы сэмулируете всё это идеально и не отличимо от железного, то вы сделаете идеальный эмулятор, который, конечно же, распознать нельзя. Это уже принцип фильма «Матрица» получается или солипсизма. Вероятно на практике это невозможно и вы быстро упрётесь в проблему, когда код прогоняете, но он отличается от железного и гугл ответ не принимает. Тут вам нужно будет разобраться, почему он отличается. Чтобы это понять, вам в общем случае нужно дизассемблировать переданную виртуальную машину, разобраться в переданном байткоде. Пока вы это будете делать, они уже выпустят новую виртуальную машину. Если же у вас получилось эмулировать устройство и вы смогли зарегистрировать ботов, ну, очевидно этих ботов распознают в дальнейшем и будут разбираться, как вы их зарегистрировали. Изучат ваши ответы и постараются модифицировать байткод и/или виртуальную машину так, чтобы использовать другие методы и исключить уже уязвимые. Понятно, что процесс итеративный, но, вероятно, гуглу тут выигрывать проще, чем вам.
Поэтому я и не буду этим заниматься ;)
Мне было интересно, копал ли топикастер эту тему дальше. С практической точки зрения меня больше интересует применение вирутальных машин внутри приложения для защиты его данных.

Здесь показана интересная фишка — генерация не только нового исполняемого кода, но целиком виртуальной машины для единственной проверки. На такой идее можно построить систему защиты контента в приложении, каждой инсталляции отдавать с сервера свою версию виртуальной машины, которая будет работать только на данном конкретном устройстве и уметь расшифровывать только данный конкретный файл.
Эта идея не нова: vmpsoft.com/support/user-manual/introduction/what-is-vmprotect

И уязвима она совсем с другой стороны: не «дизассемблировать переданную виртуальную машину, разобраться в переданном байткоде», а запустить его на выполнение на реальном телефоне (одном на 100500 эмуляторов) и передать результат от имени эмулятора.
Я несколько о другом. Предположим, приложение имеет платный контент. Проверка оплаты происходит на сервере. Если сервер банально отвечает да/нет, то вся система оплаты ломается парой байт.
Если же сервер передаёт после покупки зашифрованный контент и виртуальную машину, специально заточенную для расшифровывания этого контента, причём только на этом конкретном устройстве, плюс приложение хранит в железном KeyStore какие-то данные для работы этой виртуалки, то ломать эту конструкцию будет гораздо сложнее.

Или я изобретаю ещё один велосипед? ;)
Вот насчет заточки под прям конкретное устройство — я это не очень представляю. Но в целом вы сейчас еще раз описали принцип работы DroidGuard :)

Данные (строки, например) внутри байт-кода можно считать тем самым контентом. Байт-код несет в себе логику по работе с этими данными, а виртуальная машина исполняет команды.
Отсюда и возникает изначальный вопрос, какие системные вызовы делает DroidGuard, чтобы идентифицировать устройство?
Что есть на поверхности:
  • Android ID
  • Application ID
  • Order ID — уникальный идентификатор покупки
  • марка/модель/ABI
  • случайное число, ключ для расшифровывания которого храним в KeyStore

Раньше ещё можно было потрогать MAC, IMEI, но и этого должно хватить, чтобы сделать уникальную виртуалку со своим уникальным набором команд и регистров, на которой достаточно реализовать какой-нибудь кастомный вариант ChaCha20.
А в чём интерес этой фишки? Вы всегда можете реализовать внутри виртуальной машины ещё одну виртуальную машину, например и так сколько угодно раз. А передавать машинный код, в который будет вшит нужный байткод. Честно говоря я не понимаю, почему гугл так не делает.
Интерес в том, чтобы максимально затруднить копирование платного контента, предоставляя каждый раз уникальный блок данных и уникальную виртуалку для его расшифровывания.
Много слоёв будут слишком медленно работать на конечном устройстве. Плюс лишние слои не добавят безопасности, если она вся основана на нескольких переменных, которые лежат почти на поверхности. Мы с вами просто не знаем, где их читать.
Проблема в том, что байт-код для проверки у гугла каждый раз новый и разный, а платный контент — уникальный и один на всех. После того, как виртуальная машина его расшифрует и он окажется в незашифрованном в виде в памяти, можно будет снять дамп и дальше его распространять.

Конечно, смотря о каком контенте идет речь и как этот контент используется. В том же DroidGuard даже значения переменных в памяти хранятся в зашифрованном виде. Но это не мешает с помощью дебагера перехватить их значения в тех местах где они используются.
Понятно, что абсолютной защиты не существует и при наличии достаточно большого бюджета и/или мотивации ломается всё. Но подобные методы защиты отпугнут недостаточно мотивированных копателей. Плюс встроенный head hunting ;)

Пример подобного приложения с платным контентом пробегал здесь позавчера, lamptest.ru. В его платной версии показываются дополнительные параметры лампочек. Если не защищать весь контент, который приходит с сервера, то нехорошим людям достаточно просто сделать бесплатный клон этого приложения типа lamptest.pro, который будет круче, и зарабатывать на рекламе и/или подписках.
Системных вызовов меньше 400 ;)

А если еще и параметры возможные подсчитать?

Google поглотил Impermium, команда перешла в Google
Вот Вы и описали трудоустройство в Google не через собеседования
Тут как повезет. Некоторое время назад Гугл выкупил небольшую компанию в Украине. Люди около года радовались, хотя и не вполне понимали что происходит: зарплату платили а задач не ставили. Через год всех уволили. В чем смысл? А смысл в том, что у компании была небольшая наработка, и Гугл выкупил права на эту наработку, а люди им и #*#*# не нужны были.
мы тоже радовались

а сейчас это ассоциируется с кадрами из каких-то кинохроник когда нацисты по первости вывозили евреев якобы в трудовые лагеря. хз почему
Закон Годвина
Круто, я не верил, но это случилось :) Буквально 200 с хвостиком сообщений хватило, чтобы упомянули нацистов.
При этом гении-олимпиадники внутри Google не могут родить ничего дельного (я на Google в обиде, имею право так считать).
Насколько я понимаю, тот же DroidGuard — проект компании Impermium. Google поглотил Impermium, команда перешла в Google, а в Android появилась толковая защита от фрода.
так он таки будет жить, остаётся только «выбирать качественную пищу для поглощения», а иначе это грозит несварением. Тут интереснее задуматься как это можно организовать чтобы заработать
smart and gets things done — вот насчет gets things done это хороший вопрос.

Умение проходить гугловские интервью говорит лишь об умении проходить гугловские интервью. Самые комфортные свои работы я находил вообще без дурацких интервью с олимпиадными задачками. Самое короткое интервью заняло три минуты с VP
Первое моё собеседование было для меня таким стрессом, что я подумал «Так не пойдёт!». Я решил прокачать этот скилл. Как разработчику Андроид приложений, мне постоянно пишут всякие рекрутеры, грех было этим не воспользоваться. Я решил отвечать на ВСЕ предложения. Итого, за три месяца, что я этим занимаюсь, у меня было около 20 телефонных интервью и пять очных. И я прям чувствую, что стал намного уверенней, расслабленней. Мне стало легче сосредоточиться на решении задачи. Бонусом прокачал английский и получил некое представление о хотелках разных работодателей.
Интересно, сколько из 25 собеседований Вы не прошли? Или все были успешными?
В основном, это были разговоры с рекрутерами. Я неплохо так завысил ожидаемую зарплату, поскольку всё устраивало и на нынешней работе. Поэтому основная масса отказов была из-за высокой зарплаты. А вот при общении уже с реальными работодателями я завалил два интервью (оба про алгоритмы сортировки) и успешно прошёл три. Одна фирма была стартапом и уже собиралась меня нанять, но тут январь, годовой отчёт инвестору и потеря финансирования. Другая фирма прислала мне готовый контракт с зарплатой на 10% меньше моих запросов и я отказался. Вот в пятницу опять телефон с потенциальным работодателем.
да суть не в том сколько ты пройдешь, а как быстро адаптируешься к стрессу. вот читаю здесь коменты и офигеваю… програмисты програмисты, а никак самой просто сути не поймут — чем больше таких интервью тем больше подкованней и уверенней становишься… это же не ракетная наука
не все вокруг экстраверты, для меня например огромный стресс ходить на собеседования, в полной мере я это испытал когда ушёл из сисадминства и 1С в обычный программинг… и если с 1С и сисадминством работа сама меня находила, в программинге пришлось искать самому… с ужасом представляю что через какоето количество лет придется ещё раз проходить через этот процесс…
так вот именно по этому и нужно практиковать то что боишся, ведь только так побороть страх можно и попроще к этому стрессу относится. Я тоже раньше боялся этого пздц как сильно, но после енного количества встреч и переговоров както ушел страшок и прочие мелочи, стал более сфокусированным на вопросах и ответах. Практика превыше всего и нечего боятся там. За то что пойдете поговорить никто не осудит вас кроме вас самих. По проще нада жить и относится к этому
За то что пойдете поговорить никто не осудит вас кроме вас самих

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

потому что например работаешь на разных работах, получаешь 100500 денег и весь такой уважаемый профи, а потом идешь на собеседование на +20% от твоей ЗП, а тебя начинают валить голой академической теорией как джуна… и в итоге выходишь оттуда… как будто у тебя и нет опыта за плечами и кучи успешных проектов… ты незнаешь основ… и собеседующие смотрят на тебя снисходительно… ну чё ты такой лох то… а потом обсуждают что «ходят черти кто на собеседования, найти нельзя нормальных людей»

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

не особо спасает даже понимание что я был на двух собеседованиях всего чтобы найти работу не имея коммерческого опыта в (обычном) программинге и вообще не просев даже по зарплате по сравнению с прошлой работой (одинесником, где у меня около 8 лет опыта)… т.е. не-безуспешно тыкался и разочаровался
ну сударь если так относится к этому то мне вас жаль — ведь получается что вам всего страшно и хрен его знает как вы тогда в жизни вообще… если вы боитесь что какойто чел который видит вас впервые будет чтото думать о вас и вам это важно то… ноу коментс тут. то есть получается вам даже важно что прохожие люди о вас думают… сидите дома а когда идете на работу смотрите тупо в пол и не подымайте глаз
если бы мне всё было реально так страшно что я тупо в пол на работе смотрю, то я бы никогда бы не добился своего положения нынешнего
Одно дело боятся, другое боятся и делать. я просто описал этот страх и что он реален и более серьёзен чем кажется. Это не помешало мне и иметь оффлайновый бизнес (7 лет и побегать потом с ним по прокуратуре отбиваясь от уголовки когда он развалился) и поработать в куче самых разных отраслей, от ремонта электрооборудования в вагонах до банковского процессинга (в разных отделах)… сейчас вот программинг, от написания успешного сервиса в одно лицо до просто бекенд-программист (вынужденный дауншифтинг в профессии но с повышением зп, для повышения квалификации)
Вы скорее всего экстраверт если не понимаете что это нельзя перебороть усилием мысли… да можно натренироваться, я когда работал с 1С получил навык общения с начальством что меня ни раз выручало… но всёравно подсознательно меня это очень всё угнетает
оно и будет угнетать. я просто говорю что не нада заострять внимание на этой части а переступать ее. я был в ваших ботинках, и меня тоже угнетало и угнетает любая такая процедурка… но таковы реалии и мы должны просто справлятся с ними. Учитывая ваш опыт вы уже просто ассом должны стать в этом моменте.
Хах… я чую прям сглазил, сегодня стартап где я работал, двинул кони… пойду собеседования проходить :))
удачи! самое главное ничего не боятся, а вынести для себя чето новое из переговоров.
> меня это очень всё угнетает

А надо сместить фокус недовольства с «я такой несуразный» на «они такие гондоны» :)
М.б. поможет
Вот поэтому человек проходит собеседования, когда не собирается менять работу. Рекрутеры смотрят на соискателя снисходительно, как на джуна и думают, что он им не подходит. А соискатель уже прошёл собеседование и получил работу и смотрит на рекрутёров, как на официантов, пытающихся ему услужить. Психологически, позиции уравновешиваются и стороны на равных. После нескольких итераций такая позиция становится привычной социальной ролью. А теперь вспомните или представьте, как Вы будете проходить собеседование имея 8 лет реального опыта- спокойно, легко, расслабленно. Даже если не знаете чего-то, ответите что-то типа- за 8 лет мне это не понадобилось и в гугле меня пока не забранили. И вполне возможно, что такой ответ устроит работодателя. Так вот, пройдя 10-50-100 собеседований, вы сможете так ответить имея 2 недели опыта и возможно, работодателя это снова устроит.
  • Пожалуйста, не надо путать интроверсию и социальную тревогу. Одно не подразумевает другого (хотя часто встречаются вместе).
  • Практика как раз хорошо помогает от тревожности. Завалите вы одно собеседование, второе — и в какой-то момент придет осознание того, что ничего катастрофичного в этом нет. Зато каждое хорошее техническое собеседование — это отличный срез своих знаний: чем хорошо владеешь, а где плаваешь.
  • Каждое успешно пройденное собеседование даёт мощный плюс к самооценке. Прекрасное чувство.
  • Не забывайте — на другом конце стола зачастую сидит такой же человека, как и вы. И, возможно, он волнуется больше вашего.

Удачи!
Я когда-то неуютно чувствовал себя на собеседованиях, я тогда разослал резюме и з-пл указал на уровне 60-70% от рынка. За месяц — около 40 собеседований. Под конец я уже мог отвечать на вопросы автоматом, не дожидаясь пока интервьюер сформулирует свой вопрос целиком, в том числе и типовые задачки на сообразительность. В принципе ничего нового никто не спрашивал, на 99% все стандартно. А поскольку мне на тот момент уже работа была не нужна, то я и не волновался особо.
Сейчас, если мне нужна работа, то я в первую неделю собеседуюсь в неинтересные мне конторы. Для поднятия тонуса. После этого уже на автомате проскакиваешь.
Я конечно в курсе, что отнимать чужое время не совсем красиво (сколько стоит час программиста итд), но тут дело такое. Либо я в хорошем тонусе попадаю на хорошее место, либо это место занимает кто-то другой.
Врят ли они просили реализовать именно base64, по сути они просили реализвать перевод из одной системы счисления (256) в другую (64 — автор сам выбрал) на выходе и получится base64 в поправкой на алфавит и некоторые тонкости. Эта задача изучается в одном семесте/четверти с «Привет, мир!».
Кажется, перевод в base64 намного проще, чем в систему с произвольным основанием.

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

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

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

Всё-таки base64 — это перевод 3 байтов в 4 c помощью битовых манипуляций, а дальше обработка массива в цикле, а не превращение данных в длинное целое и попытка потом реализовать эффективно операции деления.
Програмирование и есть математика.
И кстати, ваша формулировка «c помощью битовых манипуляций» (и картинка с битами в голове) мешает вам же искать другие решения, почему не использовать таблицу? Надо всего то 64Mb памяти, это может внезапно оказаться быстрее плохой реализации с битами.
Потому что: для преобразования одного блока из 3 байт нужна будет только одна операция хоть и дорогая по тактам (примерно mov eax, [tbl + esi]), а для «битовых манипуляций» операций будет на порядок больше, пусть и дешевых.
А как у такого подхода с доступом к памяти? 64 метра в кэш, как мне кажется, не войдут, и miss'ы постоянные будут.
Для общего случая да, будет в несколько раз хуже, но напрмиер если на входе в основном будут строчные латинские буквы/цифры/пробел/скобки (читай обычный текст) то нужные куски таблицы попадают в кеш и этот способ уже работает быстрее битовых операций.
Даже скучный «обычный текст» вряд ли уместится в L1. Вот если вы регулярно кодируете пустые файлы — там уже можеть быть выигрыш. Но даже и в этом случае он нифига не гарантирован: L1 выдаёт данные через 3-4 такта, за это время десяток простых операций можно исполнить…
PoC pastebin.com/MwHy4cF1
на чем было под рукой, размер исходных данных только кратный трем, в примере 30Mb

Random source data: []byte{0x52, 0xfd, 0xfc, 0x7, 0x21, 0x82, 0x65, 0x4f, 0x16, 0x3f}...
Run bitwise 0.053900 s
Base64: Uv38ByGCZU8WP18PmmIdcpVmx00QA3xNe7sEB9Hi...
Run tabular 0.128237 s
Base64: Uv38ByGCZU8WP18PmmIdcpVmx00QA3xNe7sEB9Hi...

Text source data: :d9d fxqpe 0bq9}{mbx3kdadbqf8 ...
Run bitwise 0.042929 s
Base64: OmQ5ZCBmeHFwZSAwYnE5fXttYngza2RhZGJxZjgg...
Run tabular 0.024196 s
Base64: OmQ5ZCBmeHFwZSAwYnE5fXttYngza2RhZGJxZjgg...


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

$ ./a
Prepare table

Random source data: []byte{0x52, 0xfd, 0xfc, 0x7, 0x21, 0x82, 0x65, 0x4f, 0x16, 0x3f}...
Run bitwise 0.040010 s
Base64: Uv38ByGCZU8WP18PmmIdcpVmx00QA3xNe7sEB9Hi...
Run tabular 0.118122 s
Base64: Uv38ByGCZU8WP18PmmIdcpVmx00QA3xNe7sEB9Hi...

Text source data: :d9d fxqpe 0bq9}{mbx3kdadbqf8 ...
Run bitwise 0.033740 s
Base64: OmQ5ZCBmeHFwZSAwYnE5fXttYngza2RhZGJxZjgg...
Run tabular 0.037435 s
Base64: OmQ5ZCBmeHFwZSAwYnE5fXttYngza2RhZGJxZjgg...


А если добавить в алфавит еще и большие буквы, то сразу становится стабильно не пыщпыщ:
Text source data: Ds1OwN"G}nUKsDeVtsZjbd"mqv:YlA...
Run bitwise 0.034508 s
Base64: RHMxT3dOIkd9blVLc0RlVnRzWmpiZCJtcXY6WWxB...
Run tabular 0.052095 s
Base64: RHMxT3dOIkd9blVLc0RlVnRzWmpiZCJtcXY6WWxB...
Антон, можно на ты, почти вместе учились. При добавлении больших букв, все опять же зависит от входных данных, в этом тесте буквы выбираются ПСП с нормальным распределением, в реальном тексте распределение будет совсем другим как и результат по времени. Ниже описал что для таблиц результат зависит от производительности памяти а для бит от производителности процессора. Итого для таблицы производительность завит от входных данных и памяти а для битовых операций только от скорости считалки, ну а тест показывает что возможны условия когда таблица быстрее.
Да, в общем случае для данных с мощьностью алфавита 256 с нормальным распределением бинарный способ будет быстрее.
Судя по всему, вопрос в объёме L2/L3 кеша.
Используя валявшийся под руками 32гиговый текстовый файл (proto2 дамп) табличный побеждает стабильно, неважно го или плюсы (на плюсах разве что вдвое быстрее чем на го).

==== GO:
Run bitwise 0.047352 s
Run tabular 0.022693 s
=== C++O0:
Run bitwise 0.0737085s
Run tabular 0.0408408s
=== C++O3:
Run bitwise 0.0233191s
Run tabular 0.0193432s


интересно; дома попробую потыкать палочкой на личных ноутах, у них процы несколько постарше, будет интересно посмотреть где точка невозврата
PoC pastebin.com/MwHy4cF1
на чем было под рукой
Это не PoC, а PoLoK (Proof of Lack of Knowledge). Вы бы ещё Python взяли и начали там что-то мерять.

Да, разумеется, если взять язык, в котором битовые операции медленные, а обращение к памяти — быстрое, то можно ещё и не таких вещей наизобретать. Но мы вроде говорили не об этом?

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

Результат у меня такой:

$ g++ test.cc -O2 -o test
$ ./test
Prepare table
Text source data:f axhtg6xr1grgiwotdn0kuvufyo36
Run bitwise 
3.2983s 
Base64: ZiBheGh0ZzZ4cjFncmdpd290ZG4wa3V2dWZ5bzM2
Run tabular 
7.24175s
Base64: ZiBheGh0ZzZ4cjFncmdpd290ZG4wa3V2dWZ5bzM2
$ grep model /proc/cpuinfo | sort -u
model		: 63
model name	: Intel(R) Xeon(R) CPU E5-2690 v3 @ 2.60GHz

Никаким ускорением даже и не пахнет. Даже на текстовых данных. Причём я даже глянул на godbolt — нет, никакой векторизации нету, всё честно: сдвиги и битовые манипуляции.
1. Если говорить про компилируемые языки, то скорось битовых операций и обращений к памяти едвали можно считать различными, конечно будут нюансы зависящие от реализации компилатора но в целом разницы нет.
2. Пока что примеры были на компилируемых языках, возьмите интерпретируемые, вы будете уверены что там биты будут быстрее?
3. Запустил ваш же пример на процессоре с чуть меньшей частотой
$ ./test
Prepare table
Text source data:f axhtg6xr1grgiwotdn0kuvufyo36
Run bitwise
4.12588s
Base64: ZiBheGh0ZzZ4cjFncmdpd290ZG4wa3V2dWZ5bzM2
Run tabular
4.69363s
Base64: ZiBheGh0ZzZ4cjFncmdpd290ZG4wa3V2dWZ5bzM2

$ grep model /proc/cpuinfo | sort -u
model : 79
model name : Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GHz

Разница уже не 120% а всего 14%, подозреваю что с той же памятью но меньшей частотой CPU результат будет ещё интереснее. Потому что с битами мы упираемся в частоту, а с таблицей в память.
4. Посмотрел godbolt, убедился что при O2
*((uint32_t*)&result[j]) = *((uint32_t*)&tbl[block]);

лучше
std::memcpy(&result[j], &tbl[block], sizeof(uint32_t));

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

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

учитывая, что нельзя просто прочитать как дворд и использовать в лоб (точнее можно — в табличном методе, еще немного ускорить можно за счет этого).
Исходные данные будут кучно и подряд, а таблица — в другом месте и вразнобой, т.е. с промахом на каждом обращении.
а вот тут и возникает вопрос в объёме и количестве независимых кешлиний. пока эксперименты показывают что на Intel® Xeon® W-2135 CPU все нужные полосы влезают в кеш и весьма и весьма успешно работают…
Не возникает. Вы забываете о том, что кроме вычисления base64 программа (если это не бенчмарк) занимается чем-то ещё.

Мне это напоминает историю с каким-то чуваком, который когда-то давно в LKML появился и начал объяснять, что ядро плохо написано и вообще его разработчики идиоты. Его попросили показать «мастер-класс» — и он «ускорил» (примерно похожим образом) вычисление TCP/IP чексуммы. Раза в четыре, если не ошибаюсь.

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

Таблички с предвычисленными значениями были актуальны в 70е-80е годы, когда память была быстрой, а процессоры медленными… Но в те времена 64MiB стоили таких денег, что никому и в голову бы не пришло их на base64 отдать.
Имелось ввиду что скорость битовых операции в разных компилируемых языках мало отличимы по скорости. И отдельно операции с памятью в разынх компилируемых языках мало отличимы по скорости. А не то что битовые не отличимы от памяти. Это все было к тому что:
Да, разумеется, если взять язык, в котором битовые операции медленные, а обращение к памяти — быстрое, то можно ещё и не таких вещей наизобретать.

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

Тут фишка в том, что в спецификации Go написано:
There is no upper limit on the shift count. Shifts behave as if the left operand is shifted n times by 1 for a shift count of n.

А в спецификации C++:
The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.

Что это обозначает? Что в Go вы вынуждены кодировать shift тремя-четырьмя операциями CPU, а в C++ — достаточно одной.

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

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

И всё бы ничего, но вот только готовность выделить пресловутые 64GiB — указывает на то, что эта задача для вас ну просто очень-очень важно… так с какого перепугу вы используете язык, который заметно отстаёт от оптимума?

без разницы на каком языке писать такой тест, пропорции будут примерно одинаковые, а абсолютные значения будут отличаться в зависимости от компилятора.
Тогда почему в вашей программе таблица выигрывает иногда, а моей — всегда проигрывает, хотя иногда с разгромным счётом, а иногда — немного? Но проигрывает всегда…
Разница уже не 120% а всего 14%, подозреваю что с той же памятью но меньшей частотой CPU результат будет ещё интереснее. Потому что с битами мы упираемся в частоту, а с таблицей в память.
Нет — и это мы уже выясняли. Вы же сами чётко чуть выше пишите: нужные куски таблицы попадают в кеш и этот способ уже работает быстрее битовых операций. Если бы ваш код упёрся в память — то там уже ни о каком выигрыше и речи бы не шло.

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

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

Так вам над этим 64-метровым числом надо повторять операцию деления на 64 до тех пор, пока в частном не получится 0, т.е. 87 миллионов раз. Операция деления таких длинных чисел занимает большое время, вам нужно вручную пройтись по всем разрядам (пусть даже вы будете обрабатывать по 64 бита за раз), аккуратно делая переносы остатка с разряда на следующий разряд. Навскидку, сложность предложенного вами решения получается O(n^3). Битовый же энкодер base64 даёт O(n), причем без тяжеловесной для CPU операции деления.

Не туда ответил

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

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

Однако если его чуть-чуть модифицировать и использовать три таблички по паре килобайт — то есть уже шанс вписаться в L1 кеш, однако, во-первых, не факт, что пользователям вашей процедуры так уж понравится, что вы существуенную долю кеша заняли, а во вторых — тут уже всё равно будут нужны дополнительные манипуляции и не факт, что будет выигрыш.
Даже без модификаций, на огрниченном алфавите (например текст на одном языке) может давать выигрыш. Выше выложил proof of concept.
Google не единственная компания на планете, хотя для разработчиков под Android быть частью такой компании это идеальный пункт в резюме. С другой стороны, это даже хорошо, что у этой компании столь замороченный и сложный процесс собеседования, мало связанный с реальной повседневной работой. Это означает, что у конкурентов Google как минимум есть хорошие шансы найти себе в команду качественных разработчиков вроде Вас, кто умеет видеть задачу и способны в ней детально разбираться. Ну и в компаниях поменьше Google можно быстрее вырасти и добиться своих целей (меньше ступеней в иерархии должностей с мЕньшими ограничениями по переходу выше).

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

Хотя точно могу сказать, что мне подготовка пошла все-таки в плюс. Теперь каждый раз когда пишу код, автоматом думаю о сложности O(n). Раньше такие вопросы приходили в голову только если что-то медленно работало и это дело надо оптимизировать.
Тренировки мозга и навыков по алгоритмам это всегда полезно. Ну и важно помнить о балансе в вопросах оптимизации. Идеальный код это хорошо, но в нынешнем мире капитализма он не самоцель, иначе это необязательная потеря времени, ресурсов и конкурентоспособности.
По-моему, как раз уже пора делать ставку на близкий к идеалу код. И я сейчас говорю не столько про оптимизацию, сколько про размер готового продукта и баги в нём. Хотя эти 3 вещи сильно коррелируют, так что все 3 важны.
В моем опыте за десяток лет пока только один случай, когда ставка именно на серьезный рефакторинг кода и его качественное улучшение существенно сыграла по деньгам.

Своеобразный случай, потому как продукт готовили на продажу уже как небольшой по доходу и работающий бизнес. Сначала проект пытались продать AS IS, с проблемами не только в коде, но и в документации API, серьезными проблемами в момент пиковых нагрузок от клиентов и прочими прелестями. Продажа не состоялась, цену продукта примерно ожидали в $180..200k (копейки).

После окончательной потери надежды продать или привлечь доп средства на развитие, владелец этого бизнеса чуть позже случайно познакомился с командой, которая занималась консультированием и private TPA (частный техаудит проектов), ребята предложили помочь оценить самые дорогие проблемы в проекте и потратить полгода на его доведение до стабильно работающего состояния за 20% от конечной стоимости повторной продажи. Команда у них также была своя (4-5 человек примерно) + несколько временно привлекаемых консультантов по AWS и лоеры для аудита схем монетизации. За несколько месяцев было все донастроено по инфраструктуре, далее переписаны криво реализованные сервисы, протестировали уже дополненные тесты, дописали доки.

Была возможность слегка поучаствовать в этом и наблюдать со стороны. Сравнивая визуально репу старого проекта и репы нового, кода стало раз в 10 меньше, сервисов (API endpoints) тоже поубавилось, тестов различных появилось много (нагрузочные), внедрена автодокументация на javaDoc, поправлена старая. Короче технически проект был причесан и вылизан очень грамотно.

После всего, через год в сумме (из-за ожидания каких-то конкретных эвентов, типа бизнесс-выставок и встреч) у проекта появилось несколько покупателей, им был передан отчет по аудиту и проделанной работе, также переделанные основные доки по проекту и в конечном итоге после аукциона его продали за $1.8m (сильно больше ожидаемого). Проект по тематике довольно нишевый, связанный с оптимизацией логистики, страхования, хранения и перевозки грузов. Далее через год этот проект уже выкупила одна из продуктовых сетей (кажется Kroger) за $4m. Да, за прошедший год у проекта появилась другая команда.

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

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

Так что первые версии продуктов, вернее где-то первый год существования бизнеса в рынке — сервисы/продукты, увы, всегда будут жрущими ресурсы и тормозящими, но выполняющими те бизнес-процессы, которые приносят доход и действительно нужны. И только они сначала улучшаются, после идут уже всякие улучшения в UI use-cases, разбор и оценка качества пользования сервисом, размеры бинарников, network traffic shaping и прочее. Поэтому либо так, либо на рынке будет существенно меньше выбора. Если он будет вообще.

Знание Base64 сразу выделяет людей, которые интересуются simd :) ибо это по сути одна из тренажерных задачек.

Но… Но если подумать? Base64 — это упихивание бинарных данных в печатные символы.
64 намекает что мы используем 64 символа, 6 бит. НОК(6, 8) = 24. То есть каждые 3 байта можно нарубить на ровные 4 символа.

Это как перевести в 64-ричную систему исчисления указанное число.

itoa же можете реализовать? ну вот ровно так же, только не по основанию 10, а по основанию 64…
Сотрудник одной компании рассказывал про собеседование вчерашней студентки. Не вдаваясь в подробности, компания в основном использует C#, из натива — максимум C++, при этом у девушки по нисходящей начали спрашивать про C, Asm и «завалили» её только на вопросах о физической реализации ЭВМ.
Компания выглядит адекватной, и я сомневаюсь, что девушка из-за незнания принципа работы транзисторов не попала на работу, однако, думаю, она испытала немалый стресс. (Я бы испугался, если бы почувствовал, что человек специально ищет тему, на которой можно меня завалить)
Я не думаю, что вы далеки от уровня специалистов в гугл, скорей просто такой типаж людей. Я вот тоже на собеседованиях — это только 10% от меня в нормальном состоянии, а есть люди, которые в стрессовой ситуации при общении наоборот показывают 150% от себя в нормальном состоянии.
Поэтому идет селекция по определенному типажу психики.
А кто зафейлил тока непонятно. Собеседование это функция которая принимает людей и дает тру фолс, если она на тех может решать рабочие продуктовые задачи дает фолс значит фейлит она, в данном случае гугл.

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

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

Когда-то Макса Хоувел (разработчика Homebrew) не взяли в Google. Он по этому поводу такой твит выдал:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

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

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

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

Что касается — только кажется и Микрософт. Загубить можно все. Не принимать в расчет очевидность параметров готового решения оправдывая это некомпетентностью процесса интеграции, не самый верный путь.
Инфраструктуру вместо работы...? не понимаю… Возможно я какой-то неправильный, но я не разделаю развитие одного от другого. Это обоюдно необходимые вещи.

Если у вас сотни продуктов, писать тулинг под каждый из них выходит слишком накладно. Мы ведь здесь говорим конкретно о Гугле — вот конкретно в Гугле инфраструктура общая для всех. Запустить примитивный сервис во множестве регионов на инфраструктуре Гугла у вас займет меньше часа. Ваша задача — делать сервис, а не решать проблемы деплоймента во множество датацентров, чекина кода в репозиторий только после прохождения каких-то тестов и получения апрувалов от ревьюеров, лоудбалансинга и прочих вещей. Вы все это получите бесплатно. Делать это все на уровне каждого продукта — просто неэффективно. Поэтому инфраструктура и продукты разделены. Но опять же — хотите работать над инфраструктурой — пожалуйста. Хотите работать над продуктами — милости просим. Хочется поделать одно, потом другое — можно менять команды, ну или тратить 20% своего времени на любые другие задачи помимо вашей основной работы (это сейчас реже практикуется, но все еще существует).

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

Почему вы считаете работу над продуктом «желанием быть кодером» — тоже не очень ясно. Работа над продуктом включает множество составляющих. И сбор требований, и дизайн, и согласование разных моментов с партнерами (upstream callers, downstream service providers), и планирование, и релиз — далеко не только кодинг.

Пожалуй я закончу. Я вам про одно, вы мне про другое.

единый тулинг для мониторинга, пуша в прод и прочее.

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

обычно да, два )) одно депрекэйтед, другое допиливается. но суть в том, что каждой команде не надо изобретать свой велосипед. ну и есть исключения. скажем, замены боргу не предвидится, код-ревью и билд — тоже в единственном экземпляре.
Я был бы очень зол если мне на ТЕЛЕФОННОМ интервью дали бы такой вопрос…
Побуду кэпом: нужно было при подготовке к собеседованию учесть специфику конкретного отдела, в данном случае DroidGuard. Видимо они там занимаются более низкоуровневой разработкой, поэтому и такой вопрос.
Я вот об этом не подумал, поэтому такого вопроса не ожидал :) А вообще вопрос очень логичный в контексте проекта DroidGuard. Битовые операции, все дела.
Кстати я пробовал задавать вопросы, подразумевающие битовые операции. Быстро перестал и ушел на более простую алгоритмику — графы, динамика.
Как мне кажется, довольно специфический навык.

Но учитывая, что резюме пришло через реверс, вполне вероятно тоже бы задал что-нибудь более низкоуровневое… Правда, не знаю как бы прошло. Есть интерес сыграть в ролевую игру тренировочного интервью? :D

Ставка: по приколу, так что нервов и напряга должно быть меньше
Мне по телефону предложили обяснять как бы я запрограмировал алгоритм решения игры пятнашки. Только позже я узнал что по алгоритмам игры написаны более десятка книг.
А если не секрет, вы тогда к какому выводу самостоятельно пришли? Я пытался сам додуматься минувшей зимой и меня хватило лишь на A-Star, которую я в последствии попытался заменить на IDA-star (не смог с двух попыток в реализацию и отложил всё в ящик).
Именно поэтому вам предложили описать, а не написать.

Это хорошая задачка на «поговорить». В пятнашках 20 триллионов вариантов, так что имея кластер её можно решить полностью.

А можно два поиска в ширину «навстречу друг другу» отправить. А можно тот, который «с конца» заранее рассчитать.

Там есть о чём поговорить! Именно этим задача и интересна: готового единственного «правильного» ответа нету и можно смотреть в какие области более склонен идти кандидат.

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

datacompboy что скажете?(я видел ваш пост про интервью, но все же)
Ну и про саму статью. Очень интересно услышать ваш комментарий.
А что тут скажешь? Я уже писал всё что знаю по интервью :) Да, проходят не все.
Я проходил по приколу без ожиданий — подозреваю, это помогло =)
Да и фиг с ним, с гуглом! Зато получили незабываемый опыт и наверняка ещё здесь напишут вам. Удачи!
Спасибо!
НЛО прилетело и опубликовало эту надпись здесь
В двух словах — для проверки настоящий у вас телефон или это эмулятор.
НЛО прилетело и опубликовало эту надпись здесь
Это больше как гонка в стиле оружие-броня. Что бы спамеры тупо задолбались подстраиваться под такие изменения.
Спасибо за статью!
Мне понравился ваш подход — хотел пройти собеседование, готовился, но не вышло. Так редко пишут, чаще бывает — «да не очень-то и хотелось, и вообще после отказа я понял, какие они дураки там».

А когда через год вам перезвонят и снова пригласят пройти собеседования — вы согласитесь?
Честно говоря, я после отказа наоборот понял, что в таком интервью куда больше смысла, чем в стандартных вопросах про Android SDK и про всякий синтаксический сахар Kotlin. Мне хоть и обидно, но их подход вполне оправдан. Завтра выйдет новый фреймворк, а фундаментальные знания не устареют.

Я пока пару лет делал игры на Unity, так в Android успела революция произойти: вместо Java пришел Kotlin, RxJava стал золотым стандартом, Android SDK распался на Android Jetpack Components… Ничего, все можно довольно быстро освоить. Даже сертификат получил красивый от Google.

Насчет перезвонят я так скажу. Собеседование я проходил чуть больше года назад :) Не перезвонили. Но я им сам недавно повторно написал. Если посмотреть правде в глаза, они мне нужнее, чем я им: Google в резюме — он такой один, а из таких как я у них очередь стоит.
НЛО прилетело и опубликовало эту надпись здесь
Вакансии не заполняются потому, что нет необходимости их быстро закрыть. Соответственно из сотни кандидатов берут 2-3 (но тут стоит учесть не только то, что требования высокие, но и то, что из-за громкого имени все, кого выгнали за то, что они три строчки написать не могут в Гугл тоже собеседования).
отлично отомстил )
А почему «отомстил»? Я свое обещание (не болтать лишнего) в целом-то сдержал. Кода виртуальной машины нет, как работает интерпретатор не рассказал… А вся остальная информация и так была в интернете — про запрос, про protobuf, про apk и так далее. Разве что про спрятанные сообщения никто не писал.
ну после публикации на хабре про эту пасхалку, народ может ринуться проходить тем же путем и что и ты прошел и посылать им запросы на устройство в гугл. получается их идея с привлечением гениев способных найти пасхалку будет не состоятельной и им придется придумывать другую.
А смысл? :) Это же не дает ровным счетом ничего, никаких преимуществ. Если нет знакомых работающих в Google, можно просто попробовать в linkedin написать кому-нибудь и попросить отправить резюме эйчарам. Будет ровно такой же результат.
А меня вот прям бесят такие вопросы на собеседованиях не_для_джуниоров…
Они написали человеку сами, значит нашли его по шагам той истории, когда он ковырял их продукт, и поковырял неплохо так. Т.е. у человека есть опыт решения задач, где-то сложных где-то не очень. И тут вопрос про реализацию base64… Если заглядывать под капот каждой функции которую используешь — то так и будешь под этим капотом сидеть, а не задачи бизнеса решать!

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

И правильно сделал. Все это жадность, получить мидла за денежку джуна, или сеньора за денежку мидла (я не про ваши конкретные вопросы).
У меня как-то, лет 5 назад было собеседование на позицию мидла .net в наших топ 5 интеграторах, я туда пошел уже просто для опыта собеседований (год шлялся, еле нашел). Стандартный набор — интерфейс vs абстрактный класс, boxing / unboxing, напиши пузырьковую сортировку, async/await, using, бла-бла-бла и прочий шлак из собеседований, думаю, чета они про шаблоны проектирования забыли, ан нет, напишите реализацию синглтона. Ок, пишу. И тут прорвало — напишите на бумажке еще 5 реализаций синглтона, назовите и опишите все паттерны из книги Desing patterns, бинарные деревья, какие-то реализации низкоуровневых блокировок, алгоритмы аппроксимации пиков, и все дальше и глубже.
Я не выдерживаю и спрашиваю — что, неужели они у них мидлы такие, все это знают?
В ответ, гордо — У нас все мидлы уровня сеньеров!
Я, офигевая — Что? А получают они как мидлы?
Не задумываясь, и еще гордее — Да!
Ясно-понятно, до свиданья.
А я лучше бы на бумажке реализовывал алгоритмы.

Я как раз таки хорошо умею делать велосипеды и быстро разбираюсь в новых либах.
Но как то решил попробовать с С++ пересесть на С#. С ним я и до этого работал, но в основном с .Net core.
Тут предложили на одну фирму поработать. В итоге им все эти фундаментальные знания, знания алгоритмов и прочее — нафиг не нужно. Им нужно на зубок знать весь .Net винды.
ASP .Net, Entity Framework, MVVM, MFP, MVC и т.д.
А когда я говорил, что писал асинхронные сервера на .net core на сокетах, писал врапперы во круг собственных сишных либ — они смотрели как на иродиевого.

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

Вы бы друг друга просто не поняли. Причём в обе стороны: вы бы пытались строить велосипеды там, где есть готовые функции, а ваши коллеги городили бы страшные многотонные конструкции, тем, где можно обойтись велосипедиком на 100 строк.

Эти два рода деятельности сегодня настолько разошлись, что вот то, что им было нужно — получило отдельное название: application engineer. И да, такие Гуглу тоже нужны — но это отдельная вакансия!
предложили на бумажке реализовать алгоритм поиска простых чисел и бинарную сортировку

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

Задача на интервью — понять способен ли человек мыслить, или он «конечный автомат» ;).
Вот, я, например, могу пользоваться топором. Знаю, как сделать топорище, даже видел сам процесс его изготовления из берёзового полена. Видел по телевизору, как работают кузнецы, как резать и формировать металл вокруг наковальни. Смогу нажечь угля из дров или набрать каменного угля, я знаю, как он выглядит. Смогу сделать кирпичи, чтобы сложить небольшую доменную печь. Но вот загвоздка, я не знаю, как выглядит железная руда. Реально не знаю, может когда и видел, но не догадывался что это именно она.

Так кто вам больше нужен: лесорубы, которые делают конечный продукт, или кузнецы, шахтёры, металлурги, геологи? Если мне надо посмотреть на реализацию Base64, то я быстро найду Base64.java в том же Android. Но не каждый Senior, а тем более Middle знает, что бывают другие, более эффективные кодировки типа Base85, или более простые типа Hex. А уж вопрос какую где лучше применять сможет поставить в тупик даже интервьюера ;)

Чтобы проверить, что человек умеет мыслить, то ему надо дать задание по конкретной теме, например, тестировщикам я предлагал придумать 10 способов разбить стакан, стоящий на соседнем столе, а все без исключения разработчики делали тестовое задание очень близкое к тому, чем они потом будут заниматься. Сразу было видно, знает ли человек нужный нам язык или фреймворк.
То задание проверяло не «заучил ли кандидат наизусть реализацию base64», а как раз наоборот — «как кандидат подойдёт к решению незнакомой задачи».
НЛО прилетело и опубликовало эту надпись здесь
Прекрасный, великолепный, достойный ответ для application enginer'а — но тогда уж, если вы ничего сами писать не хотите, вы должны знать готовые библиотеки, которые это умеют.

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

Такие знания статичны. Если всегда механически применять полученные когда-то знания, то в результате получится: «знаю один фреймворк (библиотеку) и сую его (ее) во все проекты».
Почему же статичны? Библиотеки меняются, подходы меняются, «наука на месте не стоит». Application Engineer'ы — они тоже разных уровней бывают.

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

P.S. И да, очень часто их путают. И ставят Software Engineer'ов на задачу «натягивания скина на Drupal» или, наоборот, Application Engineer'а на задачу «придумавания нового алгоритма для обработки данных на графе». Последнее, впрочем, реже: так как зарплата у Software Engineer'а обычно выше, то чаще Application Engineer'ы пытаются устроиться на эту позицию, а не наоборот.
НЛО прилетело и опубликовало эту надпись здесь

Интересный пример, но не релевантный. Речь идет о том, а умеете ли вы пользоваться топором, или только бензопилой? И более того, а способны ли вы заправить бензопилу когда в ней кончится бензин? Знаете ли вы что кроме бензина, туда еще и масло надо заливать? :).
Это если мне дровосеки нужны.
Ну и я не говорю еще о том, что сейчас часто встречаются люди не знающие что «руда» из вашего примера в принципе существует...


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

Обычно в разговоре на собеседовании сразу становится понятно, надо ли давать человеку тестовое задание, которое лишь повторяет какой-то уже реализованный кусок реального проекта, но мы не рассказываем ему, откуда такая задача взялась.
А человеки с умными словами обычно отсеиваются ещё на стадии чтения этих слов в их резюме. Типа «сетевые протоколы: HTTP, JSON, XML» ;)
И ещё очень полезно посмотреть, на какие паблики они подписаны.

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

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

PS. могу купить, разобрать и собрать бензопилу
PSS. могу точить цепи от бензопил ;)
а способны ли вы заправить бензопилу когда в ней кончится бензин? Знаете ли вы что кроме бензина, туда еще и масло надо заливать?
Нет, никогда не держал в руках бензопилу, никогда масло ей не менял, бензин не заливал.
Но я понимаю, зачем она нужна, как работает, где она применима, а где нет. И если вдруг, мне нужно будет ей вдруг(!) воспользоваться, я достану инструкцию, распилю несколько досок (возможно и кривовато), но выполню свою работу.
Да, я не задрот бензопилы, и опоры будут кривоваты, но зато работа будет выполнена. Если построенный дом окажется востребованным клиентами, то можно будет кривые доски и перезапилить ровнее. А если дом окажется ненужным(нет клиентов), то и не жалко было потраченного времени. MVP во всей красе. Вам шашечки(мастер бензопил), или ехать(человек, умеющий быстро осваиваться)?
Конечно же, если бы я работал на пилораме, то мне просто необходимо было бы владеть бензопилой. Но чаще всего, кроме бензопилы, нужно знать про 100500 инструментов, какие они бывают, и какой лучше где применить. Архитекторы зданий например, не все держали в руках инструменты, а кто держал — наверняка не все инструменты на свете. Но это не мешает им строить дома, и делать свою часть работы.

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

показывают способность помнить — если учился хорошо
Знаю много противоположных примеров, кто учился плохо, ничего с универа не помнит, но понимает, что нужно заказчику, выдаёт готовые продукты в короткие сроки, и именно так как просил заказчик. Поэтому у меня обратное мнение — тот, кто помнит отлично универ — либо гений, либо у него синдром отличника.
И если вдруг, мне нужно будет ей вдруг(!) воспользоваться, я достану инструкцию, распилю несколько досок (возможно и кривовато), но выполню свою работу.
А как вы поймёте, что ей нужно воспользоваться? Вам начальник скажет? Так в Гугле нет начальников, дающих вам техзадание описывающих в деалях какими подходами пользоваться…

Знаю много противоположных примеров, кто учился плохо, ничего с универа не помнит, но понимает, что нужно заказчику, выдаёт готовые продукты в короткие сроки, и именно так как просил заказчик.
Но у Гугла ведь нет заказчика…
А как вы поймёте, что ей нужно воспользоваться?
Вот же писал:
Но я понимаю, зачем она нужна, как работает, где она применима, а где нет.

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

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

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

ПС. Вас бы я на работу не взял :). Принцип «Good enough» у нас категорически не приветствуется.
— Наливаем в стакан кипящее масло из фритюрницы.
— Запускаем в комнату ребёнка, отбираем мобилку, запрещаем разбивать стакан.
— Достаём из кармана гранату. Бросаем её в стакан.
— Играем стаканом в футбол.
— Накрываем стол до конца. Играем свадьбу.
— Приглашаем жену и любовницу. Привязываем к поясам гантельки на верёвочках. Устраиваем весёлый свадебный конкурс – кто первым попадёт гантельной в стакан.
— Наливаем в стакан метиловой незамерзайки. Не разбился? Ну вот мы и прошли один из тестов, который стакан выдержал.
— Находим подходящий подшипник. Натягиваем в тугую на стакан. Кидаем их в жидкий азот.
— Берём перфоратор и высверливаем дырками имя любимой девушки.
— А теперь то же самое – только лазером. И помощнее.
— Загоняем в вибратор. Прогоняем по всем частотам.
— Используем в качестве изолятора. Хватит 40 киловольт.
— Кидаем стакан в бардачок теслы. Запускаем теслу в космос. Ждём.
— Просто ждём. Если ждать достаточно долго…
— Подходя с чисто философской точки зрения, стакан уже разбит.
— Хотя если по-настоящему абстрагироваться, то стакан не только уже разбит, но и ещё разбит.
— Нельзя наполовину разбить стакан. Или можно?
— Бросаем в стакан чёрную дыру.
— Запускаем в комнату трёх тестировщиков, трёх котов, трёх псов с привязанными к хвостам консервными банками, Киркорова и агил. Выключаем свет.
— Подгоняем танк.
— Осторожно, аккуратно, деликатно, выбрасываем стол в окно.
— Поджигаем стол.
— Ставим стакан в сейф Шредингера.
— Расплавляем стакан, отливаем из него стеклянный хер. Выдаём дураку под расписку его и пару защитных перчаток.
— Отпиливаем у стола все ножки. Тем самым защищаем объект от разбивания в состоянии «стояния на этом столе».
— Стучим по стакану карандашом, по звуку проверяем, а не разбит ли он уже.
— Спорим в пьяной компании, что стакан можно засунуть в … да что там… тут все программисты..., в сраку. При попытке извлечения стакан разбивается. Реальный случай. Я лежал в одной палате с человеком, который пострадал, поводя эксперимент. У него были сломаны нос, нога и челюсть. Так что соблюдайте технику безопасности, если соберётесь повторить.
— Становимся Президентом России. Жмём большую красную кнопку.
— Если не помог предыдущий пункт — отсылаем Креосану.
— Просто засовываем в посылку и посылаем почтой России.
— Засовываем в посылку, платим за объявленную ценность в 100 000р и посылаем почтой.
— Берём стакан на митинг по защите… ну вы меня поняли.
— Обеспечиваем в комнату свободный доступ. Каждую ночь наливаем в стакан 100 грамм водки. Повторяем до ожидаемого эффекта.
— Привязываем к ножке стола ноги секретарши будущего босса. Начинаем кидать в неё замороженные какахи. Или лучше незамороженные. Для чистоты эксперимента.
— Прибиваем стакан гвоздём к столу.
— Забиваем стаканом гвоздь в стол.
— Забиваем столом стакан в гвоздь.
— А у вас ещё есть стаканы? А то меня ещё столько вариантов осталось!
— Отдаём задание на аутсорс.
— Объявляем конкурс на поставку 10 битых стаканов.
— Делаем из стакана секундный маятник. Чтобы… да неважно, что, процесс изготовления так выбесит…
— Подгоняем 1000т пресс. Сбрасываем пресс на стакан.
— Берём две ровные сухие сосновые дощечки. Ставим между ними стакан. Сверху аккуратно ставим слона. Сбрасываем на них пресс.
— Вбиваем в стакан черенок лопаты. Доливаем пива по вкусу.
— Предлагаем просто взять, просто взять и сломать мой богатырский меч о стакан. Если возьмут на работу.
— Устраиваем в комнате просмотр инсталляции. Внезапно объявляем приз в 1000р за лучший перфоманс.
— Закладываем на вертолёте крутой вираж. Стакан соскальзывает со стола. Если не разбивается, делаем мёртвую петлю.
— Наполняем комнату водой. Одеваем акваланг. Ныряем. Обматываем стакан тухлым мясом. Выныриваем. Заныриваем в комнату акулу.
Гениально!
И ведь некоторые из собеседуемых не могли придумать и пяти способов.
Передал тестировщикам, боюсь теперь они до конца дня будут хихикать ;)
С другой стороны, всё это многообразие можно и нужно редуцировать, отбрасывая неоптимальные эквиваленты. Как минимум, воздействовать можно на стакан, можно на среду (стол, здание, и пр.). Можно построить модель стакана и разбить модель. Воздействие может быть механическое (удар, давление, вибрация), акустическое как частный случай, термическое, электрическое, химическое, лучевое… административное… Философский подход хорош. Опять же, многое зависит от определения понятий «разбить», «стакан» и их совокупности. Короче, меньше повторяемости по существу, больше охват. Хотя, если баг возникает именно со слоном на берёзовых досках при использовании прессов с массой более 99999 тонн… Я не тестировщик. Я не знаю, насколько это типичная ситуация.
Знаете, по поводу неудачного (?) собеседования, пожалуй тут многое зависит от того, кто вас собеседует. Что-то мне подсказывает, что в гугл попадают люди и с куда меньше компетенцией, чем у вас.
А вообще после таких статей хочется забухать…
А вообще после таких статей хочется забухать…

Вы же понимаете, что желание «забухать» ненормально по определению, вне зависимости от надуманной причины?


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


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

В Гугле в Цюрихе хорошо платят — гугл+швейцария стоило того, чтобы попробовать. Другое дело, что слишком хорошо выступить на собеседовании тоже чревато.

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

Не хотите рассказать подробнее?

Нет. Как написал в комментах ниже — оклематься бы и нервы поправить, а то заклюют ведь — для многих Гугл это до сих пор сказочное место, куда набирают гениев, где задачи интересные, work-life balance идеален, а жизнь приятна и похожа на праздник.
Мои проблемы будут выглядеть нытьём зажравшегося «тракториста».
Про собеседование вы уже рассказали в комментарии habr.com/ru/post/419945/#comment_19016677 — за него огромное спасибо. А могли бы на организационные вопросы ответить?
1. Какие есть возможности релокации из Цюриха в штаты (L1/H1B), или не интересовались?
2. Про гугл много пишут что они предлагают средний total compensation, но с competitive offer могут сильно ее поднять. Так ли это?
1. Я ни в коем случае не хочу в штаты и противился бы всеми силами, если бы меня туда отправляли. В Швейцарии намного лучше ситуация как с жильём, так и с транспортной доступностью офиса.
2. Даже не задумывался. Когда мне выдали оффер, зарплату сразу предложили даже больше той, за которую я планировал торговаться.
В Швейцарии намного лучше ситуация как с жильём, так и с транспортной доступностью офиса.

кроме калифорнийского кампуса есть еще вашингтонский (сиэтл-керкленд). там и с жильем, и с доступностью офиса пока получше калифорнийского. его тоже можно рассматривать в качестве варианта.

Да, в Вашингтоне и погода получше.

1. можно переехать по L1 через год, и на H1B тоже тут же подадут (там уже зависит от удачи — получишь или нет). и гринкард файлят сразу.
2. сложно сказать. выше среднего наверное, но не прям заоблачно. и да, оферы от других компаний очень сильно помогают с поднятием.
Про гугл много пишут что они предлагают средний total compensation, но с competitive offer могут сильно ее поднять. Так ли это?
Да, это везде так, и гугл не исключение. Никто не будет вам сразу давать жирный офер (особенно если вы приходите не из FAANG) — надо немного поторговаться, и офер от другой компании лучшее для этого средство.
Выше — это L5 против L4?
Да нет, всего лишь L3-L4. Мне кажется, я тянул на «upper L3» — у меня было всё отлично с техническими навыками, но в области софт-скиллов и «бюрократии» — написании дизайн-доков, оценке приоритетов и планировании всё было так себе, потому что на предыдущем месте эти навыки пусть и требовались, но не так сильно. И импакт, конечно же, куда уж без импакта.
С командой и менеджером повезло — думаю, они довольно быстро смогли оценить мой реальный уровень, но решили, что я смогу подтянуться.
Об L5 я, пока, даже не задумываюсь — оклематься бы.
По-моему у вас классический impostor syndrome, как они это сами называют. Хороших технических навыков вполне достаточно должно быть на L4. Не дайте им себя запугать всеми этими формальными требованиями — это делается, чтобы вам было можно меньше платить :). Некоторые знакомые мне L5 совершенно не умеют писать дизайн-доки, оценивать приоритеты и планировать, но тем не менее стабильно получают meets expectations из года в год и не парятся.

То, что вас взяли на уровень выше, — это однозначно плюс, поскольку не надо лишний раз проходить через промо (вот там будет реальная нервотрепка). Еще, говорят, очень сложно уволить человека из гугла.
на пятом все же положено уметь и дизайн-доки писать, и приоритеты оценивать, и планировать. другое дело, что meets expectations внутри гугла хорошим рейтингом не считается. он как бы второй снизу (после needs improvement). хотя если особых амбиций нет, то можно в в принципе на meets expectations на пятом хоть всю жизнь провести.
Всё так. Я просто к тому, что на деле эти формальные требования сильно относительны, и уважаемый lanseg слишком сильно парится и себя недооценивает, на мой взгляд. Хотя, конечно, я не знаю деталей его конкретной ситуации.

Вот то же самое хотел написать, только постеснялся «диагноз по фотографии» ставить. Как можно понять в первые полгода из-за чего у тебя проблемы с планированием, от недостатка опыта или потому что любая простейшая задача требует длительных раскопок эзотерической инфраструктуры? Кроме того, если у lanseg нет конкретного инсайда от интервьюеров или комитета (надеюсь, что нет), то я очень сомневаюсь, что результаты интервью повиляли на hiring level.

бывают случаи, где интервьюеров просят дать рекомендацию в том числе и по уровню, и в таких случаях результаты интервью влияют на уровень.
Планирую активно начать подаваться в FAANG, было бы интересно узнать про ваш опыт. Как я понимаю, уровень определяется больше не на algorithms (leetcode-задачки), а на system design? Или ошибаюсь?

Что такое FAANG?

То что в западных комьюнити (cscareer на reddit, blind) считают топ-компаниями для работы в плане зарплаты и/или market cap. На данный момент Facebook Apple Amazon Netflix Google + в список можно добавить Dropbox, Uber, Airbnb, Linkedin
уровень изначально определяется вашим опытом (количеством лет, над чем работали, и т.д.). дальше под уровень набирается набор интервьюеров — они должны быть способны понять, тянете ли вы на этот уровень или нет. на начальные уровни дизайна может и не быть. на высокие уровни — да, решает дизайн и в некотором роде behavioral. Хотя если окажется, что задачи вы решать совсем не умеете, то интервью тоже провалите.

в целом, полезно с рекрутером заранее про уровень все обговорить. если вас интересует 5-6 в гугле, то стоит заранее убедиться, что вам луп не на 3-4 устраивают.
Есть даже такая легенда: однажды один программист загуглил «mutex lock», а вместо результатов поиска попал на страницу foo.bar, решил все задачи и устроился на работу в Google.
У меня сейчас в закладках foo.bar висит. Никак не соберусь поиграть. На работу в гугл не собираюсь, к тому же, после этого фубара такая же головомойка как и у самых рядовых кандидатов.
А его же вроде сейчас прикрыли (временно):
foobar is currently down for extended maintenance. If you'd like to be notified when we are back online, please sign up here.

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

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

А про кодирование последовательности байт в 6-ти битную «символьную кодировку» и про прочие сортировки пузырьками можно за пару минут и википедии прочитать.

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

А про кодирование последовательности байт в 6-ти битную «символьную кодировку» и про прочие сортировки пузырьками можно за пару минут и википедии прочитать.

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


А про кодирование последовательности байт в 6-ти битную «символьную кодировку» и про прочие сортировки пузырьками можно за пару минут и википедии прочитать.

А когда нужно не 6 бит, а какие-нибудь 5 бит? Надо представлять как это работает, чтобы хотя бы знать, что можно адаптировать base64, только не 3 байта в 4 перобразовывать, а 5 в 8.
Если человек не может понять, что как тут можно битовую последовательность нарезать на кусочки для base64, то и эта новая, уникальная задача займет слишком много времени или вообще будет неподъемна.

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

Ну какие тут тонкости? Или человек додумается до разбиения на биты, хоть и с подсказками, или — нет. А тонкости особо не важны. Если кандидат -1 где-то в коде не поставит, пустит 2 последовательных цикла вместа одного, или забудет про граничное условие, то я подскажу. Это минус, но не красный флаг.

Через 3 дня после звонка я получил письмо, в котором мне сообщали, что собеседовать дальше меня не хотят
Ну не хотят — как хотят. На работу не взяли, NDA не подписали! Можно смело выкладывать исходники!
Ради чего их выкладывать? Просто чтоб напакостить?
Лучше их продать плохим парням!
Ммм, скрытые намеки.
Лучше продать их китайцам
Не напакостить, а отомстить! Не хотят, что бы распространялась — могли принять на работу(человек-то согласен и явно способный) и подписать NDA. А хорошая статья на английском с сырцами вполне может принести вакансию в какой-нибудь фирме занимающейся безопасностью.
Инженеры-программисты делятся на два типа:
1) Неосиляторы — те, кто ноют, что в гугле (подставить любую компанию из Долины) спрашивают задачки на простенькие алгоритмы для джунов
2) Разумные — те, кто понимают, как на самом деле проходят интервью в топ кампании, зачем они имеют такой формат и как они на самом деле оцениваются.

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

Вам не приходило в голову, что это послание – не приглашение? Вы копали код защиты. Можно предположить, что вы нашли ещё один слой защиты, только на этот раз – психологический. Потенциально вас могли и взять, но главная цель, вполне возможно, была иная – отвлечь от взлома некоторую часть ломающих, используя в качестве наживки авторитет компании. Проверить и «отсобеседовать» их, взять на заметку, убедительно попросить не разглашать.
Главное, вполне сработало.
Кстати до, очень похоже, сразу обратил внимание что «приглашения» чересчур восторженно-навязчивы.
Определенно тут приложили руку психологи «отдела безопасности»-)
Наверняка об этом знать нельзя, конечно. Разве что сотрудник-ренегат через сто лет в мемуарах расскажет.
Но, судя по фактам, получилось именно так.

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

Совсем не похоже на «О, это наш человек!». Это «прям-очень-сильно-занятый-сотрудник-боооольшой-сеееерьёзной-компании» хмуро смотрит «ну кто там опять ковыряется, задолбали».
Я все-таки должен отметить, что само общение было очень вежливым и корректным :) Но общение ограничилось вопросом «зачем», взыванию к совести и благоразумию и просьбой не шарить наработки с плохими людьми.
Скажем так, я немного дальше зашел, чем эти сообщения. Дальше там тоже ничего интересного нет, к сожалению. Цели полностью симулировать работу DroidGuard у меня не было. Плюс у Google есть отличная возможность ответного хода — просто обновить эту нативную библиотеку, и все наработки по реверсу превратятся в тыкву.
Ребята, вы гении, если вы туда смогли попасть! Серьезно. Я не представляю, как можно пройти через эту полосу препятствий.

У меня знакомый туда таки попал. Они выкупили стартапчик вместе с конторой, и сотрудниками которые его пилили.
Троянский конь — проверенный веками метод.
Они выкупили стартапчик

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

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

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

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

Не могу сказать наверняка, но, скорее всего, в этом и была проблема. Надо было честно об этом сказать. Интервьюэр работает с этим вопросом и представляет насколько сложно в него врубиться с первого раза. На телефонном интервью не оценивают ваши навыки, смотрят на потенциал и на очевидные red flags. Если умолчать, что знаете вопрос — это сразу red flag. Вам самому нравится работать с людьми, которым не доверяешь?
Нет никакой проблемы в том, чтобы не решить задачку, тут важен процесс. Насколько вы были вовлечены, насколько задавали хорошие вопросы. Как у вас вообще с софт скиллз? Возможно, вы недооцениваете этот компонент.
Хороший вопрос про софт скиллз. Недооцениваю, факт :) Я все время считал, что главное — это техническая часть и решить все задачи. Но мне уже объяснили, что не совсем так (особо для Google).
Никто не заметил что задача была сериализовать массив строк?
Решение:
1. придумать разделитель
2. экранировать в строках этот разделитель и возможно спец символы (если есть)
3. склеить строки с этим разделителем

Использование base64 для строк даст только экранирование спец симвлов (если они вообще есть) и увеличение размера на треть. Дальше интервьюер пытается направить на правильный путь, зная как работает предложенный вариант можно было бы понять что это так себе решение, но и тут пустота. Два вопроса — два не правильных ответа, есть смысл продолжать?
Так я вроде и не писал, что я — недооцененный гений, а интервьюер спрашивает какую-то ерунду :) Все было честно и справедливо, а Google — просто не мой уровень. Это нормально, люди разные. Если бы все были одинаково умные, то как бы в Google попадали лучшие?
Знание base64 — не показатель уровня, скорее всего дело было в другом.

А вообще, в качестве разделителя можно использовать нуль-символ, так что мудрить с base64 необязательно.
Это если нуль-символа нет внутри строки.
Зачем тогда их называть строками? Если нет символа конца данных — просто по ходу хэша считаем размеры, добавляем в конце каждого из массивов.
Зачем тогда их называть строками?

Кроме Си, на свете есть и другие языки.

добавляем в конце каждого из массивов

В начале. А иначе вы этот конец потом не найдёте.
В конце тоже можно, инфа 100%. Если найдёте коллизию — отправлю 500 рублей вотпрямщас.

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

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

Но не важно. Вот вам две строки:
"\0\1\2" + 30 Тб повторений '\2'
"\0\1\2" + 30 Тб повторений '\2' + "\1"

Первая — это "\0\1" (длиной 2 символа) и за ней 10 трлн строк "\2\2" (длиной 2 символа каждая).
Вторая — это "\0" (длиной 1 символ), за ней 10 трлн строк "\2\2" (длиной 2 символа каждая), и в конце "\2" (длиной 1 символ).
Результат — вы не можете вычленить первую из сериализованных строк до того, как прочитаете все 30 Тб.
Сорян, про хэш это я понапридумывал.
Все равно вы молодец — такую работу проделать. Желаю вам удачи в будущем!
Спасибо!
Просто любопытно стало, что именно имеется в виду под «программа похожая на Hex-Rays IDA»? Это конкретная программа, которую вы почему-то не хотите называть или IDA, которой у вас «как бы нет»? :)
Ее родимую. Просто говорят, она должна быть платной.
Мне повезло, мне попался вопрос, который я заранее видел в интернете и который я уже решал перед собеседованием.


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

Конечно жалко, что рускоязычное комьюнити мертвое в плане взаимопощи в подготовке к подобным собеседованиям. Крохи на dou.ua и здесь не в счет. Китайцы, например, подробно описывают как они проходят интервью, решают вместе задачки, делятся опытом как выбить больше денег и т. п. и т. д. Ваша задачка кстати в топ 70 на литкоде по тегу Гугл, если по частоте попадания на интервью отсортировать за 2 года. Но вы наверняка даже не знаете про литкод, т. к. смотрите выше про мертвое комьюнити.
как видите, задача простая, решение известное, но все эти задачи имеют бесконечную глубину и отростки — всегда можно найти точку где человек не знает и начать смотреть как он будет решать её, а не вспоминать.
В идеальном интервью вопрос будет, например, такой. Но я много читал про случаи, когда просто требуют написать быстро код для решения конкретной задачи уровня medium+/hard без особых follow up questions

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


Если кандидат знает задачу, она так легко идёт, что я уверен, не все могут заметить смену курса. :) надеюсь, по крайней мере.

вы наверняка даже не знаете про литкод

Да не то чтобы я был прям такой дремучий :)

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

Ну и может не совсем насчет комьюнити… Но мне уже два человека отписались из Цюрихского офиса Google, посоветовали как лучше готовиться и т. д. Так что взаимопомощь есть.
Да, наверно все не так уже и плохо. Удачи вам в новых попытках.
То то я ни разу не вводил аккаунт гугла в андроид. Как знал, что ничего хорошего он не делает. А потом и вовсе перешёл на LineageOS, надеюсь, там таких приколов с выполнением непонятных левых бинарников нету.
НЛО прилетело и опубликовало эту надпись здесь
Во-первых, гугл на очном интервью тоже кормит обедом, причём весьма неплохим :-)

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

А из Google за два года я больше никаких сообщений не получал.
НЛО прилетело и опубликовало эту надпись здесь
Не вижу в предложении реализовать base64 ничего предвзятого. Ещё раз, цель интервьюера — не определить, насколько Андрей крут и просвещён, а определить, насколько он подходит в конкретный проект.

Меня и из гугла, и из FB через год после первого (проваленного) собеседования звали отсобеседоваться снова, но я уже не искал работу.
НЛО прилетело и опубликовало эту надпись здесь
Я-то как раз люблю в битах ковыряться, поэтому base64 не боюсь, и поэтому у них на собеседовании я потерялся на задаче совсем другого плана (комбинаторика).

Судя по статье, описанный «квест» вовсе не был частью отбора, а вставили его просто так, по приколу — как и упомянутый в самом начале статьи com.android.egg.

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

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


далеко не высокими зарплатами

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


ни топикстартеру, ни мне никакого «детального фидбека» не предоставлялось

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

НЛО прилетело и опубликовало эту надпись здесь

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


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

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

или либо работаете в Google небольшое время, чем до сих пор очень гордитесь :)

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

Про какой «hiring committee и детальный фидбэк» вы говорите, я так и не понял

Про комитет вам уже рассказали ниже, ну и про зарплаты вы тоже заблуждаетесь — они не самые высокие в индустрии, это правда, но они все же выше подавляющего большинства. Есть, правда, нюанс — существует поправка на географическое положение офиса. Например, в Калифорнии или Нью-Йорке платят больше, чем в Колорадо.
НЛО прилетело и опубликовало эту надпись здесь
Т.е. вы считаете, что абсолютно все инженеры Google, проводящие интервью, подобно вам, добросовестно подходят к делу, и, прежде всего, их заботит будущее компании, а не личные обстоятельства/настроение?

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

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

Хочу вот еще к этому добавить:


человек прошел очень нетривиальный «входной тест», и смог расшифровать хитро спрятанную «пасхалку»

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


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


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

НЛО прилетело и опубликовало эту надпись здесь
Тогда объясните, для какой цели, с вашей точки зрения, данная «пасхалка» (а, точнее, сложная техническая загадка) была помещена гуглом в продакшн код?

это способ попасть в рекрутинг пайплайн. большинство резюме, пришедших в гугл, не пройдут до этапа даже звонка от рекрутера. решивший же пасхалку получает шанс проинтервьюироваться.
НЛО прилетело и опубликовало эту надпись здесь
Я могу только сказать, что Base64 было первым, что пришло мне в голову :) Простое готовое решение из коробки, а весь код задачи занимает три строчки. Страшно признаться, но я даже не знал, на сколько именно вырастут исходные данные. Всю жизнь использовал и в голову не приходило посмотреть, что из 3 байт выходит 4, а размер увеличивается на треть.

Я так привык: есть задача — решаем, есть проблема — оптимизируем. «Преждевременная оптимизация — корень всех зол.» (с) Дональд Кнут.

Это плохо и точно не характеризует меня как хорошего разработчика. Поэтому с Гуглом нам оказалось не по пути.

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

А вообще мне интервью понравилось, и интервьюер тоже. Приятный парень, я после интервью был уверен, что я его прошел. У меня из моего опыта общения с сотрудниками гугла пока складывается впечатление, что главный критерий отбора у них — это быть приятным в общении :) После статьи несколько человек из Цюрихского офиса отписались, посоветовали, как готовиться и т. д.
НЛО прилетело и опубликовало эту надпись здесь
Но job offer-а от них я так и не получил.
Именно так. Если, не дай бог, вы покажите интервьюируемому, что вы чем-то недовольны, и даже, ужас какой, упомяните чем именно — получите тот ещё разнос от начальства. Потому даже не надейтесь по реакции интервьера понять — получите вы оффер или нет. Это вам не Яндекс.
Я так привык: есть задача — решаем, есть проблема — оптимизируем.
И вот именно людей с подобным подходом и было призвано отсеять собеседование.

«Преждевременная оптимизация — корень всех зол.» (с) Дональд Кнут.
Как же все задолбали выдёргиванием этой фразы из контекста.

Если вы почитаете оригинал, то обнаружите, что сама эта фраза служит уточнением к другой, почти прямо противоположной: в развитой инжереной дисциплине улучшение в 12%, легко получаемое, никогда не рассматривается как несущественное — и я верю, что подобный же подход должен возобладать и в програмимровании (in established engineering disciplines a 12% improvement, easily obtained, is never considered marginal; and I believe the same viewpoint should prevail in software engineering).

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

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

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

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

Это же хорошо, что в индустрии много людей, как я («с подобным подходом»). Пока нас много, у вас будет хорошая работа :) Если все были бы лучшими, то кто тогда работал бы в топовых компаниях?

Как же все задолбали выдёргиванием этой фразы из контекста.

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

Communications of the ACM CACM Volume 17 Issue 12, Dec 1974

Тут как раз про излишнюю оптимизацию и рост сложности.

Computer Programming as an Art by Donald E. Knuth
Another important aspect of program quality is
the efficiency with which the computer's resources are
actually being used. I am sorry to say that many people
nowadays are condemning program efficiency, telling
us that it is in bad taste. The reason for this is that we
are now experiencing a reaction from the time when
efficiency was the only reputable criterion of goodness,
and programmers in the past have tended to be so
preoccupied with efficiency that they have produced
needlessly complicated code; the result of this unnecessary complexity has been that net efficiency has gone
down, due to difficulties of debugging and maintenance.

The real problem is that programmers have spent
far too much time worrying about efficiency in the
wrong places and at the wrong times; premature
optimization is the root of all evil (or at least most of it)
in programming.


We shouldn't be penny wise and pound foolish, nor
should we always think of efficiency in terms of so
many percent gained or lost in total running time or
space. When we buy a car, many of us are almost
oblivious to a difference of $50 or $100 in its price,
while we might make a special trip to a particular
store in order to buy a 50¢ item for only 25¢.

А вы специально обрезали цитату «на самом интересном месте»? Потому что продолжение-то вашей цитаты следующее:My point is that there is a time and place for efficiency; I have discussed its proper role in my paper on structured programming, which appears in the current issue of Computing Surveys.

Тут Кнут прямо явно ссылается на свою другую статью.

Но даже и в той цитате, что вы привели, есть слова I am sorry to say that many people nowadays are condemning program efficiency, telling us that it is in bad taste — это, собственно, то, что делаете вы.

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

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

Да, конечно, можно удариться в другую крайность и начать писать функции в 10'000 строк в попытках избежать потерь на передачу данных — и это ни к чему хорошему не приведёт, так как вы в этих функциях запутаетесь.

Но сегодня, увы, превалирующая доктрина приводит к ровно противоположной проблеме: вы теряете настолько много на банальных бессмысленных индирекциях, что попытки выиграть что-то на векторизации, «раскрутке» циклов или на каких-нибудь заранее аллоцированных массивах (то есть как раз вещи, про которые Кнут и писал, что их не стоит делать в 97% случаем) выглядят, по меньшей мере странно: какие, нафиг, 12%, если у вас за счёт «новейшего дизайна» программа требует в 100 раз больше памяти, и в 10 раз больше времени, чем оптимальная?
Но, судя по словам Андрея, последовавший за этим вопрос: «а напишите мне алгоритм кодирования base64», по моему, явно выходит за рамки телефонного (да и white board) интервью.
А что тогда туда входит, я извиняюсь? base64 — это, фактически задача чуть сложнее сложения чисел в массиве. Нет, там тоже есть куда углубиться (вот тут, например)… но просто закодировать строку — это вот примерно этот уровень.

Если не спрашивать даже подобные задачки на интервью, то… что тогда спрашивать?
НЛО прилетело и опубликовало эту надпись здесь
Взгляните, например, на С-шную имплементацию, будет чуток посложнее, чем «сложение чисел в массиве».
Именно что «чуток». Посмотрите на ассемблерный выхлоп сложения двух массивов — сложность вполне сравнима, разница только в том, что оптимизации за вас компилятор делает, а в случае с base64 вам это руками нужно делать.

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

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

Помнит ли он детально RFC?
Сдалось вам это RFC. Там base64 посвящена одна страница. И, я вас уверяю, интервьюер бы простил вам перепутанные символы "+" и "/". И даже не обиделся бы, если бы вы вместо "=" использовали бы, скажем, минус. Не в этом же дело-то!
НЛО прилетело и опубликовало эту надпись здесь
Человек приплел, от волнения, ни с того, ни с сего, base64, а от него сразу попросили этот алгоритм написать.
Но ведь он же приплёл, его никто за язык не тянул!

А если он просто забыл, как именно реализуется base64 — вы такое можете представить?
Я бы был скорее удивлён, если бы он все детали и тонкости помнил. Конечно же речь шла про то, чтобы увидеть как он его будет «на лету» реализовывать, а не как он его вспомнит и в готовом виде на интервьюера «выльет». Раз он сам вспомнил — значит где-то что-то видел… А для такой простой задачи больше-то и не нужно!

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

Вот вы, не заглядывая в stackoverflow и не гугля, можете слету выдать эффективный base64 для Unicode strings?
Чем Unicode строки перед вами провинились? И причём тут base64? Или вы хотите результат в виде UCS-2? Или вообще что?

Или, например, без гугла выдать алгоритм CRC-64?
CRC-64 не выдам — я там коэффициенты не помню. Но ясно же, что это остаток от деления на какой-то полином 64й степени и xor'ами всё должно делаться…

< сходил в Гугл >

Ух ты: CRC64, оказывается, бывает аж два: ISO и ECMA… Но в целом — та же фигня: полином 64й степени, xor'ы, всё как ожидалось… В чём подвох?

P.S. А к чему был «ассемблерный выхлоп», я вообще не понял…
К тому, что вы откопали какую-то странную «высокоэффективную» реализацию, которая, тем не менее, включает в себя дикое количество комментариев. Простейшая реализация гораздо проще и короче…
НЛО прилетело и опубликовало эту надпись здесь
Ну сто раз уже написали вам разные люди, что задача «реализовать base64» — совсем не на вспоминание, и не для «ходячего SO». О том, что принцип base64 — перевод в 64-ричную систему, говорит само его название. Для того, чтобы перевести число из одной СС в другую, вам нужен подробный RFC?!
Человек приплел, от волнения, ни с того, ни с сего, base64, а от него сразу попросили этот алгоритм написать.

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


Опять же, задача в сериализации массива строк. Кандидат мог предложить хоть base64, хоть hex. Тут абсолютно фиолетово, какими именно символами что кодируется, какой padding используется и т.д. Если не помнишь, как base64 реализуется, придумай что угодно другое, только помни, зачем в этой задаче его приплел (что бы в закодированных строках не встречались придуманные тобой разделители).

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

Вот вы сейчас зачем-то придумываете то, чего не было :)

Интервьюера устроил мой ответ с base64 для экранизации разделителей, и я его реализовал в google docs. После этого мне предложили реализовать base64. А вот дальше с подсказками интервьюера с горем пополам я написал что-то похожее на base64.

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

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

Говорят, что очень возможна и обратная ситуация: можно не решить исходную задачу, но пройти собеседование. Охотно верю.

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


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

Но, насколько я знаю, просто вообще нет у разработчиков никакой возможности влиять на рекрутеров и процесс найма.

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

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


А referral… Сколько грусных мемов я видел про то, что "мой referral опять отсеян даже без телефонного интервью! T_T".


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

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

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

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


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

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

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

Читаем 250 символов, выбираем наиредчайший и используем его для экранирования в этом куске. Повторяем, пока строка не кончилась.
Распаковщик читает символ для экранирования, потом читает до символов <экран>0. Если распаковано 250 символов, считывается новый символ экранирования.


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


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

Т.е. в среднем и в лучшем случае алгоритм с экранированием сильно лучше base64.
В среднем случае он таки хуже — и сильно хуже.

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

Почему вы счиатете, что строки в которых более 33% данного, выбранного символа — средние? Если брать не '\', а какой-нибудь 0x01? А только такие при экранировании увеличатся хотя бы на треть, как base64 сделает со всеми строками.


Если сроки случайные — то наоборот.

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


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


Более того, я уже привел алгоритм, который гарантированно не раздувает строки более чем на 1% при этом требует константной памяти и выполняется за один проход по строке. Из base64 вы такого никогда не сделаете.

Более того, я уже привел алгоритм, который гарантированно не раздувает строки более чем на 1% при этом требует константной памяти и выполняется за один проход по строке. Из base64 вы такого никогда не сделаете.
С этим — согласен.
такая «пасхалка» вряд-ли была заложена обыкновенными инженерами с целью «просто поржать», практически наверняка это акция менеджмента. Наверняка сложность была выбрана, чтобы отсеять большинство кандидатов (вернее, что найдут ее считанные единицы из миллионов), т.е. разгадавший загадку заведомо будет высокого уровня

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

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

Мне уже написал один человек из Amazon, предложил пойти к нему в команду. Правда, там энтерпрайз в Канаде. Не знаю, может не тратить попытку и подать резюме в Amazon на что-то более релевантное моему опыту мобильного разработчика :)

Да, H1B нужен, конечно. Я в Цюрих метил прежде всего потому, что у меня гражданство Евросоюза и мне не надо никаких дополнительных разрешений-виз и т. д.
Разве не надо? Цюрих-то не в Евросоюзе.
Тут пишут, что надо.
Я в миграционном законодательстве не очень, но насколько я понимаю, нужен только residence permit. Но он в любой стране Евросоюза нужен, если живешь там больше 90 дней, а не туристом. Ну и для Болгарии и Румынии больше каких-то ограничений.

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

Разве что в штатах сложнее, да. Знакомый прошел собеседование, а с квотой пролетел.