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


  • 0
    H

    @elmirap For your set.remove(new AbstractMap.SimpleEntry<>(stock, map.get(stock)));, I don't think it will remove the existing element in the set. Unless you give the exact same object so that it can be removed


Log in to reply
 

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