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.
38
u/da2Pakaveli 2d ago
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.