Goldman Sachs Interview Question
Software Engineer / DevelopersTeam: Strategies Group
Country: India
Interview Type: In-Person
Well searching time in a max heap can be optimized upto N/2 at max, so according to me a regular max heap won't help. You can either choose an
1. Skip list: Which on average take O(log n) time for inserting,searching and replacing. You can keep a pointer to the last node always for LRU entry, updation of which will O(1) time if Skip list is implemented using a Quad node.
2. Heap structured search trees (HSST) looks another good option. But skip list being a standard and more evolved DS, I would like to give it a shot at first.
just a priority queue should be fine. It can be implemented by linkedlist. all nodes are sorted so that inserting, searching and replacing will take log(n) time
Array of structure...
struct page
{
int page_no;
int flag;
}
if flag=0, it means that page is not in memory..
otherwise it is preasent in memory.
array is sorted..
In this way we don't have to delete any elment.
Just search and update the flag.
Searching takes O(logn) time and updating flag takes O(1) time.
1) Construct a linked list of pages present in the cache such that the "least recently used" page will always be at end and the "most recently used" page will always be in front of the list. Each node of the list contains the page number and it's address in the cache.
2) Construct a "height balanced" binary search tree (like AVL tree). Each node of the tree will store the page number and the address of corresponding node of the linked list.
FOR EACH REQUEST: Search the page number in the tree (O(log n)).
=> If the page is present in the list then delete this node from the list and insert it in front of the list (O(1)).
=> If page is not present then load it from memory and insert it front of the list (O(1)). Insert corresponding node in the tree (O(log n)).
=> If the list is full then delete the last node from the list (O(1)) and the corresponding node from the tree (O(log n)).
NOTE that we can also perform all the operations in constant average time using HashMaps.
Use a double-linked list to store the pages with the most recently used page in the head of the list and the least recently used page in the back of the list.
APage<=>BPage<=>CPage
Then use a map to map the page ID to the page.
A->APage
B->BPage
C->CPage
Search: O(1) from the map, O(1) remove and add to front of list
Insert: O(1) in the map, O(1) by adding to the front of the list
Replace: O(1) in the map, O(1) by removing from back of list and adding to front of list
Delete data by scheduler using cleanData method.
package com.learning.lru;
import java.util.ArrayList;
import java.util.concurrent.locks.ReentrantReadWriteLock;
public class MyLRUCache {
private ArrayList<Data> dataHolder = new ArrayList<Data>();
ReentrantReadWriteLock lock = new ReentrantReadWriteLock(true);
private final long dataLifetime = 5000;
public Data getData(int i) {
try{
lock.readLock().lock();
if(dataHolder.size() == 0){
System.out.println(" NO Data Found");
return null;
}
return dataHolder.get(i);
}finally{
lock.readLock().unlock();
}
}
public boolean putData(Data d) {
try{
lock.writeLock().lock();
dataHolder.add(d);
return true;
}finally{
System.out.println(" Final Data size "+dataHolder.size());
lock.writeLock().unlock();
return false;
}
}
public boolean cleanData() {
int i=0;
if( dataHolder.size()==0){
System.out.println(" NO Data to clean");
return true;
}else{
System.out.println(" Data Size "+ dataHolder.size());
System.out.println(" lock status "+lock.getReadHoldCount());
}
try{
lock.writeLock().lock();
for(Data d : dataHolder){
if(System.currentTimeMillis()-d.getTimeStamp().getTime() > dataLifetime){
//tempHolder.add(d);
dataHolder.remove(i);
i++;
}
}
}finally{
lock.writeLock().unlock();
return false;
}
}
}
//Client code
package com.learning.lru;
import java.util.Date;
public class LRUClient {
public static void main(String[] args) {
MyLRUCache cache = new MyLRUCache();
LRUClient client = new LRUClient();;
Thread lruc = new Thread(client .new LRUConsumer(cache));
Thread lrup = new Thread( client .new LRUProducer(cache));
Thread lrucl = new Thread( client .new LRUCleaner(cache));
lrup.start();
lruc.start();
lrucl.start();
//use scheduled
}
class LRUConsumer implements Runnable{
MyLRUCache cache ;
LRUConsumer(MyLRUCache cache ){
this.cache=cache;
}
@Override
public void run() {
try {
Thread.sleep(10);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println(" Consuming Data ---------->>>>>>>>");
while(true){
for(int i=0; i<20;i++){
//System.out.println(" DATA :>>>"+cache.getData(i));
}
}
}
}
class LRUProducer implements Runnable{
MyLRUCache cache ;
LRUProducer(MyLRUCache cache ){
this.cache=cache;
}
@Override
public void run() {
try {
Thread.sleep(10);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println(" Putting Data ---------->>>>>>>>");
for(int i=0; i<20;i++){
cache.putData( new Data(i, new Date(System.currentTimeMillis())));
}
}
}
class LRUCleaner implements Runnable{
MyLRUCache cache ;
LRUCleaner(MyLRUCache cache ){
this.cache=cache;
}
@Override
public void run() {
try {
while(true){
//Thread.sleep(3000);
System.out.println(" Cleaning Data ---------->>>>>>>>");
cache.cleanData();
}
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
}
Why not use double linked list and a Hash (made from RB trees like in C++)? Inserting would involve checking first whether value already present which takes log n time. The Hash would store node address with value in node as key.
- anantkaushik89 June 12, 2013