Stock Ticker


  • 3

    Give a stream of stock prices, design a data structure to support the following operations:

    1. StockSticker(int k) Initialize the size of the ticker.
    2. void addOrUpdate(String stock, double price) add or update the price of a stock to the data structure.
    3. List<Map.Entry<String, double>> top() return the top k price stocks and their current prices.

  • 2
    1. 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:

    • initialize
      1. O(n * log n)
    • update price
      1. insert hash map which is O(1)
      2. delete from set and insert new item into set which are both O(log n)
    • get top k
      1. O(k)

  • 0
    Y

    This solution is great!


  • 0

    Why get top k has O(1) time complexity?
    Could you explain also what is stored in set<string, unordered_map<string,double>>, it is a little unclear for me. Thank you!


  • 0

    @elmirap
    Sorry, it is O(k), since the map is always sorted with the specified function(By default, it will be the key that is string). We can specify the sort function when we declare the map. We can get the top k items just by iterator++ k times, each time is O(1).

    The string stores the stock name, and the iterator points to the stock_dict.


  • 8

    Something similar, but in java.
    add update price -O(log(n)), red black tree is used
    get top(k) - O(k)

          public class StockTicker {	    
    	    	private int k;
    	    	private HashMap<String, Double> map;
    	    	private TreeSet<Map.Entry<String, Double>> set;
    	    	
    	    	public StockTicker(int k) {
    	    		this.k = k;
    	    		map = new HashMap<String,Double>();
    	    		set = new TreeSet<> (new Comparator<Map.Entry<String, Double>>() {
    					@Override
    					public int compare(
    							java.util.Map.Entry<String, Double> obj1,
    							java.util.Map.Entry<String, Double> obj2) {
    						int res = obj2.getValue().compareTo(obj1.getValue());
    						if (res == 0)
    							return obj2.getKey().compareTo(obj1.getKey());	
    						return res;
    					}
    	    			
    	    		});
    	    	}
    	    	
    	    	public void addOrUpdate(String stock,  double price)  {
    	    		AbstractMap.SimpleEntry<String, Double> entry =  new AbstractMap.SimpleEntry<>(stock,  price);	
    	    		if (map.containsKey(stock)) {
    	    				set.remove(new AbstractMap.SimpleEntry<>(stock, map.get(stock)));	    				
    	    		}
    	    		map.put(stock, price);
    		    	set.add(entry);     		
    	    	}
    	    	
    	    	public List<Map.Entry<String, Double>> top() {
    	    		List<Map.Entry<String, Double>> ls = new ArrayList<>();
    	    		int i = 0;
    	    		Iterator<Map.Entry<String, Double>> setIterator = set.iterator();
    	    		while (i  <  k && setIterator.hasNext()) {
    	    			ls.add(setIterator.next());
    	    			i++;
    	    		}
    	    		return ls;
    	    	}
    	    }
    

  • 0
    A

    Can't we use a min heap of size K ... ? With a comparator based of stock price.


  • 0

    @Ajeet_Singh MinHeap will allow you to get top K, but how to implement efficiently update ?


  • 0
    A

    MinHeap also has same complexity for insert and update - O(log n), like BTree or @xidui's approach with unordered_map. Even it is simpler and more suitable DS for such kind of scenarios. Please correct me if i am wrong.


  • 2

    @Ajeet_Singh In my view there are differences using both structures. For example :
    Get top elements
    You have to remove first top k elements from the heap and to insert them again. 2*klog(n) .The complexity is worst compared to O(k) in the case of a tree. Heap is partially ordered data structure not fully ordered as tree.

    AddorUpdate
    Using a heap , you have to search in the heap with complexity O(nlog(n) to find if element exists (get top element from heap, check, remove,next and so on). With map it is constant, log(n) to update the tree. Again heap satisfy jheap property, there is not full order.


  • 0
    Y

    @elmirap I thought we may use a heap with size K and a hash table to store the full data. In this case, the time complexity to get first K (remove from heap and heapify again) is 2*K.
    Update and insert from heap in this case would be O(logK) if we need to update the heap.


  • 0

    @yrxwin The time complexity of getting first top k elements from heap is klog(n), because each time you remove the first element, the heap heapify to maintain its heap property. Building Heap is O(n) op, but heapify is O(log(n)) .There is no such concept to take first K element form Map (in C++ is unordered map I think)
    it is O(1) only when you want to peek the first heap element without taking it out


  • 0

    @Ajeet_Singh
    I think update process for this problem if we use minheap should be O(n) since we first need to find it.


  • 0
    A

    Yes, got it. Thanks guys.


  • 0
    A

    @elmirap Got it, Thanks


  • 0

    @Ajeet_Singh welcome


  • 0
    J

    @elmirap Why not just use treemap?


  • 0

    @jeffery .Treemap has log(n) time complexity


  • 0
    J

    @elmirap Treeset is actually just a wrapper of Treemap (hashset is a wrapper of HashMap)
    public TreeSet() {
    this(new TreeMap<E,Object>());
    }


  • 0

    @jeffery I was thinking that you asked why didn't we use TreeMap instead of HashMap


Log in to reply
 

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