CareerCup

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

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

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 !

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

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

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.