## Walmart Labs Interview Question for Interns

• 0

Country: United States
Interview Type: Phone Interview

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

traverse the price sequence ,maintain the minimum price so far,and update the max profit with a[i]-min
time complexity O(n)

``````int maxProfit(vector<int> &a)
{
if(a.size()==0)return 0;
int min=a;
int best=0;
for(int i=1;i<a.size();i++)
{
int tmp = a[i]-min;
best = max(best,tmp);
if(a[i]<min)min=a[i];
}
return best;
}``````

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

Hi
this will not give max profit
consider 4 5 3 6 ur solution give 3
but max profit is 4

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

@Ravisingh .... this is fine actually the array contains the prices not profit/loss and since u can buy only once and then sell it only once the max profit in your example will also be 3 only not 4

@ducking ... this is similar what i was refering to(kandane's algo) however yours will not be consuming any extra space also so its definitely better

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

ravi is right. It will be 4.
buy at 4 sell at 5 then again buy at 3 and sell at 6. total profil=4

Solution:
Maintain both min(buying point) and max(selling point) over traversal, these are just candidates till either end of data than we can add it to solution set OR
if we get a[i] < min then add current min and max to solution set and update min as a[i] and clear max=0. if a[i] > max, max = a[i] and continue traversal.

The solution set will include list of buying price and linked selling price to max profit.
Total profit = summation(max[i]-min[i]) over solution set

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

My solution at the end was:

Store difference from each consecutive day in an array of size n-1 (as size of original array is 1). So now we just have to find a continuous sequence of numbers(in the difference array) whose sum is maximum and that would give us max benefit

For instance lets say
original price array = [150 ,149 ,155, 157, 137, 150, 167]
difference price array = [ -1, 6, 2, -20, 13, 17]

So in difference array 1element represent the profit or loss(if -ve) if one buys stock on first day and sells on 2nd day

Now the problem reduces to maximum sum in subarray which can be easily calculated by Kandane's Algo in worst case O(n)

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

i think according to question there is no restriction that user will buy and sell stock in sequence of days

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

yeah the user needs to buy and sell only once.. actually this is what was my ans was at that time

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

Awesome.. This is correct one..

I had similar solution but reducing the problem to maxsubsequence is something I did not think of..

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

making it subsequence problem means assumin you buy on day i and sell on day i+1 which in not correct

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

First approach: O(n^2)
Global variables : maxProfit, maxSellValue, maxBuyValue
- start from the end , and for each index j(consider it selling value) find the max profit by computing a[j] - a[i] where i < j. Put in maxProfit the max profit found if bigger than maxProfit and store in maxSellValue the value from index j and in maxBuyValue the value from index i.

Example:
array = [150 ,149 ,155, 157, 137, 150, 167]

j = 6 : maxProfit = 30 maxSellValue = 167 maxBuyValue = 137
j = 5: the three values are the same
j = 4: the three values are the same
j = 3: the three values are the same
j = 2: the three values are the same
j = 1: the three values are the same
j = 0: the three values are the same

return the three values.

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

I think we can even go with 2 variables max and min and iterate through each element of the array and keep track of min and max until at each index. And at the end return min and max.

This would cost O(n) time and O(1) space.

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

We have to find min first and a max after such that max - min = maxprofit .This can be done in O(n). while traversing start with first price as min, keep going forward , if you find a lower number then update min. If you find higher number than min, update max and maxprofit using curent min and max. whenever u find a new min after a max has been identified then update the min and reset the max. repeat. always update maxprofit any better poitns are found. this should work for all cases . (assuming prices are not -ve ofcourse)

case of 15,25,10,30. ans shud be 10,30

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

will it work for this one?

150, 153,139,140,129

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

Lets the price process is N{1,...n}
create another array M{1,...,n-1} where M[i] is the maximum element in array N[i+1,...,n]; require O(n)
and output this max.
complexity O(n)+O(n)

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

Use a sliding window of x < N days. Calculate mean of these prices and then with each day slide the window to right by one i.e. take mean of next x numbers. If price is moving over the mean of last x days then buy and if it is going below that sell.

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

``````Profit[size] = {0}
Min{size] = {0}
profit = 0;
Min = price;
for ( i = 1; i < n; i++) {
if (price[i] < Min[i-1]) {
Min[i-1] = price[i];
else {
Min[i] = Min[i-1];
}
profit[i] = price[i] - Min[i];
}``````

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

``````int getProfit(int arr[], int len)
{
int count = 0, profit = 0, buy_val = 0;

for(int i=0;i<len;i++)
{
if(arr[i] <= arr[i+1])
{
count++;
}
else if(count)
{
count = count * arr[i];
count = 0;
}
}

return profit;
}``````

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

1- Start from the end, and keep max
find Minima in the array
diff = max - min

- Move to next, if > max then repeat 1

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

Following the simplest solution I can think of:

``````public Integer findBestStockBuySellPointsSimple(List<Integer> list) {
Integer currentMin, tempMin, currentMax, currentMaxProfit = 0;
tempMin = currentMin = currentMax = list.get(0);

for (Integer price : list) {
if (price < tempMin)
tempMin = price;

if (price - tempMin > currentMaxProfit) {
currentMin = tempMin;
currentMax = price;
currentMaxProfit = currentMax - currentMin;
}
}
return currentMaxProfit;
}``````

1 - Remember the last lowest price.
2 - If the difference to the current price is bigger than my last
maximum you got a new maximum profit.

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

``````public class BuySellProblem {

/**
* @param args
*/
public static void main(String[] args) {

int tempProfit=0;
int commitProfit=0;
int tempSell=0;
int commitSell=0;

int[] input = {110 ,149 ,137, 147, 148, 151, 100};

for (int i = 0,j=1; j < input.length; i++,j++) {

int tempDiff=input[j]-input[i];

if(tempDiff>0)
{
tempProfit=tempProfit+tempDiff;
}
}
tempSell=input[j];
commitProfit=tempProfit;
commitSell=tempSell;
}
{

}

if( commitSell<tempSell)
{
commitSell=tempSell;
}

}
else
{
commitProfit=tempProfit;
commitSell=tempSell;
}

}
if( commitSell<tempSell)
{
commitSell=tempSell;
}

tempProfit=0;

}

}

System.out.println("MaxSell:"+commitSell);
System.out.println("MaxProfit:"+commitProfit);

}

}``````

O(n)

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

``````public static void printMaxRange(int[] a){ //Stock numbers increasing sell & buy

int currMax = 0;
int prevMax = Integer.MIN_VALUE;
int start = 0;
int end = 0;
int prevElement = 0;
for(int i = 0; i < a.length; i++){

if(a[i] < prevElement){
currMax = a[end] - a[start];
if(currMax > prevMax){
prevMax = currMax;
}
start = i;
end = i;
}
else if(i == a.length-1 && a[i] > prevElement){
currMax = a[i] - a[start];
if(currMax > prevMax)
prevMax = currMax;
end = i;
}
else if(a[i] > prevElement){
end = i;
}

prevElement = a[i];
}

//prevMax = currMax;

System.out.println("Max Profit : " + prevMax);
System.out.println("Range Start : " + start);
System.out.println("Range End : " + end);
}``````

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

package com.walmart.careercup;

public class MaximizeStockProfit {
private static final long[] GIVEN_SAMPLE=new long[] {44,43,46,54,20,43,45,48,41,45,50};

public static void main(String[] args){
int currentIndexMin = 0;
int currentIndexMax = 0;
boolean lookForNewMax=false;
boolean lookForNewMin=true;
boolean captureData=false;

int minIndex=currentIndexMin;
int maxIndex=currentIndexMin;

int i=0;
while(i<GIVEN_SAMPLE.length){

boolean shouldIncrement=true;

if(lookForNewMax && (GIVEN_SAMPLE[i]>GIVEN_SAMPLE[currentIndexMax])){
currentIndexMax=i;

} else if( lookForNewMax && GIVEN_SAMPLE[i]<GIVEN_SAMPLE[currentIndexMax] ) {
lookForNewMin=true;
lookForNewMax=false;

captureData=true;
}

if(captureData || i==GIVEN_SAMPLE.length-1 ) {
if((GIVEN_SAMPLE[currentIndexMax] - GIVEN_SAMPLE[currentIndexMin] >GIVEN_SAMPLE[maxIndex] - GIVEN_SAMPLE[minIndex])
||
(GIVEN_SAMPLE[currentIndexMax] - GIVEN_SAMPLE[minIndex] >GIVEN_SAMPLE[maxIndex] - GIVEN_SAMPLE[minIndex])){
minIndex=(GIVEN_SAMPLE[currentIndexMin]<=GIVEN_SAMPLE[minIndex])? currentIndexMin:minIndex;
maxIndex=currentIndexMax;
}
captureData=false;
currentIndexMin=i;
}
if(lookForNewMin && GIVEN_SAMPLE[i]<GIVEN_SAMPLE[currentIndexMin]){
currentIndexMin=i;
} else if(lookForNewMin && GIVEN_SAMPLE[i]>GIVEN_SAMPLE[currentIndexMin] ) {
lookForNewMin=false;
lookForNewMax=true;
currentIndexMax=i;
shouldIncrement=false;
}
if(shouldIncrement) ++i;
}

if(GIVEN_SAMPLE[minIndex]<GIVEN_SAMPLE[maxIndex]){
System.out.println("Buy on day ["+(minIndex+1)+"] at price ["+GIVEN_SAMPLE[minIndex]+"], and sell on day ["+(maxIndex+1)+"] at price ["+GIVEN_SAMPLE[maxIndex]+"]");
} else {
System.out.println("You can't make money on this stock with long strategy. Try shorting it.");
}
}
}

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

``````package com.walmart.careercup;

public class MaximizeStockProfit {
private static final long[] GIVEN_SAMPLE=new long[] {44,43,46,54,20,43,45,48,41,45,50};

public static void main(String[] args){
int currentIndexMin = 0;
int currentIndexMax = 0;
boolean lookForNewMax=false;
boolean lookForNewMin=true;
boolean captureData=false;

int minIndex=currentIndexMin;
int maxIndex=currentIndexMin;

int i=0;
while(i<GIVEN_SAMPLE.length){

boolean shouldIncrement=true;

if(lookForNewMax && (GIVEN_SAMPLE[i]>GIVEN_SAMPLE[currentIndexMax])){
currentIndexMax=i;

} else if( lookForNewMax && GIVEN_SAMPLE[i]<GIVEN_SAMPLE[currentIndexMax] ) {
lookForNewMin=true;
lookForNewMax=false;

captureData=true;
}

if(captureData  || i==GIVEN_SAMPLE.length-1 ) {
if((GIVEN_SAMPLE[currentIndexMax] - GIVEN_SAMPLE[currentIndexMin] >GIVEN_SAMPLE[maxIndex] - GIVEN_SAMPLE[minIndex])
||
(GIVEN_SAMPLE[currentIndexMax] - GIVEN_SAMPLE[minIndex] >GIVEN_SAMPLE[maxIndex] - GIVEN_SAMPLE[minIndex])){
minIndex=(GIVEN_SAMPLE[currentIndexMin]<=GIVEN_SAMPLE[minIndex])? currentIndexMin:minIndex;
maxIndex=currentIndexMax;
}
captureData=false;
currentIndexMin=i;
}
if(lookForNewMin && GIVEN_SAMPLE[i]<GIVEN_SAMPLE[currentIndexMin]){
currentIndexMin=i;
} else if(lookForNewMin && GIVEN_SAMPLE[i]>GIVEN_SAMPLE[currentIndexMin] ) {
lookForNewMin=false;
lookForNewMax=true;
currentIndexMax=i;
shouldIncrement=false;
}
if(shouldIncrement) ++i;
}

if(GIVEN_SAMPLE[minIndex]<GIVEN_SAMPLE[maxIndex]){
System.out.println("Buy on day ["+(minIndex+1)+"] at price ["+GIVEN_SAMPLE[minIndex]+"], and sell on day ["+(maxIndex+1)+"] at price ["+GIVEN_SAMPLE[maxIndex]+"]");
} else {
System.out.println("You can't make money on this stock with long strategy. Try shorting it.");
}
}
}``````

Time complexity O(n)

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.