Amazon Interview Question for Software Developers


Country: India
Interview Type: Written Test




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

Can you clarify the problem with input and expected output? At first glance, a hashmap would be efficient for findStockPriceAtGivenTimeStamp, but for deleteAndGetMinimumStockPriceForToday I need some input/out examples to detail its implementation( i.e minHeap or even extra min variable in each hash entry might suffice, or another hashMap to hold day's min). Can you clarify the problem more?

- tnutty2k8 September 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can't we use a balanced BST?

- Bgeek September 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Below are the expected I/O

TimeStamp - 1, 2, 3, 4, 5
Price - 12,34,4,1,18

findStockPriceAtGivenTimeStamp(3)
Output - 4

deleteAndGetMinimumStockPriceForToday()
Output - 1

findStockPriceAtGivenTimeStamp(2)
Output - 34

deleteAndGetMinimumStockPriceForToday()
Output - 4

- bholeNath September 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There is some clarification needed here

What is meant by delete? Are we deleting the entire log and returning the minimum value, or are we deleting the minimum value? If we're deleting the minimum value, we need to keep the values in a min-heap. Otherwise, we can just keep track of the minimum value as it comes in, and replace it if there is a lower one.

Additionally, keeping the incoming (timestamp, price) tuples in an random access array, we can find prices at a given timestamp in either constant time, if the timestamps are regular known, intervals, or in logN with binary search through the array if the timestamps are not regular, known intervals.

Pointers from the min-heap nodes to the array will allow us to delete individual items, but if we do, we must use binary search to find timestamps since the array indices will no longer be analogous to timestamp intervals in the regular interval case.

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

/*
store stock prices and timestamp both in a map and a priority queue to access.
changes during insertion and deletion should be cascaded to both the queue and the map
 */
public class StockPricesEtc {

    public static void main(String[] args) {
        /*TimeStamp - 1, 2, 3, 4, 5
        Price - 12,34,4,1,18
        */
                StockPricesEtc spe = new StockPricesEtc();
                spe.put(1L,12);
                spe.put(2L,34);
                spe.put(3L,4);
                spe.put(4L,1);
                spe.put(5L,18);

        System.out.println(spe.findStockPriceAtGivenTimeStamp(3L));
        //Output - 4

        System.out.println(spe.deleteAndGetMinimumStockPriceForToday());
        //Output - 1

        System.out.println(spe.findStockPriceAtGivenTimeStamp(2L));
        //Output - 34

        System.out.println(spe.deleteAndGetMinimumStockPriceForToday());
        //Output - 4
    }
    private
    Map<Long, Wrap> map = new HashMap<>();
    private PriorityQueue<Wrap> min = new PriorityQueue<>((x, y) ->
    {
        double d = x.d-y.d;
        return Math.abs (d )< 0.0001 ? 0 : (d < 0 ? -1 : +1);
    });

    class Wrap {
        private Long t;
        private Double d;

        Wrap(Long t, Double d) {
            this.t = t;
            this.d = d;
        }

    }


    void put(Long timestamp, double price) {
        Wrap w = new Wrap(timestamp, price);
        map.put(w.t, w);
        min.offer(w);
    }
    Double findStockPriceAtGivenTimeStamp (Long t ) {
        Wrap w = map.get(t);
        return w == null ? -1.0: w.d;
    }
    Double deleteAndGetMinimumStockPriceForToday (){
        Wrap w = min.poll();
        if (w== null) return -1.0;
        map.remove(w.t);
        return w.d ;
    }
}

- Makarand September 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I assume streaming related questions should be tackled using observer design pattern.

- steephen September 22, 2017 | 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