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."
You
"Caching? Isn't this as hard as naming things?"
Interviewer
"No, hard as off by one problems."
You
(dangit, i already look stoopid)
Interviewer
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
You
LRWho?
Interviewer
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