Решение нескольких задач от 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
    

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

    Благодарю за внимание.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 5

      +7
      Спасибо за перевод. Если подумать, то первую задачку можно решить чуть короче:
      function encodeString(s) {
          // "AAAABB" -> [["AAAA", "A"], ["BB", "B"]]
          const matches = s.matchAll(/(.)\1*/g)
          const mapFn = ([s, с]) => s.length + с
          return Array.from(matches, mapFn).join('')
      }
      
      function decodeString(s) {
          // "4A2B" -> [["4A", "4", "A"], ["2B", "2", "B"]]
          const matches = s.matchAll(/(\d+)(.)/g)
          const mapFn = ([, n, c]) => c.repeat(n)
          return Array.from(matches, mapFn).join('')
      }
        +5
        первая регулярка крутая, пойду почитаю
        можно еще вспомнить про replace:
        encodeString = str => str.replace(/(\w)\1*/g, (x, y) => x.length+y)

        decodeString= str => str.replace(/(\d+)(\w)/g, (_,x, y) => y.repeat(x))
        
          +1
          Отличное решение. Вы выиграли. :)
            0
            фантастика
          0

          deleted

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое