|
Assume that you have 2^32 bytes of memory .....
Microsoft Interview Questions and Answers
(Continued from previous question...)
108. Assume that you have 2^32 bytes of memory .....
Question:
Assume that you have 2^32 bytes of memory. When a program asks to allocate memory, a 4kb chunk of memory gets allocated. It can be allocated at any position (e.g. 0, 57, 8192). Now assume we have a function called lookup(), which, when fed an arbitrary address, (1) returns the value of the starting address of the chunk encompassing the requested address if it was allocated, or (2) returns a value indicating false if no block was allocated. Lookup must work IN CONSTANT TIME. To help clarify the functionality, here is some example expected behavior:
Allocate(1) /* allocates bytes 1-4096 */
Allocate(4099) /* allocates bytes 4099-8194 */
Lookup(123) /* returns 1 */
Lookup(4096) /* returns 1 */
Lookup(4098) /* returns -1 or false */
Lookup(6042) /* returns 4099 */
Lookup(8198) /* returns -1 or false */
To the readers, my solution had 2 checks maximum (and thus was O(1)). I have provided the solution as pseudocode, java code, and given links to images depicting the reasoning behind my solution as responses below.
maybe an answer:
Now we need to determine what the hashtable will store. Before we get to that, let's consider various allocation scenarios (using memory address 4096 as an example):
1. No objects were allocated in 4096
2. One allocation was done, before 4096, but which proceeds past 4096
3. One allocation was done, at/after 4096, which proceeds until/past 8192
4. There were two allocations, one before 4096 and one after first_allocation + 4096;
I decided to store the following:
IF an allocation begins in a certain chunk [chunk# * 4096, (chunk#+1)*4096), store the address of where the allocation begins. The hashtable mapping would be chunk#->allocated memory address.
/* Assume HashMap hash has key-value pairs of type <Integer, Integer> */
/* auto/unboxing in java means I don't care about Integer<->int conversions */
public int lookup(int lookup) {
Integer input_address = lookup;
int address_return, new_return_value;
if (hash.containsKey(input_address/4096)) {
address_return = hash.get(input_address/4096);
if (input_address >= address_return)
return address_return;
if (input_address < address_return) {
if (hash.containsKey(input_address/4096 - 1)) {
new_return_value = hash.get(input_address/4096 - 1);
if (new_return_value + 4096 > input_address)
return new_return_value
else
return -1;
} else {
return -1;
}
}
} else {
return -1;
}
return -1; /* shouldn't get here, ever */
}
(Continued on next question...)
Other Interview Questions
| 