Microsoft Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

First glimpse though, pretty sure there's a better solution somewhere outhere :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

This comment has been deleted.

Comment hidden because of low score. Click to expand.
0

First 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:
- 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.

Comment hidden because of low score. Click to expand.
0

Hi,
I could not get your solution. Can u pls illustrate with an example?

Comment hidden because of low score. Click to expand.
0

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) {
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 */
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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) {

} // it checks and returns immediately

if (new_return_value + 4096 > input_address)
return new_return_value
}

return -1; /* shouldn't get here, ever */
}

Comment hidden because of low score. Click to expand.
0

@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!

Comment hidden because of low score. Click to expand.
0

@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?

Comment hidden because of low score. Click to expand.
0

@woohoo: Yes, so I thought. Just wanted to be sure if I was on the right track. That was pretty clear :) Thanks !

Comment hidden because of low score. Click to expand.
0

Good approach. This is how virtual memory with paging works in operating system concepts as well.

Comment hidden because of low score. Click to expand.
0
of 0 vote

- 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.

Comment hidden because of low score. Click to expand.
0

you should not have that constraint as 0-4095 are valid input and output values

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0

that doesn't tell you where (the actual address) the block of allocated memory began. it can only tell you if those 4k divisions are used or not.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.