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^12