Jane Street interview question

How would you bound the memory usage of this function?

Interview Answer

Anonymous

27 Apr 2015

I proposed to implement an LRU cache based on a JavaScript array, popping out the first element and push a new one to its end upon invoking a memoized function with a new argument (FIFO buffer). Got stuck a bit when discussing the complexity of `shift` operation in JS (turns out I don't know how JavaScript arrays are implemented).