Design a unique ID generator in HLD - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ Architecture

intermediate

Identify the correct architecture for a distributed unique ID generator

You want to design a system that generates unique IDs across multiple servers without collisions. Which architecture below best ensures uniqueness and scalability?

A A centralized server generates IDs sequentially and all clients request IDs from it.

B Clients generate random IDs independently without coordination.

C Each server generates IDs using a timestamp combined with a unique server ID and a sequence number.

D IDs are generated by hashing client IP addresses and timestamps.

💡 Hint

Think about how to avoid collisions and maintain scalability without a single bottleneck.

Option C uses a combination of timestamp, server ID, and sequence number to ensure uniqueness and scalability. Option C creates a bottleneck. Option C risks collisions. Option C can cause collisions and is not reliable.

❓ scaling

intermediate

Estimate the capacity of a unique ID generator system

Your unique ID generator uses 41 bits for timestamp (in milliseconds), 10 bits for machine ID, and 12 bits for sequence number per millisecond. How many unique IDs can the system generate per millisecond?

A 4096 IDs per second

B 4096 IDs per millisecond

C 1024 IDs per second

D 1024 IDs per millisecond

💡 Hint

Calculate how many IDs the sequence number allows per millisecond, then convert to per second.

12 bits for sequence number means 2^12 = 4096 IDs per millisecond. Since 1 second = 1000 milliseconds, total per second is 4096 * 1000 = 4,096,000 IDs. The question asks per millisecond but options focus on per millisecond or per second. The correct choice is 4096 IDs per millisecond.

❓ tradeoff

advanced

Choose the best tradeoff for ID length vs. uniqueness duration

You design a unique ID with 64 bits total. You can allocate bits between timestamp and sequence number. Allocating more bits to timestamp increases the time range IDs remain unique, but reduces IDs per millisecond. Allocating more bits to sequence number increases IDs per millisecond but shortens uniqueness duration. Which allocation is best for a system needing 10,000 IDs per millisecond and uniqueness for 10 years?

A 39 bits timestamp, 14 bits sequence number

B 41 bits timestamp, 12 bits sequence number

C 42 bits timestamp, 11 bits sequence number

D 38 bits timestamp, 15 bits sequence number

💡 Hint

Calculate if the timestamp bits cover 10 years and if sequence bits cover 10,000 IDs per millisecond.

14 bits sequence number = 16384 IDs per millisecond, which covers 10,000 IDs. 39 bits timestamp covers about 17 years (2^39 ms ≈ 17 years), which covers 10 years. Other options either have too few sequence bits or too few timestamp bits.

🧠 Conceptual

advanced

Identify the main challenge in distributed unique ID generation

What is the biggest challenge when designing a distributed unique ID generator that works across many servers?

A Ensuring IDs are cryptographically secure

B Minimizing the size of the ID to 16 bits

C Generating IDs that are human-readable

D Avoiding collisions without a central coordinator

💡 Hint

Think about what happens when multiple servers generate IDs independently.

The main challenge is avoiding collisions (duplicate IDs) without relying on a central server, which can become a bottleneck or single point of failure. Cryptographic security and human readability are less critical. Minimizing ID size to 16 bits is impractical for uniqueness.

❓ component

expert

Trace the request flow in a Snowflake-like ID generator system

In a Snowflake-like distributed ID generator, which sequence correctly describes the request flow when a client requests a new ID?

A 1,2,3,4,5,6

B 1,3,2,4,5,6

C 2,1,3,4,5,6

D 1,2,4,3,5,6

💡 Hint

Think about the logical order from request to ID generation and response.

The client first sends the request (1). The service checks timestamp (2). If timestamp same as last, increment sequence (3). If sequence maxed, wait (4). Then compose ID (5) and return it (6). Other orders break logical flow.