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