Yahoo Interview Report
- 0of 0 votes
AnswersWe maintain stock prices of various companies. A stream of stock updates are coming in the form of ticker and value pair (example YHOO, 36.00). This value needs to be updated. We have a module of GUI that always displays top 5 stock prices at any given point of time. How would you maintain these values in memory?
- nosyDeveloper November 22, 2013 in United States
My solution was to maintain a max-heap and a map that maps ticker to the corresponding node in the heap. At every update, we look-up the node and update the value, but also note if it is an increase or decrease in value. If increase, we do a sift-up, if decrease, we do a sift-down on the heap for that node. For giving the top five values at any point of time, we don't want to disturb the order in the heap so we would copy the top five levels to a different memory and then perform 5 extract and heapifies on it.| Report Duplicate | Flag | PURGE
Yahoo Software Development Manager Data Structures - 1of 1 vote
AnswersThere is an array of characters, say A[ ] and there is another array of doubles of equal size say W[ ]. Need to design a method called randomChar( ) that will return a character, but the probability of returning a character at index i ie. A[i] will be W[i].
- nosyDeveloper November 22, 2013 in United States
eg. A = ['a', 'b', 'c']
W = [0.3, 0.5, 0.2]
Then randomChar() called around 100 times should return approx 30 times 'a', 50 times 'b' and 20 times 'c'.
My approach was calculating cumulative probability for the array, eg. W' = [0.3, 0.8, 1.0], then generating random number between 0 and 1 and finally looking up the cumulative array for the right range of the number using binary search. The main problem was the modifications to the normal binary search to check the correct range of generated random number.| Report Duplicate | Flag | PURGE
Yahoo Software Development Manager Algorithm