Как решает типичные проблемы программист Google

в 9:39, , рубрики: Google, skillbox, Алгоритмы, Блог компании Skillbox, Программирование, решение проблем, управление разработкой, Учебный процесс в IT

image

От переводчика: публикуем для вас перевод статьи Стива Меррита, сотрудника 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 -1

4. Переводим в код все, что можем

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

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 рекомендует:

Автор: fokus-lop

Источник

* - обязательные к заполнению поля