Katkat
Back

Implement bitmap font render/compress/invert

StripeSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to manipulate 2D bit arrays, implement Run-Length Encoding (RLE) for data compression, and perform grid-based coordinate transformations.

Problem Statement

You are building a lightweight rendering engine for a monochrome display. A bitmap is represented as a list of strings, where '0' represents an off-pixel and '1' represents an on-pixel.

Implement a class BitmapProcessor with the following methods:

  1. invert(bitmap): Returns a new bitmap with all '0's flipped to '1's and vice versa.
  2. compress(bitmap): Compresses the bitmap using Run-Length Encoding (RLE) on each row. For each row, return a list of tuples representing (value, count). For example, "000110" becomes [('0', 3), ('1', 2), ('0', 1)].
  3. decompress(compressed_data): Reconstructs the original bitmap from the RLE format.

Constraints

  • The bitmap is a list of strings of equal length.
  • Rows and columns are between 1 and 500.
  • Time complexity should be O(R * C) where R is the number of rows and C is the number of columns.

Example

bitmap = [
    "001",
    "110"
]
# Invert -> ["110", "001"]
# Compress -> [[('0', 2), ('1', 1)], [('1', 2), ('0', 1)]]

Edge Cases

  • Empty bitmap (empty list).
  • A bitmap consisting of a single pixel type (all '0's or all '1's).
  • A bitmap with only one row or one column.

Hints

Hint 1

To invert, iterate through every character in each string and map '0' to '1' and '1' to '0'.

Hint 2

For compression, maintain a counter that resets whenever the current character differs from the previous one, then store the pair once the sequence ends.

Hint 3

For decompression, iterate through the list of tuples and use string multiplication (e.g., char * count) to reconstruct each row segment.

Follow-up questions

  • How would you modify the compression algorithm to perform RLE across the entire 2D grid as a single sequence rather than row-by-row?
  • If the bitmap was extremely sparse (e.g., 99% '0's), would RLE still be the most space-efficient compression method? Why or why not?
  • How would you handle potential memory constraints if the bitmap size increased to 10,000 x 10,000?