CareerCup

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

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?

Can't we use a balanced BST?

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

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.

/*
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 ;
    }
}