Comments 457
А про устройство в другую компанию есть планы написать? Было бы круто.
А почему андроид? После проведённой подготовки произвольный swe же пыщпыщ
Вот и получается, что Андроид я знаю, а собеседование не прошел.
А то, куда наверное прошел бы, я не знаю.
Такой вот парадокс )
Перейти из команды в команду не проблема и требуется лишь интервью с менеджером новой команды, которое из себя представляет разговор о твоих интересах и рассказ о том, чем занимается эта команда.
Я бы попробовал опять, но просто на SWE, а потом, уже поняв что и как устроено внутри, решить куда хочется дальше идти.
*ирония*
По вашей логике, только гуманитарии не могут пройти собеседование в Гугл? Вот вы, например, работаете в Гугл или вы — гуманитарий?
Велик шанс что вас возьмут и дадут довольно рутиные задачи, где вообще не надо применять эти все знания… так что может оно и к лучшему?
Но такое упорство заслуживает уважения.
Конкретные знания — выветриваются. Натренированный мозг — остается. Становится проще понимать алгоритмы других разработчиков, легче найти фундаментальные проблемы — то есть самые опасные и дорогие. Много в общем пользы. Из личного опыта — я вообще тестировщик с уклоном в автоматизацию, код если и пишу то настолько примитивный, насколько это вообще возможно. Но опыт изучения алгоритмов, структур данных и соревнований на том же Hakerrank дают возможность достаточно быстро оценить в целом написанное разработчиком решение и выделить потенциально опасные места. При том что алгоритмов я, наверное, не вспомню по памяти вообще ни одного уже.
Я, правда, в специализированных конторах по разработке ПО не работал — я программы пишу в одиночку (потому что я просто инженер в НИИ, а не в IT-фирме). Пишу программ я много. Самых разных. И игры, и простенькие 3D-движки и чёрт знает, что ещё. Как для себя, так и по работе. Задач требуется решать массу. Кому это просто посчитать, а кому-то сложный комплекс нужен с большущим GUI. И вот никак я не могу понять, чем вы в IT-конторах занимаетесь, что вам нужны все эти деревья и сортировки? Ну правда, я давно заметил, что самое сложное в программе — это обеспечить интерфейс для маленького (по сравнению с обёрткой вокруг) модуля. Этот модуль и есть то, ради чего программа делалась. И в этом модуле могут быть все эти алгоритмы. Но он получает конкретные данные (это как фильтр в фотошопе, а вокруг него весь остальной фотошоп) и часто достаточно прост. Непростая вот вся остальная обвязка с проверкой ошибок, получением данных, реакцией на действия пользователя, автоматика. Есть, правда, «чистые программы» — там почти вся программа такой вот модуль. Но это специфическая задача автоматики. Так вот, я чего не понимаю-то: как так выходит, что у меня в ПО эти алгоритмы встречаются достаточно редко и самым сложным не являются, а послушать вас всех, так у вас кроме алгоритмов в программе, считай ничего и нет — остальное не существенное. И я этого нифига не понимаю. Расскажите, если не сложно, в чём тут фишка.
Спасибо. :)
«И пример из личной практики. Человек, явно не понимающий ничего в сортировках, умудрился делать вставку в сортированную коллекцию за O((N^2)*lgN), вместо O(lgN). Что при размере коллекции 1000 элементов дает примерно 7 000 000 (7 миллионов, Карл) операций, вместо 7.»
Графы — поиск пути почти в любой игре. Или на карте.
Деревья — TreeMap из Java. Мне вот один человек на собеседовании доказывал, что это ненужная штука и можно отсортировать HashMap. Шутник.
Матрицы — любая банальная операция в машинном обучении. Там сплошные матрицы.
Т.е. шаг в сторону от GUI, и вот они, алгоритмы )
И опять же вопрос не столько в том, что они требуются, а в том, что надо понимать, как что работает.
Я уже упомянул выше про сортировку HashMap. На мой взгляд такой уровень знаний для разработчика неприемлем.
Но многие могут с этим конечно не соглашаться.
Я уже упомянул выше про сортировку HashMap. На мой взгляд такой уровень знаний для разработчика неприемлем.
Но многие могут с этим конечно не соглашаться.
То есть, человек может накатать с нуля операционку (так бывает — не Windows, конечно, но вполне рабочую), сделать систему управления боеголовкой (так тоже бывает), накатать автоматику станка или высоконадёжного устройства с резервированием, но вот HashMap он не использует и не применяет. А уровень знаний почему-то остаётся неприемлем. Почему же? Что помешает открыть книжку и найти требуемое? Почему в инженерной практике не требуется значть вот прямо всё — есть справочники, есть пособия по проектированию. Вот не знаю я, как делать лопасти турбины. Открываю литературу и читаю: все расчёты есть. Так же и со схемотехникой. Нужен мне прецизионный усилитель — открываем, читаем, изучаем, применяем. Тогда что не так с IT? Я не понимаю. :)
Вот, кстати, а где вы эти хэши используете? Я такое максимум в шахматной программе использовал для определения повтора позиций и не более.
Вот, кстати, а где вы эти хэши используете?Да везде же. В Java всего два варианта Map: HashMap и TreeMap. Остальное завязано на них так или иначе. И если мне надо удобно хранить пару ключ-значение с доступом по ключу (разумно быстрым), то естественно я использую одну из них. И так как в среднем HashMap быстрее (если знать как его готовить), то использую я его. А TreeMap как раз в тех редких случаях, когда нужна сортировка по ключам.
Открываю литературу и читаю: все расчёты есть.Вот вы читаете. А другой возьмет и запилит на production сервер в «горячее» место HashMap с кастомным объектом в качестве ключа и не переопределенной хэш функцией. Что сервер сделает от такого? Естественно «умрет», так как поиск в мапе деградирует с O(1) до O(N). А зачем ему читать доки? Он же где-то слышал, что HashMap быстрый.
И да, я видел на собеседовании людей, которые не знают что такое хэш и как он используется в HashMap, но при этом HashMap используют.
. И если мне надо удобно хранить пару ключ-значение
Вопрос был в том, для чего вам может понадобиться хранить пару ключ-значение и тем более делать это с хэшем? Два примера (оба связаны с анализом текста для интерпретации/компиляции) тут привели. Но это вряд ли распространённые задачи.
и запилит на production сервер
Давайте всё же без web (я не знаком с web и не занимаюсь им). Меня интересует обычный Си++ и прикладное ПО, запускаемое на ПК пользователей.
Хранить пару ключ-значение например чтобы из списка в миллион пользователей (или сообщений, или отчетов или чего угодно) можно было быстро выдернуть искомое по ID. Например железяка (мы же не рассматриваем веб, пусть будет прямая связь по bluetooth) говорит, что пользователь 100500 изменил местоположение и присылает новые координаты. Почему не присылает все данные по пользователю? Потому, что они могут быть несколько мегабайт. Нечего забивать канал. Я беру HashMap, в который у меня все пользователи загружены при коннекте к железке, быстро выдергиваю пользователя, меняю данные и уведомляю пользователя через UI. Да, можно было хранить пользователей списком, но тогда бы мне пришлось просмотреть миллион пользователей (в худшем случае). И так каждый раз. А сообщения такого типа могут прилетать от каждого пользователя.
И да, это примерное описание реальной ситуации, с которой я сталкивался.
Вот смотрите: вы пользуетесь всеми этими строками, хэшами, стеками, очередями, деревьями и прочим. Почти всё из этого покрывается stl. Вы будете писать свой алгоритм сортировки только если у вас есть специфика в данных. Всё остальное время вы будете вызывать функцию из библиотеки. Зачем в этом случае вам помнить алгоритмы сортировок? Что это вам даст? Ничего. Та же история со всем остальным. Если вам понадобится балансировать дерево — найдёте и так, как это сделать. Искать подстроку в строке с максимальной скоростью — точно так же.
Далее, в программе всё это перечисленное составляет, наверное, столь малую часть, что непонятно, почему эта часть возведена в абсолют. Я вот об этом и спрашиваю: моя практика показывает, что сложность разработки ПО не связана с тем, что принято называть алгоритмами. Она связана с внутренней организацией, с общими алгоритмами работы ПО, с прозрачным взаимодействием между модулями, с предусматриванием возникающих ситуаций, но никак не с сортировками, поиском и прочим. Именно поэтому я и спрашиваю вас, что такое вы постоянно пишете, что у вас на первое место постоянно вылезает не архитектура ПО, а все эти стандартные алгоритмы? Вы отвечаете — мы ими ищем пользователей, строки и прочее. Неужели у вас вся программа — это бесконечный поиск с минимальной обработкой? У меня почему-то программы выглядят как автоматы с кучей состояний в зависимости от того, что хочет пользователь. Скажем, вот пользователь решил включить режим рисования. Отменяем всё незавершённое в предыдущем режиме, начинаем новый. Пользователь щёлкнул мышкой — запоминаем точку, предварительно пересчитав координаты из экранных координат в мировые с учётом масштаба и смещения системы координат. Пользователь продолжает дальше щёлкать мышкой и перемещать поле зажав другую кнопку мышки. Отслеживаем курсор и отрисовываем линию, соединяющую соседние точки между собой и всё остальное, уже нарисованное пользователем (простой список нарисованного есть). Пользователь замкнул фигуру. Проверяем, выпуклая ли она? Если да, заносим её в список с определением описывающего прямоугольника и позволяем рисовать дальше заново. Алгоритмы до сих пор так и не появились. Это примерно так работает у меня редактор карт. Конечно, можно захотеть странного в данном случае — разбить список готовых объектов на дерево для оптимизации вывода графики, но во-первых, даже если я это сделаю, то это составит крохотную часть программы, а во-вторых, пользователь физически не нарисует столько простых объектов, чтобы оно начало тормозить даже на P-233. Потому что пробежать список и выбросить всё, с координатами описывающего прямоугольника вне экрана очень быстрый процесс.
Именно поэтому я и спрашиваю вас, что такое вы постоянно пишете, что у вас на первое место постоянно вылезает не архитектура ПО, а все эти стандартные алгоритмы?
Ну вообще архитектура тоже важна, и ее тоже проверяют. Другое дело что проверить навыки в ней сложнее, можно наболтать что угодно, а маленькое тестовое покажет далеко не все. А алгоритмы и структуры можно проверить довольно быстро, притом они сразу покажут примерный уровень знаний, способностей, интереса и подобного. К тому же на бэкенде постоянно с этим сталкиваешься на самом деле, а если каждый раз гуглить (тем более не зная собственно что гуглить) — выйдет большая потеря времени, а то и качества.
К тому же на бэкенде постоянно с этим сталкиваешься на самом деле,
Мне кажется, у нас разные Солнечные системы. :)
Пользователь замкнул фигуру. Проверяем, выпуклая ли она?А вот кстати и алгоритм. Из раздела Computational Geometry. Неважно, как мы это проверяете, но это алгоритм, готовый или самодельный.
Другой пример — однажды мы делали систему где важной частью была древовидная сущность — дерево с произвольным количеством дочерних узлов. Нам надо было ходить вверх\вниз, собирать множество и подмножество объектов, и прочее. Это, конечно, не rocket science, но поиск в ширину и глубину пришлось использовать.
Много было более мелких эпизодов, когда ты видишь неэффективный код и правишь его просто чтобы улучшить производительность — как то раз применял сортировку подсчетом, менял проверку наличия цифр в строке с регулярки на линейный поиск (почему все так любят регулярки? Они ж медленные. Откуда я это знаю? — из курса алгоритмов) и тд. Но, конечно, у меня не было ничего настолько сложного, чтобы пришлось прямо изобретать алрогитм. А писать свою сортировку слиянием это вообще зачем? Я не уверен, что олимпиадники в задачах пишут сортировки сами (только если это не смысл задачи), мне кажется это просто трата времени.
Я к тому, что писать алгоритмы каждый день может и не придется, но знание как они работают помогает писать более эффективный код.
Я не уверен, что олимпиадники в задачах пишут сортировки сами (только если это не смысл задачи), мне кажется это просто трата времени.
Ну, на областной в 2000 году мы таким точно не занимались. Но вот решение японского кроссворда таки было. А что там на всероссийской и выше, тем более сейчас, я не знаю. :)
вот пример. у вас будет стэк и задача в любой момент времени отдать какую-то минимальную на весь стэк величину. стек то получает элементы, то теряет. и как у гугла спросить есть ли что-то такое?
я согласен, что не надо знать прямо дострочно алгоритмы. это уже перебор, но сами алгоритмы надо знать и понимать на уровне псевдокода — просто чтобы не оказалось, что вы пилили алгоритм комивояжера неделю. даже если все получилось и заработало (что несомненно является успехом) — трата времени неоправданна.
аналогична ситуация с паттернами. их придумали не просто для того, чтобы было что спрашивать у джунов на собеседовании, а чтобы экономить время.
но вот привожу пример зачем их нужно знать — чтобы не сливать время и деньги проекта в канализацию велосипедами.
вы же конечно знаете скажем перемножение Карацубы? замечательнейший ведь алгоритм, согласны?
В условиях ограничений по ресурсам (на мобильнике, например) кто-то малограмотный просто воспользовался бы стандартным алгоритмом из библиотеки и получил перерасход аккумулятора и расход времени.
вы же конечно знаете скажем перемножение Карацубы?
Нет, не знаю. Я знаю что есть CORDIC (цифра за цифрой) для быстрых математических операций. А вообще, сопроцессор у нас чем занимается? Электричество только жрёт что ли? А оптический умножитель не хотите применить (да, если бы была задача на скорость и устройство сами бы проектировали, я бы на этапе создания железа бы уже задал ряд вопросов)? :) Есть и такое.
В условиях ограничений по ресурсам (на мобильнике, например) кто-то малограмотный просто воспользовался бы стандартным алгоритмом из библиотеки и получил перерасход аккумулятора и расход времени.
Мне кажется, вы шутите. У меня тут сложные вычислительные задачи (да, обсчёт модели гироскопа дорогая штука. А уж если ещё и фильтр Калмана добавить...) на микроконтроллерах работают с крошечным ОЗУ и смешными мегагерцами. А вы мне рассказываете про перерасход аккумулятора и расход времени на мобильнике?! Это которые многоядерные с частотами в пару ГГц? Там подсветка сожрёт больше, чем вы наоптимизируете. Да, собственно, работа сайтов на старом оборудовании прекрасно показывает всю вашу оптимизацию — они не работают на компьютерах, скажем, 2004 года. Не хотят-с. Тормозят вплоть до зависания.
у вас будет стэк и задача в любой момент времени отдать какую-то минимальную на весь стэк величину. стек то получает элементы, то теряет. и как у гугла спросить есть ли что-то такое?
Кстати, как вы это решали? Мне приходит в голову хранить поступающие значения в отсортированном связанном списке (сделав его обычной структурой с указателями на предыдущий и последующий элементы — т.е. без stl (чтобы указатели на элементы не менялись) ну и указатели на начало и конец завёл бы), добавляя вставкой элемент куда надо. А в стеке хранить указатель на элемент списка, убирая или вставляя его. Соответственно, начало списка и его конец всегда будут указывать на большее и меньшее число.
ого! вместо единичного времени вставки в стек вот так запросто перейдем к линейному времени(место-то надо найти). и правда… где 1 такт на вставку, там и секунду подождать можно (если стек не из 100 элементов, конечно). только вот как из стека потом вынимать-то… немножко конфуз с правилом FILO выходит.
а решается это самым типовым алгоритмом с созданием дублирующего стека.
> А вы мне рассказываете про перерасход аккумулятора и расход времени на мобильнике?!
а кто сказал. что подсветка вообще будет работать? может это приложение отслеживает геопозицию и шлет на сервер как маяк, например. там вообще экран не нужен. а если подбирается телефон с максимальным временем жизни (ну вот пожадничаю я на нормальную спутниковую сигналку для авто и подброшу телефон) — будет подбираться железо с минимальным процессором.
> У меня тут сложные вычислительные задачи (да, обсчёт модели гироскопа дорогая штука. А уж если ещё и фильтр Калмана добавить...)
куда уж мне с 3 миллиардами финансовых операций в сутки 24/7 в swift-е и обязательно не в кластере… написать абы как и пусть банки в очереди ждут пока транзакция досчитается. (и такое в практике было)
только вот как из стека потом вынимать-то… немножко конфуз с правилом FILO выходит.
Так же. В стеке-то указатель на список. Из списка выбросить элемент пара пустяков.
а решается это самым типовым алгоритмом с созданием дублирующего стека.
А подробнее? Вот пришло число — вы его поместили в первый стек. А что со вторым стеком делать?
куда уж мне с 3 миллиардами финансовых операций в сутки 24/7 в swift-е и обязательно не в кластере… написать абы как и пусть банки в очереди ждут пока транзакция досчитается. (и такое в практике было)
И тормозит у вас, конечно, именно умножение чисел, да? ;) Вот эти самые 3 миллиарда финансовых операций в сутки, это сколько умножений в секунду требуется? Неужели, однотактный умножитель в ваш процессор почему-то не завезли? Просто сдаётся мне, вы оптимизировали то, что не требовало оптимизации. Или вам профайлер показал, что программа на умножениях застревает? Но судя по вашей специфике, это будет странно.
вопрос с добавлением в отсортированный список не отпадает. золотое сечение тут использовать не получится — элементы лежат в памяти не подряд.
это не HashMap и ткнуть в нужный элемент не получится. чтобы получить, скажем, 4й элемент придется обратиться к 1му, от него ко второму, от него к третьему и лишь потом получите нужное.
а теперь представим список из 1_000_000_000 элементов и вы добавили какое-то число, равное max-1… можно идти домой — сегодня результата не будет.
а если подробнее — просто рядом размещается стек с актуальным минимумом. вынимается элемент — минимум стирается и сверху оказывается новый. добавляется — создается новый элемент.
это вот действительно самая типовая задача.
И тормозит у вас, конечно, именно умножение чисел, да?
это возможно удивит, но систем, в которых виновата в тормозах только 1 операция почти нет.
но вот после чистки кода от таких вот "типовых" решений подняли производительность на треть. это кропотливая и далеко не быстрая работа.
вопрос с добавлением в отсортированный список не отпадает.
Да, не отпадает.
это возможно удивит, но систем, в которых виновата в тормозах только 1 операция почти нет.
Профайлер часто показывает, что такие системы бывают. :) Но вот что умножение у вас виновато в тормозах, так это сильно вряд ли.
но вот после чистки кода от таких вот «типовых» решений
А если умножение вернуть стандартное, быстродействие у вас ухудшается?
А если умножение вернуть стандартное, быстродействие у вас ухудшается?
этого никто не станет делать. улучшения проводились массово, а не точечно.
общая идея была "будем считать каждый байт и такт".
кстати, можете взять jmh и просто поэкспериментировать. у меня выходило, что при ограничении в 64 мегабайта стандартное умножение отставало уже очень даже заметно больше величины погрешности. а есть и похуже требования.
Профайлер часто показывает, что такие системы бывают
моя практика показывает, что 9 из 10 java-программистов пытаются профилировать приложение без включения спец режима на горячем..) хорошо если они тогда хоть что-то там найдут.
посмотрите лекции Паньгина из Однокласников для примера.
общая идея была «будем считать каждый байт и такт».
До ассемблера с оптимизацией кэшей и оптимизаций предсказаний ветвлений вы, надо полагать, ещё не добрались? :) (шутка :) )
моя практика показывает, что 9 из 10 java-программистов
Я не пишу на java. Только Си и Си++. :) Поэтому проблемы java мне не ведомы.
До ассемблера с оптимизацией кэшей и оптимизаций предсказаний ветвлений вы, надо полагать, ещё не добрались?
ну вообще-то до изучения исходников добрались.
Поэтому проблемы java мне не ведомы.
откуда вам знать, что не повторяете ту же ошибку и используете профайлер по максимуму его возможностей?
да и не покажет профайлер криво написанного кода. был в моей практике товарищ, который сначала делал фуллсканы справочника, а потом только выяснял а надо ли оно ему вообще было. всего лишь поставить проверку до выборки и получаем, что 90 процентов операций было в холостую. профайлер молчал как партизан у немцев)
ну вообще-то до изучения исходников добрались.
Вообще, полагаю, для написания высокоскоростного приложения java не лучший выбор. Но у вас мобильник, так что понятно, почему java.
откуда вам знать, что не повторяете ту же ошибку и используете профайлер по максимуму его возможностей?
От профайлера типа Intel VTune мне (в Си++) нужно просто увидеть, где программа проводит большую часть времени во время работы и какая конкретно операция жрёт процессор больше всего. Что показывает профайлер для java — не в курсе.
> полагаю, для написания высокоскоростного приложения java не лучший выбор
предположение не верно. страшно удивитесь, но путем некоторых ухищрений и манипуляций Java может даже обогнать плюсы за счет более качественной оптимизации байт-кода. но это требует опять же знаний. а не книжек уровня 1го курса. плюс уж извините, но плюсы крайне неудобны в крупных проектах. бардак с именованиями, редкие обновления спек, множество велосипедов по причине отсутствия стандартных типовых библиотек для не слишком стандартных вещей. одни утечки памяти чего стоят — в проекте из нескольких тысяч файлов допустить подобное ничего не стоит. посетите что-нибудь из конференций jug.ru (для дотнетовцев тоже есть) — сильно удивитесь подходам в крупных компаниях.
как я вас понял — вы работаете без команды и обмена опытом нет. может быть в этом проблема? сходите на собеседование в крупную компанию — запомните на чем завалите собеседование.
сам лет 7 назад собеседовался в mail на позицию разработчика в skyforge. на вопрос о графах в итоге выдал бред, что «сейчас компьютеры настолько мощные, что знать этого не нужно».
провалил. выпросил книжки для самообучение. прочитал… до сих пор стыдно)))
> и какая конкретно операция жрёт процессор больше всего.
ну в том же Java профайлере операция может быть слишком высокоуровневой. то что там что-то написало — не значит ровным счетом ничего. например. не выйдет заглянуть внутрь for без бубна.
самое смешное, что далеко не все понимают, что профайлер «врет» чтобы программа не повисла из-за слишком пристального внимания.
Я нашел решение, которое удовлетворяет всем упомянутым ограничениям (операции с постоянным временем) и постоянное дополнительное пространство.
Идея состоит в том, чтобы сохранить разницу между минимальным значением и номером ввода и обновить минимальное значение, если оно больше не является минимальным.
public class MinStack { long min; Stack<Long> stack; public MinStack(){ stack = new Stack<>(); } public void push(int x) { if (stack.isEmpty()) { stack.push(0L); min = x; } else { stack.push(x - min); //Could be negative if min value needs to change if (x < min) min = x; } } public int pop() { if (stack.isEmpty()) return; long pop = stack.pop(); if (pop < 0) { long ret = min min = min - pop; //If negative, increase the min value return (int)ret; } return (int)(pop + min); } public int top() { long top = stack.peek(); if (top < 0) { return (int)min; } else { return (int)(top + min); } } public int getMin() { return (int)min; } }
ничего странного. сказано же, что она типовая. но вы же не по каждой задаче идете в гугл с целью узнать нет ли готового решения? и первое предложенное с ходу решение этой простейшей задачки отправило бы систему думать о смысле бытия.
Бывают задачи на несколько минут. Бывают на несколько дней. А бывают и на годы.
я просто к чему это все. я пытаюсь донести простую мысль.
алгоритмы надо знать не для галочки. их надо знать просто для того, чтобы понимать какая работа уже была проделана с максимальной эффективностью.
еще с универа придерживаюсь правила — «страшен не тот. у кого атомная бомба, а тот, кто знает где найти ее чертежи и материалы».
просто зная, что «что-то такое я уже видел» вы можете в пару минут поиска сократить время работы с недели до часов. в условиях бизнеса это очень много значит и самым благотворным образом может сказаться на карьере, освободив уйму времени для более интересного.
Там подсветка сожрёт больше, чем вы наоптимизируете
Ага, это пока ваше приложение не стоит на миллионах устройств, и люди не спрашивают: "А чего это оно жрёт больше других? А чего это оно проснулось?"
вот примерКонкретно в этом примере как раз все получится: по запросу в Google «stack with minimum» у меня на первой странице все ссылки по теме. Даже код есть с просьбой провести review.
что там на всероссийской и вышеЗдесь есть задачи всероссийской олимпиады.
Основы понимания алгоритмов нужно многим (как и скажем основы баз данных), но вот умение без инета написать любой алгоритм поиска в графе или сортировки — не так часто нужно. ИМХО.
Это как вопросы вроде вспомнить восьмую нормальную форму БД — да есть 0.01% программистов, которые без нее работать не смогут, но остальные могут работать с базой не вспоминания о нормальных формах.
Задача была на графы. Я быстро понял, что надо сделать, но выбрал не тот алгоритм. Когда начал писать код осознал это и переключился на другой вариант, который и дописал. Интервьюер задал несколько вопросов на тему сложности алгоритма, спросил, можно ли быстрее. Я как-то затупил и не смог. На этом время вышло и мы распрощались. Потом, минут через 10 до меня дошло, что вместо алгоритма Дейкстры, который я использовал, конкретно в этой задаче можно было бы использовать поиск в ширину, и это было бы быстрее.
Следовательно, автор сидел и реализовывал сам алгоритм.
Ясно написано, что требование было не «вспомнить и написать», а решить задачу. Не требуется при этом стандартные алгоритмы реализовывать — используй библиотеки. Конечно, понимать устройство этих библиотек надо (хотя бы для сложностной асимптотики), но помнить все тонкости реализации — не надо.
Не уверен, что вообще возможно понимать алгоритм Дейкстры, но не мочь его написать.
Да легко можно, понимается он ведь в предметных терминах, а формулируется — в терминах ЯП, причем обычно в тех терминах "чтоб производительно". Если я цикл в явном виде последний раз год назад писал — то естественно будут проблемы с тем, чтобы выразить алгоритм в рамках требуемых примитивов, если же я начну писать как удобно — то это будут всякие свертки, чистые функции и прочая иммутабельность. Мне, наверное, проще будет рекурсивную схему под дийкстру подобрать, чем записать его классически :)
Да легко можно, понимается он ведь в предметных терминах, а формулируется — в терминах ЯПЕсли будет ±1 ошибка в цикле или еще что-нибудь подобное, или код не скомпилируется из-за опечатки, никто вам ничего не скажет (ну, в нормальной компании, конечно). Опять же, никто не будет просить, чтобы вы заменяли индекс в цикле на указатель по массиву или делали еще какую-нибудь оптимизирующую дичь — асимптотика сходится, и нормально.
А вот если вы не можете выразить алгоритм достаточно подробно, чтобы оно хотя бы отдаленно напоминало код (пусть на псевдокоде, неважно), то я бы не сказал, что вы алгоритм знаете.
Мне, наверное, проще будет рекурсивную схему под дийкстру подобратьВот это очень интересно, никогда не видел Дейкстры в таком подходе. Может, статью напишете? Думаю, с заголовком вроде «как я, все забыв, придумывал с нуля алгоритм Дейкстры» пойдет на ура.
никто вам ничего не скажет (ну, в нормальной компании, конечно)
Ну вот у вас такой подход, а в статье человек пишет что интервьюверу не понравилась, что он "код часто менял".
Если можно просто описать в псевдокоде — тут, конечно, другой разговор.
Может, статью напишете? Думаю, с заголовком вроде «как я, все забыв, придумывал с нуля алгоритм Дейкстры» пойдет на ура.
Не думаю, что тут на статью наберется, речь же не о выдумывании, а просто о записи в других примитивах (как Дийкстра работает-то я помню прекрасно :)).
Ну вот у вас такой подход, а в статье человек пишет что интервьюверу не понравилась, что он «код часто менял».Со стороны интервьюера это выглядит так — человек пытается начать писать код не подумав, постоянно пропускает ключевые моменты решения и, как следствие, переделывает всё многократно, получая подсазки.
Если можно просто описать в псевдокоде — тут, конечно, другой разговор.Написание в псевдокоде не приветсвуется, но и компилировать никто не будет.
Хотел сделать как лучше, чтобы было красиво, а получилось как получилось.
Ну на вашем интервью я не был и что именно там было — не знаю. Но как интервьюер я наблюдаю часто как человек пишет код "начав не с того конца" и в результате переписывает его многократно.
Ну а ещё стоит отметить, что впечатления интервьюера и кандидата очень часто не совпадают. То, что кандидату кажется лучшим моментом интервью, интервьюер может считать полным бредом и, наоборот, кандидату кажется, что он полностью облажался, а интервьюер в восторге. При этом реальный фидбек интервьюер кандидату не сообщит.
Да, можно было хранить пользователей списком, но тогда бы мне пришлось просмотреть миллион пользователей (в худшем случае).
Пользователей-то можно так и сортированным массивом хранить. Для миллиона пользователей, наверное, и пошустрее хеша получится (хотя тут уже зависит от того, что за хеш)
И писание кода на доске выглядит дикостью. С хорошей IDE очень многое делается компом.
В общем, ваш материал почитал с удовольствием, но порадовался, что в гугл не собираюсь устраиваться. Ну и мнение о них сложилось специфическое, примерно как об армии РФ…
Вот вы читаете. А другой возьмет и запилит на production сервер в «горячее» место HashMap с кастомным объектом в качестве ключа и не переопределенной хэш функцией.
Так может усилия стоит направить на то, чтобы определить тех людей, которые "читают", а не тех, что знают двадцать вариантов сортировки?
Что сервер сделает от такого? Естественно «умрет», так как поиск в мапе деградирует с O(1) до O(N). А зачем ему читать доки? Он же где-то слышал, что HashMap быстрый.
Вообще, согласитесь, если ваш хеш деградирует на дефолтной хеш-функции до линейного, то это не хеш, а хрень.
Вообще, согласитесь, если ваш хеш деградирует на дефолтной хеш-функции до линейного, то это не хеш, а хрень.Дак на то она в Java и дефолтная, просто шестнадцатеричный идентификатор объекта.
Так может усилия стоит направить на то, чтобы определить тех людей, которые «читают», а не тех, что знают двадцать вариантов сортировки?Ну, и то и другое полезно. Каждый ли разработчик Java знает, что при сортировке массивов примитивов используется вариация быстрой сортировки, а при сортировке массивов объектов используется вариация сортировки слиянием. И для скольких из них будет сюрпризом, что быстрая сортировка может деградировать до O(N^2), а при сортировке объектов им понадобится дополнительно O(N) памяти?
Каноничную сортировку Хоара с одним опорным элементом?
Или все вариации?
так как в среднем HashMap быстрееНе оспаривая тот факт, что обычно это так, хочется дополнить. В случае TreeMap нам нужно алфавитное сравнение элементов, которое может работать быстрее, чем вычисление хеш-функции. Например, если у нас не очень большой Map из длинных массивов, то TreeMap будет на случайных данных работать быстрее, поскольку сравниваем мы до первого не совпавшего элемента за O(N), где N — размер Map, а хеш считаем — за O(M), где M — размер массива. Помнится, на каких-то олимпиадах я с этим сталкивался.
В случае идеального HashMap, мы имеем О(1) как на вставку, так и на доставание. Т.е. при вставке мы считаем хэш (если он уже не посчитан для этого объекта) и кладем в пустую ячейку. При доставании считаем хэш (если не посчитан) и делаем 1 вызов equals.
В случае с TreeMap equals будет вызываться в каждом узле, чтобы понять куда идти, т.е. lgN раз.
Итого, если даже массив из М элементов это ключ, а в мапах по N элементов, для HashMap положить это M и достать 2*M + N, а для TreeMap положить это M*lgN, и достать аналогично.
Воу-воу-воу, погодите, вы про коллизии забыли :)
И не забывайте, что для дерева lgN — это худший случай, в то время как хеш может потребовать перестройки. Если вам надо гарантировать быстрый отклик — дерево лучше, даже если оно в среднем медленнее.
А вот в дереве элемент всегда кладется как лист. А уже потом мы начинаем балансировать дерево. Т.е. lgN у нас всегда.
Да, я прекрасно понимают, что если нужна гарантия, то мы берем дерево, так как в случае HashMap гарантия это O(N).
IdeOne с кодом на C++ о том, что я имею в виду. Hash set из 1000 случайных массивов длиной 100'000 элементов работает втрое дольше, чем tree set из них же. Для map'ов ничего не поменяется. Я использовал стандартный оператор сравнения векторов, и хеш-функцию из boost. Хеш-функцию, правда, пришлось скопировать, не умею я на IdeOne использовать boost.
Причем основание этого логарифма — число возможных вариантов для элемента массива, скажем, для 32-битного числа это будет больше 4 млрд. По сути, константа, в реальном мире.
Кстати, важный момент, которые многие часто забывают.
PS: Вот версия с мапами, эффект тот же.
И в данном случае можно от этого уйти, например используя для хэша 3 элемента массива (начало, середина, конец). Снова получаем константу. Вся суть HashMap сводится к правильному выбору хэш функции, задача которой более менее равномерно размазать данные по ячейкам.
И к тому же хэш объекта можно кэшировать. Это удобно для иммутабельных объектов, например таких, как строки в Java.
Но в любом случае итог не меняется — HashMap в среднем быстрее, но может деградировать. TreeMap в среднем медленнее, но дает гарантию.
Да, в свете нового комментария от nobodyhave, мне следует уточнить, что задача авторизации пользователя любого прикладного ПО не представляет для меня интереса, как очевидная задача поиска. Меня не она интересует. :)
На самом деле, игнорировать структуры данных и их сложности можно, как мне кажется, только на очень линейных и нетребовательных к производительности задачах. А когда требуют хоть какую-то приличную скорость работы, то сразу начинаются оптимизации.
Ну вот у меня не Web, у меня HFT и всякий онлайн трейдинг.
По-моему, это задачи одно уровня: клиент-сервер. :)
У меня таких задач практически нет, потому я про них мало что знаю.
где нужно управлять железом
Так это почти любая контора, где это самое железо есть. :)
А вот интересно, например, такое слово, как «QNX» у вас какие-либо ассоциации вызывает? :) Это всё из того же мира автоматизации оборудования.
На практике (гейм дев) мне лично постоянно приходится использовать те или иные алгоритмы. Из последних — «поиск оптимально пути в графе(пришлось модифицировать алгоритм Дейкстры)» или «поиск пересечений пуль и объектов(просто перебор был жутко медленный)». Так же надо знать очень хорошо геометрию — матрицы и вектора. но в большинстве случаев уже есть библиотеки или движки которые это делают. Нет смысла пилить свой велосипед. Но в гейм деве есть ограничения производительности и весе приложения — поэтому проще сделать какое то упрощенное быстрое решение чем использовать супер навороченную библиотеку. И вот тут включается мозг ) Надо проанализировать существующие решения выбрать самое оптимальное или скомбинировать и потом доработать его.
Если например взять другую область где надо набросать UI. То там конечно не будет этих алгоритмов. Там другие задачи. Возможно вы решаете другие задачи которые редко требуют алгоритмы. Либо используете нативные средства языка или библиотеки. И вам не сильно важно что бы это был быстро.
Можно пример человека, который может на коленке написать операционку(с пруфами), и не знает концепцию хэш-таблицы?
Простые бинарные деревья на самом деле бывают редко нужны из-за специфики их работы и адресации. Хотя хороший slab allocator может эту проблемку порешать, да. А так hash + vector зачастую оказываются быстрее в реализации, когда внезапно нужно иметь упорядоченный хеш. Знание алгоритмов — это хорошо, бесспорно, но при наличии интернета достаточно умения найти подходящий алгоритм. Другой вопрос — возникнет ли такое умение, если нет базовых знаний этих самых алгоритмов...
Годится?
У меня была такая задача, когда я писал удобный (как минимум для себя) язык конфигов libucl — https://github.com/vstakhov/libucl. И там одним из важных свойств была возможность выводить конфиг после парсинга в как можно более близком к оригиналу виде (в том числе и порядок ключей объекта). Ну и производительность была тоже важна, да. Ну и в моем основном проекте Rspamd такая задача тоже встречалась. Если же нужна сортировка элементов, то такой "хеш с порядком" работает только в случае read-most структуры, иначе, конечно, дерево.
Вы, кажется, упорно пытаетесь доказать, что хэш-таблицы нужны только веб-деву и небожителям?
Потребность в алгоритмах и структурах зависит не только от конечной макрозадачи, но и от архитектурного подхода.
Пример: приложение на дельфи7, которое формирует sql запрос, выполняет его, превращает в файл одним из десятков заложенных способов, отправляет. И таких действий в приложении сотни.
Легаси содержало что-то вроде:
AdoQuery1.sql.add(Format(…
И таких от 3 до 30 строк на запрос. А потом outfile.lines.add('node' + encode(adoqwery1.fieldbyname('foo').asstring) + '/node');
Сопровождаемость отсутствует как класс.
Логично вынести шаблоны запросов в ресурсы. Ресурсы адресовать по имени. И чтобы каждый раз не расшифровывать (запросы в ресурсах зашифрованы) — кэшировать. Самое место для хэш-мэпа строка-строка.
А этапы отдельных операций, настроечные параметры — были в харрррдкоде и дельфи-формах, а теперь объявляются декларативно, в массиве константных объектов, и адресуются по имени.
Приложение, заметьте, не поменялось в смысле цели. Но затраты труда на сопровождение и доработку снизились ну просто феерически. Прежде всего — из за введения абстракций с косвенной адресацией элементов по именам.
А начальник, который создал исходный вариант, фигачит всё по-старому и в ус не дует. Ему-то хеш-мапы ни к чему, да… И даже всё работает, и бизнес-цели реализуются.
А теперь представьте, что вы хотите нанять работника. И знаете себе цену, и она высока. Вы выберете того, кто "и так справляется", того кто "умеет пользоваться" или того, кто "так хорошо понимает, что потенциально и улучшить может"?
И знаете себе цену, и она высока. Вы выберете того, кто "и так справляется", того кто "умеет пользоваться" или того, кто "так хорошо понимает, что потенциально и улучшить может"?
Вы же понимаете, что описанное в статье — как подготовка к экзамену. Сдал и забыл?
И восстановить навык при необходимости займет максимум 1-2 месяца, тогда как получить его с 0 потребовалось 1.5 года.
Не-не. Это как ездить на велосипеде ) Если научился решать задачки, то это останется.
Ну, не знаю. Я не раз ловил себя на том, что помню, что задача Х решается неким хитрым методом, но при этом самого метода — не помню. Потому что дело было года 3 назад.
Для пятилетнего ребёнка умножение — «хитрый метод» для быстрого подсчёта. Для третьекласника решение задач с помощью уравнения — тоже «хитрый метод», который они не помнят.
Нет, ни то ни другое хитрым методом не является, т.к. в обоих случаях — это вполне алгоритмизируемая штука.
А вот когда вы ОДУ, при помощи хитрой замены решаете, приводя к некоторому виду, в котором оно уже решается при помощи алгоритма — это как раз то самое. Потому что замена ниоткуда не следует и не выводится (если только вы не придите к разделяемым переменным через группы Ли), никакой логики в ней нет.
Именно в этом смысл хитрости метода — в его логической невыводимости и неалгоритмизируемости. Вы либо его знаете, ну, как наизусть, либо вам везет, и он приходит в голову при переборе.
С-но если он в голову пришел — и вы его потом забыли, то тот факт, что вы его когда-то использовали, вам уже ничем и не поможет. И никакое понимание не поможет, потому что понимать там банально нечего.
Так в том и речь, что хитрым метод является только до тех пор, пока человек не понимает более глубоких вещей, лежащих в его основании.
Вы, видимо, не поняли. Смысл хитрого метода именно в том, что ничего глубокого в его основании не лежит. Иначе бы он не был хитрым.
Вот вы дальше пишите о пузырьковой сортировке — не существует никаких глубоких оснований, которые вам помогут вывести код пузырьковой сортировки, не зная его.
Вы либо знаете пузырьковую сортировку, либо не знаете.
По-этому пузырьковая сортировка — замечательный пример хитрого метода.
Вы же понимаете, что при найме не проверять соискателя на соответствие именно Вашим критериям профессионализма (которые могут формироваться и на основании баланса спроса и предложения, кстати, помимо собственно "разумной достаточности") — это за не то, что обычно делают адекватные люди?
Правда уточню — я пишу на Си и Си++. И не для Web.
что вы все такое программируете (чем занимаетесь), что используете тот же обход дерева в ширину?В такой постановке вопроса — в 99.9% случаев ничего. Еще в 0.1% случаев — дописываю во внутреннюю SDK какую-нибудь ранговую эвристику в СНМ или что-нибудь такое. Оно потом будет использоваться везде и всеми.
Но помимо этого, я каждый день решаю, что мне использовать — LinkedList или ArrayList, и мне важно не ошибиться в этих решениях.
PS: А поскольку мне все же своя рубашка ближе к телу, для меня лично в знании алгоритмов и структур данных важнее всего возможность получить более вкусные офферы.
В моей практике гораздо чаще встречаются задачи уровня разобраться с работой с технологией (например, с DirectShow, с сокетами, с портами, с написанием драйвера, да с чем ещё угодно), чем делать обход чего либо.В моей тоже. Я, правда, тоже пишу в основном на C и C++ и не для Web.
Правда уточню — я пишу на Си и Си++. И не для Web.
PS: А поскольку мне все же своя рубашка ближе к телу, для меня лично в знании алгоритмов и структур данных важнее всего возможность получить более вкусные офферы.
Следовательно, причина распиаренности алгоритмов в том, что их зачем-то спрашивают те, кому они не нужны. :)
Т.е. там не причинно-следственная связь, а эмпирически установленная закономерность.
Кроме того, не стоит забывать, что лучше всего решается та задача/класс задач, которую ты уже решал или видел её решение. Но когда потребуется решить принципиально новое, решишь ли ты, ещё большой вопрос. А типовые задачи можно и в книжке посмотреть.
Если человек смог осилить алгоритмы это говорит о том, что он более менее умен, мотивирован и усидчив.
Но я не вижу прикладной их ценности. Это сродни олимпиаде по математике. И я полагаю, что как шахматы развивают только шахматы, то и алгоритмы только сами себя и развивают в мышлении. Но сложность программы не определяется этими самыми алгоритмами. В ПО Шатта вряд ли есть эти самые алгоритмы, а сложность этого ПО ужасающая.
Я где-то читал исследования, что люди играющие в шахматы значительно успешнее не играющих. Там было про уровень дохода и образования. Попробую найти вечером.
Как позиционируется — шахматисты развивают способность просчитывать и дисциплину. Для тех кто думает что это легко, попробуйте рассчитать хотя бы на 5 ходов вперед все возможные ходы на каждом ходе. Это несложно, но нужна самодисциплина.
Хотя я лично думаю, что люди играющие в шахматы уже заведомо были умнее других и росли в других условиях.
Да, в случае с шахматами — это явно отношение корреляции, а не причинности.
сколько ни пытался, не смог в них ни текст набрать, ни таблице посчитать
мозг только кажется универсальным, на самом деле — он точно такая же специализированная программа. Выдающийся пример — академик Фоменко. В математике — призер. В истории — писатель. Его специально хотели завалить, приходили на лекции с диктофоном, но он был умным — на своих лекциях о математике говорил только о математике (как я понял, разговор об истории на лекции по математике и мог бы послужить поводом для увольнения, как нарушение основных обязанностей в институте). Вот выдающийся пример интеллекта, который попутно породил целую ветвь лженауки в истории
Память точно не развивают. Проводилось исследование, в котором шахматистам разных уровней предлагали запомнить расположение фигур на доске. Если расположение фигур соответствовало какому-нибудь шахматному паттерну, профессионалы запоминали отлично, а новички — плохо. Если же расположение фигур было случайным, все уровни запоминали его одинаково плохо.
Тема развития определенных навыков и влияние этих навыков на все остальные аспекты жизни хорошо раскрыта в книге "Peak: Secrets from the New Science of Expertise". Автор книги является также автором исследования про 10000 часов, и в этой книге он объясняет, что популярная трактовка "10000 часов практики == профессионал" является неверной.
Если человек смог осилить алгоритмы это говорит о том, что он более менее умен, мотивирован и усидчив.
Если человек рассортировал вручную 1 тонну гречнево-рисовой смеси — это то говорит о том же самом.
Оба навыка, как было здесь не раз замечено, имеют весьма небольшую вероятность на применение в реальной жизни гуглокодера (про тривиальные отличия поиска в хэше от поиска в списке говорить не будем).
Глядя на лаги и тормоза хангаутса, джимэйла, да и андроида в целом, требующего 8 ядерного процессора, чтобы лончер минимально плавно листался, не нахожу подтверждения тезиса о большом внимании гугла и его кодеров к оптимизации алгоритма в своих изделиях.
А типовые задачи можно и в книжке посмотреть.Поэтому на собеседованиях любят динамическое программирование — оно, как правило, нарабатывается большим опытом. И, зная динамическое программирование, изобрести алгоритм Дейкстры можно, а вот наоборот — нельзя.
Я-то ведь чего спрашиваю? Эти алгоритмы подаются как первостепенной важности вещь. Но моя практика показывает, что они применяются в прикладном в очень ограниченных объёмах (если вообще применяются), а основная сложность ПО вовсе не в алгоритмах, а скорее, в архитектуре и обеспечении прозрачного взаимодействия десятков/сотен/тысяч компонентов.
думаю, как бы поизящнее и повыразительнее выражать запросы по AST и по data flow
Не знаю, какие именно запросы и как именно надо выражать, но вроде же в llvm есть встроенные средства для паттерн-матчинга по поддеревьям?
Программирование — это, во многом, искусство. Создание сложной сущности из ничего. Программист, подобно Творцу, создает упорядоченную вселенную из хаоса равновероятных единиц и нулей.
Некоторые части любого искусства могут быть формализованы.
Всегда есть пытливые умы, которые глядя на художника скажут: «ага! ты не просто творишь, братец! Ты делаешь два мазка слева-направо, а потом один вертикальный, и вот так вот подрезаешь!». Это научные работники, их хлебом не корми — дай понавыдвигать гипотез и научным методом потыкать прекрасное со всех сторон.
Когда толпа научных работников собирается вместе, самые правдоподобные гипотезы они признают теориями и записывают их в монографии, затем в учебники.
Таким образом, эти трудолюбивые жучки помогают превращению искусства в технологию.
Бизнесу плевать на искусство, ему нужна технология. Она даёт возможность привлекать к производству не только талантливых художников, но и индийских маляров за еду, что весьма позитивно сказывается на финансовой стороне вопроса (качество, по большому счету, никто никому не обещал, не просит и не ждёт).
Каждого новоприбывшего маляра нужно проверить, что он хотя бы в первом приближении маляр, знает какой стороной раму на холст натягивают и какой кистью куда тыкать, чтобы не сильно попортить материал.
Алгоритмы (и, например, паттерны) — это такие отехнологиченные кусочки искусства, формализованные общие места, странички Библии.
Естественно, проще всего (и быстрее!) проверить маляра, прогнав по общим местам технологии и ключевым символам веры.
Когда вместо маляра бизнесу на зуб по недоразумению попадается художник, оба остаются в легком шоке от методов друг друга, дальнейшая любовь — дело лишь счастливого случая.
Таким образом, незначительная часть ПО подается как суть всего исключительно за неимением другой, сколько нибудь формализованной, сути, а также в целях повышения эффективности (снижения издержек) бизнеса.
А человек, который докажет, что P = NP маляр или художник? Он же кроме алгоритмов ничего не знает.
А мяляр, который может снизить стоимость издержек для бизнеса в 10 раз, заменив 100 строчек кода достоин называться художником, или не очень?
А мяляр, который может снизить стоимость издержек для бизнеса в 10 раз, заменив 100 строчек кода достоин называться художником, или не очень?
Здесь год назад был человек с ником idot, так вот, он писал, что он как-то ускорил скорость корректного «чистого» кода (на паттернах и агалогичных вещах) с часу до 5 минут, выкинув все эти шаблонные компоненты. Это, я так понимаю, и есть художественный подход. А нехудожественный, надо полагать, описан в статье «архитектурные астронавты». :)
«Вы печатаете на клавиатуре заклинание, и вот экран дисплея оживает, показывая объекты, которых не было и могло не быть никогда
. Но если хоть один символ, один пробел в магической формуле не находится строго на своем месте, волшебство не работает.»
В сложной системе, если она сделана абы как, точно так же вы просто утонете в концепциях и взаимосвязях между объектами задолго до того, как проект вообще появится. А уж сколько интересных неучтённых ошибок вы получите на этапе отладки — это будет сказка. :) У меня тут есть коллега, решающий задачу автоматизации в лоб — я его программу загоню легко в состояние, в котором она начнёт делать с аппаратурой нечто невменяемое. Потому что он вместо общего заложил частности. Алгоритмов, кстати, это ПО не содержит — оно чисто автоматика.
P.S. Несмотря на то что я топлю за знание алгоритмов программистами у самого знания эти почти отсутствуют, как и в сфере которой приходится заниматься. За что кстати 1сников заслуженно часто ругают.
Это все равно что не понимать хотя бы примерно как работает железо, интерпретаторы, компиляторы, ос (не в деталях, а поверхностно хотя бы знать должны все, чтобы чушь не писать)
Плюс странно если нормальный программист не знает алгоритмов, ему же это должно быть просто интересно даже самому узнать.
Он не то, что не знает, он знает что можно делать и какие бывают структуры данных и чем они удобны. Это не значит, что он напишет балансировку дерева, но это значит, что он знает, что это можно сделать и это что-то даст при обходе дерева.
А интересны ему могут быть совсем не дебри теории стандартных алгоритмов. Алгоритмы всего лишь метод обработки каких-то данных и программа делается вовсе не ради этих алгоритмов. Вот решение задачи, для которой и писалась программа, и может составлять интерес.
Ну и конкретные задачи — задачами, но ведь всегда интересно что и как внутри устроено.
Ладно, ладно. Вот у вас есть сотовый? Вы знаете, что это — устройство с использованием радиоволн. А вот знаете ли вы методы модуляции, параметры антенны и сможете всё это реализовать? Очень сомневаюсь. А ведь вам, следуя такой логике, должно было быть интересно, как там оно внутри устроено. Но вот мне преподаватель по вакуумной и плазменной электронике как-то сказал на экзамене «Вы что, хотите понять все курсы? Это невозможно. Максимум — останутся в голове какие-то основы и обрывки». Так и здесь. Прочитал книжку — не факт, что даже понял методики и доказательства — но потребуется, можно найти реализацию и сделать. Так всё инженерное образование построено! Почему программисты должны быть другими?
Но, возвращаясь к ПО: в ПО кроме этих самых стандартных алгоритмов полно ведь других вещей — почему же нужно делать акцент именно на алгоритмах? Я полагаю, что на них свет клином не сошёлся.
А если интересно вообще множество вещей? Голова лопнет на этапе ухода в конкретику и нюансыНасколько я помню, в agile обычно считается, что лучше всего для работы подходит команда из «T-shaped» специалистов. Это такие специальные люди, которые знают все области средненько, а одну — очень хорошо. Исходя из такой логики, наверное, более или менее всем полезно поверхностное знание алгоритмов и структур данных.
Он обзывал меня с коллегой идиотами и тупыми, но понять, что происходит при введении подобной системы единиц и почему это получается он не способен даже с формулами.
Ваш математик явно неправильный. Правильные математики люди добрые и душевные, людей почем зря идиотами не называют.
Мне кажется я как раз в своем комменатрии вам этот секрет и открыл. Изучение алгоритмов, на мой взгляд, нужно в первую очередь для тренировки мозга. Если вы внимательно прочитаете мой комменатрий, то найдете там фразы вроде такой:
При том что алгоритмов я, наверное, не вспомню по памяти вообще ни одного уже.
Что, впрочем, не совсем правда, забыть бинарный поиск нужно сильно постараться например.
Это, конечно, не значит что алгоритмы сами по себе не нужны — вам накидали множество примеров где они таки нужны. Но в случаях когда нужен алгоритм достаточно уметь это заметить и уметь алгоритм найти. А вот тренированный мозг, который может заметить потенциальную проблему и быстро накидать корректную абстракцию вы на SO уже не найдете. Я этот мозг использую буквально каждый день и очень хорошо вижу разницу с теми, кто алгоритмы и структуры данных всякие не изучал. Время объяснения потенциальной проблемы, например, просто кратно отличается.
Это, конечно, не значит что алгоритмы сами по себе не нужны — вам накидали множество примеров где они таки нужны.
Вот именно, что накидали примеров того, где они нужны. А я разве примеры спрашивал? Я спрашивал вполне конкретную вещь: откуда у вас всех акцент именно на алгоритмах? Я на 100% уверен, что могу поставить задачу вам такую, что вы ни разу не используете ни одного стандартного алгоритма, но при этом задачу провалите полностью и утонете в абстракциях и взаимодействиях между компонентами, просто потому, что никогда такого не делали. Вот подобная задача:
1) Имеются три вычислителя, объединённые шиной CAN.
2) Каждый вычислитель имеет четыре процессора, соединённых в звёздочку через двупортовое ОЗУ.
3) Первый процессор подключён к первой шине CAN, второй ко второй, третий к третьей. Четвёртый является DSP и реализует математическую модель и является центром звёздочки. Вычислители соединенты по первой шине. Вторая идёт на обмен с рядом устройств. Третья тоже идёт на некие устройства.
4) Одно из устройств на первой шине управляет электропитанием всех компонентов системы (и вычислителей). Все устройства вне вычислителей троированы.
5) Имеется система тактирования с частотой 32 Гц. Это — системный такт обмена и по результатам обмена производится вычисление модели в заивисимости от команд по магистральному последовательному интерфейсу.
6) Модели нужно около 27 кБ ОЗУ для расчётов и буферов. Скорость CAN не позволит передавать такой объём в каждом такте.
7) Первые процессоры подключены к магистральному последовательному интерфейсу.
8) Каждый момент времени работает только один вычислитель. Второй в горячем резерве. Третий в холодном (выключен).
9) Имеются два программиста. :) Удачи им в написании ПО с резервированием отказов компонентов (отказать может любой. Перезагрузиться, кстати, тоже — время штатной работы исчисляется годами. Потеря связи — запросто. Зависание — легко. Отказ — это когда перезапуски не помогают восстановить управляемость) и синхронизацией данных между вычислителями (с запоминанием того, что вообще делает устройство в данный момент и чем заняты компоненты комплекса и математическая модель). Ах да, язык — Си99.
Вот такое я понимаю — это у меня тут типовая задача. Возможных ситуаций, которые должна отрабатывать программа — до фига. И алгоритмы в решении никак не помогут.
Фух. :)
До 2005 года я любил писать разные простые игровые и прикладные программы и баловался с 3D-графикой. В 2005 мне пришлось начать работать с аппаратурой. И оказалось, что мышление тут потребуется изменить.
Выделение абстракций, построение структур данных и разработка алгоритмов должны быть ровно такими же. Если вам потребовалось изменить мышление, то либо вы не понимаете о какой части мышления я говорю, либо вы не владели этими навыками до того как занялись разработкой на аппаратуре.
Отсюда я заключаю, что тренировка мозга гораздо больше связана с анализом и решением возникающих нестандартных ситуаций, а вовсе не с запоминанием и пониманием стандартных алгоритмов.
Нет, вы определенно не прочитали мой комментарий на который ответили. Приведите мне мою цитату где я говорил про запоминание стандартных алгоритмов. Про понимание еще можно за уши притянуть, я его хотя бы не отрицал явно в комментарии, но если разобраться, то и про понимание я ничего не говорил. Я говорил про опыт работы с разными алгоритмами, с разными структурами данных и про опыт применения этого всего. То есть именно что с
анализом и решением возникающих нестандартных ситуаций
А еще вы сначала жалуетесь что вам накидали практических задач, а вы просили не это, а потом пишете мне практическую задачу и просите меня ее решить. Вам не кажется что вы несколько сами себе же противоречите в ваших желаниях?
Если вам потребовалось изменить мышление, то либо вы не понимаете о какой части мышления я говорю, либо вы не владели этими навыками до того как занялись разработкой на аппаратуре.
Я говорю о архитектуре приложения. О методах работы.
Я говорил про опыт работы с разными алгоритмами, с разными структурами данных и про опыт применения этого всего.
Я уже в сумме раз пять каждому написал, о чём мой вопрос. Зачем вы пытаетесь отвечать на придуманный вами самими вопрос? Ну вот зачем? Я нигде не говорил, что не нужно хотя бы прочитать стандартные алгоритмы. Я спрашивал, почему вы их поставили на первое месте в разработке ПО. И только.
То есть именно что с анализом и решением возникающих нестандартных ситуаций
Ситуации, описанные в книжке, по которой вы изучали алгоритмы, уже являются стандартными.
А еще вы сначала жалуетесь что вам накидали практических задач, а вы просили не это, а потом пишете мне практическую задачу и просите меня ее решить. Вам не кажется что вы несколько сами себе же противоречите в ваших желаниях?
Да нет, же. Я вам просто показываю, почему алгоритмы не являются пупом Земли. Я не говорю, что их и читать не стоит. Я говорю, что оценивать разработчика по знанию конкретного алгоритма и просить его всё это реализовать тут же на доске есть просто глупость.
Я говорю о архитектуре приложения. О методах работы.
А я говорю о навыке построения абстракций и умении работать с алгоритмами.
Я спрашивал, почему вы их поставили на первое месте в разработке ПО.
Так покажите мне где я их поставил. Это не я пять раз отвечаю на неправильный вопрос, это вы не удосужились прочитать мой комментарий ипросите от меня чего-то вами же придуманного. Был вопрос:
Ох… стоит ли оно того? если такие знания потом на практике не использовать — выветриваются быстро.
Я написал почему стоит. Как вы из этого сделали вывод что я считаю изучение алгоритмов самым важным в разработке ПО для меня — загадка.
Ситуации, описанные в книжке, по которой вы изучали алгоритмы, уже являются стандартными.
Опять вы приписываете мне то, чего я не говорил. Покажите мне мою цитату из которой следует что речь идет только о книжках. Или все задачки которые опубликованы на массе сайтов — они тоже автоматически становятся стандартными? В самом посте тоже, между прочим, описывается что просто прочитать книгу недостаточно.
Я вам просто показываю, почему алгоритмы не являются пупом Земли. Я не говорю, что их и читать не стоит. Я говорю, что оценивать разработчика по знанию конкретного алгоритма и просить его всё это реализовать тут же на доске есть просто глупость.
Из первого второе не следует. Алгоритмы — да, это не пуп земли. Но умение с ними работать говорит о том, что у программиста тренированный мозг, а обзор того как программист решает исскуственную задачу на доске дает данные для того чтобы предсказать как этот программист будет работать. Не самый совершенный способ, часто может отсеивать хороших программистов, но в условиях избытка желающих, как у гугла, очевидно работает.
Впрочем вы можете попробовать опказать логическую цепочку как из первого вашего утверждения:
алгоритмы не являются пупом Земли
следует второе:
оценивать разработчика по знанию конкретного алгоритма и просить его всё это реализовать тут же на доске есть просто глупость.
Если оно будет логично и связно, то я готов признать вашу правоту. Но я сомневаюсь что это возможно, потому что мои наблюдения говорят об обратном.
То есть вы считаете, что это — типовая задача для разработчика, а веб/мобильное, любой клиент-сервер, любой комилятор/интерпретатор — нет?
по некоторым обстоятельствам семейного характера
Как Вам удается совмещать семью-работу-обучение? Просто я никак не могу найти этот баланс, только два из трех получается совместить. :(
Но как вы сами понимаете, такое возможно только на ограниченном отрезке времени.
Например сейчас, с появлением третьего ребенка я бы уже так не смог.
Тут, говорят, диды по 15 детей рожали, успевая при этом гектары перепахивать на сивой кобыле.
График был: с 3:30 до 17:00, обед в том же поле (без смузи).
Такие дела.
Но это не наше детство… ;)
Где-то была статья про таджиков (100 чего-то там про Таджикистан), так у них ребёнок к колыбели привязывается как-то (без подушки под головой), снизу пакетик, а сами в поле.
Ничего, скоро вырастут и попереженятся, и Вы опять со сверспособностью найти время.
У меня четверо от 7 до 15, время на учёбу вроде находится, но потом смотришь как всё кругом запущено, и вот уже и нет его...
Вообще это можно сравнить со спортом. Например, я бегаю по утрам. Пригодится ли мне когда-то умение бегать? Возможно нет. Повысит ли это мою выносливость в целом? Скорее да.
Здесь вполне возможна ошибка выжившего ("не выжившего", да). То есть неизвестно сколько там разработчиков с такими проблемами в текущей системе. Гугл же огромный, очевидно что любая система будет иметь проблемы время от времени. Собственно раз они придерживаются таких собеседований, значит либо это в целом работает и ничего лучше они придумать не смогли. Ну или не смогли ввести в работу, я подозреваю что из-за величины компании бюрократия там процветает.
Я замечал что выбрасыванием результатов (пусть даже интересных) можно людей подтолкнуть к увольнению гораздо быстрее, чем скучными задачами, которые однако идут в продакшен и использутся.
Чувство собственной нужности и полезности (пусть даже лишь как отдельного винтика в крупной корпоративной машине) людям нужно.
Вы удивитесь, но "не показывать" можно далеко не только бардак. И между "оформить разрешение на посещение с камерой" и "позвать выйти на улицу" тоже как бы разница есть.
А зачем бибиси платить большие деньги за разрешение на съемку в офисе если можно снять на лужайке? А может им вообще было важно именно в таком формате снять, чтобы не отвлекать от интервью рекламой офиса гугла. Тысячи причин могут быть чтобы сделать именно так.
Это не так.
Система как раз отстроена на наем крепких середняков (ну и плюсом — мы лучше отсеем хорошего девелопера, чем пропустим плохого) — гении в энтерпрайзе сильно не нужны, а если и нужны на какие-то конкретные узкие места, их хантят отдельно.
А логика такая что если человек способен к собеседованию чуть разобраться в базовых алгоритмах — можно брать, легаси точно потянет.
Нет, далеко не олимпиада — задачки где-то на уровне leetcode'овского medium, ничего сверхъестественного там нет. Интервью на дизайн тоже ничего сложно не представляет из себя если есть какой-никакой бэкграунд в похожем технологическом стаке. Плюсом оценивают пресловутую коммуникабельность и прочие софт-скиллы. И как тут уже заметили таки да, команду можно выбирать + internal mobility работает очень хорошо. Есть даже внутренний стартап-инкубатор где с бюрократией сильно проще чем в среднем по больнице, и туда также постоянно нужны люди, как и в другие проекты.
многие не согласятся, потому что
— строка в резюме почетная
— знакомства с новыми людьми из крутой компании
— хорошие бонусы
— возможность клевой релокации
— после такой работы чувствуешь себя реально опытным бойцом
Почему-то, есть стереотип, что для устройства в Гугл нужно мастерски знать алгоритмы, на уровне олимпиадных чемпионов, а о практических, или системных вещах можно забыть.
Я вынес свои принципы после собеседований:
- Медленное рабочее решение лучше быстрого, но плохо работающего. Решение за экспоненциальное время, лучше, чем решение, которое должно было бы работать за линейное время, но работало через раз.
- Большинство задач даётся в «открытом» виде, без полного набора критериев и требований. Так что, считается хорошим тоном «Будет ли этот код запускаться в нескольких потоках?», «Есть ли какое-то ограничение по памяти?», «Будет ли это приложение кроссплатформенным?», «Это полностью решается классом X из java.util.concurrent, можно ли использовать его?»
- Ну и, конечно же, комментировать. «Тут нужно отлавливать NPE», «Этот код не будет потокобезопасным, если бы нужен был потокобезопасный код, то я бы использовал метод Б»
Как-то так. Я хорошо ответил на алгоритмические и архитектурные вопросы и так себе на объектно-ориентированный дизайн, в итоге сейчас пишу эту простыню из Цюриха.
В вашем случае звезды сложились, в моем нет )
Можете привести пример из первого пункта? Вы имеете в виду имба-задачи как Traveling Salesman, которую разные гении начинают оптимизировать путем "а давайте брать ближайшую незанятую точку и идти туда"? (Хотя тут уже все перекопано и есть эвристичестие решения, которые ошибаются на 0.05% от идеального-преидеального варианта)
Просто если человек решал много задач, у него отпечатывается "неполное решение = вообще не решение", то есть если код не прошел даже самый крайний corner case — может идти лесом.
Просто если человек решал много задач, у него отпечатывается «неполное решение = вообще не решение», то есть если код не прошел даже самый крайний corner case — может идти лесом.
— мне кажется, от этой привычки избавляются уже после первых месяцев работы и начинают понимать, когда нужно исчерпывающее решение, а когда достаточно сделать всё «в первом приближении».
Бывший коллега как-то уехал в одну московскую крутую компанию(имя называть не стану), прошел все круги ада собеседований, что только у него не спрашивали, один из вопросов вообще был «а как вы оптимизировали бы решето аткина»(сам завис, через 10 лет после окончания вуза такие вещи вообще не вспомнишь если не применяешь, а вероятность применения близка к нулю), и в результате коллегу взяли и за три года работы по его словам он не применил ничего о чем спрашивали на собеседовании включая почти всех кто сидел в их здании. От лукавого все это, от лукавого.
И на сколько я слышал от многих знакомых такая фигня с собеседованиями только у гугла, остальные не доходят до такого маразма с требованиями, особенно когда понимают что гонять по алгоритмам фронтенд разработчика это глупость.
Надо же как-то фильтровать миллионы желающих работать в Гугле. Все примерно знают одинаково технологии. Остаётся заставлять решать задачки.
Бывший коллега как-то уехал в одну московскую крутую компанию
Тут нету крутых компаний. Яндекс что ли?
А что такое крутая компания? Вот если положив руку на сердце — чем для среднестатистического разработчика Гугл отличается от многих других компаний, даже региональных, кроме громкого имени и клевой записи в резюме? От того что компания «крутая» и распиаренная не говорит что именно вам придется там заниматься чем-то действительно интересным.
А потом погроммист проходит в Google, резко прыгает к вершине пирамиды Маслоу и начинается выпендреж: "5 строк за год всего лишь послал", "Ну вот в деньгах не факт что больше чем во многих других компаниях"...
А вы посмотрели, что там по уровню жизни в Цюрихе?
А что там с уровнем жизни? Вроде бы все замечательно. Цены ниже чем в долине, зарплаты не то чтобы сильно ниже если вообще. Рядом в 15 минутах езды на машине есть масса городов с заметно более низкими ценами. Впрочем сам я там не жил, только по рассказам знакомых говорю, могу и ошибаться.
а работа в гугл реально стоит такого гемора?Полтора года (это с нуля, я так понял, а так было бы быстрее) интересных занятий, общеразвивающих для мозга, ради того, чтобы получить навыки, позволяющие без проблем получить оффер практически в любой интересующей тебя компании? Плюс, если все-таки пойдешь в Google, строчка в резюме, благодаря которой на тебя будут смотреть не так, как на «еще одного иммигранта»? Ну даже не знаю.
Да мне особо никто не сообщал, на кого именноЭто известная проблема, пока сам не спросишь, не колются. Я спросил в конце онсайта, когда было уже поздно менять, и был удивлен, что меня с без недели пятью годами опыта и текущей строчкой в резюме «Senior в Deutsche Bank» собеседуют на джуна.
Буквально сегодня общался с рекрутером из Google, правда они сами меня нашли. Так же предлагают Цюрих.
На следующей неделе будет первое техническое интервью, тут даже больше интересно попробовать и проверить себя.
Сам рекрутер звонил из Лондона, общались через Hangouts и это действительно было не очень, частые фризы, рассыпание картинки и заикания звука.
В Google тоннами шлют свои биографии со всех стран мира. Шанс что рандомное резюме пробьется, равен std::numeric_limits<double>::epsilon(). Из каждого утюга пишут, что не шлите через сайт pdf, отправьте через знакомого, иначе вам придет "привет, досвидания" автоматом.
Логика такая, что если формочки там клепает overqualified профессор компуктерн саенс, прошедший отбор 1000 человек на место, то пусть это и будет профессор, который к тому же еще точно знает, что в начало списка добавлять миллион элементов по отдельности вредно, а не какой-то рандомный во всех смыслах парень.
Выше вы же писали про $300-400к в год для сеньора. Клепатель формочек получает за троих сеньоров, что ли?
за гроши? в лос аламосе?
Ну, с какого-то момента это перестает играть большую роль. И по моим ощущениям люди которые уходят в науку в этом плане изначально проще к деньгам относятся, им важнее то, чем они занимаются чем то, сколько за это платят (в разумных пределах естественно).
Ну это и не отличается как-то существенно от зарплаты сениоров в Сан-Франциско:
немного выше, но все таки сениор — это как раз, наверное, аналог full professorship, а не associate.
Да, вы сейчас скажите про всякие бонусы с опционами — но профессора точно так же на грантах сидят.
Как видно, просто зарплата сениора и джуниора не сильно различается (всего 30%).
В любом случае, какого-то вывода о том, что в науке меньше платят, из этих данных сделать нельзя.
Мир вообще штука несправедливая.
Я пока вижу, что подавляющее большинство окружающих меня людей с готовностью выкладывают несколько сотен долларов за новый телефончик, но отнюдь не готовы и десятку пожертвовать на научные исследования. А значительная доля так вообще считает ученых бездельниками и верит в плоскую землю.
Ну а то, что куча сделанного выбрасывается в корзину не говорит ни о чём — общество с готовностью оплачивает и эту корзинную деятельность.
После окончания курсов я осознал, что многие знания это многие печали. Если раньше я просто знал, что ничего не знаю, то теперь начал осознавать, что именно я не знаю.
so true. Чем больше материала изучаешь, тем больше знаешь о том, чего не знаешь.
автора можно похвалить за настойчивость и трудолюбие,
2 года готовится к экзаменам это подвиг, серьезно.
Но если подавать заявку в Гугл на разработчика Андроид, то как бы нужно 90% времени читать документацию Андроид! Ведь работа будет связана либо с разработкой/оптимизацией фрагментов новых/старых версий Андроид, либо с реализацией сервисов Гугл на Андроид, не так ли?
У Вас ведь спрашивали именно документацию Андроид
«А дальше начались несколько неожиданные вопросы в духе «а что в классе Х делает метод У»»
Со стороны автора рассказа все выглядит как детский сад, Вы просто отняли время у Гугл, играли в игру «собеседование в Гугл», явно не желая получить положительный результат и работать в Гугл, а просто хотели приключений.
И еще раз, 2 года подготовки вызывают уважение.
Так написано: "работа будет связана либо с разработкой/оптимизацией фрагментов новых/старых версий Андроид, либо с реализацией сервисов Гугл на Андроид", то есть и Android-разработчик, и разработчик Android.
Можно подозревать что сил на разработку всего Android, т.е на оболочку, API, свистелки, сервисы типа Google Play тратится несоизмеримо больше сил, чем на создание клиентов приложений на всем готовом, то есть в сорцы нырять пришлось бы все равно. Точно ничего не утверждаю, в Google не работал Android-девом, где-либо еще тоже.
Может, они искали по случаю пацана, который упоролся и выучил наизусть исходники Android API, и сэкономит время команде. И не прогуливал универ, чтобы рассказать как хэшмап работает.
Так же я упоминал в статье, что да, рекрутер мне озвучил то, что будут вопросы с андроид спецификой, но не смог привести пример.
Т.е. готовился я играть по одним правилам, а когда сели за стол, то правила слегка поменялись.
А неожиданность вопросов не в том, что они по андроиду, а в сути. Ну не уровень это гугла, спрашивать, что какой метод делает. А особенно как. Т.е. был вопрос, что написано внутри метода. Может я его 3 года назад смотрел, а они там код переписали.
Интересно, интервьюеры как-то представлялись?
интервьюеры как-то представлялись?Обычно кратко представляются, вроде «привет, меня зовут Алекс, я из команды Android Z»
Ну не уровень это гугла, спрашивать, что какой метод делает. А особенно как.Ну это смотря как сформулировать и как оценивать ответ.
Меня вот в одной компании спрашивали «как реализован std::distance?» Я ответил, что впервые такое название слышу. Интервьювер сказал, что это функция, которая выдает расстояние между двумя итераторами и спросил, как бы я ее реализовывал — ну я и рассказал, как бы я это делал, со всякими std::enable_if, с обсуждением того, логично ли выдавать отрицательный ответ, если на вход даны два RandomAccessIterator в неправильном порядке, и тд. По-моему, неплохой вопрос получился.
Ну и довольно сильно мотивирует на учебу и новые знания, спасибо.
— Напишите нам код на доске.
(Начинаю писать код, исписал доску)
— Ой, знаете, а у нас тут хромбук есть, но я им как-то никогда не пользовался. Хотите?
-Нет, спасибо, давайте не будем отвлекаться
Опять же, хромбук поюзать можно, но писать-то придется в гуглодоке. IDE никто не даст.
Возможно, в других офисах ноутбук действительно предлагают.
Писать код на доске неудобно хотя бы тем, что за долгие годы практики руки привыкают набирать открывающую и закрывающую скобки одновременно, парой, и никак иначе :)
А чем плохо код на доске писать?
Я, например, с детства ненавижу писать на доске. Меня напрягают следующие вещи:
1) надо писать от руки (пишу медленнее раз в 10-20, чем набираю)
2) надо писать от руки на вертикальной поверхности, мне это тупо в разы неудобнее, чем на горизонтальной
3) мало места, мелкими буквами писать не люблю и выйдет ещё медленнее чем нормальными
4) нужно постоянно отходить чтоб окинуть взглядом написанное
5) волнуюсь, оказавшись перед доской под чьим-то пристальным взором, будто в школе будто опять очутился (учился там хорошо, но у доски всегда нервы)
Ох нет. Помнится, в Яндексе мне как-то раз попался один наглухо упоротый интервьювер, требовавший «чтобы вообще вот без ошибок было».
Вы же не прошли? Ну и радуйтесь, не придется с ним работать :)
Да и в целом, в процессе работы на хоть сколь-нибудь сложным алгоритмом с множеством граничных случаев, этих «стрелочек с кружочками» в итоге может стать столько
Я вот не помню задачек из собеседований, которые существенно больше пары десятков строк кода требовали. И если при написании этих строчек у кандидата мешанина на доске, то это тоже звоночек.
Я вот не помню задачек из собеседований, которые существенно больше пары десятков строк кода требовали.
К этим 20 строчкам еще надо алгоритм привести, из алгоритма на все 200.
На алгоритмическом интервью вы должны просто написать код и дать к нему устные комментарии. Объём кода, который ожидает увидеть собеседующий обычно очень невелик (и вряд ли требует более 5 минут на собственно написание). Сколько вы при этом наболтать успеете — дело добровольное.
Что значит «еще надо алгоритм привести»? Кому и куда его приводить надо?
Ну вот вы написали алгоритм "влоб", получилось 200 строк. Его, конечно, можно переписать за 20. Но надо еще переписать.
Сколько вы при этом наболтать успеете — дело добровольное.
Ну при чем тут наболтать? Вы еще предложите в уме интегралы брать.
Человек придумывает алгоритм, по ходу дела пишет код. Естественно, что если человек наперед не знает алгоритма, код будет сильно неэффективен. Не в плане оптимизаций (хотя частично и в них) но именно в плане выразительности.
Естественно, что если человек наперед не знает алгоритма, код будет сильно неэффективенНет, это неестественно. Нормальный разработчик сначала немного подумает, а потом начнёт писать. Идеального кода сразу, конечно, не получится. Но и разбухания в 10 раз не будет.
Нормальный разработчик сначала немного подумает, а потом начнёт писать.
Естественно, однако продумывать имеет смысл в общих чертах, далее уже следует фиксировать то, что придумано (и это на самом деле может быть далеко до результата) и инкрементально идти к результату. Разработчика, который зачем-то пытается чисто в уме досконально алгоритм продумывать, я бы назвал, как минимум, странным.
Но и разбухания в 10 раз не будет.
Ну насчет 200 строк я все же утрировал, да, но раза в 3 — вполне себе. И если 20 строк — это тьфу, мало, то 60 для рукописного кода — уже ощутимо.
Да и вообще, с-но, писать код сперва "чтоб работало" и уже потом его причесывать — это стандартная практика, согласитесь.
Кроме того, задачи для собеседований нарочно выбираются так, чтобы простыни кода там не понадобились; скорость письма/набора при их решении — вообще не фактор успеха.
Кроме того, задачи для собеседований нарочно выбираются так, чтобы простыни кода там не понадобилисьПопробуйте написать на доске (да даже и на бумажке) код для Андроид. Например Activity + AsyncTask + TextWatcher + пару побочных классов типа таймера. И снабдить это минимальной бизнес логикой.
И вы неприятно удивитесь размеру )
В письмах с ходу не нашел, но есть такая строчка
«Be sure to test your own code and ensure it’s easily readable without bugs.»
Для кого-то баг это ошибка в алгоритме, а для кого-то пропущенная скобочка.
Из всех трат Google напрямую оплачивает только билеты. Отель, еда и проезд оплачиваются кандидатом.
Как-то подозрительно, раньше точно так не было. Даже 2 года назад так вроде не было. Бронируют отель и самолет, за еду потом можно по чекам получить.
Мне кажется, что вы зря пытались пройти именно на Android разработчика. Во-первых, это, имхо, одна из самых неинтересных вещей, которыми можно заниматься в Google. Во-вторых, проще пройти как SWE и потом уже трансфериться, если уж очень хочется именно в Android.
Ну и хочу добавить, что интервью — это несколько рандомный процесс и методы оценивания и вопросы некоторых людей являются, мягко говоря, неоптимальными (и не следуют гайдлайнам. какой нафиг код на System Design?)
А то что процесс рандомный я уже понял. Если бы было время — может еще бы покидал кубик, но не сложилось.
Как-то подозрительно, раньше точно так не было. Даже 2 года назад так вроде не было. Бронируют отель и самолет, за еду потом можно по чекам получить.
Отель не оплачивают в том случаи, если ни в одном из отелей с которыми есть договоренности нет свободных мест. Такое бывает если о собеседовании договариваться почти в последний момент, либо в это же время было какое-то крупное событие (например для Швейцарии это может быть сезон зимних видов спорта).
Проезд внутри страны и еда компенсируются дейсвительно по чекам после.
В целом считаю что лучшее что вы с этого получили это знания в процессе подготовки.
Но ничто не мешает развиваться почти также и без подготовки куда либо, а просто по фану и наличию свободного времени. Тогда и собеседования в такие компании не будут проблемой, слышал (точнее видел интервью с ними) как люди с первого раза проходили чуть ли не в любую компанию.
Сам в алгоритмах не силен, просто прочитал пару книг, и иногда напоминаю себе что и такое бывает :)
Пробовали общаться через Hangouts, но качество было ужасное, поэтому переключились на телефон.Подход к подбору кандидатов явно требует перемен. Относится и ко многим российским компаниям.
Подход к подбору кандидатов явно требует перемен.
Так если они хотели видео звонок, то не по скайпу же HR'у гугла организовывать, над ними потом весь инет смеется будет. К тому же качество могло проседать на стороне кандидата, тут ничего не сделаешь, какое программу видео-звонков не бери, кроме как перейти на телефон.
Hangouts (именно как видеоконференция) весьма достойно работают (исходя из моего личного опыта конечно). Я постоянно делаю конф-коллы с друзьями, очень нравится то, что не нужно каких-то специальных телодвижений делать — просто кидаешь ссылку и человек тут же присоединяется к конференции (гуглоаккаунт нужен, да, но он почему-то есть у всех без исключения моих знакомых) — не нужно ничего устанавливать и где-то помимо гугла регистрироваться. Если начинаются фризы/лаги — это обычно из-за качества соединиения (а скорее из-за кривой маршрутизации) на той или другой стороне, выключаешь hd и все становится лучше.
Есть еще интересный факт — hangouts официально ПО для видеоконференций внутри гугла (https://www.blog.google/products/g-suite/how-google-went-all-video-meetings-and-you-can-too/), а это значит что сами гугловцы отбивают десятки тысяч видеоконференций в день, соединяя зачастую офисы в разных городах и странах.
Я обычно ничего не спрашиваю на собеседовании, если мне и так все понятно. Предоставляю возможность человеку самому рассказать о себе (задолго до собеседования, с помощью научных публикаций, патентов, GitHub, блога, etc).
Мне кажется есть два подхода:
- нанять человека здесь и сейчас если точно известно что он делал тоже самое и делал это хорошо,
- нанять лучшего человека из очереди аппликантов, не важно по какому критерию (можно по IQ, можно по вызубренным алгоритмам)
Какой конкретно подход наверное зависит от самой компании (например очень большие компании имеют бесконечную очередь желающих туда попасть) и области о которой идёт речь (в hardware например имеется куда более глубокая специализация, и часто требуется человек с конкретным skill set и опытом)
Так как подаваться через сайт дело достаточно гиблое, занялся поиском знакомых, работающих в Google.
Мне года четыре назад написал рекрутер из Google на Linkedin, но я ему честно сказал тогда, что проходить собеседование не готов. Просил стажировку, — к сожалению, мест не было. Договорились, что буду готовиться и потом сам свяжусь с ним. Проконсультировался у aml на счёт необходимой глубины знаний в python, но решил, что не готов.
Этой весной, занимаясь подготовкой инфраструктуры для повторного прохождения QSA-аудита для получения сертификации PCI, выяснилось, что у k8s с этим всё очень плохо. Немного подумав, я решил, что если и заниматься k8s, то лучше сразу в Google, о чем и было написано в сопровождающем письме к отклику на вакансию SRE через careers.google.com.
Через несколькой дней позвонил HR с просьбой подтвердить намерения, позадавал уточняющие вопросы (в какой офис хотите? и т.д.), после чего прислал письмо со ссылкой на google calendar, где необходмо было выбрать удобный мне слот для первого телефонного интервью.
В процессе поиска информации о формате данных интервью, я натыкался на типичные вопросы, которые там задают… и назначил интервью через 4 дня, решив, что если не смогу пройти первичную отсеевалку, то явно мне дальше делать нечего. Звонок прошёл хорошо, и меня попросили зарегистрироваться на Coding Coaching Session, для подготовки ко второму телефонному звонку.
На CSS было человек десять: трое не досидело до середины, уточняющие вопросы задавали очень вяло.
Смысл CSS ровно один — у них есть анкета, которую заполняет интервьювер по ходу собеседования и чтобы умозаключения более последовательные, а оценки о них более приближенны к реальности — есть манифест о том, как надо себя вести.
CSS прошёл, написал письмо.
Назначили нового HR из Сингапура.
Начал звонить первый HR и спрашивать в каком офисе я хочу работать и когда можно назначить дату телефонного звонка. Ок, накладочка вышла.
Я уезжал в отпуск в Европу, о чем уточнил в письме, поэтому второй звонок назначили через неделю.
Готовиться к интервью с особым усердием я не стал, посмотрел несколько типовых задач, да и только.
Во-первых, вместо обещанной сессии по программированию на 45 минут, я получил сессию по nix internals & programming.
Минут через 10 после начала разговора, когда мы еще не с головой залезли в дебри файловой системы, я уточнил что ожидал вообще-то сессии по python. "Сорян", — сказали с той стороны монитора, и пообещали отметить это в анкете.
30 минут мы общались по теории, после чего перешли к практике.
Сначала я и второй рекрутер не видели текст задачи, потому что основной интервьювер писал не в тот документ, после чего у меня отвалился интернет: 10 минут драгоценного времени потрачены зря, но резервный канал под боком и едем дальше: пытаемся обсудить как можно хранить и процессить данные по задаче. Ок, договорились — наконец-то начинаем писать код… на 45 минуте.
И тут же первая (и последняя) сложность:
— Я не знаю какие параметры принимает функция (из стандартной библиотеки) и что она возвращает
— Да мы тоже не знаем, в гугле стандартную библиотеку не юзают, у нас все своё
— Эээ, давай откроем документацию?
— Нет времени, пофантазируй
— унылая_двухминутная_фантазия_о_возможных_методах_и_функциях.jpg
— Время закончилось
Фидбэк за второй звонок: solid knowlege за unix internals и "больше фокусируйтесь на программировании" за вторую часть.
HR уточнила согласен ли я с оценками, на что я ответил: согласен, ведь задача не решена, но организация интервью была очень странная — я так и не понял чего я не знаю и как готовиться дальше (ха-ха!). "Я ж вам присылала список литературы для подготовки… не получали? Странно."
В итоге могу сказать, что каких-то откровений не увидел, обычный собес и обычный человеческий фактор.
Просто компания очень большая, и людей, которые собеседуют, и которые собеседуются — очень много, поэтому не все с первого раза заходят на нужный круг.
Собственно, именно поэтому так много и горят по негативу: много месяцев готовился, а попал на интервью к бро, который не очень хорошо интервьюирует.
Мне кажется, ничто не демонстрируют все будет нынешних принципов найма в IT, чем подобные статьи.
Люди готовятся не к решению практических задач на работе, а к прохождению интервью.
Что предложите нанимателям вместо таких собеседований?
А что, кроме как "напишите бинарный поиск на доске" и "скажите, какая сложность у сортировки пузырьком" больше вопросов не бывает? Не, ну серьезно?
Почему бы не взять какую-нибудь реальную таску, решение которой не сильно завязано на особенности внутренней архитектуры вашего проекта, и не отревьюить вместе с кандидатом?
Заодно и он посмотрит, с чем работать будет. В реальности, а не "мы предлагаем интересные задачи".
А что, кроме как «напишите бинарный поиск на доске» и «скажите, какая сложность у сортировки пузырьком» больше вопросов не бывает? Не, ну серьезно?
На собеседовании в Гугле вопросы совсем не такие. Не на заучивание алгоритмов, а на их творческое применение.
Почему бы не взять какую-нибудь реальную таску, решение которой не сильно завязано на особенности внутренней архитектуры вашего проекта, и не отревьюить вместе с кандидатом?
Во-первых, чтобы не показывать кишки непубличных проектов каждому встречному. Во-вторых, потому что в компаниях размером даже в 1/10 Гугла любой проект будет завязан на стотыщ внутренних сервисов, и одно только объяснение «чем мы здесь пользуемся» займёт дольше, чем само ревью.
В сайтоклепательной конторе из десяти человек подход к найму, конечно, будет другой, чем в Гугле.
На собеседовании в Гугле вопросы совсем не такие. Не на заучивание алгоритмов, а на их творческое применение.
Судя по тому, что написано в статье, человек готовился скорее именно к простому заучиванию алгоритмов. Курсы проходил, задачки решал.
Гугла любой проект будет завязан на стотыщ внутренних сервисов, и одно только объяснение «чем мы здесь пользуемся» займёт дольше, чем само ревью.
Да никогда не бывает такого, что нету таски, в которой не завязано совсем на все. Если у вас таких нет — значит совсем уж говнокод, да.
И, опять же, если человеку не будет все понятно — то первые же три заданных им вопроса о его квалификации скажут больше, чем пятичасовые тесты на выпрыгивание из миксера при помощи алгоритма Дийкстры.
А вот решение задачек это как раз творческое их применение. Откройте например Hackerrank и возьмите задачу пусть даже не Expert, а Hard. С 95% вероятностью вы не найдете стандартного алгоритма для ее решения. Решение будет состоять либо из модификации стандартного алгоритма, а для этого надо понимать, что у него внутри, либо из комбинации стандартных алгоритмов, причем комбинации не самой очевидной.
А вот решение задачек это как раз творческое их применение. Откройте например Hackerrank и возьмите задачу пусть даже не Expert, а Hard.
Так большинство этих задач, с-но, и есть на знание того, как их решать. Точнее — на применение вполне конкретных и часто довольно-таки специфичных приемов, которые надо для решения просто тупо знать.
Опять же, задача обычно разбивается на подзадачи. Каждую из них можно решить каким-то способом. Была вот одна интересная Hard задачка. Там в одной из ее частей надо было делать RangeMinQuery. Стандартная вещь, даже банальная, но ни один из четырех опробованных вариантов не прошел по скорости, так как это было «узкое место» в задаче. В итоге после пары часов раздумий придумался вариант, использующий еще более банальные prefix sum, но сделанные очень нестандартным способом. И взлетело. Помогло ли мне знание стандартных алгоритмов? Скорее нет. Помогли ли мне навыки решения задач с их использованием? Да, я смог взглянуть на проблему с разных сторон, примерить разные решения и найти верное, пусть и не очевидное.
Стандартная вещь, даже банальная, но ни один из четырех опробованных вариантов не прошел по скорости
Вот это кстати бесит часто на такого рода ресурсах — в чем проблема сразу указать требования по сложности? Не охота же тратить время на реализацию алгоритма, чтобы потом узнать, что "по времени не прошло".
Например вот:
https://www.hackerrank.com/challenges/build-a-string/problem
Понятно что решается динамикой за O(n^3), и интуитивно понятно, что такой вариант не пройдет. Но сколько надо? O(n^2logn)? O(n^2)? меньше?
5х10^7 — 10^8 операций, зависит от сложности операции.
У нас 3 теста, каждый по сложности в худшем случае 30000, т.е уже получаем примерно 100 000. Т.е. тут вырисовывается что-то в духе O(N*lgN*lgN) или O(N*sqrt(N)).
И опять же — в реальной задаче вам никто не скажет сложность. В лучшем случае ограничение по времени, как и здесь. А уже ваша задача подобрать сложность, чтобы влезть в ограничения.
И опять же — в реальной задаче вам никто не скажет сложность.
Ну, в реальной задаче я могу запустить длинное решение и определить сложность по тому, на сколько требуется быстрее. Тут такое не пройдет.
Конечно, если представлять примерно, на чем там у них и с какой скоростью крутится все — это дело упрощает.
Почему не пройдет?
Ну там же время не пишут? Просто говорят, что "нишмогла" за ограничение, так?
Я обычно писал синтетические тесты, эмулирующие данные из худшего случая и смотрел, что там со временем.
Но у них же не мой компуктер.
Просто говорят, что «нишмогла»Это да, потому и пишу тесты.
По многим задачам есть открытые тесты. И пишут, сколько по времени ушло на тест. Возьмите такой тест и прогоните у себя на машине. Теперь вы знаете, насколько ваш комп быстрее.
Мой был в 2-3 раза. Т.е. если я вижу, что решение худшего случая на моей машине 10 секунд, я близок к цели. Считает уже минуту — точно мимо.
Конкретно в задаче, которую вы привели выше — NlogN, Nlog^2N или N√N предполагается, судя по ограничениям. Учитывая, что корень — это, как правило, корневая эвристика, которая, как правило, оптимизируется до логарифма использованием дерева, предположу, что тут все же один из двух первых вариантов. Дальше уже можно смотреть — если применяется какой-то стандартный логлинейный алгоритм плюс в комбинации с чем-то или в задаче у нас двумерные данные, по которым может хотеться построить дерево — то Nlog^2N, иначе NlogN. Но двумерные деревья слишком сложны для интервью, так что я бы сказал, что здесь, скорее всего, NlogN предполагается.
PS: Условия задачи не читал, только ограничения.
Я лично не знаю людей, которые ее решат вместе с написанием кода за полчаса. Хотя они есть ) Я кстати тоже не решу, на Hard задачки у меня уходило минимум по несколько часов, а иногда и дней.
sqrt(N) могут давать некоторые техники и алгоритмы, и обычно дерево там не помощник. Например square root decomposition и Mo algorithm.
Хотя, возможно вы просто знаете больше меня )
Спасибо за алгоритм Мо, никогда о нем раньше не слышал. По сути, в нем тоже строится дерево высоты 2, в каждом узле которого мы знаем минимумы. Если это дерево сделать бинарным, получится разреженная таблица, которая проще в реализации, работает всего за O(N) с предподсчетом за O(NlogN) и не требует оффлайновости запросов, лишь неизменный массив.
Правда, с другой стороны, она требует в logN раз больше памяти. Если хочется впихнуть в O(N) памяти, нужна структура Фараха-Колтона-Бендера, которая слишком сложна для написания на собеседовании. Но в подобной задаче упомянуть ее будет не лишним.
Ну и да, есть алгоритмы с корневым временем работы — например, дискретное логарифмирование. Но сомневаюсь, что подобные алгоритмы хотя бы изредка спрашивают на собеседованиях на обычного разработчика.
deleted
Да никогда не бывает такого, что нету таски, в которой не завязано совсем на все.
Дело не в количестве непосредственных зависимостей задачи, а в размере полного графа транзитивных зависимостей. В случае Гугла получается, что ближайшая система, о которой внешний кандидат может иметь хоть какое-то представление, находится в 3-4 шагах от начальной точки. Единственный выход: заменять конкретику на абстрактные расплывчатые описания, что примерно эта подсистема делает и какие у неё ограничения. Но system design собеседования примерно на таком уровне детализации и ведутся.
Судя по тому, что написано в статье, человек готовился скорее именно к простому заучиванию алгоритмов.Зачем судить по пересказу, если можно посмотреть на реальные задачи с собеседований Google? Сами убедитесь, что они не на заучивание.
А если нет гитхаба соискателя — то гитхаб работодателя! :)
Личный гитхаб просто увеличивает шансы.
На самих интервью какой приблизительно сложности алгоритмические задачи были?
Даже только после курсов ситуация была не сильно отличающейся. Знание только теории не прокатит, нужна практика. Т.е. нужно натренировать мозг разбивать задачи на части, оценивать сложность каждой части и пытаться найти для нее наиболее подходящее решение. А для того, чтобы решение было подходящим, в голове должна быть база того, чем можно пользоваться.
Так что буду пока потихоньку подтягивать знания.
Ну то есть, я, скорее, сказал бы, что «решать 100% hard и быть в состоянии накодить в рамках типичного времени для интервью 50-75% hard» — это уже то самое «с запасом».
Т. е. читаю условия и вообще не понимаю как решать, известные алгоритмы по теме тоже не понятно как применять.
Что делать в этом случае?
Пытаться решить «в лоб» максимально тупым способом?
Гуглить по условиям задачи, смотреть названия алгоритмов в результатах поиска и пытаться их применить самому?
Какой-то другой способ?
- В первую очередь — понять асимптотику, это можно сделать по ограничениям.
- Потом — выписать все алгоритмы, которые на требуемую асимптотику похожи, и попытаться понять, какие из них могут быть применены в этой задаче.
- Понять (наверное, тут только большой опыт и gut feeling поможет), относится задача к динамическому программированию, жадным алгоритмам или еще какой-нибудь такой большой группе — в этом случае можно попробовать сформулировать все в терминах соответствующей группы алгоритмов (причем заметьте, эти группы — они вообще довольно обширны и сильно пересекаются, например, разбираясь в динамике, можно придумать с нуля алгоритм Дейкстры).
- Разумным образом ослабить ограничения — скажем, если вы подозреваете быстрое возведение в степень, сначала решить задачу просто с умножением. Ну или считать, что памяти бесконечно много для начала.
- Выбросить часть ограничений или требований, или, напротив, ввести новые, чтобы было проще решать — скажем, задачу на графе сначала решить для пустого графа, потом для графа из 1 ребра, потом для дерева, потом для кактуса, потом для связного графа, а уже потом — обобщить на общий случай.
- Нарисовать на бумажке десяток небольших примеров.
- Попытаться посмотреть на ту же задачу в других терминах — скажем, если есть матрица, представить себе граф, для которого эта матрица будет матрицей смежности.
- Для задач на динамику можно «вывернуть задачу наизнанку» — вместо вопроса, скажем, «сколько раз нужно кидать в окно транзистор, чтобы найти самый низкий этаж, с которого он разбивается, в здании из n этажей?» рассмотреть «для какого максимально высокого здания будет достаточно k бросков?», чтобы дальше добавить бинарный поиск по ответу.
- Возможно, еще что-то, этот список — только то, что сразу в голову пришло.
PS: Чисто по моему опыту — решите десять тысяч задач, и вы будете заранее знать все или почти все алгоритмические задачи с собеседования в Google.
— написать брутфорс решение. Самое простое, самое тупое, но рабочее.
Отсюда есть 2 плюса. Во-первых, при написании брутфорса очень часто вырисовывается структура решения. И потом, просто меняя в ней компоненты, можно добиться нужной скорости.
Во-вторых, на маленьких тестах вы сможете проверять ваши следующие решения. Т.е. если умное решение не проходит тесты на платформе, то пишем генератор тестов (обычно 10-20 строчек кода) и запускаем его в бесконечный цикл, в котором тест будет решаться брутом и «умным» алгоритмом. При несовпадении ответов останавливаемся, смотрим на тест и дебажим умный алгоритм.
Но в какой момент таки будет иметь смысл погуглить какие-то алгоритмы по теме, которые не знаешь?
И по поводу последней части — мне кажется, на собеседовании в том же гугле вряд ли прокатит «не молчать, чем вообще решить задачу». Вкатят минус и до свидания.
Десять тысяч?? Уровня medium-hard? Сколько времени это у вас заняло, если не секрет??
Само собой зависит от свободного времени. Допустим, 20 минут на задачу, 2 часа в будний день и 4 в выходной. Примерно 50 задач в неделю. 200 недель, 4 года ) Если брать более сложные задачи, то еще дольше.
Допустим, 20 минут на задачу, 2 часа в будний день и 4 в выходной. Примерно 50 задач в неделю. 200 недель, 4 года
Это же 3600 часов в сумме. Я просто не представляю размер морковки, которую человек должен иметь перед носом, чтобы решиться на такие инвестиции, если он не испытывает вполне четкое удовольствие от самого процесса.
если он не испытывает вполне четкое удовольствие от самого процессаДумаю, что если человек занимается этим столько времени, то испытывает )
Как я уже писал про себя, мне решать задачки нравилось. И если бы у меня было больше свободного времени, то я бы продолжил этим заниматься просто от любви к искусству )
если он не испытывает вполне четкое удовольствие от самого процессаЗаставлять себя вообще редко бывает полезно. Меня прямо перло с решения всех этих задач.
И по поводу последней части — мне кажется, на собеседовании в том же гугле вряд ли прокатит «не молчать, чем вообще решить задачу». Вкатят минус и до свидания.
Тут вы не правы. Отнюдь не всегда собеседующий ожидает услышать полное решение задачи. Есть куча разных вариантов:
а) Задача очень сложна и ожидается лишь разумное продвижение в нужную сторону.
б) Исходная задача не имеет решения и ожидается разумное сужение проблемы.
в) Задача NP-полна и не может быть разумно оптимизирована — ожидается лишь написание кода реализующего, по сути, полный перебор.
Если не молчать, предлагать варианты, задавать уточняющие вопросы, то собеседующий сам укажет чего именно надо.
Если не молчать, предлагать варианты, задавать уточняющие вопросы, то собеседующий сам укажет чего именно надо.
Ну вот опять же, что вы говорите о сферическом в вакууме собеседующем, который понимает и укажет, что выше человек говорит: "начните рассуждать, и хороший интервьювер направит ваши мысли в правильном направлении.", а вот в статье в итоге интервьюер сказал, что "слишком подсказок много пришлось давать, все плохо".
Применительно к интервью была задача, явно связанная с графами, но для меня на тот момент немного неочевидная. Соответственно я начал рассуждать не тему поиска пути, говорил про backtracking, поиск в глубину, A*. В общем, минут через 5-10 я бы наверное дорассуждался до поиска в ширину, а может и двух, через которые решалась задача. Но интервьюер пошел своим путем.
Задачу я в итоге решил полностью и оптимально. Код писал без подсказок. Только про проверку граничных случаев забыл, так как это уже было за несколько минут до конца интервью.
Ну, на самом деле, когда дают подсказки когда я о них не просил, а потом говорят, что их было слишком много, это не комильфо.Согласен, что интервьюер был не прав озвучивая такой фидбек кандидату. По хорошему, он вообще не должен был ничего говорить.
Задачу я в итоге решил полностью и оптимально.Я уже писал выше, что само решение задачи не так интересно. Больше интересно именно то, что происходит в процессе. Как человек движется к решению. какие идеи озвучивает.
в какой момент таки будет иметь смысл погуглить какие-то алгоритмы по теме, которые не знаешь?Перед тем, как решать задачи по теме. Сначала — лекции про Дейкстру, потом — задачи на Дейкстру, иначе не решишь.
мне кажется, на собеседовании в том же гугле вряд ли прокатит «не молчать, чем вообще решить задачу»Мне кажется наоборот, хотя сам я не пробовал (именно в Google, в Яндексе, скажем, пробовал, помогло). Если ты рассуждаешь, то и самомй проще додуматься получается, и интервьювер может увидеть, что тебя переклинило и ты не можешь заметить маленький очевидный кусочек — он его подскажет, и задача будет решена.
Десять тысяч?? Уровня medium-hard? Сколько времени это у вас заняло, если не секрет??Большая часть их была проще, наверное (сложно оценить, я на leetcode вообще не зарегистрирован). Более или менее постоянно — 10 и 11 классы. Плюс по три недели летом после 7, 8 и 9 классов. Ну и немного на младших курсах, но там прямо немного. Десять тысяч — это примерная оценка.
Более или менее постоянно — 10 и 11 классы. Плюс по три недели летом после 7, 8 и 9 классов. Ну и немного на младших курсах, но там прямо немного. Десять тысяч — это примерная оценка.
Тут надо, наверное, уточнить, сколько в среднем на одну задачу уходило. Потому что если 30-60 на задачу, то это какие-то совсем безумные сроки, если только не заниматься ежедневно часов по 8+ в день.
Странно мне всегда казалось что там ищут креативных людей, а не "доводить до автоматизма". Ну его этот гугл
Там ищут людей способных решать поставленные задачи оптимальными способами. Собеседования людей способных ставить задачи проходит по-другому.
И по моему опыту, человек либо может сам спокойно решить задачу и нужно может пару подсказок и его осеняет, либо сколько не подсказывай, человек не может написать пару циклов с правильными условиями.
Я бы хоть FizzBuzz спрашивал, если бы его не все знали. Проблема в том, что вопросы часто утекают и их запрещают спрашивать. Поэтому интервьюерам приходится придумывать новые задачи, которые не популярны и не такие сложные. Несложные задачи, которые не сводятся тривиально к известным всем, не так просто придумать, поэтому некоторым попадаются замудренные.
А хорошую работу в Швейцарии веб-разрабом из ЕС легко найти
Зависит есть ли уже гражданство в ЕС (или может постоянное резиденство ЕС, не блю карта). Если нет, то почти нереально, ИМХО (если не в гугл). Я пробовал — первый вопрос граэданство ЕС или право на работу в Швейцарии есть, нет — увы, вы нам не подходите… Местным фирмам, чтобы взять не гражданина ЕС нужно куча сил, времени и денег, а очередь граждан десятки и сотни человек на место, т.к. зарплата сильно выше. Хотя может я не сильно мотивирован был.
P.S. Подавайтесь, к нам, в Люксембург, проще, а уровень жизни тоже высокий. Ну, или в Германию.
Да, в итоге денег оставаться все равно в Цюрихе будет больше, но именно поэтому конкурс туда большой, грубо говоря для любого программиста в ЕС переехать в Цюрих, как правило, выиграть в деньгах, поэтому желающих… дох… фига.
Поэтому гугл чуть ли не единственная компания готовая нанимать не граждан ЕС в Швейцарию.
P.S. Люксембург где-то посередине между Германий и Швейцарией, зарплаты после налогов раза в 1,5 выше, чем в Берлине, а траты явно меньше чем в Швейцарии (и Бельгия, Франция и Германия в часовой доступности на общественном транспорте). При этом нет таких заморочек как в Швейцарии с наймом иностранцев.
Согласен, что стоит смотреть только на достижимые варианты. А еще крайне желательно считать разницу налогов и цен для своей потребительской корзины, а не для средней.
Спасибо за ответ) С резидентским гражданством ЕС все норм. Люксембург — как второй и уже последний для меня сейчас вариант. Тоже за. Благодарю что просветили, а то были сомнения. Гуглил много, но лучше услышать «по опыту». Подписался, думаю придется когда-нибудь посоветоваться. Заранее спасибо!
github.com/jwasham/coding-interview-university
а по факту:
1) выпиливал некоторые моменты использования гуавы, потому что жрёт памяти как не в себя
2) заканчивался пул коннектов, потому что их использование из какой-то другой гугловой библиотеки было настолько НЕ ОЧЕНЬ очевидным(да, потом нашли пример в доках, да, разработчик не посмотрел)
3) вы видели gmail?), больной ублюдок вообще интерфейс придумывал
Но тем не менее, осадочек остался, ожидаешь-то большего.
Как подготовиться к собеседованию в Google и не пройти его. Дважды