How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Databricks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Databricks during technical interviews.

Implement run-length encoding and decoding | Databricks Coding Question

Quick Overview

This question evaluates proficiency in string manipulation and encoding algorithms, specifically run-length encoding and decoding, along with attention to edge cases such as empty inputs and single-character runs and correct handling of repetition counts.

Implement run-length encoding and decoding

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a string consisting of lowercase English letters. You need to implement run-length encoding (RLE) and its corresponding decoding. 1. **Encoding** - Input: a string `s`, e.g., `"aaabccccd"`. - Output: an encoded string where each maximal group of consecutive identical characters is replaced by the character followed by the count of repetitions, e.g., `"a3b1c4d1"`. 2. **Decoding** - Input: an RLE-encoded string as described above, which is always valid (i.e., alternates between characters and positive integer counts), e.g., `"a3b1c4d1"`. - Output: the original string, e.g., `"aaabccccd"`. Constraints: - `0 <= len(s) <= 10^5` for both encoding and decoding inputs. - Counts in the encoded string fit in a 32-bit signed integer. Tasks: - Describe how to implement `encode(String s)` and `decode(String encoded)`. - Explain the time and space complexity of each function. - Consider edge cases such as empty strings and runs of length 1.

Quick Answer: This question evaluates proficiency in string manipulation and encoding algorithms, specifically run-length encoding and decoding, along with attention to edge cases such as empty inputs and single-character runs and correct handling of repetition counts.

Part 1: Implement Run-Length Encoding

Given a string `s` containing only lowercase English letters, compress it using run-length encoding. Replace each maximal group of consecutive identical characters with the character followed by the number of times it appears consecutively. For example, `aaabccccd` becomes `a3b1c4d1`. If the input string is empty, return an empty string.

Constraints

0 <= len(s) <= 10^5
`s` contains only lowercase English letters
Run counts fit in a 32-bit signed integer

Examples

Input: 'aaabccccd'

Expected Output: 'a3b1c4d1'

Explanation: The runs are `aaa`, `b`, `cccc`, and `d`.

Input: ''

Expected Output: ''

Explanation: An empty string encodes to an empty string.

Input: 'a'

Expected Output: 'a1'

Explanation: A single character forms one run of length 1.

Input: 'abc'

Expected Output: 'a1b1c1'

Explanation: Each character is different, so each run has length 1.

Input: 'zzzzzzzzzz'

Expected Output: 'z10'

Explanation: A run can have a multi-digit count.

Solution

def solution(s):
    if not s:
        return ''

    parts = []
    current = s[0]
    count = 1

    for ch in s[1:]:
        if ch == current:
            count += 1
        else:
            parts.append(current)
            parts.append(str(count))
            current = ch
            count = 1

    parts.append(current)
    parts.append(str(count))
    return ''.join(parts)

Time complexity: O(n), where n is the length of `s`.. Space complexity: O(n) for the output being built..

Hints

Scan the string from left to right while tracking the current character and how many times it has repeated.
When the character changes, append the previous character and its count to a result list, then start a new run.

Part 2: Implement Run-Length Decoding

Given a valid run-length encoded string `encoded`, reconstruct and return the original string. The encoded string always alternates between a lowercase English letter and a positive integer count. Counts may have multiple digits. For example, `a3b1c4d1` should decode to `aaabccccd`. If the input string is empty, return an empty string.

Constraints

0 <= len(encoded) <= 10^5
`encoded` is always valid
Counts fit in a 32-bit signed integer

Examples

Input: 'a3b1c4d1'

Expected Output: 'aaabccccd'

Explanation: Expand each letter by its count: `a` 3 times, `b` 1 time, `c` 4 times, `d` 1 time.

Input: ''

Expected Output: ''

Explanation: An empty encoded string decodes to an empty string.

Input: 'a1'

Expected Output: 'a'

Explanation: A count of 1 means the character appears once.

Input: 'z10'

Expected Output: 'zzzzzzzzzz'

Explanation: Counts can have multiple digits.

Input: 'a2b3c1'

Expected Output: 'aabbbc'

Explanation: Expand `a` twice, `b` three times, and `c` once.

Solution

def solution(encoded):
    if not encoded:
        return ''

    parts = []
    i = 0
    n = len(encoded)

    while i < n:
        ch = encoded[i]
        i += 1

        j = i
        while j < n and encoded[j].isdigit():
            j += 1

        count = int(encoded[i:j])
        parts.append(ch * count)
        i = j

    return ''.join(parts)

Time complexity: O(n + L), where n is the length of `encoded` and L is the length of the decoded output.. Space complexity: O(L) for the decoded output..

Hints

Read one character at a time, then read all consecutive digits after it to form the full count.
Appending pieces to a list and joining at the end is more efficient than repeated string concatenation.

Quick Overview