Как подготовиться к собеседованию в Google и не пройти его. Дважды



    Заголовок статьи звучит как epic fail, но на самом деле все не так однозначно. Да и в общем и целом эта история закончилась весьма позитивно, хоть и не в Google. Но это уже тема для другой статьи. В этой же статье я расскажу о трех вещах: каким образом проходил мой процесс подготовки, каким образом проходили интервью в Google и почему же на мой взгляд все не так однозначно, как может показаться.

    Как все начиналось


    Одним холодным кипрским зимним вечером мне вдруг пришла в голову мысль, что мои познания в классической Computer Science весьма далеки даже от средних, и с этим надо что-то делать. Если кстати вдруг кто-то еще не читал, почему вечер кипрский и холодный, то можно об этом узнать здесь. После некоторых размышлений было решено для начала пройти онлайн курс по алгоритмам и структурам данных. От одного из бывших коллег слышал про курс Роберта Седжвика (Robert Sedgewick) на Coursera. Курс состоит из двух частей (часть 1 и часть 2). Если вдруг ссылки поменяются, то можно всегда нагуглить по имени автора. Каждая из частей идет 6 недель. В начале недели выдаются лекции, а в течении недели еще нужно делать упражнения. Первая часть курса покрывает базовые структуры данных, основные виды сортировок и сложность алгоритмов. Вторая часть уже более продвинутая, начинается с графов и заканчивается такими вещами как Linear Programming и Intractability. Обдумав все вышеизложенное, я пришел к выводу, что это именно то, что мне нужно. Тут кстати пытливый читатель может спросить, а при чем же здесь Google. И действительно, до этого момента он был тут совсем не при чем. Но мне нужна была цель, так как заниматься 12 недель вечерами без цели несколько затруднительно. А какая может быть цель в получении новых знаний? Конечно, их применение на практике. В повседневной жизни это достаточно проблематично, а вот на собеседовании в крупную компанию запросто. Беглое гугление показало, что Google (уж простите за тавтологию) является одной из крупнейших компаний в Европе (а я рассматривал именно Европу), в которой проводят такие собеседования. А именно, их офис находится в Цюрихе, Швейцария. Итак решено — учимся и идем собеседоваться в Google.

    Подготовка к первому заходу


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

    • Лектор говорит на достаточно четком английском
    • Материал хорошо структурирован
    • Шикарные презентации, показывающие внутренности каждого алгоритма
    • Грамотная подборка материала
    • Интересные упражнения
    • Упражнения автоматически проверяются на сайте, после чего создается отчет

    У меня работа над курсами обычно проходила следующим образом. За 1-2 дня я прослушивал лекции. Затем проходил быстрый тест на знание материала. Остаток недели делал упражнение в несколько итераций. После первой получал свои 30-70%, последующие доводили результат до 97-100%. Упражнение обычно заключалось в реализации какого-нибудь алгоритма, например Seam carving или bzip.

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

    Так как был еще только май месяц, а собеседование я запланировал на осень, я решил продолжить свое образование. После просмотра требований к вакансии, было принято решение пойти параллельно по двум направлениям: продолжить изучение алгоритмов и пройти базовый курс по машинному обучению. Для первой цели я решил переключиться с курсов на книгу и выбрал монументальный труд Стивена Скиены (Steven Skiena) «Алгоритмы. Руководство по разработке» (The Algorithm Design Manual). Не такой монументальный, как у Кнута, но все же. Для второй цели я опять пошел на Coursera и записался на курс Эндрю Ына (Andrew Ng) Machine Learning.

    Прошло еще 3 месяца, и я закончил курс и книгу.

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

    Курс меня более чем порадовал. Автор явно знает свое дело и рассказывает интересно. Плюс изрядную часть, а именно линейную алгебру и основы нейронных сетей я помнил еще с университета, поэтому особых трудностей не испытал. Структура курса достаточно стандартная. Курс разбит на недели. Каждую неделю сначала идут лекции вперемешку с короткими тестами. После лекций выдается задание, которое нужно сделать, отправить и оно автоматически проверится. Вкратце, список преподаваемого в курсе следующий:
    — cost function
    — linear regression
    — gradient descent
    — feature scaling
    — normal equation
    — logistic regression
    — multiclass classification (one vs all)
    — neural networks
    — backpropagation
    — regularization
    — bias/variance
    — learning curves
    — error metrics (precision, recall, F1)
    — Support Vector Machines (large margin classification)
    — K-means
    — Principal Components Analysis
    — anomaly detection
    — collaborative filtering (recommeder system)
    — stochastic, mini-batch, batch gradient descents
    — online learning
    — map reduce
    — ceiling analysis
    После прохождения курса, понимание всех этих тем присутствовало. Через 2 года уже почти все естественно забылось. Рекомендую тем, кто не знаком с машинным обучением и хочет получить хорошее понимание базовых вещей для движения дальше.

    Первый заход


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

    Интервью тоже было через Hangouts. Сначала минут 5 поговорили обо мне, потом перешли к задачке. Задача была на графы. Я быстро понял, что надо сделать, но выбрал не тот алгоритм. Когда начал писать код осознал это и переключился на другой вариант, который и дописал. Интервьюер задал несколько вопросов на тему сложности алгоритма, спросил, можно ли быстрее. Я как-то затупил и не смог. На этом время вышло и мы распрощались. Потом, минут через 10 до меня дошло, что вместо алгоритма Дейкстры, который я использовал, конкретно в этой задаче можно было бы использовать поиск в ширину, и это было бы быстрее. Через некоторое время позвонил рекрутер и сказал, что интервью в целом прошло хорошо и надо бы организовать еще одно. Договорились на еще через недельку.

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

    И этой истории я сделал несколько выводов:

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

    Подготовка ко второму заходу


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

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

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

    Книги и статьи


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

    Книг я прочитал 5: Algorithms, 4th edition (Sedgewick, Wayne), Introduction to Algorithms 3rd Edition (Cormen, Leiserson, Rivest, Stein), Cracking the Coding Interview 4th edition (Gayle Laakmann), Programming Interviews Exposed 2nd edition (Mongan, Suojanen, Giguere), Elements of Programming Interviews (Aziz, Lee, Prakash). Их можно разделить на 2 категории. В первую попадают книги Седжвика и Кормена. Это теория. Остальные это подготовка к интервью. Седжвик в книге рассказывает примерно то же самое, что и в своих курсах. Просто в письменном виде. Нет особого смысла читать внимательно, если вы проходили курс, но проглядеть стоит в любом случае. Если курс не смотрели, то имеет смысл почитать. Кормен мне показался чересчур занудным. Осилил честно говоря с трудом. Вынес оттуда только master theorem, да несколько редко используемых структур данных (Fibonacci heap, van Emde Boas tree, radix heap).

    Книгу для подготовки к интервью стоит прочитать хотя бы одну. Они все построены примерно по одному принципу. Описывают процесс интервью в крупных технологических компаниях, дают базовые вещи из Computer Science, задачки на эти базовые вещи, решения задачек и разбор решений. Из приведенных трех я бы наверное рекомендовал Cracking the Coding Interview как основную, а остальные по желанию.

    Алгоритмические задачи


    Это наверное был самый интересный пункт подготовки. Можно, конечно, сесть и тупо решать задачи. Для этого есть много разных сайтов. Я в основном использовал три: Hackerrank, CodeChef и LeetCode. На CodeChef задачи разбиты по сложности, но не по темам. На Hackerrank и по сложности, и по темам.

    Но как я сразу для себя выяснил, есть более интересный способ. И это соревнования (programming challenges или programming contests). Все три сайта их предоставляют. Правда с LeetCode есть проблема — неудобная временная зона. Поэтому я не участвовал на этом сайте. Hackerrank и CodeChef предоставляют достаточно большое количество различных соревнований, длительностью от 1 часа до 10 дней. У разных форматов разные правила, ну да это про это можно долго рассказывать. Основная суть, почему соревнования это хорошо, это внесение соревновательного (и снова тавтология) элемента в процесс обучения.

    Всего я поучаствовал в 37 соревнованиях на Hackerrank. Из них 32 были рейтинговые, а 5 или спонсируемые (я даже получил 25$ в одном из них) или по фану. В рейтинговых я 10 раз входил в топ 4%, 11 раз в топ 12% и 5 раз в топ 25%. Лучшими результатами были 27/1459 в 3-х часовом и 22/9721 в недельном.

    На CodeChef я перешел, когда на Hackerrank соревнования стали устраивать реже. Всего я успел поучаствовать в 5 соревнованиях. Лучшим результатом было 426/5019 в десятидневном соревновании.

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

    Просмотр видео


    Прочитав книжку Скиены, я в принципе заинтересовался тем, чем он занимается. Как и Седжвик, он является профессором в университете. В связи с этим, в сети можно найти видеозаписи его курсов. Я решил просмотреть курс COMP300E — Programming Challenges — 2009 HKUST. Не скажу, что мне сильно понравилось. Во-первых качество видео не очень. Во-вторых я не пробовал сам решать задачи, разбираемые в рамках курса. Так что вовлеченность была не очень высокая.
    Также в процессе решения задачек, пытаясь найти правильный алгоритм, я натыкался на видео Tushar Roy. Он работал в Amazon, а сейчас работает в Apple. Как позже я для себя выяснил, у него есть канал на YouTube, где он выкладывает разбор различных алгоритмов. На момент написания статьи канал содержит 103 видео. И надо сказать, что разбор в его исполнении сделан очень прилично. Я пробовал смотреть других авторов, но как-то не зашло. Так что этот канал однозначно могу рекомендовать к просмотру.

    Прохождение курсов


    Тут я особо ничем не занимался. Просмотрел видео из Android Developer Nanodegree от Google и прошел курс от ИТМО How to Win Coding Competitions: Secrets of Champions. Nanodegree вполне себе, хотя ничего нового оттуда я естественно не узнал. Курс от ИТМО в плане теории немного скомканный, но задачки были интересные. Я бы не рекомендовал с него начинать, но в принципе время на него было потрачено не зря.

    Изучить опыт других людей


    Само собой множество людей пытались попасть в Google. Кто-то попал, кто-то нет. Некоторые писали об этом статьи. Из интересных вещей наверное отмечу вот эту и вот эту. В первом случае, человек подготовил для себя список того, что ему нужно выучить, чтобы стать Software Engineer и попасть в Google. Попал он в итоге в Amazon, но это уже не так важно. Второй мануал написан инженером Google, Ларисой Агарковой (Larrr). Помимо этого документа, можно также почитать ее блог.

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

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

    Второй заход


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

    После общения за жизнь решили, что через недельку будет Hangouts интервью, все как в прошлом году. Неделя прошла, пришло время интервью, но интервьюер не появился. Прошло 10 минут, я уже начал нервничать, как вдруг кто-то ворвался в чат. Как выяснилось чуть позже, мой интервьюер по какой-то причине не смог появиться и ему срочно нашли замену. Человек был несколько не готов как в плане настройки компа, так и в плане проведения интервью. Но затем все пошло хорошо. Задачку я решил быстро, описал где возможны подвохи, как их можно обойти. Обсудили несколько разных вариантов задачи, сложность алгоритма. Потом еще 5 минут пообщались, инженер рассказал свои впечатления от работы в Мюнхене (в Цюрихе видать срочной замены не нашли), на том и расстались.

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

    Пока готовил документы, попутно обсуждал с рекрутером предстоящее интервью. Стандарное интервью в Google состоит из 4 алгоритмических и одного System Design. Но, так как я устраивался как Android разработчик, мне было сказано, что часть интервью будет с Android спецификой. Какие именно и в чем будет специфика я из рекрутера так и не смог вытрясти. Насколько я понял, это ввели относительно недавно и он сам был не очень в курсе. Также меня записали на две тренировочные сессии: как проходить алгоритмическое интервью и как проходить System Design интервью. Сессии были средней степени полезности. Там мне тоже никто не смог рассказать, что же спрашивают у Android разработчиков. Поэтому моя подготовка в этот месяц свелась к следующему:

    • Покупке маркерной доски и написании 2-3 десятков самых популярных алгоритмов на ней по памяти. По 3-5 штук каждый день. Итого каждый был написан несколько раз.
    • Освежении в памяти разной информации по Android, которую не использую каждый день
    • Просмотре нескольких видео про Big Scale и все такое

    Как я уже говорил, параллельно я делал документы для поездки. Для начала у меня запросили данные, чтобы сделать пригласительное письмо. Потом я долго пытался выяснить, кто же на Кипре делает визы в Швейцарию, так как швейцарское посольство этим не занимается. Как выяснилось, этим занимается консульство Австрии. Позвонил и записал на прием. Там затребовали пачку документов, но ничего особо интересного. Фото, паспорт, вид на жительство, кучу разных справок и естественно пригласительное письмо. Письмо тем временем все не приходило. В итоге поехал с обычной распечаткой и это вполне прокатило. Само же письмо пришло еще дня через 3, причем кипрский FedEx не сумел найти мой адрес и пришлось ехать за ним самому. Заодно получил все в том же FedEx'e посылку, которую они тоже не смогли мне доставить, так как не нашли адрес, и которая там лежала с июня (5 месяцев, Карл). Так как я о ней не знал, что естественно и не предполагал, что она у них есть. Визу я получил вовремя, после чего мне забронировали отель и предложили варианты перелета. Варианты я подкорректировал, чтобы было удобнее. Прямых рейсов уже не было, в итоге летел туда через Афины, а обратно через Вену.

    После того как все формальности с поездкой были улажены, прошло еще несколько дней и я собственно вылетел в Цюрих. Добрался без приключений. От аэропорта до города доехал на поезде — быстро и удобно. Немного поплутав по городу нашел отель и заселился. Так как отель был забронирован без еды, отужинал по соседству и завалился спать, ибо рейс был утренний и спать уже хотелось. На следующий день позавтракал в отеле (за отдельные деньги) и отправился в офис Google. Всего в Цюрихе у Google несколько офисов. Мое собеседование было не в центральном. И в общем-то офис выглядел достаточно обычно, так что не довелось мне посмотреть на все плюшки «нормального» офиса Google. Зарегистрировался у администратора и сел ждать. Через какое-то время вышел рекрутер и рассказал мне план на день, после чего отвел в комнату, где и должны были проходить интервью. Собственно в плане значились 3 интервью, обед и еще 2 интервью.

    Интервью номер раз


    Первое интервью было как раз по Android. Причем вообще никак не было связано с алгоритмами. Сюрприз, однако. Ну да ладно, так даже привычнее. Попросили сделать определенный UI компонент. Сначала обсудили, что и как. Предложил сделать решение на RxJava, описал, что именно и почему бы сделал. Сказали, что это конечно хорошо, но давайте сделаем средствами Android фреймворка. А заодно напишем код на доске. Причем не просто компонента, а всей Activity, использующей этот компонент. Вот к такому я был не готов. Одно дело писать на доске алгоритм на 30-50 строчек, а другое дело лапшу Android кода, пусть даже с сокращениями и комментариями в духе «ну, это я писать не буду, так как и так очевидно». Получился какой-то винегрет на 3 доски. Т.е. задачу-то я решил, но выглядело это стремно.

    Интервью номер два


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

    Интервью номер три


    На это раз System Design, который вдруг тоже оказался Android. Нужно было разработать приложение с определенным функционалом. Обсудили требования к приложению, к серверу, к протоколу коммуникации. Далее я стал описывать, какие компоненты или библиотеки я бы использовал при построении приложения. А затем при упоминании Job Scheduler случился некоторый затык. Суть в том, что я никогда не использовал его на практике, так как в момент его выхода как раз переключился на поддержку приложений, где задач для его применения не было и в помине. При разработке последующих было тоже самое. То есть в теории я знаю что это за штука, когда и как применяется, но опыта в применении нет. И интервьюеру это похоже не сильно понравилось. Потом попросили написать код. Да, при разработке приложения сразу нужно писать код. Опять же Android код на доске. Получилось снова страшненько.

    Обед


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

    Интервью номер четыре


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

    Интервью номер пять


    И снова Android интервью. Интересно, зачем я учил алгоритмы весь год?
    Сначала было несколько простых вопросов. Потом интервьюер написал на доске код и попросил найти в нем проблемы. Нашел, объяснил, исправил. Обсудили. А дальше начались несколько неожиданные вопросы в духе «а что в классе Х делает метод У», «а что внутри у метода У», «а что делает класс Z». Что-то я конечно ответил, но потом сказал, что в работе в последнее время с этим не сталкивался и естественно не помню, кто, что и как в деталях делает. После этого интервьюер расспрашивал, что я делаю сейчас. И вопросы пошли на эту тему. Тут я уже отвечал гораздо лучше.

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

    На то, чтобы обработать результаты интервью ушло полторы недели. После чего мне сообщили, что я был «a bit below the bar». То бишь немного не дотянул. Если конкретнее, то 2 интервью прошли хорошо, 2 немного не очень, а System Design очень не очень. Вот если бы хотя бы 3 прошли хорошо, то можно было бы побороться, а так без шансов. Предложили заходить еще через год.

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

    Заключение


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

    • За полтора года я узнал огромное количество вещей, связанных с разработкой программного обеспечения.
    • Я получил немалое удовольствие, участвуя в соревнованиях по программированию.
    • Я съездил на пару дней в Цюрих. Когда еще туда выберусь?
    • Я получил интересный опыт интервью в одной из крупнейших IT компаний мира.

    Таким образом, все произошедшее за эти полтора года можно просто считать обучением, или тренировкой. И результаты этой тренировки дали о себе знать. Моя мысль покинуть Кипр дозрела (по некоторым обстоятельствам семейного характера), я успешно прошел несколько собеседований в другую известную компанию и через 8 месяцев переехал. Но это уже совсем другая история. Тем не менее, думаю, что мне все равно стоит поблагодарить Google как за эти полтора года, которые я работал над собой, так и за 2 интересных дня в Цюрихе.

    Что я могу сказать напоследок. Если вы работаете в IT, подготовьте себя к интервью в Google (Amazon, Microsoft, Apple и т.д.). Возможно, когда-нибудь вы туда заходите попасть. Даже если не захотите, то поверьте, от такой подготовки вам хуже не станет. В том момент, когда вы поймете, что можете (пусть даже только при удачном стечении обстоятельств) пройти интервью в одну из этих компаний, перед вами будет открыто гораздо больше дорог, чем перед началом вашей подготовки. А все, что вам потребуется в пути это цель, настойчивость и время. Желаю успехов :)
    Поделиться публикацией
    Комментарии 457
      +2
      Пару раз не прошёл интервью в Амазон (они очень активно нанимают), впечатления остались очень положительные — их сотрудники действительно пытаются узнать твои сильные стороны, уважительно и профессионально ведут процесс собеседований (ни какого сравнения с другой известной крупной компанией). Многому научился в процессе подготовки. Рекомендую — полезное и увлекательное занятие, только планку нужно высокую ставить, чтобы не сожалеть, когда ее преодолеете.
        +3
        Фигасе. Гугл заболел, что-ли? Я андроид разраб — три раза проходил онсайт в гугле в MV и самый приближенный к андроиду вопрос был «а покажите над чем раньше работали», три четверти заданий обычно динамическое программирование и отстаток почему-то простецкие задачки с leetcode.
          +1
          А, это Цюрих, не MV.
            0
            Прошу простить, а MV это где?
              –3
              Ме́кленбург-Пере́дняя Помера́ния (Abkürzung MV). Германия получается, если правильно понял
                +11

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

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

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

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

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

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

                            Я бы попробовал опять, но просто на SWE, а потом, уже поняв что и как устроено внутри, решить куда хочется дальше идти.
                          +8
                          Ничего страшного, я даже в небольшие компании интервью, где спрашивают все вот эти заумные алгоритмы и задачки, которые не имеют отношения к реальной работе и проектам, заваливаю, но это не сильно мешает в итоге найти подходящего работодателя.
                          • НЛО прилетело и опубликовало эту надпись здесь
                            • НЛО прилетело и опубликовало эту надпись здесь
                                +4
                                Да, гуманитарии объявляют войну! Гуманитарии — это не только грузчики, технички и кассиры! Гуманитарии тоже люди!
                                • НЛО прилетело и опубликовало эту надпись здесь
                                    +13
                                    Грузчики, технички и кассиры — тоже люди. Вообще все вокруг люди, за исключением тех, кто не люди.
                                      0
                                      Грузчики это же физики!
                                    +4
                                    По своему опыту знаете? :)
                                    *ирония*
                                      0
                                      А не пробовали читать текст прежде, чем искромётно шутить?
                                        +5

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

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

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

                                              +4
                                              А оно вообще надо?

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

                                              С другой стороны, стоит делать то, что прёт, и тогда вопросов таких не возникнет. Меня в своё время очень радовал курсеровский курс по биоинформатике с Певзнером. Очень драйвово, садишься, зашариваешь, решаешь алгоритмические задачки, хотя всё био от моей практики ну очень далеко.
                                              +14
                                              Ох… стоит ли оно того? если такие знания потом на практике не использовать — выветриваются быстро.

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

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

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

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

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


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

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


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

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


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

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

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


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

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


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


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

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


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

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


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

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

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

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

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

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


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

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


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

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


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

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


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


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

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

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


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

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


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

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


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

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


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


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

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

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


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

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


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

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


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

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

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


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

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


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

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

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

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

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

                                                                                                          ну в том же Java профайлере операция может быть слишком высокоуровневой. то что там что-то написало — не значит ровным счетом ничего. например. не выйдет заглянуть внутрь for без бубна.
                                                                                                          самое смешное, что далеко не все понимают, что профайлер «врет» чтобы программа не повисла из-за слишком пристального внимания.
                                                                                                            0
                                                                                                            От профайлера типа Intel VTune мне (в Си++) нужно просто увидеть, где программа проводит большую часть времени во время работы и какая конкретно операция жрёт процессор больше всего

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

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

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

                                                                                                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;
                                                                                                    }
                                                                                                }

                                                                                                  +1

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

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

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

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

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

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


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

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

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

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


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

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

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

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

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


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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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


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


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

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

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

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

                                                                                                                  +3

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

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

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

                                                                                                                          +1

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

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

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

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

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

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

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

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

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

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

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


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

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

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

                                                                                                                                    +1

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

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


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

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

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

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

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

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


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

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

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

                                                                                                                                                  Глядя на лаги и тормоза хангаутса, джимэйла, да и андроида в целом, требующего 8 ядерного процессора, чтобы лончер минимально плавно листался, не нахожу подтверждения тезиса о большом внимании гугла и его кодеров к оптимизации алгоритма в своих изделиях.
                                                                                                                                                    0
                                                                                                                                                    Если человек рассортировал вручную 1 тонну гречнево-рисовой смеси это говорит о том что он глуп или золушка.
                                                                                                                                                      +2
                                                                                                                                                      или что у него крестная фея — я бы серьезно задумался о такой возможности и вам советую. Крестная фея была бы куда более крутой фичей, даже при условии ограниченной работоспособности предоставляемых ею карет
                                                                                                                                                  0
                                                                                                                                                  А типовые задачи можно и в книжке посмотреть.
                                                                                                                                                  Поэтому на собеседованиях любят динамическое программирование — оно, как правило, нарабатывается большим опытом. И, зная динамическое программирование, изобрести алгоритм Дейкстры можно, а вот наоборот — нельзя.
                                                                                                                                            0
                                                                                                                                            Я вот недавно для себя писал игровой движок гексагональный — намучался с алгоритмами когда делал поиск пути.
                                                                                                                                              0
                                                                                                                                              Но я правильно понимаю, что этот поиск пути махонькая часть движка?
                                                                                                                                              Я-то ведь чего спрашиваю? Эти алгоритмы подаются как первостепенной важности вещь. Но моя практика показывает, что они применяются в прикладном в очень ограниченных объёмах (если вообще применяются), а основная сложность ПО вовсе не в алгоритмах, а скорее, в архитектуре и обеспечении прозрачного взаимодействия десятков/сотен/тысяч компонентов.
                                                                                                                                              +3
                                                                                                                                              Делал оптимизатор для самодельного компилятора — бегал по графу.

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

                                                                                                                                              Искал дубликаты в большой базе — делал блумфильтр (и оценивал вероятность false positives).

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

                                                                                                                                              Но, конечно, для того же блумфильтра все эти оценки я не помню, я залез в википедию и посмотрел формулы (ну и убедился, что там написанный вывод разумен, и моя реализация более-менее удовлетворяет предположениям).
                                                                                                                                                0
                                                                                                                                                Я половины написанных слов не знаю. :)
                                                                                                                                                  0
                                                                                                                                                  А зачем писать свой компилятор? (я далек от чистой разроботки, просто для интереса в каких случаях это требуется)
                                                                                                                                                    0
                                                                                                                                                    Ответы могут быть от традиционных («для нашего устройства выгоднее создать свой контроллер со своей ISA и своим компилятором, чем лицензировать существующие») до хайповых («пишем компилятор для смарт-контрактов в новом блокчейне»).
                                                                                                                                                      0
                                                                                                                                                      Реализовывал DSL для, собственно, некоторой предметной области.
                                                                                                                                                      0
                                                                                                                                                      думаю, как бы поизящнее и повыразительнее выражать запросы по AST и по data flow

                                                                                                                                                      Не знаю, какие именно запросы и как именно надо выражать, но вроде же в llvm есть встроенные средства для паттерн-матчинга по поддеревьям?