Interview Question for Software Engineers

Country: United States

Comment hidden because of low score. Click to expand.
of 1 vote

LinkedHashMap. Cannot post link, so you can google it.

impletement LRU class which extends LinkedHashMap and override removeEldestEntry like this:

class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V>{  
    private int capacity;  

    LRULinkedHashMap(int capacity){  

    protected boolean removeEldestEntry(Map.Entry<K, V> eldest){   
        return size() > capacity;  

- Guozi149 October 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
of 1 vote

protected boolean removeEldestEntry(...) ?

- blckembr October 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
of 0 vote

Keep a linked list in the node for each entry. In Swift:

class CacheEntry {
    var next : CacheEntry?
    let value : String
    let key : String
    init(key : String, value : String) {
        self.value = value
        self.key = key // only used for deletion

class Cache {
    var entries : [String: CacheEntry] = [:]
    var head : CacheEntry? = nil
    let cacheMax : Int
    var cacheCount = 0
    init(maxSize : Int) {
        self.cacheMax = maxSize
    func findKey(key : String) -> String? {
        return entries[key]?.value
    func insert(key : String, value : String) {
        let newEntry = CacheEntry(key: key, value: value)
        entries[key] = newEntry = head
        head = newEntry
        if cacheCount > cacheMax {
            let (prev, last) = findLast()
            if let last = last {
                if let prev = prev {
           = nil
                entries[last.key] = nil
    func findLast() -> (CacheEntry?, CacheEntry?) {
        var prev : CacheEntry? = nil
        var element: CacheEntry? = head
        repeat {
            prev = element
            element = element?.next
        } while element?.next != nil
        return (prev, element)
    func printLinkedList() {
        var element : CacheEntry? = head
        repeat {
            element = element?.next
        } while element?.next != nil
let cache = Cache(maxSize: 5)
cache.insert("A", value: "AV")
cache.insert("B", value: "BV")
cache.insert("C", value: "CV")
cache.insert("D", value: "DV")
cache.insert("E", value: "EV")
cache.insert("F", value: "FV")
cache.insert("G", value: "GV")

- possen October 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 votes

your findLast() function has O(n) complexity which would make cache insert very inefficient when the capacity is at full.

It would be the same as though we implement the cache using a linked list

- anonus October 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
of 0 vote

Not particularly efficient or clean, but simple. Keeps a counter of "age" (in terms of number of operations on the cache), and simply evicts the entry with the minimal age when inserting into a full cache.

# implement a LRU cache with only a single container

class LRU:
    size = 3
    cache = {}
    counter = 0
    def __init__(self, size=3):
        self.size = size
    def find(self, key):
        if key not in self.cache:
            return None
        entry = self.cache[key]
        entry[1] = self.counter
        self.counter += 1
        self.cache[key] = entry
        return self.cache[key][0]
    def insert(self, key, val):
        if len(self.cache) >= self.size: # find the oldest, to evict
            lruK = None
            lruAge = None
            for k in self.cache.keys():
                entry = self.cache[k]
                if lruK == None:
                    lruK = k
                    lruAge = entry[1]
                    if entry[1] < lruAge:
                        lruK = k
                        lruAge = entry[1]
            del self.cache[lruK]
        self.cache[key] = [val, self.counter]
        self.counter += 1

- mjf October 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

I read it from here once : Java Generics and collections --> page 229

We can use make a class that extends class LinkedHashMap, it has a function removeEldestEntry which we can override.
The Idea behind implementation is to have a map and let it grow till it reaches its capacity. Then we can remove the oldest element from the map which is exactly like removing the least recenty element from cache.

Following is the implementation:


class LRUCache<K,V> extends LinkedHashMap<K,V>{
		private int maxEntries;
		public LRUCache(int maxEntries){
			super(16,0.75f,true); // 16 is initial capacity and 0.75f is load factor
			this.maxEntries = maxEntries;
		protected boolean removeEldestEntry(Map.Entry<K,V> eldest){
			return size() > maxEntries; 

- lordzuko October 08, 2015 | Flag Reply

Add a Comment

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.


is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More


CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More