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 Take-home Project rounds at Stripe.

What role is this question designed for?

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

Implement bitmap font render/compress/invert

Quick Overview

This question evaluates proficiency in bitmap and matrix manipulation, lossless compression/decompression techniques, and modular code reuse for transformations such as inversion, targeting skills in data representation, algorithmic correctness, and space-time trade-offs.

Company: Stripe

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

## Bitmap Character to Image Conversion (3 phases) You are given a **bitmap lookup table** (a dictionary/map) that represents a tiny “font”. - **Key**: a character (e.g., `'J'`) - **Value**: a 2D grid (matrix) of `0/1` integers where: - `0` = background pixel - `1` = foreground pixel Example bitmap for the letter **`J`** (10 rows × 6 columns): ``` 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ``` ### Phase 1: Basic printing Implement a function that, given the lookup table and an input character, **prints the character’s bitmap to the console in the same grid format** (preserve rows/columns). ### Phase 2: Compression & decompression To save space, implement: 1. `compress(bitmap)`: Convert a 2D `0/1` matrix into a more compact representation. 2. `decompress(compressed)`: Restore the original 2D matrix. Requirements: - The decompressed bitmap must be **identical** to the original. - After decompressing, print the bitmap again (reuse Phase 1 printing). Notes: - You may choose any reasonable compression format (e.g., row-wise run-length encoding (RLE), storing coordinates of `1`s, etc.), but it must support lossless round-trip. ### Phase 3: Manipulation & reuse Perform an additional transformation on the bitmap(s), then print the result. - Example transformation: **invert** the bitmap (swap `0` and `1`). - You must **reuse** part of your Phase 2 code (e.g., decompress → manipulate → print, or manipulate compressed data then use existing logic). ### Assumptions / clarifications - All bitmaps are rectangular matrices. - Printing can be `0/1` separated by spaces (or equivalent consistent formatting). - The lookup table may contain multiple characters; your functions should work for any entry in the table.

Quick Answer: This question evaluates proficiency in bitmap and matrix manipulation, lossless compression/decompression techniques, and modular code reuse for transformations such as inversion, targeting skills in data representation, algorithmic correctness, and space-time trade-offs.

Part 1: Render a bitmap character

You are given a lookup table that maps single-character strings to rectangular 0/1 matrices. Return the selected character bitmap as a multiline string. Each row must preserve the original order of pixels, with values separated by a single space. Although the original task says to print to the console, return the string so it can be tested.

Constraints

0 <= number of rows in the chosen bitmap <= 200
0 <= number of columns in each row <= 200
Each cell is either 0 or 1
The chosen bitmap is rectangular

Examples

Input: ({'J': [[0, 1, 0], [0, 1, 0], [1, 0, 0]]}, 'J')

Expected Output: '0 1 0\n0 1 0\n1 0 0'

Explanation: A normal multi-row bitmap should be rendered exactly row by row.

Input: ({'A': [[1, 0], [0, 1]], 'B': [[1, 1], [1, 0]]}, 'B')

Expected Output: '1 1\n1 0'

Explanation: The function should select the requested character from a lookup table containing multiple entries.

Input: ({'E': []}, 'E')

Expected Output: ''

Explanation: Edge case: an empty bitmap has no rows, so the result is an empty string.

Input: ({'I': [[1, 1, 1, 1]]}, 'I')

Expected Output: '1 1 1 1'

Explanation: A single-row bitmap should not add extra newlines.

Hints

Process the bitmap one row at a time.
Build each row as a string first, then join all row strings with a newline.

Part 2: Lossless bitmap compression with row-wise RLE

Compress a rectangular 0/1 bitmap using row-wise run-length encoding (RLE). Use this exact format: result[0] must be [[rows, cols]]. For each bitmap row i, result[i + 1] must be a list of [value, count] pairs describing consecutive equal values from left to right. Your implementation should also be able to decompress this format internally to verify that the original bitmap can be restored exactly, but the function should return only the compressed structure.

Constraints

0 <= rows <= 200
0 <= cols <= 200
Each cell is either 0 or 1
The bitmap is rectangular
Your compression must be lossless when decompressed

Examples

Input: [[1, 1, 0, 0], [0, 0, 0, 1], [1, 0, 0, 1]]

Expected Output: [[[3, 4]], [[1, 2], [0, 2]], [[0, 3], [1, 1]], [[1, 1], [0, 2], [1, 1]]]

Explanation: Each row is independently encoded into runs.

Input: [[0, 0, 0, 0]]

Expected Output: [[[1, 4]], [[0, 4]]]

Explanation: A row with one repeated value becomes a single run.

Input: [[1, 0, 1, 0, 1]]

Expected Output: [[[1, 5]], [[1, 1], [0, 1], [1, 1], [0, 1], [1, 1]]]

Explanation: Alternating bits produce many short runs.

Input: []

Expected Output: [[[0, 0]]]

Explanation: Edge case: an empty bitmap stores only its dimensions.

Hints

Scan each row from left to right and group consecutive equal values into runs.
Store the original dimensions so decompression knows how many rows and columns to rebuild.

Part 3: Invert a compressed bitmap

A bitmap is stored in the exact row-wise RLE format from Part 2: compressed[0] is [[rows, cols]], and each remaining element is a row of [value, count] pairs. Decompress the bitmap, invert every bit so that 0 becomes 1 and 1 becomes 0, and return the resulting 2D matrix. The intended approach is to reuse the decompression logic from the compression problem.

Constraints

0 <= rows <= 200
0 <= cols <= 200
The compressed input follows the exact Part 2 format
All values are 0 or 1
The decompressed bitmap is rectangular

Examples

Input: [[[2, 3]], [[0, 1], [1, 2]], [[1, 1], [0, 2]]]

Expected Output: [[1, 0, 0], [0, 1, 1]]

Explanation: Decompress to [[0, 1, 1], [1, 0, 0]] and invert every bit.

Input: [[[1, 1]], [[0, 1]]]

Expected Output: [[1]]

Explanation: Edge case: a single pixel flips from 0 to 1.

Input: [[[2, 2]], [[1, 2]], [[1, 2]]]

Expected Output: [[0, 0], [0, 0]]

Explanation: All foreground pixels become background pixels.

Input: [[[0, 0]]]

Expected Output: []

Explanation: Edge case: an empty compressed bitmap decompresses to an empty matrix.

Hints

First rebuild the original bitmap row by row from the [value, count] runs.
After decompression, each bit can be inverted with 1 - bit.

Quick Overview