Re:I had to give a wrong answer to get the job (2017)
by SilasX on Monday July 19, 2021 @05:51PM
(#27887658)
So it would be fine if they had said, "okay, for this problem let's add the requirement that every add must be fast, because it's within a frame rendering loop", but (from OP's description) they didn't even seem to understand that's a separate desideratum, or that it doesn't mean the amortized time is bad.
Re:I had to give a wrong answer to get the job (2017)
by tomxor on Tuesday July 20, 2021 @05:51AM
(#27891768)
It's probably implicit, it's a gaming company, however it might be fair to say the interviewers didn't appreciate the possibilities outside of gaming and unconsciously assumed this context was understood.
Re:I had to give a wrong answer to get the job (2017)
by tomxor on Monday July 19, 2021 @03:50PM
(#27886608)
> worst case, not the average
Yup, I can't remember which book but I'm pretty sure I remember reading some stuff from Michael Abrash about how some of the algorithms in quake were changed for worse average performance but better worst case performance. It's fairly intuitive when you think about the context... and that is the critical point - abstract problems are interesting, but it's important to evaluate them in their full context.
Real time systems including games have hard limits on how long something can take in the worst case, not the average. In games this manifests as: All the stuff has to be done in 16ms to render a frame on time, if we're late the user will perceive a glitch. The consequences can be worse in control systems in any number of real-world systems where a glitch can lead to stability problems.
So getting back to TFA, this is part of knowing what the "right" answer is for the context.