Bloomberg LP Interview Question Financial Software Developers
It will be a greedy algorithm to maximize profits.
Array A = {1, 4 , 5 ,2, 3}
for i = 1->4
{
if A[i+1]>=A[i]
Buy with all the money or hold
else
Sell All or Dont Buy(first trade)
}
Sell all on the 5th day
----
This will always maximize profit.
If in a week the stock goes 8-4-3-2-1 there is no way profit can be made.
And if its a 1-2-4-6-8 then you need to buy the first day and sell it the last day.
Naive solution is O(n^2)
With DP, we can achieve an O(N) solution.
The idea is to have a class like::
class DP1
{
int max_profit;
int min_val;
public DP1(int min_val,int max_profit)
{
this.max_profit = max_profit;
this.min_val = min_val;
}
public DP1()
{}
}
The min_val field contains the min value of the max-min=profit, for each DP(i).
The main idea is: when do we change the min_val for a particular DP(i) ?
We do that, when arr[i] - dp[i-1].min_val becomes less than 0.
Then, we set the profit to 0, and update dp[i].min_val=arr[i].
Heres, the code::
public class MaximumProfit
{
public static int maxProfit (int[] arr, int n)
{
DP1[] dp_arr = new DP1[n];
dp_arr[0] = new DP1(arr[0],0);
for(int i=1;i<n;i++)
{
dp_arr[i] = new DP1();
if(dp_arr[i-1].max_profit < (arr[i] - dp_arr[i-1].min_val))
{
dp_arr[i].min_val = dp_arr[i-1].min_val;
dp_arr[i].max_profit = arr[i] - dp_arr[i-1].min_val;
}
else
{
if(arr[i]- dp_arr[i-1].min_val < 0)
{
dp_arr[i].min_val=arr[i];
dp_arr[i].max_profit=0;
}
else
{
dp_arr[i].min_val = dp_arr[i-1].min_val;
dp_arr[i].max_profit = dp_arr[i-1].max_profit;
}
}
}
return dp_arr[n-1].max_profit;
}
public static void main(String[] s)
{
int[] arr = {1, 4 , 5 ,2, 3};
System.out.println(maxProfit(arr, arr.length));
}
}
Just a guess.
For this particular problem, for simplicity, the investment strategy is to buy shares with all of his money, or sell all of his shares to obtain profit, or do nothing.
Let M[i] is the maximal cash at hand at the end of one day (then no shares at hand), let S[i] the maximal shares at hand ( with some remainder cash R[i]). Then we have:
M[i] = max( M[i-1], R[i-1]+P[i]*S[i-1]), S[i] = max(S[i-1],M[i]/P[i]),P[i] is the price. M[6] is what we want.
Assume the man has 1 share at beginning, then use the above formulation, we can get maximal $7. Correct me.
Example\Algo:
-----------------
Key Sol: to get 1st min and last max | Profit=Max-Min
A#[01234]
A[14523]
Min=1
Max=5
Code:
----------
Private int BestProfit(Array A[] ,int N )
{
int Min=A[0];
int Max=A[1];
int MinCount=0;
int Profit=0;
for (i=2;i<N-1;i++)
{
If ( MIN > A[i] && MinCount=0)
{
MIN=A[i];
MINCount++;
}
Else If ( MAX < A[i] && i<=N)
{
MAX=A[i];
}
Profit=Max-min;
return Profit;
}
}
Remove condition : && MinCount=0
Add condition where Maxindex is stored in another variable
$1 -- 1st day
$5 -- 3rd day
$2 * 2.5 (shares) -- 4th day
$3 * 2.5 (shares) -- 5th day
Total 7.5 - 1 = 6.5 $ --> profit
in order to max profit, u must to buy at the lowest price and to sell at the highest price when the price is increasing. u should hold nothing when the price is decreasing.
for example, this data contains two price increasing period: 1,4,5 and 2,3
you only need to identify how many increasing period in the given data
day 1: $1
day 2: $4
day 3: $5
day 4: $2
day 5: $3
So, buy on the first day and sell on the third. 5 - 1 = 4 profit.
then buy on the fourth and sell on the fifth. 3 - 2 = 1 profit. giving us a total of $6 with $5 profit.
how to code it.....soon
int main()
{
int a[5] = {1, 4, 5, 2, 3};
int total = a[0];
bool buy_sell = false;
for(int i = 0;i<= sizeof(a)/sizeof(int)-1; i++)
{
if(a[i] < a[i+1] && buy_sell == false)
{
total = total - a[i];
buy_sell = true;
}
else if(a[i] > a[i+1] && buy_sell == true || i+1 == sizeof(a)/sizeof(int))
{
total = total + a[i];
buy_sell = false;
}
std::cout<<total<<" index "<<i<<std::endl;
}
std::cout<<"Final total:- "<<total<<" profit:- "<<total - a[0]<<std::endl;
return (EXIT_SUCCESS);
}
#include <iostream>
int main() {
int a[5] = {1, 4, 4, 2, 8};
int total = 100;
bool hasBought = false;
int remainder = 0;
int curNumOfShare = 0;
for(int i = 0;i<= sizeof(a)/sizeof(int)-1; i++){
if (a[i] < a[i+1] && !hasBought){
hasBought = true;
curNumOfShare = total / a[i];
remainder = total % a[i];
}
else if ( (i == sizeof(a)/sizeof(int)-1 || a[i] > a[i+1])
&& hasBought){
hasBought = false;
total = a[i] * curNumOfShare + remainder ;
}
}
std::cout<<"Final total: "<<total<<" profit: "<<total - 100<<std::endl;
return (0);
}
My bad:
A more robust version.
int main()
{
int a[5] = {9, 4, 5, 2, 3};
int total = 0;
int first_time_buy;
bool buy_sell = false;
bool buy_first_on_occasion = false;
for(int i = 0;i<= sizeof(a)/sizeof(int)-1; i++)
{
if(!buy_first_on_occasion && a[i] < a[i+1])
{
total = a[i];
first_time_buy = a[i];
std::cout<<"First time ";
buy_first_on_occasion = true;
}
if(a[i] < a[i+1] && !buy_sell && i+1 != sizeof(a)/sizeof(int))
{
total = total - a[i];
buy_sell = true;
std::cout<<"buy @index- "<<i<<" for $"<<a[i]<<" current balance $"<<total<<std::endl;
}
else if(a[i] > a[i+1] && buy_sell || i+1 == sizeof(a)/sizeof(int) && buy_sell)
{
total = total + a[i];
buy_sell = false;
std::cout<<"Sell @index- "<<i<<" for $"<<a[i]<<" current balance $"<<total<<" profit $"<<total - first_time_buy<<std::endl;
}
}
std::cout<<"Final balance:- $"<<total<<" profit:- $"<<total - first_time_buy<<std::endl;
return (EXIT_SUCCESS);
#include <iostream>
using namespace std;
int main() {
int a[] = { 1, 4, 5, 2, 3 };
int initialCash = 10;
int cash = initialCash;
int holdings = 0;
for (int i = 0; i < 5; i++) {
if (holdings == 0 && (a[i + 1] > a[i])) {
//it goes up, if possible buy stocks
holdings = cash / a[i];
cash = cash % a[i];
}
if (holdings > 0 && (a[i + 1] < a[i]) || i == 4) {//i=4 so we sell on the last day
//it will go down, sell the stocks
cash += holdings * a[i];
holdings = 0;
}
}
cout << (cash - initialCash);
}
1 #include<stdio.h>
2
3 int buynumber;
4 int remain = 1;
5
6 int price[ ] = {1,4,5,2,3};
7
8 int buy(int price, int* remain)
9 {
10 buynumber = *remain / price;
11 *remain -= buynumber * price;
12 }
13
14 int sell(int price, int* remain)
15 {
16 *remain += buynumber * price;
17 buynumber = 0;
18 }
19
20 main(){
21 int i = 1;
22 while(price[i]){
23 if(price[i-1] < price[i] && remain >= price[i-1])
24 buy(price[i-1], &remain);
25 else if(price[i-1] > price[i])
26 sell(price[i-1], &remain);
27 i++;
28 }
29 if(buynumber && price[i] == 0)
30 remain += buynumber * price[i-1];
31 printf("%d\n", remain);
32 }
What does multiple trading mean? Cannot buy more than one share a day? or cannot keep buying a stack of shares, sell them, buy again, sell again on the same day??
// Practice3.cpp : Defines the entry point for the console application.
//
#include <iostream>
using namespace std;
int price[] = {1, 4, 5, 2, 3};
int balanceAmount = 1;
int balanceShares = 0;
bool bBought = false;
void Sale(int iDay)
{
balanceAmount += (balanceShares * price[iDay]);
balanceShares = 0;
cout << "\n\nSale |" << balanceShares << "|" << balanceAmount << endl;
}
void Buy(int iDay)
{
balanceShares += (balanceAmount / price[iDay]);
balanceAmount -= (balanceShares * price[iDay]);
cout << "\n\nBuy |" << balanceShares << "|" << balanceAmount << endl ;
}
int _tmain(int argc, _TCHAR* argv[])
{
int TempDay = 0;
int NumOfDays = sizeof(price)/sizeof(int);
while(TempDay < NumOfDays)
{
if(bBought)
{
if(price[TempDay - 1] < price[TempDay] && price[TempDay] >= price[TempDay + 1])
{
Sale(TempDay);
bBought = false;
}
}
else
{
if(price[TempDay] < price[TempDay + 1])
{
Buy(TempDay);
bBought = true;
}
}
TempDay++;
}
cout <<balanceAmount;
return 0;
}
DP -- it's not just for porn stars.
- Anonymous March 02, 2010