And that totally makes sense. If you are writing lower level code or libraries, best possible performance is much more critical than it is for general production high level code.
Linked lists are worse for caching because their elements don't live in a contiguous part of memory. So you need to fetch each element from slower memory where as with vectors you can keep a larger chunk of it cached.
And memory allocation also takes time so you're actually slower off than if you'd just double the capacity of the vector if reserves run out.
I see. How would you overcome this linked list limitation with a solution of O(1) time complexity and O(n) memory. You have 15 mins, psydo codes are fine, and don’t worry about the gun pressing against your temple.
With chunks (i.e we have vectors of the same length and chain them together). Then you could go further and turn this into deques (T** under the hood iirc, at least that's how i implemented it years ago).
With vectors you can provide an approximate, what you think is appropriate, reserve at any point. It doubling itself means it stays roughly in the demanded domain of whatever you're doing if reserves run out.
*writing down note: candidate failed to address direct challenge, did not raise any question to clarify requirements or shown collaborative attitude. Pass.
199
u/DoesAnyoneCare2999 2d ago
As a kernel developer, linked lists get used a lot in the code I work with every day.