Stripe·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Apr 2026Remote

Summary

Stripe coding round, one meaty question about bitmap compression that took up the whole session. More systems-flavored than pure algo, which I wasn't expecting from a coding interview.

Questions Asked (1)

You have a bitmap lookup table mapping characters to 2D pixel grids. Implement compress(table) and decompress(compressed) for this table, then use the decompressed glyph to render a given character. Also discuss expected compression ratio and the tradeoff between encoding cost and rendering cost.

System DesignTechnical Trade-offsAlgorithms & Data Structures

Author's notes

I started with run-length encoding on each row of '#' and ' ' characters, which felt obvious, but then they pushed on packing bits into bytes and I fumbled around for a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the bitmap format and constraints, then design a compression scheme that exploits spatial redundancy (e.g., run-length encoding per row) and implement compress/decompress with clear APIs. Finally, render a character by decompressing its glyph and mapping pixels to output, and analyze compression ratio and trade-offs between encoding and rendering costs.

Pro tip: Quantify the trade-off: for example, RLE can achieve 10-20x compression on typical fonts, but decompression adds CPU cost; consider caching decompressed glyphs to amortize rendering cost.

1. Clarify requirements and constraints

Ask about bitmap dimensions, character set size, expected compression ratio, and whether compression is lossless. Confirm if rendering is to a screen or buffer.

2. Design compression algorithm

Choose a simple yet effective method like run-length encoding (RLE) per row, or bit-packing for sparse bitmaps. Explain why it suits 2D pixel grids.

3. Implement compress and decompress

Write functions that take a table (map of char to 2D array) and return compressed data, and vice versa. Ensure decompress(compress(table)) == table.

4. Render a character

Given a character, decompress its glyph (or use cached version) and output it as a 2D grid or string. Discuss handling missing characters.

5. Analyze compression ratio and trade-offs

Estimate compression ratio based on bitmap sparsity. Discuss encoding cost (time to compress) vs rendering cost (time to decompress and draw), and when to cache.

Key Points to Mention

Run-length encoding (RLE) for rows of pixels, with escape codes for runs.
Bit-packing for sparse bitmaps (e.g., storing only set bits).
Compression ratio depends on glyph complexity; typical fonts achieve 5-20x.
Trade-off: higher compression reduces storage but increases decompression CPU cost.
Caching decompressed glyphs to avoid repeated decompression during rendering.
Edge cases: empty glyphs, variable glyph sizes, and handling missing characters.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.