## 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.
3
of 7 vote

``````Declare MinSoFar = arr[0], MaxProfit = 0, newProfit = 0;
for (int i=1; i< arr.length;i++)
{
if(arr[i]<MinSofar)
MinSoFar = arr[i];
else
{
newProfit = arr[i]-MinSoFar;
if (newProfit>MaxProfit)
MaxProfit = newProfit;
}
}
return(MaxProfit);``````

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

<pre lang="" line="1" title="CodeMonkey52018" class="run-this">package com.bloomberg;

/**
* Created by IntelliJ IDEA.
* User: andrey
* Date: 10/20/11
* Time: 9:14 PM
*/
class Profit {

public static void main(String[] args) {
process();
}

public static void process() {

int[] price = {-2, -4, 30, -50, 90, -60, 100, 120};

int sell = 0;
int profit = 0;
int complexity = 0;

for (int i=0; i<price.length; i++) {
for (int j=i; j<price.length; j++) {
complexity ++;
// sell is more than buy
if (price[j] > price[i]) {
int delta = price[j] - price[i];
if (delta > profit) {
profit = delta;
sell = j;
}
}
}
}
System.out.println("complexity="+complexity);
}
}
</pre><pre title="CodeMonkey52018" input="yes">
</pre>

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

Output:
buy at -60 and sell at 120
complexity=36

So, I was wondering if the complexity can be decreased... Any ideas? Working on mine.

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

I will put a code later but algorithm is like follows:

1) Find the max value in the array.
2) Find the value before the max value such that (max - value) is maximised.

Complexity O(n)

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

Your algorithm doesn't solve this case:

90 100 10 80

max is 100, but best buying price is 10 and best selling price 80

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

good,

A- given array
take 2 variable S and p// s- smallest ,p-max profit;
s=A[0];p=0;
for(i=1;i<n;i++)
{
if(s<A[i])
{ if(p<(A[i]-s) )
p=A[i]-s;
}// end of outer if
else s=A[i];
}// end of for
printf("max_profit = %d\n",p);

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

This works in O(n), in a single pass. Why so many users have presented O(n^2) solutions after this? Isn't this the simplest solution?

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

yes, this is an awesome code...the brute force approach is o(n2). So pple might not have optimized it to o(n) after this.

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

Yes. In general this can be acheived at O(n) time. Here is my c# version

``````internal void BestBuySellingTime()
{
int[] a = { -2,    4,     30,  140,   -50,     90,    -60,    100,   120 };
//          9AM 10AM      11AM  11:30       12PM    12:30  1 PM    2PM     3PM     4 PM

// Get the max.. profit
// best buying price = -60
// best selling price = 120

int min = a[0];
int maxProfit = 0;

for (int i = 1; i < a.Length; i++)
{
if (a[i] < min)
{
min = a[i];
}
else
{
if (a[i] - min > maxProfit)
{
maxProfit = a[i] - min;
}

}
}
Console.WriteLine("Max Profit " + maxProfit);``````

}

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

check [-3, 100, -5, 4] You are buying at minimum buying price not for max profit.

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

Awesome code.

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

I mean the one from nijju

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

void findBestPrices(int[] prices)
{
int min = 0;
int max = 0;
if(prices.Length==0||prices.Length==1)
{
Console.WriteLine("Array Size is less than or equal to 1");
}
else
{
for(int i=1;i<prices.Length;i++)
{
if (prices[i] < prices[min] && (i != prices.Length - 1)
{
min = i;
max = i;
}
else if(prices[i] > prices[max])
{
max = i;
}
}
}
Console.WriteLine("\nLowest Price " + prices[min] +" Highest Price " + prices[max]);
}

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

{
int MAX=0;
int X=0;
int b,s;

if(size>1)
{
MAX=A[1]-A[0];
}

for(int i=0;i<size;i++)
{
for(int j=i;j<size;j++)
{
X=A[j]-A[i];
if(X>MAX)
{
s=j;
b=i;
MAX=X;
}
}
}

*sell=s;

return MAX;
}

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

Yes, it can be improved, at least by a factor of 4.
First, create a table of "extremes", i.e. the min/max values.
This way the table {1,3,5,4,2,-1,3,5,7,6,3} becomes {1, 5, -1, 7, 3}
now, in the new table you will want to buy at price 1, -1 or 3 (need to decide later) and sell at price 5 or 7.
So both iterators will advance 2 positions at a time (hence the improvement 4 times).

Here is the code:

``````class Profit {

public static void main(String[] args) {
processSmarter();
}

public static void processSmarter()
{
int iterations = 0;
int[] price = {-2, -4, 30, -50, 90, -60, 100, 120};

int[] extremes = new int[price.length];

extremes[0] = price[0];
extremes[1] = price[1];
int currentExtreme = 1;
boolean goingUp = price[1]>price[0];

for(int i = 2; i<price.length; i++)
{
iterations++;

if(goingUp && price[i] > extremes[currentExtreme] ||
!goingUp && price[i] < extremes[currentExtreme] )
{
extremes[currentExtreme] = price[i];
}

if(goingUp && price[i] < extremes[currentExtreme] ||
!goingUp && price[i] > extremes[currentExtreme]	)
{
goingUp = !goingUp;
currentExtreme++;
extremes[currentExtreme] = price[i];
}
}

int whenSell = 0;
int maxProfit = 0;

for(int bIterator = buyHour; bIterator <= currentExtreme; bIterator+=2)
{
for(int sellTime=bIterator+1; sellTime<=currentExtreme; sellTime+=2)
{
iterations++;
if(extremes[sellTime] - extremes[bIterator] > maxProfit)
{
whenSell = extremes[sellTime];
}
}
}

System.out.println("number of iterations = " + iterations);
System.out.println(whenBuy + "  " + whenSell + "   " + maxProfit);

}
}``````

and the output is:
number of iterations = 12
-60 120 180

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

public void getMaxProfit(int a[]) {
int oldMinIndex =0,oldMaxIndex =0,oldProfit=-1000;
int MinIndex=0,MaxIndex=1,Profit=-1000;
while(MaxIndex<a.length) {
if(a[MinIndex]<a[MaxIndex]){
Profit=a[MaxIndex]-a[MinIndex];
if(Profit>oldProfit) {
oldProfit=Profit;
oldMinIndex=MinIndex;
oldMaxIndex=MaxIndex;
}
}else{
MinIndex=MaxIndex;
}
MaxIndex+=1;
}
if(Profit>oldProfit){
System.out.println("Selling Index-"+MaxIndex);
System.out.println("Profit-"+Profit);}
else{
System.out.println("Selling Index-"+oldMaxIndex);
System.out.println("Profit-"+oldProfit);}
}

}

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

complexity O(n)

``````#include <ext/hash_map>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace __gnu_cxx;
using namespace std;

int main()
{
int arr[] = {1, 5, 9, 8, 7, 6};
int min = arr[0], max = min;

// Dump input
copy(arr, arr + sizeof(arr)/sizeof(int), ostream_iterator<int>(cout, ","));
cout << endl;

// Find max and min (for hash effectiveness, all keys should be positive)
for(int i; i < sizeof(arr)/sizeof(int); ++i)
{
if(min > arr[i]) min = arr[i];
if(max < arr[i]) max = arr[i];
}

// Shift keys towards zero using found minimum
for(int i; i < sizeof(arr)/sizeof(int); ++i)
arr[i] -= min;

// Create hash map of (max - min) buckets for price->time mapping and insert the input data
max -= min;
hash_map<int, int> priceToTime(max);
for(int i; i < sizeof(arr)/sizeof(int); ++i)
{
if(priceToTime.find( arr[i] ) == priceToTime.end())
priceToTime[ arr[i] ] = i;
}

// Hash map is now sorted by key, stock price
// Create sorted vector using prices (Linux hash_map doesn't support reverse_iterator for some reason)
hash_map<int, int>::iterator it = priceToTime.begin();
vector<int> prices;
while(it != priceToTime.end())
{
prices.push_back(it->first);
++it;
}

// Search for max PNL
vector<int>::iterator v_it = prices.begin();
vector<int>::reverse_iterator v_it_r = prices.rbegin();
while(priceToTime[*v_it] > priceToTime[*v_it_r])
{
++v_it_r;
}
int pnl;
if(*v_it_r > *v_it)
{
pnl = *v_it_r - *v_it;
sellT = priceToTime[*v_it_r];
}
else
{
cout << "apocalypse: the optimum cannot be found" << endl;
return 1;
}
v_it_r = prices.rbegin();
while(priceToTime[*v_it] > priceToTime[*v_it_r])
{
++v_it;
}
if(*v_it_r > *v_it)
{
if(*v_it_r - *v_it > pnl)
{
sellT = priceToTime[*v_it_r];
}
}
cout << "buy at: " << buyT << ", sell at: " << sellT << endl;
}``````

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

O(n) complexity

int main() {
int A[] = {-2, -4, 30, -50, 90, -60, 100, 120};
const int idx = sizeof(A) / sizeof(int);
int min[2] = {}; // use 2 more extra space
int max[2] = {}; // use 2 more extra space
int count = 0;

min[count] = A[0]; // init value

for(int i = 0; i < idx; i++) { // O(n)
if(min[count] > A[i] && max[count] == 0) {
min[count] = A[i];
continue;
} else if(min[count] > A[i] && max[count] != 0) {
if(count == 1) { // 2 buffer are full, eliminate the small 1.
int tmp1 = max[count - 1] - min[count - 1];
int tmp2 = max[count] - min[count];
if(tmp1 < tmp2) {
min[count - 1] = min[count];
max[count - 1] = max[count];
}
min[count] = A[i];
max[count] = 0;
} else
min[++count] = A[i];
continue;
}

if(min[count] < A[i] && max[count] < A[i]) {
max[count] = A[i];
}
}

int tmp1 = max[0] - min[0];
int tmp2 = max[1] - min[1];
if(tmp1 >= tmp2) // compare
printf("min = %d\nmax = %d\n", min[0], max[0]);
else
printf("min = %d\nmax = %d\n", min[1], max[1]);

system("PAUSE");
return 0;
}

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

{
Sell = 0;
//if Next Price greater than last buy price and greater last sell then new sell price
//If the next price is less than Last buy price then new buy price for each new
//Buy price then zero out sell price.
//Its best to save last buy and Less Price before searching for new buy and sell price
int PotentialSell=0;
for (int i =1; i < iSize; ++i)
{
//1. Is this a new Buy Price
{
PotentialSell = Sell;
Sell = 0;
}
else
if (Array[i] > Buy && Array[i] > Sell)
{
Sell = Array[i];
}
}

//do we have a valid buy sell position
if (Sell != 0 && Buy != 0)
{
return true;
}
else //if no then use previous buy sell position
if (PotentialBuy != 0 && PotentialSell != 0)
{
Sell = PotentialSell;
}
else
{
return false;
}
return true;
}

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

One of the solutions could be (except with duplicate values):
(1) Find Max (lets say index of max is 'x' in array), let it be max1
(2) Find Min in array starting from 0 to x; let it be min1
(3) Find Min (lets say index of min is 'y' in array) of the array, let it be min2
(4) Find Max in array starting from y to end; let it be max2

(5) Answer would be greatest of (max(i) - min(i)), where i is {1,2}

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

#include<stdio.h>
main()
{
int A[8]={120,100,-60,90,4,-2,-50,30};
int s,p,i;
s=A[0]; p=A[0];
for (i=1;i<8;i++)
{
if(s>A[i])
s=A[i];
if (p<A[i])
p=A[i];
}
printf("max=%d\n",p);
printf("min=%d\n",s);
printf("max_profit=%d\n",p-s);
}

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

This smells like a dynamic programming problem.
Let's define a function minBuy(i) as the min cost of buying shares from day 1 to day i.
Create an array representing this function. This can be done in O(n) time.
Let's define maxProfit(i) as the maximum profit that can be earned from day 1 to day i.
maxProfit(i) = maximum { price(i) - minBuy(i-1) ; maxProfit(i-1)}
maxProfit(1) = 0
Find maxProfit(n) using dynamic programming.
This is an O(n) algo

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

Solved in O(n)

``````#include "stdio.h"
#include "stdlib.h"
#include "math.h"

#define sizeofarray(arr) (sizeof(arr)/sizeof(int))

static int max_profit = -256;
static int sell_point = 0;

int find_max(int arr[], int start, int end)
{
int max = arr[start];
int index = start;
for(int i=(start+1); i<=end; i++)
{
if(max<arr[i])
{
max = arr[i];
index = i;
}
}

return index;
}

int find_min(int arr[], int start, int end)
{
int min = arr[start];
int index = start;
for(int i = start+1; i<=end; i++)
{
if(min>=arr[i])
{
min = arr[i];
index = i;
}
}

return index;
}

void find_max_profit(int arr[], int len)
{
int start = 0;
int end = len-1;
int max_ind,max;
int min_ind,min;

while(start<len-1)
{
max_ind = find_max(arr,start,end);
max = arr[max_ind];
min_ind = find_min(arr,start,max_ind);
min = arr[min_ind];

if(max-min>max_profit)
{
max_profit = max-min;
sell_point = max;
}

start = max_ind+1;
}

}

int main()
{
int arr[] = {-2,4,30,140,-50,90,-60,100,120,30,50};
int len = sizeofarray(arr);
find_max_profit(arr,len);

printf("Max profit is %d\n", max_profit);
printf("sell point is %d\n", sell_point);

return 0;``````

}

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

Nice code! Very easy to understand.
But it has a worst case complexity of O(n^2). Think about array when the stock price is decreasing continuously.
CLRS has solution in O(n*logn) page 68

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

O(N) time complexity....Here is my solution in Java..

import java.util.Scanner;

public class MaximumProfit {

/**
* @param args
*/
public static void main(String[] args) {

Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
int arr[] = new int[N];
for ( int i=0; i< N; i++){
arr[i] = scan.nextInt();
}
int currMin = arr[0];
int maxProfit = 0;
for ( int i=1; i<arr.length; i++){
if ( (arr[i]-currMin) > maxProfit ){
sellPriceI = i;
maxProfit = arr[i] - currMin;
}
if ( arr[i] < currMin){
currMin = arr[i];
}
}

}

}

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

Is short selling allowed?

Then selling can be before buying.

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

Here is my solution in java using a potential best buying price as ps, which is potential smallest number and potential profit as pp

``````static int findMaxProfit(int A[], int N){
int p = 0;
int pp = 0;
int s = A[0];
int ps = A[0];
for(int i = 1; i < N; i++){
pp = A[i] - ps;
if(pp > p){
s = ps;
p = pp;
}
if(A[i] > s && p < A[i] - s){
p = A[i] - s;
}
else if( A[i] < s ){
ps = A[i];
}
}
return p;
}``````

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

appropiate answer is to use modified minmax algorithm - where u keep index of the min/max aong with the value... complexity O ~ 3n/2+1

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

appropiate answer is to use modified minmax algorithm - where u keep index of the min/max along with the value... complexity O ~ 3n/2+1

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

Do we know the prices in advance? Is shorting allowed? If yes, it is as simple finding out min and max. If not, then it gets more complex and the max profit may be not same as difference between min and max.

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

If the prices are known in advance and shorting is allowed, the total profit will be the path traversed... short if it goes down next and long if it is going to go up next.

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

If the prices are known in advance and shorting is allowed, the total profit will be the path traversed... short if it goes down next and long if it is going to go up next.

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

This is pre-version of max subarray problem. First get input for max subarray problem by creating an array such that A[i]=A[i]=A[i-1].
From this array find the max subarray. Using start and end indices of this maxsubarray we get the answer. Refer CLRS for details.

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.