Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

C++ Code (Queue with DLL and Hash Map)

struct LRUCacheNode {
		int key;
		int value;
		LRUCacheNode* prev;
		LRUCacheNode* next;
		LRUCacheNode(): key(0),value(0),next(NULL),prev(NULL) { } ;
} ;

class LRUCache{
private:
    hash_map< int, LRUCacheNode* >  Map;
    LRUCacheNode *  Head;
    LRUCacheNode *  Tail;
	int Capacity ;
	int Count ;
    
public:
    LRUCache(int capacity) {
		Capacity = capacity ;
		Count = 0 ;
        Head = new LRUCacheNode;
        Tail = new LRUCacheNode;
        Head->prev = NULL;
        Head->next = Tail;
        Tail->next = NULL;
        Tail->prev = Head;
    }
    
    ~LRUCache ( ) {
        delete Head;
        delete Tail;
    }
    
    int get(int key) {
        LRUCacheNode* node = Map[key];
        if(node)
        {
            DetachNode(node);
            AttachNodeToFront(node);
            return node->value;
        }
        else
        return -1 ;

    }
    
    void put(int key, int value) {
        LRUCacheNode* node = Map[key];
        if(node)
        {
            DetachNode(node);
            node->value = value;
            AttachNodeToFront(node);
        }
        else{
			LRUCacheNode* node = new LRUCacheNode ;
            if ( Capacity == Count ) { // If Cache is Full
                RemoveLRUNode ( key ) ;					
            }
            
			node->key = key;
			node->value = value;
			Map[key] = node;
			AttachNodeToFront(node);
			Count++ ;            
        }
    }
private:
	void RemoveLRUNode ( int key ) {
		LRUCacheNode* node = Tail->prev;
        DetachNode(node);
        Map.erase(node->key);
		Count-- ;
	}

    void DetachNode(LRUCacheNode* node) {
            node->prev->next = node->next;
            node->next->prev = node->prev;
    }
    
    void AttachNodeToFront(LRUCacheNode* node) {
            node->next = Head->next;
            node->prev = Head;
            Head->next = node;
            node->next->prev = node;
    }
};

- R@M3$H.N May 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good solution.

- suwei19870312 June 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCacheUsingLinkedHashMap {


	private static int CACHE_SIZE = 4;
	public static void main(String[] args) {

		// accessOrder is true, so whenever any page gets changed or accessed,    // its order will change in the map, 
		LinkedHashMap<Integer,String> lruCache = new  LinkedHashMap<Integer,String>(CACHE_SIZE, .75F, true) {

			private static final long serialVersionUID = 1L;

			protected boolean removeEldestEntry(Map.Entry<Integer,String> eldest) {
				return size() > CACHE_SIZE;
			}

		};

		lruCache.put(0, "0");
		lruCache.put(1, "1");
		lruCache.put(2, "2");
		System.out.println(lruCache);
		System.out.println("Read 1 from the cache, after reading 1 will moved to the end of cache");
		lruCache.get(1);
		System.out.println(lruCache);
		lruCache.put(3, "3");
		System.out.println(lruCache + "  , After first 4");
		lruCache.put(4, "4");
		System.out.println(lruCache);
		System.out.println("Read 2 from the cache, after reading 2 will moved to the end of cache");
		lruCache.get(2);
		System.out.println(lruCache);
		lruCache.put(5, "5");
		System.out.println(lruCache);
		lruCache.put(6, "6");
		System.out.println(lruCache);
	}

}

{0=0, 1=1, 2=2}
Read 1 from the cache, after reading 1 will moved to the end of cache
{0=0, 2=2, 1=1}
{0=0, 2=2, 1=1, 3=3} , After first 4
{2=2, 1=1, 3=3, 4=4}
Read 2 from the cache, after reading 2 will moved to the end of cache
{1=1, 3=3, 4=4, 2=2}
{3=3, 4=4, 2=2, 5=5}
{4=4, 2=2, 5=5, 6=6}

- Anonymous May 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a queue of length 10. And a hash table with key value
The hash will have the key and the corresponding element number in the queue
The value will be stored at the element number in the queue.

Put will check if key exists will remove that element from queue and add it to last. If length 10 the will remove first element remove its key from hash and add that element in the last

- DashDash May 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

You need to be able to remove elements from the middle, queues doesn't allow this

- Anonymous May 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The best bet would be to implement doubly - LinkedHashMap.

- Miral Patel May 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is LinkedHashMap Miral? Can you please elaborate

- DashDash May 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Linked Hashmap will, apart from doing its basic work i.e, storing key value pairs, also keep track of insertion order of they keys.

LinkedHashmap knows the order in which keys were added.
So if you know firstLink and lastLink of the map then,
both your get and put operations will have O(1) complexity.

get(key, value)
- Return the map.get(key) - O(1),
- Remove it from map (link.previous = link.next) and put it back in the map making it the first element of the map.

put(key, value)
- if the list is full, then lastElement.previous.next = null; (making the second last element as the last element of the map)
- add the new element and make it the firstElement of the map.

- Miral Patel May 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using priorityQueue for caching. HashMap to maintain keyset and perform faster put and get operation. setting priority based on the time of use.

package com.amazon.practice;

import java.util.Calendar;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

class LRU<K,V> implements Comparable<LRU<K,V>>{
    private long recentUseTime = Calendar.getInstance().getTimeInMillis();
    private K key;
    private V value;
	@Override
	public int compareTo(LRU<K, V> arg0) {
		// TODO Auto-generated method stub
		return Double.compare(this.recentUseTime, arg0.recentUseTime);
	}
	
	public void setPriority(long p){
		this.recentUseTime = p;
	}
	
	public LRU(K key, V value){
		this.key = key;
		this.value = value;
	}
	
	public V getValue(){
		return this.value;
	}
	
	public K getKey(){
		return this.key;
	}
	
	public void setValue(V v){
		this.value = v;
	}
	
	public void setKey(K k){
		this.key = k;
	}
	
	public String toString(){
		return "[ "+this.key+" - "+this.value+" ]";
	}
	
}

class LRUCache<K,V>{
	private Queue<LRU<K,V>> cache = new PriorityQueue<LRU<K,V>>();
	private Map<K,LRU<K,V>> keySet = new HashMap<K,LRU<K,V>>();
	
	public void put(K key,V value){
		if(this.keySet.containsKey(key)){
			(this.keySet.get(key)).setPriority(Calendar.getInstance().getTimeInMillis());
			this.cache.remove(this.keySet.get(key));
			this.cache.add(this.keySet.get(key));
		}else{
			LRU<K,V> lruNode = null;
			if(this.cache.size()==10){
				lruNode = this.cache.peek();
			}
			if(lruNode!=null){
				keySet.remove(lruNode.getKey());
				lruNode.setPriority(0);
				lruNode.setKey(key);
				lruNode.setValue(value);
			}else{
				lruNode = new LRU<K,V>(key,value);
				this.cache.add(lruNode);
			}
			this.keySet.put(key, lruNode);
		}
	}
	
	public V get(K key){
		return (this.keySet.get(key)).getValue();
	}
	
	public void printCache(){
		Iterator<LRU<K,V>> it = cache.iterator();
		System.out.println();
		while(it.hasNext())
			System.out.print(it.next().toString());
		System.out.println();
	}
	
}

public class LRUCacheTest {
	public static void main(String[] arg){
		LRUCache<String,String> cache= new LRUCache<String,String>();
		cache.put("one", "one");
		cache.put("two", "two");
		cache.put("three", "three");
		cache.put("four", "four");
		cache.put("five", "five");
		cache.put("six", "six");
		cache.put("seven", "seven");
		cache.put("eight", "eight");
		cache.put("nine", "nine");
		cache.put("ten", "ten");
		cache.printCache();
		cache.put("eleven", "eleven");
		cache.printCache();
		cache.put("seven", "seven");
		cache.printCache();
		cache.put("eleven", "eleven");
		cache.printCache();
	}
}

- AlgoAlgae May 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

User unordered_map only..whenever size is greater than 10 then remove the first element and insert it in last . if element already exists then remove it and insert it into last.

std::unordered_map<std::string,int> mymap;

void addData(std::string &key, int value)
{
std::unordered_map<std::string,int>::const_iterator got = mymap.find (key);

if ( got == mymap.end() )
{
std::cout << "not found";

if( mymap.size() >= 10)
{
mymap.erase ( mymap.begin() );
mymap.insert( key,value);
}
}
else
{
mymap.erase(key);
mymap.insert( key,value);
}
}

- rajat singh May 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the delete, the time complexity is too high.

- linusyang2016 May 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCa<K, V> {

private final int CACHE_SIZE;
private final int initialCapacity = 16;
private final float loadFactor = 0.75F;

public LRUCa(int size) {
this.CACHE_SIZE = size;
}


public LinkedHashMap<K, V> cache = new LinkedHashMap<K, V>(initialCapacity, loadFactor, true) {

private static final long serialVersionUID = 1L;


@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
boolean ifRemove = this.size() > CACHE_SIZE;
return ifRemove;
}

};


public synchronized void put(K key, V value) {
if (value == null)
return;
else
cache.put(key, value);
}


public synchronized V get(K key) {
return cache.get(key);
}

public synchronized void clear() {
cache.clear();
}



public static void main(String[] args) {
LRUCache<String, String> c = new LRUCache<String, String>(3);
c.put("1", "one"); // 1
c.put("2", "two"); // 2 1
c.put("3", "three"); // 3 2 1
c.put("4", "four"); // 4 3 2
c.get("3");

for (Map.Entry<String, String> e : c.cache.entrySet()) {
System.out.println(e.getKey() + " : " + e.getValue());
}
}
}

- Vijay May 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is compact implementation using LinkedHashMap ... hope this helps ...

public class LRUCache<String, Integer> extends LinkedHashMap<String, Integer> {
 int capacity ;
 
 public void setCapacity(int cap){
	 this.capacity =  cap;
}
 
 public LRUCache(int cap) { 
	super(cap, 1f, true); 
	
	setCapacity(cap);
	
}
	public boolean addToCache(String key, Integer val){
		if(super.size() < this.capacity)
			this.put(key,val);
		else{ 
			super.remove(getLeastAccessedEntryKey());
			this.put(key,val);
		}
		System.out.println(this);
		return true;
	}
	
	public Integer getElement(String key){
		if(this.get(key) == null)
			return null;
		return (Integer)this.get(key);
	}
	
	public String getLeastAccessedEntryKey()
	{
		String key = null;
		Set<String> keySet= this.keySet();
		Iterator< String> itr = keySet.iterator();
		if(itr.hasNext()){
			key = itr.next();
		}
		return key;
	}
	
	void printMap(){
		System.out.println(this);
	}
	
	
}

- Abhijeet Pawar May 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice one. Exactly what I was thinking of.

- Miral. May 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think before removing the least element, you need to check if element is there in the map. if there remove it and put it back. else do leastElement check.

- Milap May 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public interface LRUCache<K,V> {

V get(K key);

void put(K key, V value);
}

public class LRUCacheImpl<K,V> implements LRUCache<K, V> {

HashMap<K,V> hm;

LinkedList<K> order;

private static final int CAPACITY = 10;

public LRUCacheImpl(){
hm = new HashMap<K,V>(CAPACITY);
order = new LinkedList<>();
}

@Override
public V get(K key) {
V val = hm.get(key);

if(val != null){
promote(key);
}

return val;
}

@Override
public void put(K key, V value) {
if(hm.containsKey(key)){
hm.put(key, value);
promote(key);
} else {
if(hm.size() >= CAPACITY){
hm.remove(order.removeLast());
}

hm.put(key, value);
order.addFirst(key);
}
}

private void promote(K key){
order.removeFirstOccurrence(key);
order.addFirst(key);
}
}

public class LRUCacheTest {

LRUCache<Integer, String> cut;

private final static String ZERO = "ZERO";
private final static String ONE = "ONE";
private final static String TWO = "TWO";
private final static String THREE = "THREE";
private final static String FOUR = "FOUR";
private final static String FIVE = "FIVE";
private final static String SIX = "SIX";
private final static String SEVEN = "SEVEN";
private final static String EIGHT = "EIGHT";
private final static String NINE = "NINE";
private final static String TEN = "TEN";

@Before
public void initialize(){
cut = new LRUCacheImpl<Integer, String>();
}

@Test
public void shouldPut() {
cut.put(0, ZERO);
assertEquals(cut.get(0), ZERO);
}

@Test
public void shouldGet() {
cut.put(0, ZERO);
cut.put(1, ONE);
cut.put(2, TWO);
cut.put(3, THREE);
cut.put(4, FOUR);

assertEquals(cut.get(3), THREE);
assertEquals(cut.get(2), TWO);
assertEquals(cut.get(1), ONE);
assertEquals(cut.get(4), FOUR);
}

@Test
public void shouldRemoveLeastRecent() {
cut.put(0, ZERO);
cut.put(1, ONE);
cut.put(2, TWO);
cut.put(3, THREE);
cut.put(4, FOUR);
cut.put(5, FIVE);
cut.put(6, SIX);
cut.put(7, SEVEN);
cut.put(8, EIGHT);
cut.put(9, NINE);
cut.put(10, TEN);

assertNull(cut.get(0));
assertEquals(cut.get(10), TEN);
}

@Test
public void shouldMarkLastRecentWhenRead() {
cut.put(0, ZERO);
cut.put(1, ONE);
cut.put(2, TWO);
cut.put(3, THREE);
cut.put(4, FOUR);
cut.put(5, FIVE);
cut.put(6, SIX);
cut.put(7, SEVEN);
cut.put(8, EIGHT);
cut.put(9, NINE);

cut.get(0);
cut.put(10, TEN);

assertNotNull(cut.get(0));
assertNull(cut.get(1));
assertEquals(cut.get(10), TEN);
}

@Test
public void shouldMarkLastRecentWhenOverridden() {
cut.put(0, ZERO);
cut.put(1, ONE);
cut.put(2, TWO);
cut.put(3, THREE);
cut.put(4, FOUR);
cut.put(5, FIVE);
cut.put(6, SIX);
cut.put(7, SEVEN);
cut.put(8, EIGHT);
cut.put(9, NINE);

cut.put(0, NINE);
cut.put(10, TEN);

assertNotNull(cut.get(0));
assertNull(cut.get(1));
assertEquals(cut.get(10), TEN);
}
}

- kabexnuf May 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using a struct and a list:

{
struct element
{
	int key;
	int value;
};

class LRUcache
{
private:
	int max_size;
	int current_size;
	list<element*> l;
public:
	LRUcache()
	{
		max_size = 10;
		current_size = 0;
	}
	int get(int key)
	{
		int value = -INT32_MAX;
		for(list<element*>::iterator it = l.begin(); it != l.end(); it++)
		{
			if((*it)->key == key)
			{
				value = (*it)->value;
				list<element*>::iterator aux = it;
				l.erase(it);
				l.push_front(*aux);
				return value;
			}
		}
		return value;
	}
	void put(int key, int value)
	{
		element * e = new element;
		e->key = key;
		e->value = value;
		
		if(current_size == max_size)
		{
			cout << "replacing oldest value: " << l.back()->key << " " << l.back()->value << endl;
			delete l.back();
			l.pop_back();
			current_size--;
		}
		l.push_front(e);
		current_size++;
	}
};

}

- NL May 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The problem requires us to maintain a searchable queue since I not only have to access the LRU, but also search for a key value in the queue optimally.

One way to attain O(log(n)) search with a well ordered queue is to assign a running number to every item in the queue, which is stored against the hash value of the key.

Let us say for cache size of 3, my input is A, B, C, B.

My queue at the end of 4th input will look like: A, C, B

Searching for B linearly is very expensive. One way to get O(log n) is to add ordered numbering to this queue. One way to do is by assigning every item that is added to the queue a number +1 of the number assigned to MRU.

Thus for this queue, I will have: A1, B2, C3, B4

My queue at the end of 4th input will look like: A1, C3, B4. My hash will look like:
A(1):A Value
B(4): B Value
C(3); C Value

Thus while accessing any key value, I will know the number assigned to it in the queue, and since the way numbering is assigned is in incremental order, I will be able to located that in O(log n) to be able to put it at the end of the queue. The item will then get a new number and the hash key will be updated with that number as well.

- y1426i May 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Map;
import java.util.TreeMap;


public class LRU {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Map<Integer,Integer> lruMap = new TreeMap<Integer, Integer>();

// By Default all element has 1 occurance in map.
lruMap.put(0, 1);
lruMap.put(3, 1);
lruMap.put(4, 1);
lruMap.put(6, 1);
lruMap.put(9, 1);
lruMap.put(8, 1);
lruMap.put(7, 1);
lruMap.put(2, 1);
lruMap.put(5, 1);
lruMap.put(1, 1);

// new entry to Map (here I am making 15 as new entry
int addNew = 15;
Boolean flag = true;
Map.Entry<Integer, Integer> min = null;

// Checking if map has same key entry then I am incrementing the value in Map.
for(Map.Entry<Integer, Integer> entry : lruMap.entrySet()){
if(entry.getKey().equals(addNew)){
lruMap.put(addNew, entry.getValue()+1);
flag = false;
}
}

// If Map has new entry then I am removing element having minimum value.
if(flag){
for(Map.Entry<Integer, Integer> entry : lruMap.entrySet()){

if(min == null || min.getValue() > entry.getValue()){
min = entry;
}
}

lruMap.remove(min.getKey());
lruMap.put(addNew, 1);
}

for(Map.Entry<Integer, Integer> entry : lruMap.entrySet()){

System.out.println("Key "+ entry.getKey() +" Value "+ entry.getValue());

}

}

}

- Amit@1220 May 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Apparently, the simplest possible implementation is,

public class LRUCache extends LinkedHashMap<Integer, String>{
	
	private int cacheSize;
	
	public LRUCache(int size) {
		super(size, 0.75f, true);
		this.cacheSize = size;
	}
	
	@Override
	protected boolean removeEldestEntry(
			java.util.Map.Entry<Integer, String> eldest) {
		// remove the oldest element when size limit is reached
		return size() > cacheSize;
	}
}

- Miral Patel May 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package zhang.juanyong.interview.amazon;

import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;

import org.apache.commons.lang.math.RandomUtils;

/**
 * 
 * @author Juanyong
 * 
 *         Implement LRU cache of size 10 which can store Key, Value pair.
 *         (get(key) & put(key,value) methods) - If we try to add 11th element,
 *         the least recently used element should get removed. - If key already
 *         present, overwrite it and mark it as most recently used.
 */
public class LRUCache2<V> {

	private final int capacity;

	private Map<V, Long> cache = new LinkedHashMap<V, Long>() {
		private static final long serialVersionUID = 5592193692539799835L;

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

	public LRUCache2(int size) {
		super();
		this.capacity = size;
	}

	public void put(V obj) {
		try {
			Thread.sleep(1);
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Long timestamp = System.currentTimeMillis();
		cache.put(obj, timestamp);
	}

	public void printCache() {
		TreeMap<Long, V> sortedMap = new TreeMap<Long, V>();
		for (V key : cache.keySet()) {
			sortedMap.put(cache.get(key), key);
		}

		for (Long key : sortedMap.descendingKeySet()) {
			System.out.println(key + " = " + sortedMap.get(key));
		}
	}

	public static void main(String[] args) {
		int[] arr = new int[20];
		LRUCache2<Integer> lruCache = new LRUCache2<Integer>(10);
		PriorityQueue<Integer> pQ = new PriorityQueue<Integer>(5,
				Collections.reverseOrder());

		for (int i = 0; i < arr.length; i++) {
			int value = RandomUtils.nextInt(10000);
			arr[i] = value;
			lruCache.put(value);

			pQ.add(value);
		}
		lruCache.printCache();
		System.out.println(pQ);
	}
}

- QAQ May 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The best solution would be :

import java.util.LinkedHashMap;
import java.util.Map;

public LRUCache<K, V> extends LinkedHashMap<K, V> {
  private int cacheSize;

  public LRUCache(int cacheSize) {
    super(16, 0.75, true);
    this.cacheSize = cacheSize;
  }

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

- Anonymous June 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;

@SuppressWarnings("serial")
class LRUCacheImplement<K, V> extends LinkedHashMap<K, V> {
	  private int cacheSize;

	  public LRUCacheImplement(int cacheSize) {
	    super(16, (float) 0.75, true);
	    this.cacheSize = cacheSize;
	  }

	  protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
	    return size() > cacheSize;
	  }
	  
	  public void displayEntries(){
		  Iterator itr=this.entrySet().iterator();
		  
		  while(itr.hasNext())
		  {
			 System.out.println(itr.next());
		  }
	  }
	}

- zv.patel June 09, 2014 | Flag


Add a Comment
Name:

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

Books

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

Videos

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