Last Updated: 26 Sep, 2021
Top K Stocks to Sell
Moderate
Asked in companies
It was a busy day at Ninja's Stock Exchange as stock prices fluctuated throughout the day. Trading isn't Ninja's cup of tea, so he appointed you to help him.
You are given 'Q' queries, each query of type-1 is an update query in which you are given ‘{Name, Price}’ denoting the name of the stock that needs to be updated with the given price, for every query of type-2 you need to find the maximum money that can be collected by selling the top 'K' stocks at that particular moment of time.
The closing price of a particular stock is equal to its last updated price. Find the total money that can be collected after selling at most ‘K’ stocks for every query of type-2.
Note :
Then given queries are in the form of a stream (they are sequential), so they should be processed in the given order. That is: you should not solve them offline by iterating through the back or by iterating in any other order.
For Example :
If N = 4 , K = 2 and Queries = { 1, “a,” 30 }, { 1, “b,” 20 } , { 1, “a,” 10 } , { 1, “c,” 100 } , { 2 }
There is a query of type-2 after processing four queries of type-1.
Then we can sell in the possible ways:
Sell “a” and “b” and collect 10 + 20 = 30.
Sell “b” and “c” and collect 20 + 100 = 120.
Sell “a” and “c” and collect 10 + 100 = 110.
Therefore we can collect a maximum of 120. Note that “a” is being sold at 10 and not 30 because the last updated price in the stream for “a” was 10.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains two integers ‘Q’ and ‘K’ denoting the number of queries and the maximum number of stocks that can be sold respectively.
The next Q lines each contain one integer "QT" denoting the query type, each query of type-1 is followed by a string ‘Name’ and an integer ‘Price’ denoting the stock name and its updated price
Output Format :
For each test case, print the maximum money that can be collected for each query of type-2 in separate lines.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 ≤ T ≤ 10
1 ≤ Q, K ≤ 100
1 ≤ Name.length ≤ 10, Name contains only lowercase English alphabets
1 ≤ Price ≤ 10^6
There is at least one query of type-2
Time limit: 1 sec
Approaches
As stated clearly in the question, the given input is a stream, so we cannot process the input backwards. In a real interview, there might be a follow-up question where the input is not a stream and we have to sell the stocks after all the stock update queries have been executed, this can simply be solved by using just one ordered map and iterating from back to the front of the stock update queries and for every stock, we have to only consider the price corresponding to the first occurrence from the end (in other words: the last updated price).
To solve this question when the input is in the form of the stream note that storing just the Price vs Name information is not enough, as in future if the price of any stock updates we will have to linearly search all the stocks to find the matching name.
Though this issue can be tackled by using an additional data structure to store Name vs Price information. For every query of type-1, check if the current stock Name already exists in the Name vs Stock data, if it exists then using the last updated price from the Name vs Price data delete the entry corresponding to it from Price vs Name data, also delete the entry corresponding to it from Name vs Price data. Finally, insert the current data stream information into both the data structures.
And for every query of type-2, return the sum of K biggest prices from the Price vs Name data.
The steps are as follows :
- Initialize a hash-map “name_price” to store Name vs Price data.
- Initialize a set of pairs “price_name” to store Price vs Name data. We are using a set and not a map because there can be multiple stocks with the same price, and the map won’t allow us to store that information. Also, we can’t use a data structure like multimap because we will need to directly delete a {key, value} pair, and directly doing this is much easier if we use a set of pairs.
- Process queries, for each query of type-1, check if the current stock’s Name is present in the map “name_price”. If it is present, then find the last price for it, and delete the entry { LastPrice, Name } from “price_name”. Now insert the Name and Price values for the current stream data into both the hash-map and the set of pairs.
- For each query of type-2, return the sum of K largest prices from the map “price_name”, and in case the size of “price_name” is less than K then return the sum of all the prices in the map.