Algorithms & Data Structuresmedium

ID Allocator I

Design an ID allocator over the space [0, capacity):

a = new IDAllocator(1000)
a.allocate()        // -> smallest available ID, or -1 if none
a.release(id)       // -> true if id was allocated; false otherwise
                    //    (double-release, never-allocated)
a.setCapacity(c)    // capacity is ADJUSTABLE at runtime, up or down

Shrinking must not invalidate IDs already handed out — an ID beyond the new capacity stays valid until released; it just cannot be re-allocated while capacity is below it. If capacity grows back, previously released high IDs become allocatable again.

Hints

Hint 1

Keep a pool of released IDs, a watermark for the smallest never-handed-out ID, and a set of currently allocated IDs for release validation. The smallest free ID is the best released one under capacity, else the watermark.

Hint 2

Make setCapacity lazy — just store the number. Released IDs at or above capacity stay in the pool, dormant until capacity grows back over them; a min-ordering guarantees they never block smaller IDs.

Hints

Asked at