# Design a Small-Scale URL Shortener with Collision Handling Design the simplest small-scale abstraction that converts a long URL into a short code and resolves that code back to the original URL. Repeated requests for the same long URL should return the same short code. Keep the core design conceptual and in memory: use a hash-table or array-like model rather than assuming a database, cache, or distributed service. Explain how a hash-derived candidate code can collide and how open addressing, such as moving to the next slot, resolves that collision without losing either URL. Compare this with generating random Base62 candidates. ### Constraints & Assumptions - Treat two URL strings as the same only according to an explicitly stated equality or canonicalization rule. - A candidate short code may already belong to a different long URL. - The core answer should make create and redirect behavior understandable using in-memory structures. - Use a fixed-capacity table for the core design. Once a code is published, its entry must not move to another slot; return a capacity error if the table is full. - Persistence, databases, and multiple machines are optional extensions to discuss only after the small-scale collision model is correct. ### Clarifying Questions to Ask - Is exact string equality enough, or should equivalent URL spellings be canonicalized? - Must mappings survive a process restart, or is an in-memory interview abstraction intended? - Can codes be deleted, and if so may a deleted slot or code be reused? - Is there a fixed maximum code length or table capacity? ```hint Store enough information to verify a collision The initial hash or slot narrows the search, but the stored long URL determines whether the existing entry is the same mapping or a true collision. ``` ```hint Use the same probe sequence in both directions Creation must find an available slot deterministically, while redirect must be able to identify the code's stored entry without scanning unrelated mappings. ``` ### What a Strong Answer Covers - A minimal create operation, redirect operation, and bidirectional in-memory mapping. - Reuse of the existing code for an exactly matching long URL. - Deterministic collision handling with open addressing or another clearly explained hash-map strategy. - Load factor, fixed-capacity/full-table behavior, deletion implications for public code identity, and expected versus worst-case complexity. - A clear separation between the source-faithful in-memory model and optional persistence or sharding extensions. ### Follow-up Questions - Why can linear probing degrade to `O(n)` in the worst case? - How do tombstones preserve a probe chain after deletion? - If persistence later becomes required, what mapping and uniqueness guarantees must durable storage preserve? - How could a code hash route lookups to storage shards, and what data moves when a shard is added?