Deshaw Inc Interview Question
Country: India
Interview Type: In-Person
The problem boils down to:
Given an array, find two indices min & max such that A[max]-A[min] is maximum and max>min.
int findMAxProfit(int* A,int n) // n is the number of days
{
min=max=0;
maxProfit=INT_MIN;
for(i=1;i<n;++i)
{
if(A[i]<A[min]) min=i;
if(A[i]-A[min] > maxProfit) // if you want, update buy & sell day here
maxProfit=A[i]-A[min];
}
return maxProfit;
}
Complete code here: ideone.com/Xt1ZA
You are wrong, if stock prices are like 20, 5,10 then profit is 5 but you code says profit is 15
//Not a tested code but logic holds
int buyingPrice = arr[0];
int sellingPrice = arr[0];
int sellingDay = 1;
int nextbuyingdiff = 0;
int nextbuyingindex = 0;
for (int i = 2; i < arr.length; i++)
{
if (arr[i] > sellingPrice-nextbuyingdiff)
{
sellingPrice = arr[i];
sellingDay = i;
if (nextbuyingdiff != 0)
{
buyingPrice = arr[nextbuyingindex];
nextbuyingindex = 0;
nextbuyingdiff = 0;
}
}
if (buyingPrice > arr[i-1] && arr[nextbuyingindex] > arr[i-1])
{
if (sellingDay > i-1)
buyingPrice = arr[i-1];
else
{
nextbuyingdiff = buyingPrice - arr[i-1];
nextbuyingindex = i-1;
}
}
}
@Raj, did you bother running my code?
I have checked my code against the input set given by you & it is correctly outputting 5.
I have updated my solution with the link where i checked. Please have a look.
You update the max to the current loop variable whenever a new minimum wasn't discovered. Whenever this runs max > min will also be true, so your logic means that whenever a new minimum isn't discovered, you will run maxProfit=A[i]-A[min]; But that's not correct. You can see how with that logic, maxProfit could be replaced with a smaller maxProfit in the next iteration.
@eugene.yarovoi,Thanks for pointing out the mistake. So, While updating the maxProfit, We also need to check that whether the new profit calculated is greater than the maxProfit calculated so far.
I have updated the solution.
output: max Profit
public static void Days(int [] input)
{
int[] max=new int[input.length];
max[0]=0;
for(int i=1;i<input.length;i++)
{
max[i]=0;
for(int j=i-1;j>=0;j--)
{
int pre=0;
if(j-1>=0)
{
pre=max[j-1];
}
int post=Math.max(0,input[i]-input[j]);
max[i]=Math.max(pre+post,max[i]);
}
}
System.out.println(max[max.length-1]);
}
The general idea is buy high, seller higher, or buy low, sell high. On one day you buy. On a later day, you sell. The positive delta is your profit, which you want to maximize. Otherwise, don't trade at all:
int[] maxProfit(int[] prices)
{
int maxProfit=0;
int[] buyselldays=new int[]{0,0};
for(int b=0;i=b<prices.length;b++)
{
for(int s=b+1; s<prices.length && b<s; s++)
{
int delta = prices[s]-prices[b];
if(delta > maxProfit)
{
maxProfit = delta;
buyselldays[0]=b;
buyselldays[1]=s;
}
}
}
return buyselldays;
}
Test Cases:
1)20, 5,10
b = 5, s=10 => max profit = 5
2) 20 15 10 => don't trade
3) 5 10 35 => max profit = 30
4) 5 40 100 25 => 100 -5 = max profit 95
I think we dont need O(n^2) complexity
#include<stdio.h>
#include<limits.h>
int main()
{
int prices[]={5,40,100,25};
int i=0,j,n,max=INT_MIN,min=INT_MAX;
n=3;
i=0;
j=n-1;
while(i<=j)
{
if(i==j)
{
if(prices[i]<min) min=prices[i];
else if(prices[i]>max) max=prices[i];
break;
}
if(prices[j]>max)
max=prices[j];
if(prices[i]<min)
min=prices[i];
i++;
j--;
}
//printf("\n%d %d",min,max);
if(max>0 && min>0 && max>min)
printf("\n%d",max-min);
else
printf("\nDon't trade");
}
// This code does it for 10 predictions
//hope its right
//please comment
//complexity= O(n)
#include<stdio.h>
#include<conio.h>
void main()
{
int k=0,sell=0,day=0;
int stocks[10];
printf("Enter 10 day stock predictions :\n");
for(int i=0;i<10;i++)
scanf("%d",&stocks[i]);
int buy=day;
sell=day;
for(day=0;day<10;day++)
{
if(stocks[day]>stocks[sell])
{
sell=day;
}
else
{
if(stocks[day]<stocks[buy])
buy=day;
k++;
}
}
if(k==10)
printf("DONT BUY\n");
else
{
printf("Buy on day %d (%d), Sell on day %d(%d) ==> profit=%d\n",buy+1,stocks[buy],sell+1,stocks[sell],stocks[sell]-stocks[buy]);
}
getch();
}
#include<stdio.h>
#include<conio.h>
int main ()
{
extern void trade(int * ,int);
int arr[]={6,1,3,2,4,7};
trade(arr,sizeof(arr)/sizeof(arr[0]));
getch();
return 0;
}
void trade(int *p,int size){
int b=0,s=0,min,profit=0,i,buy=0;
min=p[0];
for(i=0;i<size;i++)
{
if(p[i]<min)
{
b=i;
min=p[i];
}
if((p[i]-min)>profit)
{
buy=b;
s=i;
profit=p[i]-min;
}
}
printf("buy on %d , sell on %d ..profit %d \n",buy,s,profit);
}
This question can be done by using stack and extra array for storing highestPrice[i..n].
i am using a my own structure : structure myStack{ int stockPrice, int index; }
Idea : Start from back and whenever you reach to val less than top of stack. push it into the stack and update the array highestPrice[i] = highestPrice[ myStack.index ] also keep updating the profit and dates in a maxProfit and boughtDate and soldDate else pop() elements till it is less than the stack elements or stack becomes empty.
Solution is O(n) time and O(n) space complexity.
#include <stdio.h>
#include <iostream>
using namespace std;
void execute()
{
int n;
int *stockPrices = NULL;
scanf("%d", &n);
stockPrices = new int[n];
for(int i = 0; i < n;i++){
scanf("%d", stockPrices + i);
}
int maxProfit;
int buyIndex, sellIndex, minIndex = -1;
maxProfit = stockPrices[1] - stockPrices[0];
buyIndex = 0;
sellIndex = 1;
for(int i = 1; i< n; i++){
if(stockPrices[i] > stockPrices[sellIndex]){
sellIndex = i;
maxProfit = stockPrices[sellIndex] - stockPrices[buyIndex];
}
if(minIndex != -1 && maxProfit < stockPrices[i] - stockPrices[minIndex]){
buyIndex = minIndex;
sellIndex = i;
maxProfit = stockPrices[sellIndex] - stockPrices[buyIndex];
}
if(stockPrices[i] < stockPrices[buyIndex]){
minIndex = i;
}
}
for(int i = 0; i< n; i++){
printf("%d ", stockPrices[i]);
}
printf("\n");
printf("Buy at %d and Sell at %d. You will get profit of %d\n", buyIndex, sellIndex, maxProfit);
delete[] stockPrices;
}
int main(int argc, char* argv[])
{
int totalTestCases;
scanf("%d", &totalTestCases);
for(int i = 0; i<totalTestCases; i++){
execute();
}
return 0;
}
The above code works in O(n) with no extra memory. I have validated it with the following test cases.
4
5
1 2 3 4 5
5
5 4 3 2 1
7
1 2 3 7 6 5 4
9
7 8 6 5 4 3 2 1 3
I am not sure whether this is the right answer, Can someone confirm?
Polishing the code with some comments.
#include <stdio.h>
#include <iostream>
using namespace std;
void execute()
{
int n;
int *stockPrices = NULL;
scanf("%d", &n);
stockPrices = new int[n];
// Read Stock Prices
for(int i = 0; i < n;i++){
scanf("%d", stockPrices + i);
}
int maxProfit;
int buyIndex, sellIndex, minIndex;
// Buy on day1 sell on day2. Initial Profit.
maxProfit = stockPrices[0] - stockPrices[0];
buyIndex = 0;
sellIndex = 0;
minIndex = 0;
for(int i = 0; i< n; i++){
// If the stock price has decreased, It might be a good time to buy. However, we do not know whether it would increase again.
// Hence save it as a minPrice so that if we find that the stock price goes up, we could use it.
if(stockPrices[i] < stockPrices[buyIndex]){
minIndex = i;
}
// If the stock price has increased from last time we planned to sell, Selling it now would definitely increase our profit.
// So choose the current price as selling price.
if(stockPrices[i] > stockPrices[sellIndex]){
sellIndex = i;
maxProfit = stockPrices[sellIndex] - stockPrices[buyIndex];
}
// Also check, the profit we make when selling at the current price and buying at found minimum till now, would increase our profit.
// If it does, then use them.
if(maxProfit < stockPrices[i] - stockPrices[minIndex]){
buyIndex = minIndex;
sellIndex = i;
maxProfit = stockPrices[sellIndex] - stockPrices[buyIndex];
}
}
for(int i = 0; i< n; i++){
printf("%d ", stockPrices[i]);
}
printf("\n");
// In case no profit, We can buy on any day, and sell on same day to make 0 profit (no loss) just to be in the game.
printf("Buy at %d and Sell at %d. You will get profit of %d\n", buyIndex, sellIndex, maxProfit);
delete[] stockPrices;
}
int main(int argc, char* argv[])
{
int totalTestCases;
scanf("%d", &totalTestCases);
for(int i = 0; i<totalTestCases; i++){
execute();
}
return 0;
}
The time complexity for this approach would be O(nlogn), hence slightly less optimal than the other solutions, but here is the idea anyway:
Build a maxHeap from the given array. Check if the index of root element in original array > index of leaf (smallest entry) in original array. If not, check for the original index of next leaf element. Once all leaves are exhausted, check for the next level till you get the original index of root > original index of current element.
#include<stdio.h>
#include<conio.h>
void main()
{
int p[3]={5,40,100,25};
int max_value=p[0];
int min_value=p[0];
int min_index=0;
int max_index=0;
int max_prof=0;
int i=1;
{
while(i<4)
{
if(min_value>p[i])
{
min_value=p[i];
}
else if(p[i]>min_value)
{
if(max_prof<(p[i]-min_value))
{
max_value=p[i];
max_prof=p[i]-min_value;
}
}
i++;
}
}
printf("max_profit: %d",max_prof);
}
Very similar concept as told by shondik
- Psycho August 09, 2012#include <stdio.h> #include <limits.h> int main () { int arr[] = {20, 5, 10}, i; int len = sizeof(arr) / sizeof(arr[0]) ; int maxProfit = INT_MIN, min = 0, max = 0 ; for ( i = 0 ; i < len ; i++ ) { if ( arr[i] > arr[min] ) { if ( (arr[i] - arr[min]) > maxProfit ) maxProfit = arr[i] - arr[min] ; } else min = i ; } ( maxProfit < 0)? printf ("\nNo profit") : printf ( "\nMax Profit = %d", maxProfit) ; getchar() ; return 0; }