SWE / New Grad · VO Coding

Stripe BitFont:位图打印、压缩还原与文本换行的不同变体

先固定字符位图的尺寸与打印语义,再用可逆压缩保真;另帖的固定宽度换行单独标成变体。

题目重点:先固定字符位图的尺寸与打印语义,再用可逆压缩保真;另帖的固定宽度换行单独标成变体。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 基础训练版 lookup table 为 character→同高同宽的 0/1 矩阵;空格间距、未知字符和多行文本按题面确认。
  • 压缩训练版可选逐行 RLE,每段存 (bit,count),解压必须恢复原宽高;RLE 只是演示选择,不称面试指定。
  • 的 * / & 替换和 72 列断行是另一变体:先决定转换发生在位图元素、输出字符还是整行文本,不能用前述 0/1 RLE 规则填补缺失题面。

解题路线

  1. 第一段校验字形高度与行宽,按行输出,必要时把多个字形同一行横向拼接;空格和未知字符需要显式 fallback,不能 KeyError 后丢掉整句。
  2. 第二段编码时记录原宽、行数及每行连续位段;解码检查 count>0、bit∈{0,1}、每行展开长度恰为宽。用 decode(encode(bitmap))==bitmap 作性质测试,再复用同一个 print 函数显示解码结果。
  3. 第三段若是位图操作,例如反色,先解码得到规范矩阵,变换后调用已有渲染路径;实际操作类型题目未公开,所以训练例需标记。
  4. 固定宽度换行版把最终显示列数设 W,字符替换后再按输出字符宽度计列;如果字形宽度不同或需要保词,必须另问是否允许切断单词。保留原始输入与渲染后的列数,测试恰 W 和 W+1。

手动走一遍

训练例一行 [0,0,0,1,1,0] 可编码为 [(0,3),(1,2),(0,1)],解码正好回原行;反色后为 [1,1,1,0,0,1]。另一个换行变体里长度恰 72 的结果保持一行,第 73 个可见字符前换行;这是对宽度边界的训练约定,不能推断原题在空格处还是任意列断。

规模与取舍

P 个位图像素时打印、RLE 编码/解码和一次逐像素变换均 O(P);压缩段数 K≤P,压缩存储 O(K),但交替 0/1 时 K=P 且带 count 可能比原位图更大。长文本换行是 O(L) 时间。

易错点与追问

容易失分的边界

  • 把题目描述里的‘假设使用 RLE’写成官方压缩格式。
  • 不存行宽便无法验证或恢复尾部 0 的数量。
  • 多字符打印时逐字打印整张图,破坏水平排版,若题面要逐字则需相反处理。
  • 把 的 72 列规则硬塞进早期压缩版。

继续深挖

  • RLE 何时反而变大,怎样选择 raw/RLE tag?
  • 非等宽字形与 Unicode 宽字符如何计算显示列?
  • 如果第三段是裁剪/旋转而非反色,哪些解码与打印函数可原样复用?
✓已复制微信号!