NVIDIA Interview Question Software Engineer / Developers
"All these overheads + O(log n) search may equal O(n)."
What do you mean by that? Almost any balanced binary search tree has at least O(log n) amortized time for any operation it supports. Its superior in every way compared to a circular linked list.
The only reason I could imagine is that you could use two linked lists... one for short term memory and one for entries that have stayed there for more than a few seconds. Like generational garbage collection. The overhead of linked list may be lower on heavy updating as well as when not updating at all. Those are the two extreme cases represented by both linked list. But if you only use ONE linked list for all memory (short term + long term) then you are basically screwed.
And of course the other argument is that you can use batching on linked lists. Like you could wait until a certain threshold of "free" calls has passed or until malloc() fails. Then you cleanup all dead entries which you have collected in a separate list, which can be sorted on invokation with std::sort(). this will provide superior performance over binary trees which do not support this kind of algorithm.
I am not very much clear about your question but u can find a very good article here which talks about allocator, I didnt go through it fully but its interesting. Once u'll start reading it u'll definetely keep on reading it.
cs.northwestern.edu/~pdinda/icsclass/doc/dsa.pdf
ohh.. sorry for skipping words in question.
The question was why do we use circular link list in place od any balanced tree in storage allocator app.? By using balanced search tree the address search time wud be reduced to O(log n) which is not the case with Link lists. To make it more clear : we are not restricted to free the memory allocated in the sequence in which it was allocated(hint)
I agree with you. And also i suppose the overhead of balancing the tree with outplay the overhead to remove items from List.
I agree with you. And also i suppose the overhead of balancing the tree with outplay the overhead to remove items from List.
I am not sure but ans could be
- Aniket October 21, 20111. maintain two pointers in case of tree whereas one in list.
2. keeping track of balance of each node in tree.
3. balancing the tree if it gets unbalanced.
All these overheads + O(log n) search may equal O(n).