Stock Ticker


  • 0
    M

    @elmirap Thanks for the sharing those. I'm still trying to fully understand this.
    Assuming we a stream of key val pairs: thinking about using a heap.
    Are you removing the elements from the heap? I thought its just returning values of the top K stocks. Is even returning top K from heap is O(klogn)?
    Secondly I thought "heapify" is O(n) --- you wrote O(log n) <-- I think O(log n) is for inserting into a existing heap. And heapify is building a heap from scratch.
    Inserting into a heap is O(log n). What is the final datastructure being used here? Sorry python user here..
    Please correct me if I am wrong.


  • 0
    M

    Here is my solution. I used a HashMap in conjunction with quickselection.

    • Inserting a stock is O(n)
    • Updating a stock is O(1)
    • Getting top k stocks (not in sorted order) is O(n) average case
    public class StockTicker {
        public class Stock{
            String sym;
            double price;
    
            public Stock(String s, double val){
                this.sym = s;
                this.price = val;
            }
        }
    
        HashMap<String,Stock> st;
        HashMap<String,Integer> ind;
        int unique;
        int max;
        Stock[] stocks;
    
        public StockTicker(int k){
            this.unique = 0;
            this.max = k;
            this.st  = new HashMap<String, Stock>();
            this.ind =  new HashMap<String, Integer>();
            this.stocks = new Stock[k];
        }
    
    
        public void addOrUpdate(String sym, double price){
            if(!st.containsKey(sym)){
                Stock stock = new Stock(sym,price);
                st.put(sym, stock);
                ind.put(sym, unique);
                stocks[unique++] = stock;
            }
            else{
                Stock update = st.get(sym);
                update.price = price;
            }
        }
    
        public List<Stock> top(int k){
            List<Stock> res = new ArrayList<Stock>();
            Stock[] temp = new Stock[max];
            for(int i = 0; i < temp.length; i++){
                temp[i] = new Stock(stocks[i].sym, stocks[i].price);
            }
    
            int top = quickselect(temp, 0, temp.length-1, k);
    
            for(int i = 0; i <= top; i++){
                res.add(temp[i]);
            }
            return res;
        }
    
        public int quickselect(Stock[] stocks, int left, int right, int kth){
            if(left == right){
                return left;
            }
    
            int split = partition(stocks, left,right);
    
            if(kth-1 == split){ return split;}
            else if(kth-1 > split){ return quickselect(stocks,split + 1, right, kth);}
            else { return quickselect(stocks, left , split-1, kth);}
        }
    
        public int partition(Stock[] stocks, int left, int right){
            int lastIndex = right;
            double pivot = stocks[lastIndex].price;
            while(left <= right){
                while( left <= right && stocks[left].price > pivot ){
                    left++;
                }
                while( left <= right && stocks[right].price <= pivot){
                    right--;
                }
                if(left <= right && stocks[left].price <= pivot && stocks[right].price > pivot){
                    swap(stocks,left,right);
                }
            }
            swap(stocks,left,lastIndex);
            return left;
        }
    
        public void swap(Stock[] stocks, int x, int y){
            Stock eleX = stocks[x];
            Stock eleY = stocks[y];
            stocks[x] = eleY;
            stocks[y] = eleX;
        }
    
        public Stock getStock(String sym){
            return st.get(sym);
        }
    }
    
    '''

  • 0
    S

    Similar idea. But clearing the PriorityQueue and adding all when calling top k. addUpdate just puts the stock in Hashmap.

    package com.practice.algo.and.ds.hashing;

    import java.util.Comparator;
    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Map;
    import java.util.PriorityQueue;

    //https://discuss.leetcode.com/topic/7/stock-ticker
    public class HashMap_LeetCode_Blmberg_StockTicker {

    public static void main(String[] args) {
        HashMap_LeetCode_Blmberg_StockTicker o = new HashMap_LeetCode_Blmberg_StockTicker(3);
        o.addOrUpdate("a",100.0);
        o.addOrUpdate("b",110.0);
        o.addOrUpdate("c",120.0);
        System.out.println(o.top());
        o.addOrUpdate("d",130.0);
        o.addOrUpdate("d",140.0);
        System.out.println(o.top());
        o.addOrUpdate("a",150.0);
        System.out.println(o.top());
    }
    private Map<String,Double> tickerMap;
    private PriorityQueue<Map.Entry<String, Double>> pq ;
    int k;
    public HashMap_LeetCode_Blmberg_StockTicker(int k){
    
        this.k = k;
        pq = new PriorityQueue<>(new Comparator<Map.Entry<String, Double>>() {
            @Override
            public int compare(Map.Entry<String, Double> o1, Map.Entry<String, Double> o2) {
                return o2.getValue().compareTo(o1.getValue());
            }
        });
        tickerMap = new HashMap<>();
    }
    
    public void addOrUpdate(String stock, Double price){
        tickerMap.put(stock,price);
    }
    
    public List<Map.Entry<String, Double>> top(){
        List<Map.Entry<String, Double>> result = new LinkedList<>();
        pq.clear();
        pq.addAll(tickerMap.entrySet());
        int i=0;
        while(i<k){
            result.add(pq.poll());
            i++;
        }
        return result;
    }
    

    }


  • 0
    K

    unordered_map<string, double> stock_dict;
    2.map<string, unordered_map<string, double>::iterator> > stock_map;

    we can customize the sort function of stock_map.

    complexity analisys:


  • 0
    O
    This post is deleted!

  • 0
    O

    @xidui Hi, can you elaborate more about "customizing the sort function of stock_map"? I though the sort
    function can be only applied to the key of a map, which is the stock name in your answer.

    Thanks a lot!

    Ref:https://stackoverflow.com/questions/2453425/how-can-i-sort-a-map-by-its-second-parameter


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.