News for hackers. Stuff that matters.
Re:I had to give a wrong answer to get the job (2017) by chaps on Monday July 19, 2021 @01:07PM (#27884941)
Just a thought -- gaming is latency sensitive. Maybe their issue with it wasn't about average performance, but that the once-in-a-while perf hit would be enough to cause a bad experience for the person playing the game? I know I'd be frustrated if there was a predictable lag spike while playing a game.
Re:I had to give a wrong answer to get the job (2017) by typon on Monday July 19, 2021 @01:19PM (#27885046)
Any game engine design worth its salt would:

1. Probably not used linked lists (contiguous layout means better cache efficiency)

2. Would try to understand their data requirements and allocate memory up front as much as possible - doing a similar amortized analysis the OP is suggesting rather than a generic "always have O(1) insertion" at the cost of using an inferior data structure (a linked list)

Re:I had to give a wrong answer to get the job (2017) by BrS96bVxXBLzf5B on Monday July 19, 2021 @03:18PM (#27886286)
Any game engine architect worth her salt would know to not speak so absolutely about cache coherency, and that if you're dealing with a use-case where iteration is massively infrequent but random insertions and removals are likely, you could be better off with the linked list :)
Re:I had to give a wrong answer to get the job (2017) by typon on Monday July 19, 2021 @05:43PM (#27887595)
Certainly if you design a scenario where linked lists are superior to use, you should use linked lists. Fortunately, these are few and far between in real production software.
Re:I had to give a wrong answer to get the job (2017) by munificent on Monday July 19, 2021 @01:21PM (#27885071)
No, latency didn't come up. (I agree that could be a reason not to use a dynamic array.) They were hung up on the idea that a dynamic array must be O(n) because at least some of the appends copy.
Re:I had to give a wrong answer to get the job (2017) by 8note on Monday July 19, 2021 @01:39PM (#27885255)
Assuming you can average over all requests imposes that latency does not matter, doesn't it?

If you're the interviewee, it's up to you to get that clarification

Re:I had to give a wrong answer to get the job (2017) by munificent on Monday July 19, 2021 @06:05PM (#27887800)
The question they asked was about its complexity in big-O terms, not so much about its real world performance, at least as I recall.
Re:I had to give a wrong answer to get the job (2017) by qu4z-2 on Monday July 19, 2021 @06:53PM (#27888218)
You explicitly said they were hung up on the "worst case O(n)" situation, so I suspect they were concerned about the latency. Insertion into a dynamic array has a worst case of O(n) and an average case of O(1), no?