manish.baj
BAN USERQuick sort's partition function usually requires moving in both directions. Since it is a singly linked list, it may not work.
- manish.baj March 26, 2013Not sure why this is a problem. Most of the dictionary words have small value of N. It will be hard to beat a good sort algorithm, IMHO. Also, you could write a bug free code in less than 5 minutes using off the shelf sort and compare, saving your company thousands of dollars in your salary, just kidding. Unfortunately interview questions have a different purpose. So I kind of agree with you.
- manish.baj March 26, 2013You need to store the offset. Could do something like this in memalign above:
ptr[-1] = align - (uint)ptr % align;
Then, in the free function, you could do something like this:
free(ptr - ptr[-1];
There is a function called posix_memalign(void** memptr, size_t alignment, size_t size) that can do this job. But I think this is not what the interviewer wanted to hear. Also posix_memalign requires that alignment be a power of 2. Somebody could claim this to be a limitation, specially in an interview. ;)
- manish.baj March 25, 2013I am not sure how it fails for large numbers. The number you used is not particularly larger considering we are using floats here, right? There will be precision loss because of using floats but it shouldn't be too bad, imho.
- manish.baj March 25, 2013I think you need min-heap. Every time you get an element in the stream, compare it against the top of the heap. If current is larger than the top, remove the top and insert the current, else discard the current.
- manish.baj March 25, 2013
Bubble sort is inefficient. May be merge sort can be used. But I am not sure how to do it in place.
- manish.baj March 26, 2013