Bloomberg LP Interview Question
Financial Software DevelopersCountry: United States
Interview Type: In-Person
<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>
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)
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
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);
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?
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.
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);
}
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]);
}
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
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);}
}
}
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;
}
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;
}
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;
}
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}
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
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;
}
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]);
}
}
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;
}
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.
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.
- Anonymous October 21, 2011