Этот пост предназначен для того, чтобы помочь вам подготовиться к предстоящим собеседованиям на доске для вашего будущего работодателя или (если вы такой же ботаник, как я) к острым ощущениям от решения проблем. Мягкое предупреждение перед тем, как вы начнете: если у вас есть надежда пройти собеседование на доске, не уподобляйтесь генеральному директору SoftBank Масаёси Сону. Если вы обнаружите, что в середине интервью у вас возникают проблемы, не просто рисуйте лошадей, входящих в «долину коронавируса» и превращающихся в единорогов. Ваш работодатель отнесет вас к категории тех, кто считает, что гидроксихлорохин лечит коронавирус. Будьте умнее.

Проблема (любезно предоставлено Hacker Rank)

Гэри — заядлый путешественник. Он тщательно отслеживает свои походы, обращая пристальное внимание на мелкие детали, такие как топография. Во время своего последнего похода он сделал ровно n шагов. Для каждого шага, который он делал, он отмечал, был ли это подъем, U, или спуск, D, шаг. Походы Гэри начинаются и заканчиваются на уровне моря, и каждый шаг вверх или вниз соответствует изменению высоты на 1 единицу. Определим следующие термины:

  • Гора – это последовательность последовательных ступеней над уровнем моря, начиная со ступени вверх от уровня моря и заканчивая ступенькой вниз до уровня моря.
  • Долина представляет собой последовательность последовательных ступеней ниже уровня моря, начиная с ступени вниз от уровня моря и заканчивая ступенькой вверх до уровня моря.

Зная последовательность подъемов и спусков Гэри во время его последнего похода, найдите и выведите количество долин, через которые он прошел.

Например, если путь Гэри s = [DDUUUUDD], он сначала входит в долину глубиной 2 единиц. Затем он взбирается на гору высотой 2. Наконец, он возвращается на уровень моря и заканчивает свой поход.

Описание функции

Выполните функцию countingValleys в редакторе ниже. Он должен возвращать целое число, обозначающее количество долин, которые преодолел Гэри.

countingValleys имеет следующие параметры:

  • n: количество шагов, которые делает Гэри.
  • s: строка, описывающая его путь

Формат ввода

Первая строка содержит целое число n, количество шагов в походе Гэри.
Вторая строка содержит одну строку s из n символов, описывающих его путь.

→Ограничения

Формат вывода

Выведите единственное целое число, обозначающее количество долин, через которые прошел Гэри во время похода.

Пример ввода

8
UDDDUDUU

Пример вывода

1

Пояснение

Если мы представим _ как уровень моря, шаг вверх как / и шаг вниз как \, поход Гэри можно изобразить так:

_/\      _
   \    /
    \/\/

Он входит и выходит из одной долины.

Прежде чем вы начнете

Подумайте об инструментах в вашем наборе инструментов: условные операторы, циклы, типы данных, область видимости, рекурсия (и это лишь некоторые из них). Как мы можем взять эти инструменты и перетасовать их, чтобы получить другой результат? Как можно взять яйца, масло, муку и сахар и приготовить 1000 разных десертов? Французы разобрались, сможете и вы! Вопросы для интервью на доске предназначены для оценки того, насколько хорошо вы понимаете фундаментальное понимание языка и применяете его для решения проблем. Я обещаю вам, что у вас есть программные инструменты для решения этой проблемы, не требующие математики.

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

Разрушая это

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

  1. Гэри всегда начинает и заканчивает на уровне моря. Это означает, что на его пути будет равное количество U и D.
  2. «Полная» долина — это отрицательное отклонение от уровня моря (переход D от уровня моря) и завершенное возвращением к уровню моря. Точно так же «полная» гора — это положительное отклонение от уровня моря (переход U от уровня моря) и завершенное возвращением на уровень моря. Обратите внимание на язык, который я использую: отклонение от отрицательного к положительному.
  3. Функция возвращает число, представляющее количество долин, через которые прошел Гэри. Нас не волнуют горы, на которые он взбирался (знаю, угнетает, правда?).

Так в чем проблема на самом деле? Допустим, уровень моря равен 0, шаг вниз равен -1, а шаг вверх равен +1. Мы хотим знать, сколько раз Гэри становился отрицательным и возвращался к 0. Нас не волнует, сколько раз он был в долине и поднимался вверх (мини-горы), если он никогда не достигал уровня моря. Обратите внимание на букву «W» в пояснении к задаче. Небольшие горы игнорируются, потому что Гэри не достиг уровня моря. Все время, пока он был отрицательным, пока точка, в которой он не достиг 0, считается за 1 долину.

Решение

Псевдокод

Мы хотим пройти каждый шаг на пути Гэри и отслеживать его возвышение после каждого шага. Если Гэри переходит на U, добавьте 1 к высоте. В противном случае можно с уверенностью предположить, что он идет D, поэтому мы вычтем 1 из высоты. ЕСЛИ в какой-то момент после первого шага в своем путешествии он достигнет уровня моря, мы хотим знать. Опять же, можно с уверенностью предположить, что если высота равна 0 после выполнения шага U, он выходил из долины, поэтому мы должны увеличить наш счетчик долины на 1. Возвращает число долины после завершения всех шагов.

JavaScript-решение

let countingValleys = (steps, path) => {
  let elevation = 0
  let valleyCount = 0
  path.split('').forEach(char => {
    if (char === 'U'){
      elevation += 1
      // console.log(`We went up. Step: ${steps}`)
      
      if (elevation === 0){
        valleyCount++
        // console.log("We finished a valley.")
      }
    }
    else {
      elevation -= 1
      // console.log(`We went down. Step ${steps}`)
    }
  
    // steps -= 1
  })
  return valleyCount
}
console.log(`Total valleys: ${countingValleys(8, 'UDDDUDUU'})`)

Чтобы понять каждый шаг или доказать решение, попробуйте раскомментировать предоставленный помощник console.log и запустить его в своем браузере.

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

Ресурсы: Ранг Хакера