Amazon Interview Question
Software Engineer / Developersdid they ask about Reference? It seems that SoftReference and ReferenceQueue can do this.
Assume 4 bytes addressing: The first 4 bytes of buffer shall point to first free buffer.
Free Buffer: [--- 4 bytes address of next free buffer --][--- 4 byte buffer size ---][--- actual buffer of size mentioned in size --]
In-Use Buffer: [--- 4 byte buffer size ---][--- actual buffer of specified size --]
Mimimum size of allocation: 4 (next) + 4 (size) + 4 (atleast 4 bytes) = 12 bytes
When you want to allocate memory, traverse the free list and find the buffer aligned 4 byte boundary greater than or equal to size requested. If free buffer is 12 more than allocation size then split it and add it to free chain. Otherwise use the entire buffer.
To deallocate, traverse the list keeping the prev free list and current free list address. If they are adjacent then merge them in one. Also if the other adjacent buffer is free merge that as well.
@seeksree is it asked in AMazon US or India..???
- Martin April 26, 2011