DescriptionQ277
Q277ArchFollow-up to Q212ASIC interview problem
Compact live allocations
TechniquesAllocatorCompactionRelocation
DifficultyHard
TopicMemory Systems
LanguageSystemVerilog
Requirements4 checkpoints
01
Problem
Compact live allocations toward the allocator base, return an old-to-new relocation map, and rebuild one consolidated free interval.
Function headerSystemVerilog
function void compact(
ref int unsigned relocated_addr[int unsigned]
);Example input and output
Use this case to check your interpretationInput
allocator=[0,99]; live blocks=(base=10,size=20),(base=50,size=10)Output
relocations={10->0,50->20}; consolidated free range=[30,99]Explanation
Packing in allocation order keeps blocks nonoverlapping and advances the final free cursor to 30.
02
Requirements (4)
- Track live allocation bases and sizes.
- Preserve allocation order and prevent overlap during conceptual movement.
- Return a relocation entry for every moved allocation.
- Rebuild the free list from the final packed cursor to the allocator limit.