Решение нескольких задач от Amazon на примере JavaScript

Доброго времени суток. Представляю вашему вниманию перевод статьи «Amazon Coding Interview Questions» автора Trung Anh Dang.

В этой статье автор приводит несколько (три, если быть точнее) задач от Amazon (как он утверждает) и свои варианты решений.

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

Итак, поехали.

Задача № 1

Кодирование длин серий или кодирование повторов (run-length encoding) — это быстрый и простой способ кодирования строк. Суть этого алгоритма заключается в замене повторяющихся символов (серии) на один символ и число его повторов. Серией называется последовательность, состоящая из нескольких одинаковых символов. При кодировании строка одинаковых символов, составляющих серию, заменяется строкой, содержащей сам повторяющийся символ и количество его повторов.

Например, строка "AAAABBBCCDAA" после кодирования повторов будет выглядеть как "4A3B2C1D2A".

Реализуйте кодирование и декодирование повторов. Строка для кодирования состоит только из букв, не содержит чисел. Строка для декодирования является валидной.

Решение

Кодирование строки

Решение довольно простое:

const encoding_string = function(string) {     if(string.length === 0) return ''          let currChar = string.charAt(0)     let count = 1     let encoding = ''          for(let i = 1; i < string.length; i++) {         const char = string.charAt(i)         if(char === currChar) count++         else {             encoding += count + currChar                          // сброс             count = 1             currChar = char         }     }          encoding += count + currChar          return encoding } 

Декодирование строки

Нам необходимо реализовать две вспомогательные функции:

1. Функцию, проверяющую является ли символ числом:

const isNumber = function(str) {     return /^\d+$/.test(str) } 

2. Функцию, возвращающую количество символов до конца строки:

const addCountAmount = function(string, char, count) {     for(let i = 1; i <= count; i++) {         string += char     }          return string } 

Вот решение:

const decoding_string = function(string) {     if(string.length === 0) return ''     let currCount = 0     let i = 0     let decoding = ''          while(i < string.length) {         const char = string.charAt(i)         if(isNumber(char)) {             const num = +char             currCount = currCount * 10 + num         } else {             decoding = addCountAmount(decoding, char, currCount)             currCount = 0         }                  i++     }          return decoding } 

Проверяем решение:

1. Строка "AAAABBBCCDAA" должна быть преобразована в "4A3B2C1D2A":

console.log(encoding_string("AAAABBBCCDAA")) // 4A3B2C1D2A 

2. Обратное преобразование:

console.log(decoding_string("4A3B2C1D2A")) // AAAABBBCCDAA 

Задача № 2

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

Например, если N = 4, то существует 5 уникальных способов:

     1, 1, 1, 1     2, 1, 1     1, 2, 1     1, 1, 2     2, 2 

Что если убрать ограничение на количество ступеней? Например, если X = {1, 3, 5}, мы можем подняться на 1, 3 или 5 ступеней за раз.

Решение

Функция, возвращающая количество уникальных способов подняться по лестнице (с ограничением):

const climb_stairs_1 = function(stairs) {     if(stairs === 1) return 1     if(stairs === 2) return 2      let prev = 1     let curr = 2     for(let i = 2; i < stairs; i++) {         const sum = prev + curr         prev = curr         curr = sum     }     return curr } 

Функция, возвращающая количество уникальных способов подняться по лестнице (без ограничения):

const climb_stairs_2 = function(stairs, nums) {     const dp = Array(stairs + 1).fill(0)      for(let i = 1; i <= stairs; i++) {         // получаем общее количество f(i - x), где x - каждое число в nums         let total = 0         for(let j = 0; j < nums.length; j++) {             const num = nums[j]              // проверяем попадание в диапазон             if(i - num > 0) total += dp[i - num]         }         dp[i] += total          // если i имеется в nums, увеличиваем значение         if(nums.indexOf(i) !== -1) dp[i] += 1     }     // получаем последнее число в dp     return dp[dp.length - 1] } 

Проверяем решение:

console.log(climb_stairs_1(4)) // 5  console.log(climb_stairs_2(4, [1, 3, 5])) // 3 

Задача № 3

Дано целое число K и строка S. Нужно найти длину самой длинной подстроки, содержащей не более K разных символов.

Например, дана s = "abcba" и k = 2. Самой длинной подстрокой с не более K разных символов является "bcb".

Решение

Вот мое решение:

const k_longest_substring = function(string, k) {     let l = 0     let r = 0     const charCount = new Map()     let longestSubstring = ''      while(r < string.length) {         const char = string.charAt(r)          // обновляем счетчик         if(charCount.has(char)) {             charCount.set(char, charCount.get(char) + 1)         } else {             charCount.set(char, 1)         }          // размер charCount равен k         // начинаем двигаться влево до тех пор, пока подстрока не будет содержать не более k разных символов         if(charCount.size > k) {             while(charCount.size > k && l < r) {                 const leftChar = string.charAt(l)                 const count = charCount.get(leftChar)                  if(count === 1) charCount.delete(leftChar)                 else charCount.set(leftChar, count - 1)                  l++             }         }          const substring = string.substring(l, r + 1)         longestSubstring = substring.length > longestSubstring.length ? substring : longestSubstring         r++     }     return longestSubstring } 

Проверяем решение:

console.log(k_longest_substring("abcba", 2)) // bcb 

Легко, не правда ли?

Благодарю за внимание.