Content-addressable blob deduplication

Write codeMedium25 min

Your task

A content-addressable store deduplicates blobs by content. You are given a list of blobs (strings). Each blob's content hash is h(s) = ((sum((idx + 1) * ord(c) for idx, c in enumerate(s)) * 1000003) ^ len(s)) % 1000000007. Two blobs are considered identical only if their content hashes match AND their actual string contents match (i.e. resolve hash collisions by comparing content). Store each distinct blob once and assign it a chunk id: the first distinct blob gets id 0, the second distinct blob gets id 1, and so on. Return a pair [unique_count, mapping] where unique_count is the number of distinct blobs and mapping is a list giving, for each input blob in order, the chunk id it resolves to.

Examples

content_dedup(blobs: list[str]) -> list
Example 1
Inputcontent_dedup(["aa", "bb", "aa", "cc"])
Output[3, [0, 1, 0, 2]]