Build a memory allocator

Why build an allocator in Python when the round is in C, C++ or Rust?

Because the part that is scored is the bookkeeping, and the bookkeeping is the same in every language. Here the memory is a bytearray and an allocation is an offset into it; in C the memory is a region from the operating system and the allocation is a pointer, which is the region's start plus that offset. Headers, splitting, the free list and merging are the same arithmetic on the same bytes. Say that once in the round, then write in whatever language the interviewer asked for.

What goes in a block header, and why does free not need a size?

The size of the block and whether it is in use, written in the 8 bytes in front of the payload the caller gets. free takes only an offset because the header sits at a fixed distance before it: step back 8 bytes and the size is there. That is also why a write before the start of an allocation is so damaging in C: it overwrites the header the allocator will trust on the next free.

First fit or best fit?

First fit takes the first free block large enough and stops, so it is cheap per call and tends to keep the large blocks at the far end of memory. Best fit takes the smallest block that is large enough, which leaves the smallest leftover but has to look at every free block unless the blocks are indexed by size, and the tiny leftovers it creates are often too small to use. I would build first fit in the round, name best fit as the alternative, and say that neither is best for every workload.

How do you merge a freed block with the block before it?

There are two ways to find the block before it. A footer copies the size to the last word of every block, so the block before is one read away and merging is O(1), at the cost of one more word per block. Or the free list is kept in address order, so the walk that finds where the freed block belongs also passes the free block before it, and merging costs a walk of the free list but no extra bytes. I would build the second in the round and name the first with its price.

What is the difference between internal and external fragmentation?

External fragmentation is free memory split into pieces too small for a request, so the bytes add up but no single block holds them; merging neighbours on free is the defence. Internal fragmentation is memory handed out but not used, such as the rounding up to eight bytes, or a 9-byte object in a 16-byte slot. A pool of fixed slots removes the external kind for one size and pays for it in the internal kind.