CareerCup

I think this is de-fragment and not fragment, right?

Did they want code or just ideas?

did he mean using delimiters like NULL and fragmenting memory whenever you see a NULL?

I am sorry yes its defragment. They need the algo as well as the code

Hello,

Is this too much different than a sparse matrix optimization? If one assumes the occupied cells as 1 and unoccupied cells as 0, then it boils down to a representation of a sparse matrix in some form, may be an array or list.

We can have an have linked list of struct containing memory add and its availability. So suppose first one is occupied then go to next struct in linked list. If that one it empty then the memory block is empty with this starting addr till the next structs memory address as the linked list is arranged ascending order of memory addr.
If two continues elements in linked list have the same status of availability then they can be merged.

Try thinking about java garbage collection strategy. You will get the answer.

huffman coding gives pretty good compression and is easy to imlpmement as well

I dont think its garbage collection coz we have defined empty and filled memory slots. Its more like how would you manage memory. There are two ways paging and segmentation. For implementation sake you can use array and write a code.

In such type of questions is pseudo-code sufficient or just a class structure is required to mention?

Was this question asked during telephonic round or on sight??

This looks like it can be solved using the Dutch National flag algorithm.

- Let bytes with NULL value be represented by 0
- Let invalid bytes be represented by -1
- Let valid bytes be represented by values other than 0 and -1

Define a method: void defrag(void *mem_loc) by shifting all zero's at the beginning, followed by -1's followed by the valid bytes. This can be easily done in O(n) time using Dutch national flag algo... in O(1) space...