Expedia Interview Question for Software Developers


Country: United States




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

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();
        }
    }

}

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

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();
        }
    }

}

- bandu June 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
        }
    }

}

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

(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).

- CFE June 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Ashutosh September 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void moveZeroes(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}

int curt = nums.length - 1;

for (int i = nums.length - 1; i >= 0; i--) {
if (nums[i] != 0) {
int temp = nums[i];
nums[i] = nums[curt];
nums[curt--] = temp;
}

}

- gogoloda February 16, 2018 | 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