Bloomberg LP Interview Question Financial Software Developers


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

- Anonymous on October 21, 2011 | Flag Reply
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 buy = 0;
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;
buy = i;
sell = j;
}
}
}
}
System.out.println("buy at "+price[buy]+" and sell at "+price[sell]);
System.out.println("complexity="+complexity);
}
}
</pre><pre title="CodeMonkey52018" input="yes">
</pre>

- melchior on October 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- melchior on October 21, 2011 | Flag
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)

- Anonymous on October 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- phantomlimb on October 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- nijju on October 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Neo on October 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- pppppppp on November 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

}

- sk on December 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on December 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Awesome code.

- yujiao on January 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I mean the one from nijju

- yujiao on January 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this? I have written in c#

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

- N.M on October 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int GetMaxProfit(int A[],int* buy,int*sell,int size)
{
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;
}
}
}

*buy=b;
*sell=s;

return MAX;
}

- Anonymous on October 21, 2011 | Flag Reply
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 whenBuy = 0;
    	int whenSell = 0;
    	int maxProfit = 0;
    	
    	int buyHour = 0;
    	if(extremes[1]<extremes[0]) {buyHour =1; }
    	
    	for(int bIterator = buyHour; bIterator <= currentExtreme; bIterator+=2)
    	{
    		for(int sellTime=bIterator+1; sellTime<=currentExtreme; sellTime+=2)
    		{
    			iterations++;
    			if(extremes[sellTime] - extremes[bIterator] > maxProfit)
    			{
    				whenBuy = extremes[bIterator];
    				whenSell = extremes[sellTime];
    				maxProfit = whenSell - whenBuy;
    			}
    		}
    	} 
    	
    	System.out.println("number of iterations = " + iterations);
    	System.out.println(whenBuy + "  " + whenSell + "   " + maxProfit);
    	
    }
}

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

- Adrian on October 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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("Buying Index-"+MinIndex);
System.out.println("Selling Index-"+MaxIndex);
System.out.println("Profit-"+Profit);}
else{
System.out.println("Buying Index-"+oldMinIndex);
System.out.println("Selling Index-"+oldMaxIndex);
System.out.println("Profit-"+oldProfit);}
}

}

- dhilip.gurusamy on October 22, 2011 | Flag
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;
    int buyT, sellT;
    if(*v_it_r > *v_it)
    {
        pnl = *v_it_r - *v_it;
        buyT = priceToTime[*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)
        {
            buyT = priceToTime[*v_it];
            sellT = priceToTime[*v_it_r];
        }
    }
    cout << "buy at: " << buyT << ", sell at: " << sellT << endl;
}

- kakawka on October 24, 2011 | Flag Reply
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;
}

- Jeff on October 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool CAlgo::GetBestBuySellPrice(int Array[], int iSize, int &Buy, int& Sell)
{
// buy low sell high
Buy = Array[0]; //select the first price as a buy price
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 PotentialBuy=0;
int PotentialSell=0;
for (int i =1; i < iSize; ++i)
{
//1. Is this a new Buy Price
if (Array[i] < Buy)
{
PotentialBuy = Buy;
PotentialSell = Sell;
Buy = Array[i];
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)
{
Buy = PotentialBuy;
Sell = PotentialSell;
}
else
{
Buy = Sell = 0;
return false;
}
return true;
}

- Andy on October 25, 2011 | Flag Reply
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}

- abh on October 28, 2011 | Flag Reply
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);
}

- Anonymous on October 29, 2011 | Flag Reply
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

- Pratik on November 15, 2011 | Flag Reply
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 buy_point = 0;
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;
			buy_point = 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("buy point is %d\n", buy_point);
	printf("sell point is %d\n", sell_point);
	
	return 0;

}

- Sean on February 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Luc on March 31, 2012 | Flag
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;
int buyPriceI = 0, sellPriceI = -1,tBuyPriceI= 0;
for ( int i=1; i<arr.length; i++){
if ( (arr[i]-currMin) > maxProfit ){
buyPriceI = tBuyPriceI;
sellPriceI = i;
maxProfit = arr[i] - currMin;
}
if ( arr[i] < currMin){
tBuyPriceI = i;
currMin = arr[i];
}
}
System.out.println(" max profit = "+maxProfit+" buy = "+arr[buyPriceI]+" "+arr[sellPriceI]);

}

}

- ovjforu on February 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is short selling allowed?

Then selling can be before buying.

- Leo on March 08, 2012 | Flag Reply
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;
	}

- Yiran Qin on March 12, 2012 | Flag Reply
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

- biswa.panda on April 24, 2012 | Flag Reply
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

- biswa.panda on April 24, 2012 | Flag Reply
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.

- xyz on May 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- xyz on May 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- xyz on May 22, 2012 | Flag


Add a Comment
Name:

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

Books

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

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More