Microsoft OA

Round 1

Questions: Implement a class Allocator that distributes variable allocations in the computer's memory.

For this task, assume that the computer's memory consists of N bytes (N is a power of 2), addressed 0..N-1. The class should have the following functions:

• Allocator(int N): Creates an allocator responsible for N bytes of memory. N is a power of 2.
• int alloc(int size): Allocates a variable of size bytes and returns the address of the first allocated byte. The size parameter is always 1, 4, or 8. The variable needs to be allocated size consecutive bytes. No byte can be allocated to two variables at once. If there is enough consecutive free space, the variable should always be allocated. If it is not possible to allocate the variable of the given size, the function should return -1.
• void free(int address): Frees the variable allocated at the given address, which means that all bytes taken by the variable are no longer allocated. Assume that address is a value previously returned by the alloc function, and that the variable it points to is currently allocated (it wasn't freed previously). After freeing a variable, the bytes it occupied can be allocated to a new variable.

Examples: For example, consider the following sequence of operations: | operation | returned Value | comment | |-----------|----------|-------|---------| | a = Allocator(8) | - | Create an allocator for 8 bytes of memory | | a.alloc(8) | 0 | Bytes 0-7 are allocated | | a.alloc(1) | -1 | There are no free bytes | | a.free(0) | - | Bytes 0-7 are freed | | a.alloc(1) | 0 | Byte 0 is allocated | | a.alloc(4) | 1 | Bytes 1-4 are allocated | | a.free(0) | - | Byte 0 is freed | | a.alloc(4) | -1 | There are no 4 consecutive free bytes |

This way 4 alloc operations succeed, which is optimal.

In the following test, it is required to perform all six allocations. The memory size is N = 16.

| operation | returned value | comment | |-----------|----------|-------|---------| | a = Allocator(16) | - | Create an allocator for 16 bytes of memory | | a.alloc(4) | 0 | Bytes 0-3 are allocated | | a.alloc(8) | 8 | Bytes 8-15 are allocated | | a.alloc(4) | 4 | Bytes 4-7 are allocated | | a.free(0) | - | Bytes 0-3 are freed | | a.alloc(1) | 0 | Byte 0 is allocated | | a.alloc(1) | 1 | Byte 1 is allocated | | a.free(4) | - | Bytes 4-7 are freed | | a.free(1) | - | Byte 1 is freed | | a.free(0) | - | Byte 0 is freed | | a.alloc(8) | 0 | Bytes 0-7 are allocated |

Scoring:

In your solution, focus on optimizing the number of successful allocations. Each test has a scenario (a planned sequence of memory allocations and releases), and a minimum number of allocations needed to pass it.

If your program performs less than the minimum required number of allocations, it will not gain points for the given test.

Assume that:

• N is a power of 2 in the range [8, 1024].
• At most 1000 alloc/free operations will be executed.
• The free operation will always be called on currently allocated addresses, returned by the alloc function.

class Allocator {
public:
    Allocator(int N) {
        // Implement your solution here
    }
    
    int alloc(int size) {
        // Implement your solution here
    }

    void free(int address) {
        // Implement your solution here
    }
};