OK my solution sucks on every level. I will do this again..
Now my sucky solution has two maps. One to map a key to a value, another one to map a key to its age. Apparently this will make every operation so expensive thanks to the key->age map. I end up updating the age of every key for both get and set.
So this most straightforward solution will guarantee you to fail large test cases. A smarter data structure is required. Why is the first solution slow? Because our data structure contains more information than what we really need. We don't need ages, but just the ordered. So instead of using a key->age map, we can actually just maintain a list to keep record of this order. If one ket gets used, we move the corresponding node to the beginning, and when we need to add another node into the list but the list already reaches the capacity, we drop the last one.
Now the expensive operation becomes the node lookup. Instead of doing a regular linear lookup, however, we use another map to map a key to its corresponding node in the list. Now even the node lookup is constant.
Alright, I need to code this out... And I just did, and i just updated my github repo. :) Check out the history of LRUCache.cc file.
(This makes me want write about another two data structures I recently learned. One is SkipList, ons is a custom data structure that can do pretty much everything in constant time. I will do this when i have the time.)
Largest Rectangle in Histogram
I admit this is too hard for me. So I learned the optimal solution from here. The time complexity is linear. There is also a divide-and-conquer solution that takes O(n logn). And of course there is always the naivest one you can resort to, which takes O(n^2).
Now I'm the type of people who are not able to come up with the linear solution myself. And I know I'm not the only one. I think our club isn't a small one. Now imagine someone in this club, for example, me, walks into a job interview, and is given the problem, and the interview expects the poor interviewee to come up with the linear solution. He/she'd be doomed. I'd be doomed. And I know I will walk out from the interview, thinking, f*, I'm doomed; and f*, it ain't fair to decide if I can fulfill this position by asking me this particular problem.
It just isn't so freaking fair. But what can you do... sigh..