Bloomberg LP Interview Question
Financial Application EngineersCountry: United States
Interview Type: In-Person
-1 for just pasting code and forcing others to read to see if has bugs
(that is, using questions posted selfishly)
int FindMaxProfit(std::vector<int> prices)
{
if(prices.size()<2) return 0;
/* Find minimum and maximum values in given list */
int min = prices.front(), max = prices.front(), minIndx = -1, maxIndx = -1;
for(int i=0; i<prices.size(); i++)
{
if(prices[i]<=min)
{
min = prices[i];
minIndx = i;
}
if(prices[i]>=max)
{
max = prices[i];
maxIndx = i;
}
}
/* If the minimum is on left side of the maximum value, maxProfit = max - min */
if(minIndx<maxIndx)
return max-min;
else
{
/* Otherwise divid the list into two lists, begin to max and max+1 to end, and repeat this function on both. Max of both is the answer*/
std::vector<int> leftVector, rightVector;
leftVector.assign(prices.begin(), prices.begin()+maxIndx+1);
rightVector.assign(prices.begin()+maxIndx+1, prices.end());
int leftHalfMaxProfit = FindMaxProfit(leftVector);
int rightHalfMaxProfit = FindMaxProfit(rightVector);
return (leftHalfMaxProfit>rightHalfMaxProfit ? leftHalfMaxProfit : rightHalfMaxProfit);
}
};
I would imagine we code it like how a human would find the answer if given a "chart" of a stock price.
I would think selling at any point in time t=T would be maximixed if we had bought the stock at the minimum price seen before that point.
So as you go along left to right in the array, keep track of the minimum stock price seen so far, and check what profit we would have gotten selling at the current time t (current element in array). And keep track of the maximum such profit seen so far.
pseudocode:
min_seen = A[0] //minimum seen in all previous time steps before
max_profit= 0
for time t = 1 to n-1; // 0 indexed arrray, need only start at 1 if exists
{
if ( A[t] - min > max_profit ) // if selling now gives greater profit
max_profit = A[t] - min;
if( A[t] < min ) // if current stock price is below min. seen before now
min = A[t]
}
Why not also include selling short at the peaks? If I buy 1 at 5, sell 2 at 9 and buy 1 at 2 I make even more.
Just saw the limit on buying and selling once. But still. You can make more money if you sell first at 9 and then buy back at 1.
Both answers calculate the "profit" as "selling_price - buying_price", which is missing a very important point, which the interviewer intended to ask probably
Say for example you had two cases:
case 1: you buy the stock at $1000/share and sell at $1500/share. You have just made $500/share in profit
case 2: you buy the stock at $100/share and sell at $200/share. You have just made $100/share in profit.
Which case is "more profitable" as the original question asks? The solutions provided will pick case 1 when in case the answer is case 2.
The profits should be "normalized" by dividing the difference between selling and buying prices with the buying price.
So profit = (selling_price - buying_price) / buying_price
Also, the question is not clear in whether selling short is allowed or not. If it is, then the problem becomes trivially simple as finding the min and max in an array of numbers
#include <iostream>
#include <limits>
using namespace std;
int main() {
const unsigned int MAX_VALUES = 8;
int data[MAX_VALUES] = {5,9,6,2,4,8,3,1};
int maxProfit = std::numeric_limits<int>::min(); //Negative Infinite!
for (int buy = 0 ; buy < MAX_VALUES ; buy++) {
for (int sell = buy ; sell < MAX_VALUES ; sell++) {
if (data[sell] - data[buy] > maxProfit)
maxProfit = data[sell] - data[buy];
}
}
cout << "Most is :" << maxProfit << endl;
cin >> maxProfit;
return 0;
}
#include <iostream>
#include <limits>
using namespace std;
int main() {
const unsigned int MAX_VALUES = 8;
int data[MAX_VALUES] = {5,9,6,2,4,8,3,1};
int maxProfit = std::numeric_limits<int>::min(); //Negative Infinite!
for (int buy = 0 ; buy < MAX_VALUES ; buy++) {
for (int sell = buy ; sell < MAX_VALUES ; sell++) {
if (data[sell] - data[buy] > maxProfit)
maxProfit = data[sell] - data[buy];
}
}
cout << "Most is :" << maxProfit << endl;
cin >> maxProfit;
return 0;
}
//Fastest way to do it using recursive function
public class MaxProfit {
public static void main(String[] args){
int[] data = {5,9,6,2,4,8,3,1};
System.out.println(maxProfit(data, data.length -1, 0));
}
static int maxProfit(int[] data, int curIndex, int prevMax){
if (curIndex == 0) {
return prevMax;
}
if (curIndex == data.length - 1){
return maxProfit(data, curIndex -1, data[curIndex-1]-data[curIndex]);
}else{
return maxProfit(data, curIndex -1, Math.max(data[curIndex]-data[curIndex - 1], data[curIndex]-data[curIndex - 1] + prevMax ));
}
}
}
//Fastest way to do it using recursive function
public class MaxProfit {
public static void main(String[] args){
int[] data = {5,9,6,2,4,8,3,1};
System.out.println(maxProfit(data, data.length -1, 0));
}
static int maxProfit(int[] data, int curIndex, int prevMax){
if (curIndex == 0) {
return prevMax;
}
if (curIndex == data.length - 1){
return maxProfit(data, curIndex -1, data[curIndex-1]-data[curIndex]);
}else{
return maxProfit(data, curIndex -1, Math.max(data[curIndex]-data[curIndex - 1], data[curIndex]-data[curIndex - 1] + prevMax ));
}
}
}
int i=0, j=0, itemp=0, jtemp=0, k=0, max=0
for (k = 1; k<sizeof(stockarray); k++)
{if (stockarray[k] > stockarray[itemp] )
{jtemp=k;
}
else {itemp=k; jtemp=k;}
if ((stockarray[jtemp] - stockarray[itemp]) > max)
{max = stockarray[jtemp] - stockarray[itemp];
i = itemp;
j=jtemp;
}
}
cout<<"the max profit is " <<max <<endl;
cout<< " the buying price is " << stockarray[i] <<endl;
cout<< "the selling price is" <<stockarray[j]<<endl;
public static void maxProfit(int arr[]) {
if (arr.length <= 1) {
return;
}
int min = arr[0];
int iMin = arr[0];
int minIndex = 0;
int max = arr[0];
int iMax = arr[0];
int tempMax = 0;
int maxIndex = 0;
for (int i = 1; i < arr.length; i++) {
if ((max-min) < (arr[i]-min) && minIndex < i) {
max = arr[i];
maxIndex = i;
if(tempMax<(max-min))
{
iMin = min;
iMax = max;
tempMax = max-min;
}
continue;
}
if (min > arr[i]) {
min = arr[i];
max = arr[i];
maxIndex = i;
minIndex = i;
}
}
System.out.println(iMin + " " + iMax);
}
public class maximumProblem {
public static void main(String args[]){
int[] ip ={5, 9, 6, 2, 4, 8, 3, 1};
int[] iparr = new int[ip.length-1];
int max = 0, left = 0,right = 0,sum=0,i,j = 0;
for(i = 0;i<ip.length-1;i++){
iparr[i] = ip[i+1] - ip[i];
}
System.out.println(" ");
for(i =0;i<iparr.length;i++){
for(j = i;j<iparr.length;j++){
sum = sum +iparr[j];
if(sum > max){
max = sum;
left = i+1;
right = j+1;
}
}
sum = 0;
}
System.out.println("Profit is :"+max+"\nFrom Day: "+left+ " To Day: " +right);
}
}
public static void maximizingProfit() {
int[] data = {5,9,6,2,4,8,3,1};
int maxProfit = 0;
int finalSp = 0;
int finalCp = 0;
for (int i = 1 ; i < data.length; ++i ) {
// selling at time 'i' will make a maximum profit of:
int sp = data[i];
for ( int j = i-1 ; j >= 0 ; --j ) {
int cp = data[j];
int profit = sp - cp;
if (maxProfit < profit) {
maxProfit = profit;
finalSp = data[i];
finalCp = data[j];
}
}
}
System.out.println("Max profit: " + (finalSp - finalCp) + ". Selling " + finalSp + " buying: " + finalCp);
}
int[] stockPrice={1,2,3,4,0};
int min=0,max=0,profit = 0;
for(int i=0;i<stockPrice.length;i++){
for(int j=i+1;j<stockPrice.length;j++){
if(stockPrice[j]-stockPrice[i]>profit){
min=i;
max=j;
profit=stockPrice[j]-stockPrice[i];
}
}
}
System.out.println(stockPrice[min]+" ,"+stockPrice[max]+" profit:"+profit);
Here is a Recursive version:
...
void FindMaxProfit( int a[], int n, int *mp )
{
if( --n == 0 )
return;
FindMaxProfit( &a[1], n, mp );
int mp2 = a[1] - a[0];
if( mp2 > *mp )
*mp = mp2;
}
...
int a[] = { 5, 9, 6, 2, 4, 8, 3, 1 };
int n = 8;
int mp = 0;
FindMaxProfit( &a[0], n, &mp );
cout << "Max Profit: " << mp << endl;
...
Output:
4
{{
package alex;
public class MaxDiff {
public static void maxDiff(int[] a) {
if (a.length < 2) return;
int end = a.length - 1;
int min = a[0];
int maxDiff = 0;
for (int i = 1; i < end; i++) {
if (a[i] < min) {
min = a[i];
} else {
int diff = a[i] - min;
if (diff > maxDiff) {
maxDiff = diff;
}
}
}
int diff = a[end] - min;
if (diff > maxDiff) {
maxDiff = diff;
}
System.out.println("maxDiff = " + maxDiff);
}
//v1 loop; mark min along the way
public static void main(String[] args) {
int[] a = {5,9,6,2,4,8,3,1}; //{1,3,6,4,2,7,-1};
MaxDiff.maxDiff(a);
}
}
}}
#include <iostream>
using namespace std;
int max(int a, int b)
{return a>b? a:b;}
int maxProfit(int price[], int n)
{
// Create profit array and initialize it as 0
int *profit = new int[n];
for (int i=0; i<n; i++)
profit[i] = 0;
/* Get the maximum profit with only one transaction
allowed. After this loop, profit[i] contains maximum
profit from price[i..n-1] using at most one trans. */
int max_price = price[n-1];
for (int i=n-2;i>=0;i--)
{
// max_price has maximum of price[i..n-1]
if (price[i] > max_price)
max_price = price[i];
// we can get profit[i] by taking maximum of:
// a) previous maximum, i.e., profit[i+1]
// b) profit by buying at price[i] and selling at
// max_price
profit[i] = max(profit[i+1], max_price-price[i]);
}
int max = profit[0];
for (int i=0; i<n; i++)
if (max < profit[i])
max = profit[i];
return max;
}
int main()
{
int price[] = {2, 30, 15, 10, 8, 25, 80};
int n = sizeof(price)/sizeof(price[0]);
cout << "Maximum Profit = " << maxProfit(price, n);
return 0;
}
- Dennis September 24, 2013