## Bloomberg LP Interview Question for Financial Software Developers

• 0

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
6
of 6 vote

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

``````void maxProfit(int prices[], int len) {
int i;

for( i = 0; i < len-1; i++ ) {
if( buy == -1 && prices[i] < prices[i+1] ) {
printf( "Buy on day %d\n", i );
} else if( buy != -1 && prices[i] > prices[i+1] ) {
printf("Sell on day %d\n", i );
}
}

if( buy != -1 ) {
printf("Sell on day %d\n", i );
}

// profit = max profit acquired
}``````

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.

e.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

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

I meant buy when its 1 and sell on 8.

Comment hidden because of low score. Click to expand.
4
of 4 vote

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.

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

Read what I wrote again. You only sell when the next day is lower.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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
[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
[5,4] do nothing
[4,8] buy at 4, sell at 8

Comment hidden because of low score. Click to expand.
0

``````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``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int findMaxProfit(int[] arr)
{

int min = arr;
int max = arr;
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;
}

Comment hidden because of low score. Click to expand.
0

I think this finds the best day to buy and best day to sell. We need to find an answer like.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0

And we need to add some delete statements for B and S when we are done.

Also, reconstructing answer is fairly simple using this logic.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
int main()
{
int array[]={3,7,4,10,11,8,5,4,8,6};
for(i=0;i<9;i++)
{

printf("bought day %d ",i+1);
}
else
{
profit+=array[i];
printf("sell stoch day %d",i+1);
}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int maxprofit(int a[],int n)
{ int profit=0;
int min=a,max=a;
for(int i=0;i<n;i++)
{ if(a[i]<min) min=a[i];
if(a[i]>a[i+1])
{ profit+=a[i]-min; min=a[i+1];}
}
return profit;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is the flow i can think of -
if( arr[i] > arr[i-1] && arr[i+1<arr[i]
sell on i and compute the profit
if(arr[i] < arr[i+1]
if(arr[i] > arr[i-1] && arr[i+1>arr[i])
Do not do anything

sell on last day. and compute profit

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

int sol;	// not more than 100 boards
//					// and 10 painters
memset(sol, -1, sizeof(sol) * 10);
//
cout<<F(A, lenA-1)<<endl;
cout<<dpF(A, lenA-1, sol)<<endl;

// system("PAUSE");
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

Time Complexity: O(n^3) for Dynamic Programming solution

Comment hidden because of low score. Click to expand.
0

Consider the following case: 30, 1, 4, 3, 17, 16, 2, 7, 9, 8, 19 in which your solution gives 18 as maximum profit which is incorrect.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Time Complexity: O(n^3) for Dynamic Programming Solution

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Maximum Sum SubArray problem

Comment hidden because of low score. Click to expand.
0

Wrong. Its longest increasing sub sequence.

Comment hidden because of low score. Click to expand.
0

I think you are right.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.