LRU Cache - Being Asked in an Interview 🤯
Just for fun
I was in Beijing a few days ago and visited a few BlockChain companies including Cobo Wallet and Bitmain Technology. Blockchain-chain-chain-chain-chain……
I attended three rounds of interviews at Cobo wallet. Cobo was founded by Shenyu (the creator of f2Pool, well known as “Discus Fish”, “神鱼”) and Jiang Changhao - an early employee of Facebook.
In addition to developers, I also met with their co-founders, Product Engineer (Grace - a pretty lady had worked for LinkedIn, she used to be a SE). I’d say this company is backed by a strong and energetic team that has world-class execution. They shared unique opinions on BlockChain and Crypto. Awesome. If I were not visiting the BlockChain companies in person, I would not believe this group of pioneers have such great enthusiasm in a bear market. It definitely worth writing another blog on their reasons of being optimistic about crypto currency. Long story short - many of them think another bull market will arrive in 2019. No comments.
The interview question made me panic
I was asked to implement a simple version LRU cache (pseudo code). My raw guess points me to HashMap
hash(key) => index => LinkedList, but with an ordering feature.
TreeMap<> came into my mind, but
TreeMap<> insertion is definitely not O(1). I began to panic cause I thought this is supposed to be a straightforward problem. I tried to explain how HashMap works and what problem we should resolve to implement an LRU cache. With his hints, I managed to build a buggy LRU cache. Anyways, in the end, I did not manage to cover many corner cases.
After struggling for about 20 mins, the interviewer looked at me with a smile and said: “You should check out
LinkedHashMap<> in Java”. Just FYI if you don’t know
LinkedHashMap<> either - LinkedHashMap from LRU Cache Example.
Alright, it reminds me of what my
Computer as an Analysis Tool professor taught me - “You don’t know what you don’t know is worse than you know what you don’t know.”
I would not say this is a trivia question that should not be used to test a person’s coding ability. It’s actually a question much better than writing a quicksort/bubble sort during a coding session.
It’s always good to check out API docs, especially the Java Docs about Collections, Map Interface etc..
My question is - will a Computer Science (CS) graduate with two-year working experience be able to explain it and code it out? If so, I should definitely go for a CS master. Rejected by NUS for Aug intake though. Although I tried hard to become more technical holding an Information Systems (IS) degree, I still can clearly tell the technical gap between IS and CS after working two years in technology domain.
Lastly, I found this question on LeetCode. It’s marked as “hard” which makes me feel less disappointed on myself :P.