Re: How many bytes per Italian character?

On Sat, 07 Apr 2007 13:32:45 -0400, Joseph M. Newcomer
<newcomer@xxxxxxxxxxxx> wrote:


I was once interviewed, and the interviewer said "what's the fastest way to allocate
memory?" and I said "malloc or new". He said, "No, come on. What's the fastest way to
allocate memory?" "malloc or new". We went around this several times, until he said
"VirtualAlloc! It's VirtualAlloc!" At which point I told him that it was a kernel API,
while malloc and new were entirely in user space, and the quickfit algorithm used by the
allocator meant that the allocation was very fast. He insisted it was "VirtualAlloc". How
a kernel call can be faster than entirely-in-user-space code escapes me. I not only used
to write storage allocators for a living, but I wrote a book with a whole chapter on how
to write high-performance, low-fragmentation allocators.

But those interviewers are real coders, software engineers?
i.e. is their real job designing and coding software? Or is their real
job asking questions with predefined answers to people?


But someone at MS told me that her standard interview question is "here is a list in
sorted order. Write the code to insert a new element in sorted order" and of 27
interviewees, 26 failed to do it, and the only one who got it right was a PhD candidate,
and she struggled to get it. I can do it with both LRU optimization for lookup and
sublinear insert performance for large lists without thinking too hard about it.

Joe: could you please elaborate on that?

With "list", do you mean "linked list"?
If with list we mean array, I could do a kind of binary search to find
the place of insertion, and then insert. This would be a O(log(n))
algorithm, am I correct?

But if I have a linked list, accessing a list node with an integer key
with O(1) performance is not possible, so I think that, to visit K-th
element, I should be forced to visit all the previous (K-1) elements,
am I correct?

So, to do the insertion in sorted order, I see only the (trivial)
linear O(n) algorithm, i.e. visit all list nodes until we find the
insertion place, then do the insertion.

I believe I am missing something here... could you please help or
pointing me to some URL/doc?

Thanks in advance
MrAsm
.

Relevant Pages

  • Re: How many bytes per Italian character?
    ... It's VirtualAlloc!" ... to write high-performance, low-fragmentation allocators. ... sublinear insert performance for large lists without thinking too hard about it. ... FINDING the insertion point is Oon the average, since you have to do linear search ...
    (microsoft.public.vc.mfc)
  • STL and pooling memory
    ... Does anybody know if STLPort or SGI STL standard allocators do memory ... Also I have had a look at the BOOST pool_alloc (to be used as a pooling ... allocator for lists), but looking into the code it doesn't seem to ever ...
    (comp.lang.cpp)
  • Re: CStringList and amount of memory
    ... I do have an undestanding of allocators but I ... completely forgot their overheads and only focussed on lists. ... Note that if your string is really 40 bytes, then you need 41 bytes to ... But should the overheads be twice of the data (40 bytes for each ...
    (microsoft.public.vc.mfc)
Loading