Expedia Interview Question
Software DevelopersCountry: United States
package ds.heaps;
import java.util.Comparator;
import java.util.Date;
import java.util.PriorityQueue;
class MinMaxPrinter {
static PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // max heap
static Comparator<Integer> c = new Comparator<Integer>() {
public int compare(Integer a , Integer b) {
return b - a;
}
};
static PriorityQueue<Integer> maxHeap = new PriorityQueue<>(c);
public static void main(String[] args) {
Runnable r1 = new Runnable() {
public void run() {
java.util.Random random = new java.util.Random();
while(true) {
int r = random.nextInt(1000000);
minHeap.add(r);
maxHeap.add(r);
sleep(100);
}
}
};
Thread t1 = new Thread(r1);
t1.start();
Runnable r2 = new Runnable() {
public void run() {
while(true) {
sleep(30000);
System.out.println("Printing min max at " + new Date(System.currentTimeMillis()).toString());
System.out.println(" min size " + minHeap.size());
System.out.println(" max size " + maxHeap.size());
System.out.println("Min " + minHeap.poll());
System.out.println("Max " + maxHeap.poll());
}
}
};
Thread t2 = new Thread(r2);
t2.start();
}
private static void sleep(int t) {
try{
Thread.sleep(t);
} catch(InterruptedException e) {
e.printStackTrace();
}
}
}
Here is the code I wrote to get the same done with a Priority Queue for the part 1.
For part 3 it is simple, you poll() 10 elements when you reach the time out.
I am not sure about part 2. What are your ideas?
package ds.heaps;
import java.util.Comparator;
import java.util.Date;
import java.util.PriorityQueue;
class MinMaxPrinter {
static PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // max heap
static Comparator<Integer> c = new Comparator<Integer>() {
public int compare(Integer a , Integer b) {
return b - a;
}
};
static PriorityQueue<Integer> maxHeap = new PriorityQueue<>(c);
public static void main(String[] args) {
Runnable r1 = new Runnable() {
public void run() {
java.util.Random random = new java.util.Random();
while(true) {
int r = random.nextInt(1000000);
minHeap.add(r);
maxHeap.add(r);
sleep(100);
}
}
};
Thread t1 = new Thread(r1);
t1.start();
Runnable r2 = new Runnable() {
public void run() {
while(true) {
sleep(30000);
System.out.println("Printing min max at " + new Date(System.currentTimeMillis()).toString());
System.out.println(" min size " + minHeap.size());
System.out.println(" max size " + maxHeap.size());
System.out.println("Min " + minHeap.poll());
System.out.println("Max " + maxHeap.poll());
}
}
};
Thread t2 = new Thread(r2);
t2.start();
}
private static void sleep(int t) {
try{
Thread.sleep(t);
} catch(InterruptedException e) {
e.printStackTrace();
}
}
}
(a) How do you prevent the minHeap.add(r) (etc) calls from interacting with the calls that read the heaps in the other thread (minHeap.size(), minHeap.poll(), etc)?
(b) My reading of the Q is that the min/max should be for each 60-second intervals, not for all time measured every 60(?) seconds. I don't think anything is resetting the min/max values.
Getting it all to work with multiple threads seems straightforward. Each server needs to keep its local maxima/minima. Then after 60 seconds, another process obtains the various threads' values and completes the arithmetic (comparing those variables and producing global maxima/minima).
Hi,
for first part
1. While reading you do not need the lock
2. While updating you need lock.
so ,
UpdateAPI (int num){
lock;
if(max<num){ max=num;}
if(min>mum){ min=num;}
unlock;
}
}
PrintAPI(){
cout<<max<<min;
}
Some might argue, at the time of update being called in some other thread goes for print then the data is inconsistent,
indeed it that way. This code is written with that intention. If consistency is important then, we got to do the lock / unlock in the print code as well.
PrintAPI(){
lock;
cout<<max<<min;
unlock;
}
second part is just load balancing.
Third part is interesting. we need 10 numbers now, hence one variable will not do
we need have an enlarge data structure
- Anonymous June 09, 2015