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

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

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