Hi All,
I just started using EPI (new book). For both problems 4.1 and 4.3 (chapter 4), I noticed they don’t take into consideration the time/space complexity of the look up table. Is that accurate for interview purpose as well?
If you need to write compilable code in an interview, you will have to take into consideration the writing the codes for the look up table. Therefore, when doing time/space complexity analysis, those solutions using look up table will no longer be optimal.
I understand that this is the best way to do it in production code since this will greatly increase the speed if you are doing those computation very often. However, I am skeptical on how an interviewers will perceive it.
If you need to do time/space analysis that involve your complete solution, it will not be a good solution at all. For example, in question 4.1, the solution that has a O(s) where s is the number of bits set to 1 will end up being faster than the look up table that has a solution of O(n/L) where n is the number of bits in the input size and L is the width of the look up table.
Can someone please comment on what is appropriate and better for interview settings?
Thanks!
JOC