LRU Cache - Being Asked in an Interview 🤯
Just for fun
I was in Beijing a few days ago and visited several blockchain companies, including Cobo Wallet and Bitmain Technology. Blockchain-chain-chain-chain-chain…
I went through three rounds of interviews at Cobo Wallet. Cobo was co-founded by Shenyu (creator of f2Pool, widely known as “Discus Fish”, or “神鱼”) and Jiang Changhao, an early Facebook engineer.
Besides developers, I also met their co-founders and their Product Engineer, Grace - a sharp and articulate former Software Engineer from LinkedIn. I’d say the team is energetic, driven, and capable of world-class execution. They shared some unique perspectives on blockchain and crypto. It was inspiring. Had I not visited these companies in person, I wouldn’t have believed this group of pioneers could remain so passionate in the middle of a bear market. Their optimism about crypto definitely deserves a separate post. Long story short: many of them believe another bull run will come in 2019. No comment.
The interview question that made me panic
I was asked to implement a simple LRU cache in pseudocode. My first instinct was a HashMap with hash(key) => index => LinkedList
, but I knew I needed some ordering logic.
I thought of using a TreeMap<>
, but its insertions aren’t O(1), so that was a dead end. I started to panic—this seemed like a basic problem. I explained how HashMap works and what challenges we’d face when building an LRU cache. With some hints, I eventually put together a buggy implementation. Still, I didn’t manage to cover all the edge cases.
After about 20 minutes, the interviewer smiled and said, “You should check out LinkedHashMap<>
in Java.” Just in case you haven’t heard of it either—here’s a great explanation.
It reminded me of what my Computer as an Analysis Tool professor once said:
“Not knowing what you don’t know is worse than knowing what you don’t know.”
I wouldn’t call this a trivia question. In fact, it’s a much better interview problem than the usual bubble sort or quicksort exercise.
Summary
It’s always a good idea to stay familiar with API docs—especially Java Docs for Collections, the Map interface, etc.
One question that lingers in my mind:
Should a Computer Science (CS) graduate with two years of experience be able to explain and implement this?
If so, maybe I should pursue a CS master’s. (Unfortunately, I was rejected by NUS for the August intake.)
Although I’ve tried hard to become more technical with an Information Systems (IS) degree, I can still clearly feel the technical gap between IS and CS after two years in the tech industry.
Lastly, I found this LRU cache problem on LeetCode. It’s labeled as “hard”—which makes me feel slightly better about myself :P
Comments