Interview at your favorite DVD shipping company

You are nervous, but ready.
Did the algorithms course, Mom's spagetti

The Interview

"Well we have a simple interview today. I want you to help design an algorithm for caching."


"Caching? Isn't this as hard as naming things?"


"No, hard as off by one problems."


(dangit, i already look stoopid)


Ok, I need you to write a caching layer that will cache N items based on key. When N is exceeded, the cache will eject the Least Recently Used item from cache.

In other words, an LRU




Great joke, very excited to see your solution. Oh and please discuss the time complexity of your algorithm after you successfully whiteboard it, then code it.

Mom's Spagetti

Ok its not that bad.

We have all the tools we need, we just need to combine a few algorithms / data structures together to make this work out.

To the whiteboard

Implementation if there is time!

Time check