Yahoo Interview Question
Software Development ManagersCountry: United States
Interview Type: Phone Interview
min heap would be a 5 element fixed storage
max heap would be ALL data seen so far as storage
Jason correct
what abt two variables that hold min value and index of min value and a 5 elements array for stocks.every time a stock update comes if it's greater than the min value then update the array..tell me whether it is gonna work?
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.
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;
}
1) man, I think min-heap is better for this problem.
- Jason November 22, 20132) 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.