## Deshaw Inc Interview Question

Country: India
Interview Type: In-Person

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

Very similar concept as told by shondik

``````#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;
}``````

Comment hidden because of low score. Click to expand.
1
of 3 vote

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

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

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 sellingPrice = arr[0];
int sellingDay = 1;
for (int i = 2; i < arr.length; i++)
{
{
sellingPrice = arr[i];
sellingDay = i;
{
}
}

{
if (sellingDay > i-1)
else
{
}
}
}

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

@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.

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

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.

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

@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.

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

if you take input as 20, 5, 3, 10,31,10 then max profit should be 28(31-3) but output from your program will be 7 ...which is incorrect

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

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]);
}``````

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

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;

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;
}
}
}

}``````

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

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

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
}``````

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

// This code does it for 10 predictions
//hope its right
//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]);
sell=day;
for(day=0;day<10;day++)
{
if(stocks[day]>stocks[sell])
{
sell=day;
}
else
{
k++;
}
}
if(k==10)
else
{
}
getch();
}

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

``````#include<stdio.h>
#include<conio.h>
int main ()
{
int arr[]={6,1,3,2,4,7};
getch();
return 0;
}
min=p[0];
for(i=0;i<size;i++)
{
if(p[i]<min)
{

b=i;
min=p[i];
}
if((p[i]-min)>profit)
{
s=i;
profit=p[i]-min;
}
}
}``````

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

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.

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

``````#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];
sellIndex = 1;
for(int i = 1; i< n; i++){
if(stockPrices[i] > stockPrices[sellIndex]){
sellIndex = i;
}
if(minIndex != -1 && maxProfit < stockPrices[i] - stockPrices[minIndex]){
sellIndex = i;
}
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?

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

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];
for(int i = 0; i < n;i++){
scanf("%d", stockPrices + i);
}
int maxProfit;
// Buy on day1 sell on day2. Initial Profit.
maxProfit = stockPrices[0] - stockPrices[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.
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;
}
// 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]){
sellIndex = i;
}

}
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;
}``````

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

// Buy on day1 sell on day2. Initial Profit.
How can you assume there will be a profit when stocks are sold on day2?
In case prices are decreasing from day 1 to day2, what should be the initial value of maxProfit in this case?

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

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.

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

#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);
}

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

What's the flaw in this?
- Find the maximum
- Until that day, keep buying all the stock available everyday (since question does not say there is any limit to how much you can buy)
- Sell on the day of the maximum
- Repeat for the part of the array after the maximum

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.

### 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.