Bloomberg LP Interview Question
Financial Software DevelopersYou 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.
What will you do if the stock prices are monotonically increasing? like 1, 2, 3, 4, 5, 6
Just to clarify, the monotonically increasing example was meant for the greedy solution and not the dynamic programming solution.
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() ??
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.
an coded answer with well explained algorithm. Please remove spaces.
tech-queries.blogspot. com/ 2010/ 07/ maximum-difference-in-array. html
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
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 ;-)
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
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]);
}
}
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;
}
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;
}
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:
- R.Kozikowski January 26, 2011x_{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) )