Bloomberg Senior Software Engineer Interview Question:
I got the job offer :) This is one of the coding question which I found a little bit challenging initially but solved it at the end.

Coding Question:
You have a stream of Stock ticker and stock volume coming in.
You need to design a function which returns the K most voluminous stocks
The function to return the most popular stock is used multiple times and needs to be very very efficient.

"""
Input Stream:
MSFT|400 IBM|1000 AAPL|500 AAPL|600 NFLX|1000 AMZN|700 GOGL|300

Result:
If there are two stock tickers with similar volume, you can return any of them in any order.

Return K = 4
AAPL|1100 NFLX|1000 IBM|1000 AMZN|700
OR
AAPL|1100 IBM|1000 NFLX|1000 AMZN|700

You can return it as a list of tuple:
[(APPL, 1100), (IBM,1000).... ]
AAPL, IBM
"""

Elimination this:
Storing in a dict and sorting the dict every time will make it very slow.

My solution was to use a combination of :

1. A dictionary to store {'StockTicker' :Node(volume, prev, next) }
2. A sroted doubly linked list. Every time I insert a volume for a stock ticker coming into the stream, I insert it at the right location using traversal either with next or prev pointers so that the LinkedList is always staying sorted.
   This will make all operations of O(N) - insertion and deletion.

A heap cannot be used because of this usecase:
AAPL|500 AAPL|600
You should have only stock ticker with its associated volume in the Datastructure.

class Node:
def init(self, val, ticker):
self.ticker = ticker
self.val = val
self.next = None
self.prev = None

class MostTradedStocks:
    def __init__(self):
        self.stock_volume = {}
        self.head = None
    
    def insert(self, curr, newVolToInsert):
		#need to implement this
      
        next_node = curr
        while curr and curr.val > newVolToInsert.val:
            next_node = curr #400
            curr = curr.next #None
     
        if curr == self.head:
            temp = self.head
            self.head = newVolToInsert
            newVolToInsert.next = temp
            temp.prev = newVolToInsert
        
        
        
    def execute_trade(self, ticker, volume):
        
        if ticker not in self.stock_volume:
            new_node = Node(volume, ticker)
            self.stock_volume[ticker] = new_node
      
        else:
            node = self.stock_volume[ticker]
            node.val += volume
                    
        if not self.head:
            head = self.stock_volume[ticker]
        
        else:
            curr = self.head
            self.insert(curr, self.stock_volume[ticker])
			curr = curr.next
            
        
    def get_top_k(self, k):
			curr = self.head
			res = []
			for i in range(k):
				res.append(curr.ticker, curr.val)