CareerCup

1) man, I think min-heap is better for this problem.

2) maintaining these values in memory
a) using multiple machines, each handles requests of a period of times slots
or
b) Memory might be saved considering the fast that some stock value can be top 5 in a time range. Can anyone suggest a good data structure to handle this case.

class Stock {
  String ticker;
  double value;
}

double lowesetIndex = 0;
double lowestValue = 0;
int numStocks = 0;

Stock[] topStocks = new Stock[5];

HashMap<String, Integer> stocksMap = new HashMap<String, Integer>();

void updateStream(Stock newQuote) {
  if (numStocks < 5) {
    // Add it to current index and just return.
    topStocks[numStocks] = newQuote;
    stocksMap.put(newQuote.ticker, numStocks);
    
    if (newQuote.value < lowesetValue) {
      lowestValue = newQuote.value;
      lowestIndex = numStocks;
    }
    
    numStocks++;
      
    return;    
  }
  
  if (newQuote.value > lowestValue) {
    if (stocksMap.hasKey(newQuote.ticker)) {
      int index = stocksMap.get(newQuote.ticker);
      topStocks[index].value = newQuote.value;
    }
    else {
      topStocks[lowestIndex] = newQuote;
    }
    
    calculateLowest();
  }
}

void calculateLowest() {
  lowestIndex = 0;
  lowestValue = topStocks[0];
  for (int ii = 1; ii < topStocks.length; ii++) {
    if (topStocks[ii].value < lowesetValue) {
      lowestValue = topStocks[ii].value;
      lowestIndex = ii;
    }  
  }
}

(1)On most part, I agree with the originator, such as storing data in a maxheap, doing sift to update.
(2)But in terms of picking top 5, there might be a simpler way to do that, I guess.
(3)We could build the maxheap with just a plain array and maintain it by ourselves. Then the GUI needs to be updated only when the first 5 items of the array is changed.

Construct a min heap of 5 elements, so that will ensure we have minimum element as the root of the heap.Whenever a new ticker comes by, we will compare it with root if it greater then we do a MinHeapify step else ignore it.
O(k) -Build Min heap
O(log k)- Minheapify

k=5.

you should use min-heap to keep track of max k elements at given time.

We will need a min-heap and a HashMap.

1. Min-heap will contain top 5 stocks.
2. when new stock comes in,
- if it is greater than min-heap, then replace the top of min-heap by this stock and down-heapify (O(log 5))
- if it is less than the min-heap, then just update/insert the value of the stock in the HashMap (O(1)) (HashMap will contain all data : not present in min-heap + present in min-heap)
- if old value of stock is present on the min-heap and the new value is less than the top of min-heap, then construct a max-heap from HashMap and take the max element into the min heap (heap can be constructed in amortized O(n))

The min/max heap approach is good but , we can think it other simple way only. As this is the streaming and need to store only top 5 values at any given point of time, we can have a double array of 6 element which will store the values while read each stock data in a loop.
Time complexity should be O(nk) where K is limit, here 5.
C++ solution:

// Here size is streaming data size, limit is to be passed as 5
double* topFiveElement(double* Data, int size, int limit)
{
    double *ptr = new double[limit+1];
    for ( int index = 0; index <= limit; index++)
    {
        ptr[index] = 0.0;
    }
    
    // Read each value from stream
    for( int i =0 ; i < size; i++)
    {
        // store it into a predefined array in decending order. Iterate at max five times only
        ptr[limit] = Data[i];
        for( int j = limit; j > 0; j--)
        {
            // Swap values if right element is larger
            if( ptr[j] > ptr[j-1])
            {
                double tmp = ptr[j-1];
                ptr[j-1]   = ptr[j];
                ptr[j]     = tmp;
            }
            else{
                // if the above condition does not staisfy exit the loop
                break;
            }
        }
    }
    return ptr;
}