Code RoomContent-defined chunk deduplication
HardPrep Room Coding #220

Content-defined chunk deduplication

CodingStorage & CDNAlgorithms & data structuresSenior–Staff~35 min

A backup system uses content-defined chunking to deduplicate a byte stream. Given a string `data`, split it into chunks using this deterministic boundary rule: scan left to right; a chunk boundary ends right AFTER index i (0-based) whenever ((ord(data[i]) * 31 + i) mod `divisor`) == 0, OR when the chunk reaches `max_len` bytes (whichever comes first), and the final partial chunk ends at end-of-string. Each chunk is the substring between boundaries. Deduplicate identical chunk strings: count how many DISTINCT chunk strings result. Return that distinct-chunk count. divisor >= 1, max_len >= 1; len(data) <= 10^5.

Implement
cdc_distinct_chunks(data: str, divisor: int, max_len: int) → int
Examples
in["aaaa",1,10]out1
What a strong answer looks like

State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.

0:00 of about 35 min
InputExpectedGot
["aaaa",1,10]1not run yetsample