Microsoft Interview Question
Software Engineer / DevelopersFirst sorry - a reasonable approach to return false would be to return a negative number. I did not word the question correctly.
I did not get into conserving space or breaking down the problem into bits. I don't think the interviewer was looking for that given his nudges during my interview. You can use either an array or a hashtable. The interviewer preferred that I use a hashtable (the logic is almost identical).
The logic behind my solution was as follows (with pseudocode):
Since memory is allocated 4k at a time, break the memory addresses into 4k chunks. These chunks will serve as the hashtable keys.
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.
My logic would then be:
1. Calculate the hash code (input_address/4096).
2. Check if the hashtable has the key from (1).
- if no key exists, return -1 ("false").
3. If it has the key, compare the value returned to your input_address:
- if input_address >= address_return,
- return address_return
- if input_address < address_return,
- lookup the key (input_address/4096 - 1) --> new_return_value
- if key does not exist,
- return -1 ("false").
- if new_return_value > input_address - 4096,
- return new_return_value
- else, return -1 ("false").
If it is unclear, let me know.
here is the actual code for now...did not check for syntax, minor errors, etc. I will post reasoning for the if-statement conditions later today if I can. It would just be illustrations of what I explained above.
/* 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 */
}
I have drawn out different possible combinations of how memory could be allocated. Here is an image depicting those cases:
img577.imageshack.us/img577/4985/q41y.jpg
Most notably, please take a look at the table I drew at the bottom of the page.
I also conducted a few (not thorough) traces of code that should help with understanding my logic in the above code. The traces for tests cases A, B, C, B+C can be found here:
img851.imageshack.us/img851/3765/q42.jpg
I am not sure how to clarify further but I hope that this helps. You can see that Case A requires only one lookup, but cases B, C, and B+C require 2 lookups to get an answer. Take the examples and traces with a grain of salt - they are meant to get the general idea across.
Hope this helps.
thanks wooohooo......
can't view the pictures though, plz update pics again
however i think it might fail incase, current block there is no allocation and it has span uptill this block from previous
Allocate(199)
Allocate(5222)
lookup(8300) - it might fail coz my map would look like
0 - 199
1 - 5222
correct me if im wrong
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;
} // it checks and returns immediately
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
}
return -1; /* shouldn't get here, ever */
}
@woohoo: Firstly, I really liked your approach. But, I have a doubt. Test case E - memory allocation starts in chunk 0 (2058 - 6154). So, the hashmap would now have one key-value pair i.e. (0, 2058). In this case, your first if condition would fail for lookup (6144) as the hashmap does not contain a key-value pair for chunk 1. Then, how would the program return 2058 ? Could you point out what I am missing on. Thanks!
@aimHigh
good catch - you are correct. my code did not match my logic. i didn't test out my above code but the expected behavior should be:
no key exists for 6144/4096->1, so lookup in chunk 0.
it seems like you have a grasp of the algorithm I was intending to portray. do you need any further clarification?
@woohoo: Yes, so I thought. Just wanted to be sure if I was on the right track. That was pretty clear :) Thanks !
- Imagine that the 2^32 bytes has 2^20 pages each of size 4k and aligned at 4k boundaries
- When an allocation request comes, it can either by aligned at 4k boundary in which case it takes the whole page. Otherwise it overlaps two adjacent pages.
- Maintain an array of 2 byte words of total 2^20 words. This array needs to be in a separate area of memory. Each word maintains the state of the imaginary 4k aligned page. The total size of the array will be 2MB
- Each 2 byte word in the array (16 bits) is divided into two portions
-- A 12 bit portion containing the start of used offset e.g. 0, 59, 23 etc.
-- A 4 bit portion containing the info whether the page is used or not. Only one bit is really needed to keep this boolean information.
With the above data structure, checking can be done in O(1) steps. Say we want to check address A
- Partition A into A20 and A12 meaning uppper 20 and lower 12 bits
- Check word A20 in the array. If it is used and the offset stored in it is <= A12, return ((A20 << 20) | offset at A20)
- Check previous word (A20-1). If it is used and A12 <= (offset at A20-1)-1, return ((A20-1)<<20 | (offset stored at A20-1))
- If we reach here, then return 0
If we can have a constraint that memory requests in the range 0 - 4095 always fail, then the above scheme of returning start address should work perfectly.
Isnt maintaining a bit set of 2^20 blocks"(each bit corresponding to the one 4k memory block)
If its allocated set it to 1 otherwise set it to 0.
The lookup function in this case would run in O(1).
Well dont know how did u implement 2 comparisons for that but even binary search on bst or just sorted array when search space is limited is of constant size, in our case that would be needed 32 iterations max because of search space size of 2^32 so its O(1) worst case actually. Id maintain starting positions for all allocated chunks as sorted list or bst and on Lookup would search in that list/bst for first allocated chunk with starting position of more than (x - 4096). if that value would be less than x, the ans is 0/false, else 1/true.
- Anonymous March 28, 2011First glimpse though, pretty sure there's a better solution somewhere outhere :)