В ходе собеседований для ежедневных тренировок был задан ряд вопросов по программированию.

Эту проблему задала компания Amazon, основанная на сжатии данных, в которой запрашивалась реализация серийного кодирования строк.

Кодирование длин серий - это простейший метод сжатия данных. Основная идея этого состоит в том, чтобы представить повторяющиеся последовательные символы как единый счетчик и символ. Кодирование длин серий - это быстрый и простой метод кодирования строк.

Например-

Он относится к категории сжатия без потерь и, следовательно, является обратимым.

Сжатие без потерь - это класс алгоритмов сжатия данных, который позволяет идеально восстанавливать исходные данные из сжатых данных.-wikipedia

Основным недостатком этого метода является то, что, когда нет повторяющихся строк, вывод будет с увеличенным размером бит или вместо сжатия он будет расширяться.

Вопрос- Реализуйте кодирование и декодирование длин серий. Вы можете предположить, что кодируемая строка не имеет цифр и состоит исключительно из буквенных символов. Вы можете предположить, что декодируемая строка действительна.

Решение:

Мы можем реализовать encode, перебирая нашу входную строку и сохраняя текущий счетчик любого текущего символа, и как только мы встречаем другой, добавляя счетчик (в виде строки) и фактический символ к нашей строке результата.

def encode(s):
    if not s:
        return ''
    result = ''
    current_char = s[0]
    current_count = 0
    for i, char in enumerate(s, 1):
        if char == current_char:
            current_count += 1
        else:
            result += str(current_count) + current_char
            current_char = char
            current_count = 1
    result += str(current_count) + current_char
    return result

Мы можем реализовать decode, перебирая закодированную строку и проверяя каждый символ на наличие цифры. Если это так, то вычислите правильный счетчик, и как только мы найдем соответствующий ему символ, расширим результат с помощью количества символов, а затем сбросим счетчик.

def decode(s):
    count = 0
    result = ''
    for char in s:
        if char.isdigit():
            count = count * 10 + int(char)
        else:
            # char is alphabetic
            result += char * count
            count = 0
    return result

Спасибо за чтение, хорошего дня! 🙂