Parcel Label Numbers
A courier prints a barcode number on every parcel at up to 16 depots. The numbers must never repeat, the depots cannot call a central server for each label (the warehouse network drops out), and sorting labels by number should roughly sort them by time. So each depot builds the number itself from three parts: the time in milliseconds, its own machine number, and a counter for labels printed in the same millisecond.
This is the Snowflake-style generator from Unique IDs. Real layouts use 64 bits; this one is squeezed into 53 bits so every ID is an exact JavaScript number and survives a trip through JSON in a browser.
Your task
An ID is t × 4096 + machine × 256 + seq, which is the bit layout:
- 41 bits:
t, milliseconds since the courier's chosen epoch (0 to 241 − 1, about 69 years). - 4 bits:
machine, the depot number, 0 to 15. - 8 bits:
seq, 0 to 255, counting IDs made in the same millisecond.
Write a class LabelIds:
constructor(machine).next(t): return a new ID for timet. Iftis later than the time of the last ID issued (or nothing was issued yet), useseq = 0. Iftequals it, use the last seq plus 1. Return-1and change nothing in two cases: the seq would reach 256 (this millisecond is used up), ortis earlier than the last ID's time (the clock moved backwards).parts(id): split any valid ID into[t, machine, seq].
JavaScript's bit operators (<<, >>, &) work on 32 bits only, so they cannot handle a 53-bit ID. Use multiplication, division and remainder.
class LabelIds
Examples
new LabelIds(5) .next(1000) .next(1000) .next(1001) .parts(4097281)
[null, 4097280, 4097281, 4101376, [1000, 5, 1]]
1000 × 4096 = 4,096,000 and 5 × 256 = 1,280, so the first ID at t = 1000 is 4,097,280 (seq 0). A second label in the same millisecond gets seq 1: 4,097,281. At t = 1001 the seq starts again at 0: 4,100,096 + 1,280 = 4,101,376. Splitting 4,097,281 back: 4,097,281 ÷ 4096 rounds down to 1000, the remainder is 1,281, and 1,281 ÷ 256 = 5 remainder 1.
new LabelIds(0) .next(2000) .next(1999) .next(2000) .next(2001)
[null, 8192000, -1, 8192001, 8196096]
After an ID at t = 2000, the clock reports 1999. Issuing an ID at 1999 could repeat one already given out in that millisecond, so the generator refuses with -1 and keeps its state. Back at 2000 it continues the sequence with seq 1, and at 2001 it starts again from 0.
Constraints
- 0 ≤ machine ≤ 15
- 0 ≤ t ≤ 2,199,023,255,551 (2⁴¹ − 1)
- parts is only called with IDs that this layout can produce, so 0 ≤ id ≤ 9,007,199,254,740,991
- At most 1,000 calls per test
Start with brute force
The simplest unique number is a shared counter in one database: every depot asks it for the next value. That needs a network call per label and stops every depot when the counter is unreachable, which is what the courier cannot accept.
Random 53-bit numbers need no coordination, but they do not sort by time, and with many labels two will eventually collide. Building the ID from time, machine and sequence gives uniqueness and rough time order with no network call at all.
Hints
0 of 4 shown- Hint 1
If two depots print a label in the same millisecond, what keeps their IDs apart? And if one depot prints two labels in the same millisecond?
- Hint 2
The machine number separates depots, and the seq separates labels from one depot within a millisecond. So the generator only has to remember two things: the time of the last ID and the seq it used.
- Hint 3
Multiplying by 4096 (212) shifts the time left by 12 bits, and multiplying the machine by 256 (28) shifts it left by 8. Splitting reverses it: divide by 4096 and round down for
t; the remainder holds the rest. - Hint 4
In
next: ift < lastreturn -1; ift === lastand the seq is already 255 return -1; otherwise set the seq (0 or last + 1), storet, and build the ID. Do not store anything before both checks pass.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Each field gets its own range of bits, so IDs from different times, depots or sequence numbers can never be equal. Multiplying by a power of two is a left shift, and dividing and taking the remainder undoes it.
Trace the first example, machine 5:
next(1000): nothing issued yet, so seq 0. ID = 1000 × 4096 + 5 × 256 + 0 = 4,097,280.next(1000): same millisecond, seq 1. ID = 4,097,281.next(1001): later millisecond, seq back to 0. ID = 4,100,096 + 1,280 = 4,101,376.parts(4097281): 4,097,281 ÷ 4096 = 1000 remainder 1,281; 1,281 ÷ 256 = 5 remainder 1. Answer[1000, 5, 1].
Two details matter in practice. Both refusals must leave the state untouched, or a refused call would burn a seq or move the clock. And IDs sort by time only roughly: two depots' clocks differ by a few milliseconds, so order across depots within that skew is arbitrary. Real generators also wait for the next millisecond instead of failing; here the caller decides.
const TIME_SHIFT = 4096; // 2^12: room for 4 machine bits + 8 seq bits
const MACHINE_SHIFT = 256; // 2^8: room for 8 seq bits
const MAX_SEQ = 255;
class LabelIds {
constructor(machine) {
this.machine = machine;
this.lastT = -1; // nothing issued yet
this.seq = 0;
}
next(t) {
if (t < this.lastT) return -1; // clock moved backwards
if (t === this.lastT && this.seq === MAX_SEQ) return -1; // millisecond used up
this.seq = t === this.lastT ? this.seq + 1 : 0;
this.lastT = t;
// multiply, not <<: JavaScript bit operators are 32-bit
return t * TIME_SHIFT + this.machine * MACHINE_SHIFT + this.seq;
}
parts(id) {
const t = Math.floor(id / TIME_SHIFT);
const rest = id % TIME_SHIFT;
return [t, Math.floor(rest / MACHINE_SHIFT), rest % MACHINE_SHIFT];
}
}TIME_SHIFT = 4096 # 2^12: room for 4 machine bits + 8 seq bits
MACHINE_SHIFT = 256 # 2^8: room for 8 seq bits
MAX_SEQ = 255
class LabelIds:
def __init__(self, machine):
self.machine = machine
self.last_t = -1 # nothing issued yet
self.seq = 0
def next(self, t):
if t < self.last_t: # clock moved backwards
return -1
if t == self.last_t and self.seq == MAX_SEQ: # millisecond used up
return -1
self.seq = self.seq + 1 if t == self.last_t else 0
self.last_t = t
return t * TIME_SHIFT + self.machine * MACHINE_SHIFT + self.seq
def parts(self, id):
t, rest = divmod(id, TIME_SHIFT)
return [t, rest // MACHINE_SHIFT, rest % MACHINE_SHIFT]Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.