I had got this question in Cisco coding round. I would be grateful if anyone could provide an approach or even an hint. Problem statement is quite long ,please bear with me.
Mr McFly has gone k number of Days into the past. He knows the prices of stocks in the stock market and how much profit they are going to generate if invested. In order to generate profit on investing in a stock ,McFly has to wait for one day to generate the profit and subsequently invest in other stock. Also his broker only allows investing in 1 stock per day and holding period is 1 day per stock. To keep things simple, if Marty invests in a stock ,he won't be able to reinvest in that stock.
McFly has an array of price of n stocks ,where price[i] denotes the price of ith stock and an array of profit of size n where profit[i] denotes the profit generated after a day of investing in the ith stock. McFly has an initial funds f and he can use the profit from stocks to invest in other stocks.Help McFly in picking at most k stocks for k days so as to maximize his funds. Any stock can be picked at any time .
Given k days into the past,initial funds f,price array and profit array print the maximum funds at the end if at most k number of stocks are picked for investment intelligently.
Constraints: 1 <= k <= 10^5 0 <= f <= 10^7
If I understand the problem correctly then I think that this problem can be solved greedily. We can define $$$t[i] = profit[i] - price[i]$$$, naturally all the values with $$$t < 0$$$ are out. Then you do this operation at most $$$k$$$ times: out of all the stocks that you can buy, you should buy the one with highest $$$t$$$ let say $$$mx$$$ and then your fund increases by $$$mx$$$. This can be done by sorting the stocks according to their prices and then using a priority queue.
It may happen this fails somewhere, so it would be useful if you can provide a link where I can test this.
After selling the stock we are getting back original price of stock + profit. I don't have the link to the problem as it only available when the round was live.
Then I guess it is even simpler? You just buy whichever stock you can buy with your fund and which has mximum profit and then add the profit to the fund and then subsequently update your priority queue.
Yess.This should work.Thank you!!