Adobe Interview Question for Computer Scientists


Team: PSE
Country: India
Interview Type: In-Person




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

Use a doubly-linked list in combination with a HashMap. The HashMap should provide value lookup by key for your cache, in O(1) time. The HashMap should also contain a pointer to the corresponding node in the doubly-linked list so that when a key is accessed, the corresponding node in the linked list can be deleted from its current position and moved to the tail, which is the position for the most recently seen node. If you see a new element you haven't seen before (that is not in your HashMap), you add it to both the HashMap and the tail of the linked list. The linked list allows you to see which element expires next in O(1) time, and if the list exceeds the number of elements you want to cache, you delete the next-expiring element from both the linked list and the HashMap.

All operations are in O(1) time (expected time, in the case of the HashMap).

If you need determinism, you can use a balanced tree sorted by key instead of the HashMap; this will be O(logN) for lookup, insert, and delete.

- eugene.yarovoi July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can a cycle linked list be better?

- notbad July 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@notbad: not really

- eugene.yarovoi July 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Use doubly linked list with a hash fucntion.
Hash funtion helps locate a node.
Double LL is needed when a node is accessed and need to be moved to head of LL(recently used.)
when elements in LL > threshold. remove element at end of LL.

- Curious July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your soln is better. Many ppl suggested on ur lines but the thing you pointed is most recent used will be placed on the head of the list and least recent used on tail of the list. Most of the time you need to work with modification of head of the list only when you dont find your match then you need to traverse down the tail

- anshulzunke August 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

import java.util.HashMap;


public class LRUCache {

	class Node{
		int key;
		int data;
		Node prev=null;
		Node next =null;
		public Node(int key, int data){
			this.data = data;
			this.key = key;
		}

		public int getKey(){
			return key;
		}
	}

	Node head = null;
	Node end = null;
	int capacity;
	int len=0;
	HashMap<Integer, Node> hm = new HashMap<Integer, Node>();

	public LRUCache(int capacity){
		this.capacity = capacity;
	}

	public void setValue(int key, int value){
		if(hm.containsKey(key)){
			Node n = hm.get(key);
			n.data = value;
			remove(n);
			setHead(n);
		}else{
			if(len<capacity){
				Node n= new Node(key, value);
				setHead(n);
				len = len+1;
				hm.put(key, n);
			}else{
				hm.remove(end.key);
				remove(end);
				Node n = new Node(key,value);
				setHead(n);
				hm.put(key, n);
			}
		}
	}
	public int getValue(int key){
		if(hm.containsKey(key)){
			Node n = hm.get(key);
			remove(n);
			setHead(n);
			return n.data;
		}
		return -1;
	}
	
	private void setHead(Node n){
		if(head == null){
			head = n;
			end =n;
		}else{
			head.prev = n;
			n.next = head;
			head = n;
		}
	}
	private void remove(Node n){
		Node pre = n.prev;
		Node post = n.next;
		if(pre==null)
			head = post;
		else
			pre.next = post;

		if(post == null)
			end = pre;
		else
			post.prev=pre;
	}
}

- Sandeep March 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think u can use minimum heap for this.

- Deepak July 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Suppose there are two very large arrays. We want to merge them into a set.  How can we do this in optimal time?

}

- SusmitaSingh09 August 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

My appologies, Maintaining minimum heap will take nlogn time , we need to reduce the time, I think LinkedHashMap or similar data structure can be used for lru cache.In case of LinkedHashMap, insertion, and deletion both take O(1) time keeping in mind that whenever we use an element we make it to the head of linkedhashmap. This way the last element will be the least used and when inserting new element we can delete the last element and insert new one in its place.

- Deepak July 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

See my implementation of the configurable and very fast MRU cache at:
codepad.org/jlzNbum3
@Evgeny: You have suggested the exact combination of DS's that I have implemented at the link above (btw, this was one of the FB phone interview questions)

- ashot madatyan July 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take a double linked list. The head will always contain the most recently used page & tail will contain the least recently page..
A hash where page number will be used for indexing will be taken. Whenever, a page fault occurs i.e. page is not in the memory[the hash slot will be empty], We will create a new node in DLL, put it in the head & store its pointer in the hash.
At any time, if a page needs to be referenced, it will be searched in the hash. If its there, we need to change at most 6 pointers to attach it at the head of DLL.
reqPage->next->prev=reqPage->prev;
reqPage->prev->next=reqPage->next;

reqPage->next=head;
reqPage->prev=NULL;
head->prev=reqPage;

head=reqPage;

- Aashish July 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

And you may need to delete the least recently seen node if your cache is a fixed-size cache.

- eugene.yarovoi July 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

sorry for above comment! ur solution is really nice !

- @shondik July 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

nice solution thanks

- anil kumar May 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

here is the solution

youtube . com / watch?v=iwyf_ElVWnI

- anish February 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;


public class LRUCache {

	class Node{
		int key;
		int data;
		Node prev=null;
		Node next =null;
		public Node(int key, int data){
			this.data = data;
			this.key = key;
		}

		public int getKey(){
			return key;
		}
	}

	Node head = null;
	Node end = null;
	int capacity;
	int len=0;
	HashMap<Integer, Node> hm = new HashMap<Integer, Node>();

	public LRUCache(int capacity){
		this.capacity = capacity;
	}

	public void setValue(int key, int value){
		if(hm.containsKey(key)){
			Node n = hm.get(key);
			n.data = value;
			remove(n);
			setHead(n);
		}else{
			if(len<capacity){
				Node n= new Node(key, value);
				setHead(n);
				len = len+1;
				hm.put(key, n);
			}else{
				hm.remove(end.key);
				remove(end);
				Node n = new Node(key,value);
				setHead(n);
				hm.put(key, n);
			}
		}
	}
	public int getValue(int key){
		if(hm.containsKey(key)){
			Node n = hm.get(key);
			remove(n);
			setHead(n);
			return n.data;
		}
		return -1;
	}
	
	private void setHead(Node n){
		if(head == null){
			head = n;
			end =n;
		}else{
			head.prev = n;
			n.next = head;
			head = n;
		}
	}
	private void remove(Node n){
		Node pre = n.prev;
		Node post = n.next;
		if(pre==null)
			head = post;
		else
			pre.next = post;

		if(post == null)
			end = pre;
		else
			post.prev=pre;
	}
}

- Sandeep March 13, 2015 | Flag Reply


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