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.
[ Parent
| on HN ]
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?