От переводчика: публикуем для вас перевод статьи Стива Меррита, сотрудника Google, который рассказывает о том, как он решает типичные проблемы программирования. Пост будет полезен, в первую очередь, начинающим программистам.
В этой статье я расскажу о своей стратегии решения проблем, возникающих в ходе работы над проектом, от старта до финиша. Я использую ее в ежедневном рабочем процессе в Google, а также при работе с кодерами любых уровней (коллегами, выпускниками bootcamps, студентами университетов). Структурированная методика минимизирует затраты времени на отладку и одновременно приводит к созданию более качественного кода.
Кстати, эта же стратегия зачастую срабатывает в ходе собеседований в крупных технологичных корпорациях. Три года назад я получил работу в Google благодаря ей.
Напоминаем: для всех читателей «Хабра» — скидка 10 000 рублей при записи на любой курс Skillbox по промокоду «Хабр».
Skillbox рекомендует: Образовательный онлайн-курс «Профессия Java-разработчик».
Шаг за шагом
Я покажу примеры в виде типичных проблем, чтобы раскрыть тему.
Проблема: «Даны две строки, sourceString и searchString, нужно вернуть первый индекс при появлении sourceString в searchString. Если searchString нет в sourceString, вернуть -1».
1. Начертите это
Сразу начать писать код — не очень хорошая идея. Сначала необходимо наметить путь решения проблемы. Начните с формирования гипотезы и доказательств своей точки зрения. И приступайте к работе только тогда, когда у вас уже есть четкий план. Если этого не сделать, то, когда работа уже началась, вы можете столкнуться с тем, что отдельные фрагменты кода будут не соответствовать друг другу.
Решение часто может быть нетривиальным, даже если задача выглядит простой. Планирование с использованием бумаги помогает найти верный подход и убедиться в том, что он сработает и в других ситуациях. Причем все это вы узнаете еще до того, как написана первая строка кода.
Поэтому не начинайте писать код, даже не думайте об этом. У вас будет много времени на работу. Вы — человек-компьютер, и вы решаете проблему.
Нанесите на бумагу алгоритм решения. Если вам что-то помогает визуализировать свой план, сделайте это. Задача — решить проблему при помощи карандаша и бумаги, без клавиатуры.
Придумайте простые входные данные. Если функция «передает строку», то «abc» — первый отличный пример. Попробуйте понять, каким должен быть верный результат. Затем подумайте о том, как вы поняли проблему, какие шаги были предприняты.
Представим, что у строк следующие значения:
sourceString: "abcdyesefgh"
searchString: "yes"Итак, мы можем видеть, что searchString находится внутри sourceString. Но как мы к этому пришли? Мы стартовали с начала sourceString и считали его до конца, просматривая каждый трехсимвольный фрагмент, чтобы увидеть, соответствует ли оно слову «yes». Например, «abc», «bcd», «cde» и так далее. Когда мы добрались до индекса 4, мы нашли «yes» и поэтому решили, что есть совпадение, и оно начинается с индекса 4.
В институте у меня был преподаватель, который задал задачу придумать инструкцию по созданию бутерброда с арахисовым маслом. За детальную и понятную инструкцию нам пообещали высшую оценку.
Я написал следующее:
«Откройте арахисовое масло, распределите его по хлебу. Положите сверху еще один кусок хлеба, и все готово».
Я думал, что справился, пока преподаватель не взял масло и не стал намазывать на хлеб, который все еще находился в пластиковой упаковке.
Программы, как и мой учитель, требуют весьма подробных инструкций, чтобы выполнение задачи стало возможным. Поэтому, когда создаем алгоритм, мы убеждаемся, что предусмотрели всё — все возможные сценарии. Возвращение правильного ответа, когда совпадение НАЙДЕНО, — это отлично, но необходимо вернуть ответ и в том случае, если совпадения НЕ НАЙДЕНЫ.
Давайте попробуем снова с другой парой строк:
sourceString: "abcdyefg"
searchString: "yes"Здесь мы начали с начала sourceString и считали его до конца, просматривая каждый трехсимвольный фрагмент, чтобы увидеть, соответствует ли он слову «yes». Когда мы добрались до индекса 4, мы нашли «yef», что было почти совпадением, но неполным, поскольку третий символ отличался. Таким образом мы продолжали считывать, пока не достигли конца строки, а затем решили, что не было совпадения, поэтому вернули -1.
Мы создали серию шагов (в программировании это называют алгоритмом), которые выполняем для решения проблемы, и мы попробовали выполнить несколько сценариев, каждый раз получая правильный результат. На данный момент мы можем быть уверены, что наш алгоритм работает, и теперь пришло время формализовать его, что приведет нас к следующему шагу.
2. Записываем алгоритм словами
Это делает шаги реальными, а значит, мы сможем обратиться к ним позже при написании кода.
- Начинаем с начала строки.
- Просматриваем все трехсимвольные комбинации (или сколько там символов указано в searchString).
- Если какие-то из них равны searchString, возвращаем текущий индекс.
- Если мы добрались до конца строки, не найдя соответствия, возвращаем -1.
3. Пишем псевдокод
Псевдокод — это не совсем код, но он «притворяется» кодом. Пример того, о чем я говорю, с учетом нашего алгоритма:
for each index in sourceString,
there are N characters in searchString
let N chars from index onward be called POSSIBLE_MATCH
if POSSIBLE_MATCH is equal to searchString, return index
at the end, if we haven't found a match yet, return -1.Я могу сделать его еще более похожим на настоящий код следующим образом:
for each index in sourceString,
N = searchString.length
POSSIBLE_MATCH = sourceString[index to index+N]
if POSSIBLE_MATCH === searchString:
return index
return -14. Переводим в код все, что можем
Сейчас нам придется позаботиться о синтаксисе, параметрах функций и правилах языка. Может быть, вы не можете написать все, и это нормально. Напишите в коде то, что вы точно знаете!
function findFirstMatch (searchString, sourceString) {
let length = searchString.length;
for (let index = 0; index < sourceString.length; index++) {
let possibleMatch = <the LENGTH chars starting at index i>
if (possibleMatch === searchString) {
return index;
}
}
return -1;
} Обратите внимание, что я оставил часть этого куска кода пустым. Это намеренно! Я не был уверен в синтаксисе для обработки строк в JavaScript, но об этом дальше.
5. Не полагайтесь на удачу
Достаточно распространенная ошибка, особенно у начинающих программистов, — использование чего-либо, найденного в сети, с надеждой на то, что это просто будет работать. Найденный фрагмент просто вставляется в собственный проект без тестирования. Чем больше участков своей программы вы не будете понимать, тем нереалистичнее успешное завершение работы.
Вероятность появления ошибки удваивается при добавлении любого элемента, в котором вы не уверены. В итоге процесс просто выходит из-под контроля.
Комментарий: вероятность появления ошибки можно рассчитать при помощи последовательности Мерсенна: a (n) = (2 ^ n) — 1
Протестируйте ваш код. Найти что-то в сети — это круто, но прежде чем добавить фрагмент в свою программу, опробуйте этот участок отдельно от всего.
В предыдущем шаге я говорил, что не знаю, как можно выбрать определенную часть строки при помощи JavaScript. Давайте поищем в Google.
https://www.google.com/search?q=how+to+select+part+of+a+string+in+javascript
Первый результат у нас из w3schools. Немного устарело, но работать будет:
http://www.w3schools.com/jsref/jsref_substr.asp
Я предполагаю, что должен использовать substr(index, searchString.length) для выделения части sourceString каждый раз. Но пока что это предположение и ничего более. Поэтому я сначала проверю его.
let testStr = "abcdefghi"
let subStr = testStr.substr(3, 4); // simple, easy usage
console.log(subStr);
"defg"
subStr = testStr.substr(8, 5); // ask for more chars than exist
"i"Теперь я точно знаю, как эта функция работает. Поэтому когда я добавлю этот фрагмент в свою программу, то уже буду знать, что, если она не работает, проблема — не в добавленном участке.
Ну и, наконец, я добавляю последнюю часть кода.
function findFirstMatch(searchString, sourceString) {
let length = searchString.length;
for (let index = 0; index < sourceString.length; index++) {
let possibleMatch = (
sourceString.substr(index, searchString.length));
if (possibleMatch === searchString) {
return index;
}
}
return -1;
}Вывод
Если вы дочитали до конца, попробуйте воспользоваться советом. Найдите проблему, с которой не можете справиться. Я гарантирую, что теперь все получится.
Удачи и счастливого кодинга!
Skillbox рекомендует:
- Практический курс «Мобильный разработчик PRO».
- Онлайн-курс «С#-разработчик с нуля».
- Двухлетний практический курс «Я — веб-разработчик PRO».
Комментарии (33)
HunterNNm
28.02.2019 13:02-1Как решает типичные проблемы программист Google — создает стартап. А как же еще то?
andreysmind
28.02.2019 19:36+1Делает презентацию описывающую проблему
Приглашает менеджеров и ведущих разработчиков на встречу
Коротко но эмоционально объясняет почему эту проблему необходимо решить и внедрить как можно быстрее
????
Через две недели идет на повышение, а баги будут чинить уже совсем другие люди.
Yaris
28.02.2019 13:47Испытываю смешанные чувства. С одной стороны, вроде и понятно, что автор хотел сказать, с другой — по прочтении условия задачи мне пришло в голову (на Питоне) sourceString.find(searchString). Городить велосипед (пусть и на собеседовании) мне в последний раз хотелось лет 10+ назад.
euroUK
28.02.2019 14:05Честно говоря, я не понимаю, зачем переводить подобные статьи. Неужели в ней есть какие-то откровения неизвестные даже студенту айтишной специальности второго курса?
Они там в гугле остальных что-ли за идиотов считают? Или у них там шанс повышения растет согласно индексу цитирования?
olegchir
28.02.2019 14:18Проблема в том, что если попытаться на собеседовании записать код в IDE без интернета, ты наткнешься на кучу чудесных открытий. Которые нигде и никогда в других случаях не встретишь. Если при реальном кодинге ты сразу напишешь финальный код и потом просто поправишь ошибки, то тут надо написать с первого раза, в условиях стресса когда руки дрожат и мысли из головы выветриваются. Отсюда этот пятиступенчатый процесс уточнения (идея -> чертеж -> алгоритм -> псевдокод -> возможно правильный код) с пятым шагом в случае наличия ноутбука чтобы прогнать на нём тесты. Это совершенно не то, что происходит в реальной жизни, люди к этому не готовы.
mehos
28.02.2019 14:38+2Это всеочевидные вещи для тех, кто сдавал экзамен по ассеемблеру на листочке вклеточку (да, без компа!).
yudinetz
28.02.2019 14:46+1Проблема в том, что если попытаться на собеседовании записать код в IDE без интернета, ты наткнешься на кучу чудесных открытий. Которые нигде и никогда в других случаях не встретишь. Если при реальном кодинге ты сразу напишешь финальный код и потом просто поправишь ошибки, то тут надо написать с первого раза, в условиях стресса когда руки дрожат и мысли из головы выветриваются.
Извините, но нет, в статье речь идет не о собеседовании, а о повседневной работе.
В этой статье я расскажу о своей стратегии решения проблем, возникающих в ходе работы над проектом, от старта до финиша. Я использую ее в ежедневном рабочем процессе в Google,
euroUK
28.02.2019 16:26Причем тут собеседования?
Если меня попросят писать код (не псевдокод, а код) на бумажке на собеседовании, я соглашусь если мне только скажут, что все в компании пишут код на бумажке.
Но в статье шла речь про работу. И если людям из Гугла всерьез приходит в голову писать статьи что можно словесно записывать алгоритм и рисовать блок схемы, то у меня только 2 предположения:
1) Для них самих это явилось откровением
2) Они считают всех работников не Гугла идиотами.olegchir
28.02.2019 16:52Зачем в реальной жизни записывать алгоритм, псевдокод и недокод, если можно сразу писать на языке программирования? Для меня это откровение, да (откровение скорей о работниках гугла, чем нечто такое, чем действительно стоит пользоваться).
Это может произойти или если ты не знаешь языка, или если тебе специально запихали палки в колёса (на собеседовании).
С другой стороны, если ты не знаешь JavaScript, ты всегда можешь написать на том языке, который знаешь, и потом странслировать на JavaScript. Наверное, есть специальный кейс — для человека, который не знает ни одного языка программирования, но как он оказался разработчиком в Google?
В целом вся эта статья с приближениями выглядит очень беспомощно
euroUK
28.02.2019 17:59Зачем в реальной жизни записывать алгоритм, псевдокод и недокод, если можно сразу писать на языке программирования? Для меня это откровение, да
Ну например за тем, что речь может касаться нового разрабатываемого функционала. Ты сидишь с бизнес-аналитиками и записываешь с их слов алгоритм. Предлагаешь сразу на Go херачить?
Картинки лучше помогают понять взаимодействие в большой системе. Иногда для этого делают стены переговорок с возможностью рисовать. В обшем, на сложных проектах помогает.
Denis631
01.03.2019 12:54Если меня попросят писать код (не псевдокод, а код) на бумажке на собеседовании, я соглашусь если мне только скажут, что все в компании пишут код на бумажк
Вы хотите работать в Гугле и получать $200к и более в год? Не хотите? Как хотите, следующий.
А если хотите, то делайте так как говорят в интервью.euroUK
01.03.2019 17:05Нет, не хочу.
Более того, я считаю, что уважающий себя спец не будет собеседоваться 10 этапов в длиной полгода-год, если ему не нужны очень сильно деньги, по нескольким причинам:
1) Зарплаты в IT и так высокие, выше какого-то порога деньги перестают быть решаюшим фактором
2) За время потраченное на все эти интервью и подготовки к ним человек может уже нормально работать и приносить пользу.
3) Сам факт, что люди закрывают вакансии по году говорит о том, что компании не нужны разработчики.
4) У хорошего спеца всегда есть предложения здесь и сейчас
Возможно, опыт работы в Гугле и полезен бывшим студентам, но я не очень понимаю зачем спецу с 10+ опытом там работать с учетом того, что 2/3 работы идет в помойку, а флагманские продукты гугла откровенно плохи
(Вспоминаю свою работу с корпоративной почтой gmail. Открыл админку, пошел кофе заварил. Выбрал приложение пошел чашку помыл. Выбрал роли — пошел покурил. А потом эти люди что-то на серьезных щах вещают про производительность)
Guitariz
28.02.2019 16:42А решение вашей проблемы в том, что никто адекватный не предъявит вам за отсутствующую точку запятой или пропущенную скобку в решении задачи на бумажке.
А если предъявит, тогда, наверно, оно и к лучшему — нечего с идиотами работать.
Vadem
01.03.2019 11:21Они там в гугле остальных что-ли за идиотов считают?
В Гугле работает порядка ста тысяч людей.
Я бы не судил о всех о них по статье одного человека.Guitariz
01.03.2019 12:46Тут два путя — статья либо фейк, либо согласована с пресс службой гугла. Если второй путь, то видимо да, можно судить.
Vadem
01.03.2019 13:44Или не согласована, т.к. автор пишет в своём личном блоге и акцентирует внимание на:
Opinions expressed in my articles are mine, not those of my employers.
Или согласована, но людьми, которые не в состоянии оценить очевидность этих советов. Или этим людям эти советы показались очевидными, но не для всех. Например, они могут быть полезны начинающим разработчикам. Или это вообще нормально для медиума давать такие советы(медиум реально переполнен капитанскими статьями). Или ещё что-то.
В любом случае, не думаю, что статью рецензировали все разработчики из Гугла.
Но да, никто не мешает думать, что гугл — это некое живое существо у которого есть единое мнение.
mpa4b
28.02.2019 16:18+1Читаю статью, а потом открываю gmail.com — и понимаю, что типичные программисты google таки смогли найти себе проблему, с которой же и не справились :)
kahi4
28.02.2019 19:22Ага, они indexOf найти в документации не смогли, судя по всему, но зато с бумажкой эффективно решили проблему!
Хотя странно выглядит эта статья. Вроде как код того же Chrome довольно таки хорош и красив, хотя судя по статье сложилось впечатление, будто бы его писало три миллиона джунов с бумажками на псевдокоде.
rgs350
28.02.2019 19:35+1А давайте каждый сотрудник google/facebook/microsoft/etc расскажет нам как решать задачи. Мы-то ничего не знаем, потому что не работаем в google/facebook/microsoft/etc. Ога. Судя по тормознутости gmail, дерьмовости skipe и говнокоду facebook средний разработчик в этих компаниях — последний человек к мнению которого стоит прислушаться.
kashey
01.03.2019 09:33Так ли думает програмист?
— читаю пачку символов нужной длины по известному смещению, если она совпадает с тем что надо — бинго!
! но тут совершенно упускается то как «сравнение» работает, что делает операцию копирования просто лишней
— иду по массиву и ищу начало последовательности. Если нахожу — начинаю смотреть что дальше. Если что-то не получается — возвращаюсь в начало и все заново.
! все хорошо, но не надо акцентироваться на «задаче», надо акцентироваться на том что надо делать. Что нужно делать — идти по строке и искать начало последовательности. Про то, что надо возвращаться назад речи и быть не может, и стоит только уточнить что есть «последовательность».
Так получается Ахо-Корасик — банально делает что сказали, и именно так и должен думать «програмист гугла».
ferreto
03.03.2019 10:08У вас уже постановка задачи неправильная: Даны две строки, sourceString и searchString, нужно вернуть первый индекс при появлении sourceString в searchString. Может, наоборот?
QtRoS
Вообще непонятен смысл статьи. Точнее связь содержимого и заголовка, который меня заинтересовал. Я ожидал реальные кейсы взаимодействия с настоящей проблемой, а что внутри? Задача с собеседования, решенная к тому не через Бойера-Мура или Кнутт-Моррис-Пратта, а "в лоб". В таком кейсе и ошибиться нельзя. Может быть ценность в рассуждении? Камон, написать на бумаге примеры, прикинуть алгоритм и перенести в код — только в Гугле так делают? В общем, разочарование.
EvilMan
В алгоритме есть проблемы, кстати. 1. Не учитывается случай, что шаблон может быть длиннее строки, в которой он ищется, или может быть пустым. 2. Бесполезные итерации в конце поиска.
olegchir
Думаю что тут решается вполне конкретная проблема — на собеседовании в Гугле нельзя писать код в IDE и пользоваться интернетом, а решение задачи идёт на скорость. Все эти срачи в твиттере о том, что юзернейм придумал решение, но ему не хватило времени записать его в виде кода. Поэтому возникает закономерный вопрос «как таким убогим образом можно сделать хоть что-то», и вот тут приходят на помощь всякие лайфхаки.
То есть, это не какой-то абстрактный совет про технологию решения проблем в общем случае, а вполне конкретная последовательность действий, которую нужно зазубрить как отче наш, как рефлекторную сборку-разборку автомата, и решать по этой схеме олимпиадные задачки, будучи разбуженным ночью.
IgorPie
До гугля тоже были программисты и тоже решали задачу на скорость. Причем тут известная торговая марка-то?
olegchir
Потому что он в ней работает и может говорить только за себя и своего работодателя?
IgorPie
А что, если в Оракал решают так же?
olegchir
Ну может и решают, и что?