Meta systems such as Messenger or Instagram often need compact, sortable IDs generated independently on many devices or nodes. Implement a distributed ID generator that produces unique 64-bit integer IDs from a timestamp, a machine ID, and a per-millisecond sequence number.
Implement a function that processes a list of generation requests in order.
Each request is a pair [timestamp_ms, machine_id] where:
timestamp_ms is a non-negative integer timestamp in millisecondsmachine_id is the ID of the node generating the IDUse this 64-bit layout:
timestamp_ms - epochmachine_idRules:
epoch is an input integer.timestamp_ms, assign sequence numbers 0, 1, 2, ....4096 requests in the same millisecond, return -1 for each overflow request.-1 for that request.machine_id is outside [0, 1023] or timestamp_ms < epoch, return -1.Return a list of generated IDs in request order.
Example 1
epoch = 1000, requests = [[1005, 1], [1005, 1], [1006, 1]][20975616, 20975617, 25169920]0, then 1; next millisecond resets sequence to 0.Example 2
epoch = 0, requests = [[10, 2], [9, 2], [10, 1024]][41951232, -1, -1]2, and the third has an invalid machine ID.0 <= epoch <= 10^121 <= len(requests) <= 2 * 10^50 <= timestamp_ms <= 10^12epoch = 1000, requests = [[1005, 1], [1005, 1], [1006, 1]]Output[20975616, 20975617, 25169920]WhyFor machine 1 at timestamp 1005, the sequence values are 0 and 1. At timestamp 1006, the sequence resets to 0.epoch = 0, requests = [[10, 2], [9, 2], [10, 1024]]Output[41951232, -1, -1]WhyThe second request is earlier than the last accepted timestamp for machine 2, and machine ID 1024 does not fit in 10 bits.epoch = 50, requests = [[50, 0], [50, 1], [50, 0]]Output[0, 4096, 1]WhyMachine 0 gets sequence 0 then 1, while machine 1 has its own independent sequence starting at 0.`0 <= epoch <= 10^12``1 <= len(requests) <= 2 * 10^5``0 <= timestamp_ms <= 10^12``0 <= machine_id <= 10^9` in input, but only `[0, 1023]` is validUse 41 bits for timestamp delta, 10 bits for machine ID, and 12 bits for sequencedef generate_distributed_ids(epoch, requests):