Convert bitmap into ASCII characters
Company: Stripe
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Question
Given an array/string of 0-1 bits representing a bitmap font, write code to render each character as a grid using '.' for 0 and '#' for 1, and concatenate multiple characters to print whole words efficiently.
Quick Answer: This question evaluates skills in binary-to-text data representation, bitmap rendering, and efficient string and array manipulation for output formatting.
You are given a bitmap font and a text to render. The font is a mapping from single characters to a row-major bitstring of length width * height. Each bit '1' renders as '#', and each bit '0' renders as '.'. Render the given text by placing glyphs side-by-side, inserting exactly one '.' column between adjacent characters. The space character ' ' is treated as a blank glyph of width columns (all '.'). If any non-space character in text is missing from the font or has an invalid bitstring length, raise a ValueError. Return the rendered result as a list of height strings (top to bottom).
Constraints
- 1 <= width <= 32
- 1 <= height <= 32
- 1 <= len(text) <= 10000
- Each font entry's bitstring length is exactly width * height
- Bits are only '0' or '1'
- Space ' ' renders as a blank glyph of width columns (all '.')
Solution
from typing import Dict, List
def render_bitmap_text(font: Dict[str, str], width: int, height: int, text: str) -> List[str]:
if width <= 0 or height <= 0:
raise ValueError("width and height must be positive")
# Prepare output lines
lines: List[str] = ["" for _ in range(height)]
# Cache decoded glyph rows for reuse
cache: Dict[str, List[str]] = {}
def decode_glyph(ch: str) -> List[str]:
if ch == ' ':
return ['.' * width for _ in range(height)]
if ch in cache:
return cache[ch]
if ch not in font:
raise ValueError(f"Missing glyph for character: {ch!r}")
bits = font[ch]
if len(bits) != width * height:
raise ValueError(f"Incorrect glyph size for {ch!r}: expected {width*height}, got {len(bits)}")
rows: List[str] = []
for r in range(height):
segment = bits[r*width:(r+1)*width]
# Validate bits
if any(b not in '01' for b in segment):
raise ValueError(f"Invalid bit in glyph {ch!r}")
rows.append(''.join('#' if b == '1' else '.' for b in segment))
cache[ch] = rows
return rows
n = len(text)
for i, ch in enumerate(text):
glyph_rows = decode_glyph(ch)
for r in range(height):
lines[r] += glyph_rows[r]
if i != n - 1:
for r in range(height):
lines[r] += '.'
return lines
Explanation
The function decodes each glyph's bitstring into height rows of width characters, mapping '1'->'#' and '0'->'.'. It builds the final output row-by-row, appending each glyph's corresponding row and inserting a single '.' column between adjacent characters. A cache avoids re-decoding repeated glyphs. The space character renders as a blank glyph of width columns.
Time complexity: O(height * width * len(text)). Space complexity: O(height * width) auxiliary (glyph cache), plus O(height * (len(text)*width + len(text)-1)) for the output.
Hints
- Interpret each glyph's bitstring in row-major order: rows of length width, from top to bottom.
- Build the output row-by-row: append each glyph's row to the corresponding output row, then add a '.' separator if not the last character.
- Cache decoded glyph rows to avoid repeated conversions when characters repeat.