Bloomberg LP Interview Question for Financial Software Developers






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

It's common dynamic programming problem. It can be solved in O(n) time and O(1) memory. Let's call the cost on i-th day as c_i. You have the best solution from the previous day assuming that You have a stock (let's call it x_i) and You sold the stock (y_i). Then you have to actualize the solution:
x_{i+1} = max ( x_{i} (hold), y_{i} - c_{i} (buy));
y_{i+1} = max ( y_{i} (do nothing, I am not sure if You are allowed to do that based on problem description), x_{i} + c{i} (sell) )

- R.Kozikowski January 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You make it too complicated.

if tomorrow stock is increasing, spend all your money buy it and sell tomorrow;

if tomorrow stock is decreasing, hold your money in pocket.

- Zhen January 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What will you do if the stock prices are monotonically increasing? like 1, 2, 3, 4, 5, 6

- Anonymous January 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just to clarify, the monotonically increasing example was meant for the greedy solution and not the dynamic programming solution.

- Anonymous January 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the dynamic programming solution makes more sense to me..

- rad# January 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just want to add if 'short sell' is allowed, this is the algorithm:

1) if next day is higher, buy today, sell next day
2) if next day is lower, short sell today, buy back next day
3) if next day is same, hold
4) A day can have both buy and sell

- Steve March 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about Sort the stock prices:
So we will have something like:[1,2,3,7,8,10,11].

Buy() at the lowest, hold until you reach the last entry and then sell() ??

- Anonymous January 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

no
remember if i is the day you buy & j is the day u sell. then i<j.

so if stock prizes are
Day 1, 2, 3, 4
$ 11, 2, 1, 10

then for best profits i needs to be 3 & j needs to be 4 but you implementation after sorting will give result as i = 3 and j = 1

- mike January 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

greedy algo

buy @local low
sell@local high

your return in this case is 8/1*11/3

- zz January 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

does sell include "shorting" option?

- Anonymous January 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

its looks like a maximum subarray problem.
First calculate a differences from 2 subsequent days & store it in array.
Like for array above 2 , 1, 7 , 8, 5, 3, 11, 10 will become
2, -1 (2-1), 6 (7-1 & so on), 1, -3, 8, 10.

Then problem reduces to find maximum subarray which can be done easily using divide & conquer mechanism.

- mike January 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if next day's stock price is decreasing: sell all holdings and short it.
if next day's stock price is increasing: cover any shorts and buy all in.

- GekkoGordan January 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

an coded answer with well explained algorithm. Please remove spaces.
tech-queries.blogspot. com/ 2010/ 07/ maximum-difference-in-array. html

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

find three indexes for solving this

repeat until the list is full

1st index Find the lowest value from lowest index till the length of array

if there is a lowest value in the list

Begin

2 1 7 8 5 3 11 10

i.e 1

2nd index From that index to length find the next lowest.

i.e till 3

1 7 8 5 3

3rd index Get the maximum from this span

i.e 8

BUY at 1st index HOLD till 2nd index and SELL at 3rd index

Lowest = 3rd index
End

ELSE

Begin
get the maximum from the list
3 11 10
i.e 11
BUY at lowest and SELL at maximum
End

- Anonymous February 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

You guys are making this way too complicated. It's not a dynamic programming problem!
Assuming no shorting allowed, depending on your position today (long or flat) and knowing the price change tomorrow you either buy/hold/sell. That's all.
Disclosure : the guy asking this question sits at Bloomberg within a hearing distance ;-)

- bloombergoid September 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think you could assume that you know the entire sequence. Just scan through the sequence, keeping track of the lowest value and highest profit.

From the maximum profit, you could get the value at which you should buy and at which you should sell. Hold in between.

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

public class StockPrice {

	private char[] operation;

	public void maximizeProfit(int[] stockPrices) {
		int buyIndex = 0;
		int sellIndex = 1;
		int candidateProfit = -stockPrices[0];
		operation = new char[stockPrices.length];
		operation[buyIndex] = 'B';
		int i = 1;
		while (i < stockPrices.length) {
			if (stockPrices[i] < stockPrices[buyIndex]) {
					operation[buyIndex] = 'H';
					buyIndex = i;
					candidateProfit = -stockPrices[i];
					operation[buyIndex] = 'B';
			} else if ((stockPrices[i] - stockPrices[buyIndex]) > candidateProfit) {
				if (sellIndex == buyIndex) {
					operation[buyIndex] = 'B';
				} else {
					operation[sellIndex] = 'H';
				}
				sellIndex = i;
				candidateProfit = stockPrices[i] - stockPrices[buyIndex];
				operation[sellIndex] = 'S';
			} else {
				operation[i] = 'H';
			}
			i++;
		}
		if (candidateProfit <= 0 || buyIndex >= sellIndex) {
			System.out.println("No Profit scenario ");
		} else {
			System.out.println("Buy Index = " + buyIndex + "  Buy price = "
					+ stockPrices[buyIndex]);
			System.out.println("Sell Index = " + sellIndex + "  Sell price = "
					+ stockPrices[sellIndex]);
			System.out.println("Profit = " + candidateProfit);
			for(int j=0; j<stockPrices.length; j++){
				System.out.print(operation[j] + " -> ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		StockPrice stockPrice = new StockPrice();
		int[] stockPrices = { 2, 1, 7, 8, 5, 3, 11, 10 };
		stockPrice.maximizeProfit(stockPrices);
		int[] stockPrices_2 = { 1, 2, -3, 4, 5, 6, 10 };
		stockPrice.maximizeProfit(stockPrices_2);
		int[] stockPrices_3 = { -1, -2, -3, -4, -5, -6};
		stockPrice.maximizeProfit(stockPrices_3);
		int[] stockPrices_4 = { -1, -2, -3, -5, -6};
		stockPrice.maximizeProfit(stockPrices_4);
	}
}

Output
---------
Buy Index = 1 Buy price = 1
Sell Index = 6 Sell price = 11
Profit = 10
H -> B -> H -> H -> H -> H -> S -> H ->
Buy Index = 2 Buy price = -3
Sell Index = 6 Sell price = 10
Profit = 13
H -> H -> B -> H -> H -> H -> S ->
No Profit scenario
No Profit scenario

- Anonymous January 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the problem is incorrectly stated. given a series of stock prices at an increasing time period find out the maximum profit. i.e. decide whether you will hold /buy/sell at specified time periods.
with this solution for
2,1,3,5,8,7,4,2,5 will be
10 ... buy at (1) and then sell at (8) ..and again buy at (2) and sell at (5).. its a simple DP problem... here is my solution..



import java.util.Scanner;


public class MaximumDPProfit {

/**
* @param args
*/
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
int stockPrices[] = new int[N];
for ( int i=0; i<N;i++){
stockPrices[i] = scan.nextInt();
}
int maxProfit[] = new int[N];
for ( int i = N-2; i >=0 ;i--){
for ( int j= i+1; j <N;j++){
if ( stockPrices[j] > stockPrices[i]){
if ( j+1 < N){
if ( (maxProfit[i]) < (maxProfit[j+1] + stockPrices[j] - stockPrices[i] )){
maxProfit[i] = maxProfit[j+1] + stockPrices[j] - stockPrices[i] ;
}
}else{
if ( maxProfit[i] < (stockPrices[j] - stockPrices[i])){
maxProfit[i] = stockPrices[j] - stockPrices[i];
}
}
}else{
if ( maxProfit[i] < maxProfit[j]){
maxProfit[i] = maxProfit[j];
}
}
}
}
System.out.println("maximum profit : "+maxProfit[0]);
}

}

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

Am I allowed to reinvest the profit to buy stock?

- Zhengyang.Feng2011 March 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the total profit is the distance traveled ignoring the direction.

- xyz May 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java
private int buyingPrice = 0;
private int sellingPrice = 0;
private int profit = 0;

public void profitMaxmizer()
{
ArrayList<Integer> p = new ArrayList<Integer>()
{
/**
*
*/
private static final long serialVersionUID = 1L;

{
add(0, 15);
add(1, 14);
add(2, 13);
add(3, 1);
add(4, 11);
add(5, 10);
add(6, 16);
add(7, 1);
add(8, 10);
add(9, 10);
}

};

int sellIndex = 0;
int buyIndex = 0;
boolean bought = false;

for(int i=1; i<p.size(); i++)
{
System.out.print("\nProfit made over a week is: " + this.profit);
if(p.get(i) > p.get(sellIndex))
{
if(!bought)
{
bought = buyIt(p,buyIndex);
}

sellIndex = i;

}
else
{
if(bought)
{
bought = sellIt(p,sellIndex);
}
buyIndex = i;
sellIndex = i;
}


}

if(bought)
{
bought = sellIt(p,sellIndex);
}

System.out.print("Profit made over a week is: " + this.profit);
}


public boolean buyIt(ArrayList<Integer> p , int i)
{
this.buyingPrice = p.get(i);
return true;
}

public boolean sellIt(ArrayList<Integer> p , int i)
{
this.sellingPrice = p.get(i);
profit = profit + (this.sellingPrice - this.buyingPrice);
return false;
}

- Anonymous March 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java solution (with whitespaces) :P:

private int buyingPrice = 0;
    private int sellingPrice = 0;
    private int profit = 0;
    
    @Test
    public void profitMaximizer()
    {
        ArrayList<Integer> p = new ArrayList<Integer>()
        {
            /**
             * 
             */
            private static final long serialVersionUID = 1L;

            {
                add(0, 15);
                add(1, 14);
                add(2, 13);
                add(3, 1);
                add(4, 11);
                add(5, 10);
                add(6, 16);
                add(7, 1);
                add(8, 10);
                add(9, 10);
            }
            
        };
        
        int sellIndex = 0;
        int buyIndex = 0;
        boolean bought = false;
        
        for(int i=1; i<p.size(); i++)
        {
            System.out.print("\nProfit made over a week is: " + this.profit);
            if(p.get(i) > p.get(sellIndex))
            {
                if(!bought)
                {
                    bought =  buyIt(p,buyIndex);
                }
                
                sellIndex = i;
                
            }
            else
            {
                if(bought)
                {
                    bought = sellIt(p,sellIndex);  
                }
                buyIndex = i;
                sellIndex = i;
            }
            
            
        }
        
        if(bought)
        {
            bought = sellIt(p,sellIndex);  
        }
        
        System.out.print("Profit made over a week is: " + this.profit);
    }
    

    public boolean buyIt(ArrayList<Integer> p , int i)
    {
        this.buyingPrice = p.get(i);
        return true;
    }
    
    public boolean sellIt(ArrayList<Integer> p , int i)
    {
        this.sellingPrice = p.get(i);
        profit = profit + (this.sellingPrice - this.buyingPrice);
        return false;
    }

- Anonymous March 06, 2014 | Flag Reply


Add a Comment
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.

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