Bloomberg LP Interview Question
Financial Software DevelopersCountry: United States
Interview Type: In-Person
Why should it be an increasing subsequence? In this sequence [1, 3, 2, 8 ] isn't it better to buy on the day when the price is 3 and sell when it's 8?
Buy Low, Sell High:
Basically, you want to buy a share if you have no shares and you know the next day the stock will trade higher, because you're at a local minimum. You want to sell a share if you have a share and you know the next day the stock will trade lower, because you're at a local maximum. Iterate through the array in O(N) time to figure out when you buy and sell. Don't buy stock on the last day for obvious reasons.
The more common variation of this problem is actually harder. Suppose you're only ever allowed to make one purchase. It would possibly be a short sighted strategy to buy at a local minimum, because you would be forgoing a future buying opportunity at an even lower price. But if you're allowed multiple buy/sell opportunities, this isn't an issue, because you can collect earning after every increase.
I suggested that but they said, that is a day by day decision procedure and not necessarily the optimal strategy. I guess that is correct; assume you have 3 5 10 you buy at 3 but should hold at 5 even though there is profit so you wait for 10. So I guess we need to look at all the steps ahead until we see a drop?
try put this on graph.at first day we need to by the stock.
If we find positive steep then price is increasing then hold.At negative slope sell.at minimum buy again.slope can be found by comparing two digits difference.
I think the condition that you can only hold maximum one share simplify the case a lot. If you can own more than one share, the case would seem complex.
This is correct, set a two-day frame. And use intent-sell, intent-buy marks. eg. 3 7 4 10 11 8 5 4 8
[3 ,7], buy at 3.
[7, 4], mark 4 as intent-sell
[4, 10], sell at 4, and mark it as intent-buy
[10,11] buy 10! and mark 11 as intent-sell
[11,8] sell at 11 and mark 8 as intent-buy
[8,5] cancel intent-buy at 8.
[5,4] do nothing
[4,8] buy at 4, sell at 8
def best_strategy(prices):
holding = False
result = []
for i in range(len(prices) - 1):
if not holding and prices[i+1] > prices[i]:
result.append(('buy', 'day %d' % i, prices[i]))
holding = True
elif holding and prices[i] > prices[i+1]:
result.append(('sell', 'day %d' % i, prices[i]))
holding = False
if holding:
i = len(prices) - 1
result.append(('sell', 'day %d' % i, prices[i]))
return result
Buy at local minima, sell at local maxima
1) Find the gradient of stock price with respect to days. ie, tomorrows stock price - todays stock price.
2) We buy or sell only when the gradient moves to either side of zero.
2.a) Buy stock on the day when tomorrows price - todays price moves from -ve value (or zero) to +ve value
2.b) Sell the stock on the day when tomorrows price - todays price moves from +ve value (or zero) to -ve value
O(n)
private static int findMaxProfit(int[] arr)
{
int min = arr[0];
int max = arr[0];
int maxProfit = max - min;
for(int i = 0; i < arr.length; i++)
{
if(arr[i] < min)
{
min = arr[i];
max = arr[i];
}
if(arr[i] > max)
{
max = arr[i];
}
if(maxProfit < max - min)
{
maxProfit = max - min;
}
}
return maxProfit;
}
int ComputeBest(int *p, size_t n)
{
int *B = new int[n + 1];
int *S = new int[n + 1];
memcpy(B, 0x00, sizeof(int) * (n + 1));
memcpy(S, 0x00, sizeof(int) * (n + 1));
for(size_t index = n - 1; index >= 0; ++index)
{
B[i] = max( B[i+1], -p[i] + S[i+1] );
S[i] = max( S[i+1], -p[i] + B[i+1] );
}
return B[0];
}
I don't understand this problem clearly. But I think it can be solved like this:
For price array A: [3 7 4 10 11 8 5 4 8]
We get the difference array B: [4 -3 6 1 -3 -3 -1 4]
So we just buy the share at the price of A[i] when B[i] > 0 and we have no share in hand!
We sell the share at the price A[j] when B[j] < 0 and we have one share in hand.
At last if we have a share in hand, just sell it.
So the result is like this:[buy sell buy hold sell hold hold buy sell]
#include<stdio.h>
int main()
{
int i,buy=-1,profit=0;
int array[]={3,7,4,10,11,8,5,4,8,6};
for(i=0;i<9;i++)
{
if(buy==-1 && (array[i+1]-array[i])>0 )
{buy=array[i];
profit-=buy;
printf("bought day %d ",i+1);
}
else
if(buy!=-1 && (array[i+1]-array[i])<0)
{
profit+=array[i];
buy=-1;
printf("sell stoch day %d",i+1);
}
}
}
The Algorithm is following
Let A[i=1 to N] is the daily stock price process and initally we don't own any stock.
start = 1;
while(start <= N)
find first element such that next element is bigger then that. set it buying price of stock.
find first element such that next element is lesser then it. set it selling price.
find profit and add it to sum and set new start to selling price element index + 1
For Example : Here in this case we will have {3,7}, {4,11},{4,8} are the buying selling tuples, and net profit is 4 + 7 + 4 = 15.
cleaned version of solution in C++
#include <iostream>
using namespace std;
void maxProfit(int prices[], int len) {
int at_hand = 0;
int profit = 0;
cout << len << endl;
for (int i=0; i <= len-1; i++) {
if (at_hand == 0 && prices[i] < prices[i+1]) {
at_hand = 1;
cout << "Buy on day " << i+1 << endl;
}
else {
if (at_hand != 0 && prices[i] > prices[i+1]) {
profit += prices[i] - prices[i+1];
cout << "Sell on day " << i+1 << endl;
at_hand = 0;
}
}
}
cout << "Net profit = " << profit << endl;
}
int main() {
int stock_prices[] = {5,4,7,4,3,6,8,4,3,6};
int len = sizeof(stock_prices)/sizeof(int);
maxProfit(stock_prices, len);
return 0;
}
The problem becomes as follows:
Find all pairs of form (A,B), where B>A, such that the sum of the differences in the numbers of every pair is maximum and no two pairs must contain the same element from the given array.
Optimal Substructure:
F(i) = max{
A[i]- A[j] + F(j-1) --> if A[i] > A[j]
OR F(j-1) --> otherwise
} where 0<=j<=i;
Base Case:
F(-1) = F(0) = 0;
/*
Given a share's prize on each day in an array. Find an algo that will give the maximum profit.
The share can be either bought or sold on a day. Not both.
*/
#include <iostream>
#include <stdio.h>
#include <Math.h>
using namespace std;
//Without Dynamic Programming
int F(int A[], int end)
{
// Base:
if( end==-1 || end==0 ) return 0;
int maxVal = 0;
for( int i=0; i<=end; ++i)
{
maxVal = max( maxVal,
(A[end]>A[i] ? (A[end] - A[i]) : 0) +
F(A, i-1));
}
return maxVal;
}
// With Dynamic Programming
int dpF(int A[], int end, int sol[])
{
if (sol[end]>-1) return sol[end];
int maxVal = 0;
for( int i=0; i<=end; ++i)
{
maxVal = max( maxVal,
( A[end]>A[i] ? (A[end] - A[i]) : 0 ) +
( (i>1) ? dpF(A, i-1, sol) : 0 ));
}
sol[end] = maxVal;
return maxVal;
}
int main()
{
int A[] = {3,10,4,6};
int lenA = sizeof(A)/sizeof(A[0]);
int sol[10]; // not more than 100 boards
// // and 10 painters
memset(sol, -1, sizeof(sol[0]) * 10);
//
cout<<F(A, lenA-1)<<endl;
cout<<dpF(A, lenA-1, sol)<<endl;
// system("PAUSE");
return 0;
}
If next day price > today's price and no stock in possession => buy
else if next day price < today's price and stock in possession => sell
Alternatively, it can solved by finding all disjoint longest increasing subarrays. This can be done in O(n). Buy on first element of subarray and sell on last element of subarray for each of these subarrays.
- Cerberuz March 11, 2013e.g. 2 1 3 6 8 2 4 1 9
Longest increasing disjoint subarrays are { 1, 3, 6, 8 }, { 2,4 }, { 1,9 }
Buy at 1 - sell at 8
Buy at 2 - sell at 4
Buy at 1 - sell at 9