Google Interview Question: Given the daily values of a s... | Glassdoor

Interview Question

Software Engineer Interview(Student Candidate) Mountain View, CA

Given the daily values of a stock, find how you can lose

  the most with one buy-sell trading.
Tags:
algorithm
Answer

Interview Answer

14 Answers

0

Or in other words, find the two points where the difference between the two are the largest in the function.

Interview Candidate on Nov 26, 2011
1

"find the two points where the difference between the two are the largest in the function" - this is incorrect. You can not go back in time when it comes to stock trading :) e.g. {2,1,10} has a maximum loss of 1-2 = -1, but has a maximum difference of -9.

Anonymous on Nov 28, 2011
0

[11,20,24,51,10,99,15,1,199,75] list of stock prices in increasing order of time stamps

Maintain two variables, min and max.

Whenever cur value of array is less than max then upadate min
do a diff between min and max and update curloss if it is less than curloss.

update max variable if value is greater than or equal to max

11 11 0
11 20 0
11 24 0
11 51 0
10 51 -41
10 99 -41
15 99 -84
1 99 -98
1 199 -198
75 199 -198

Gowri Shankar on Nov 29, 2011
4

Slight error in my previous post given above:

[11,20,24,51,10,99,15,1,199,75] list of stock prices in increasing order of time stamps

Maintain two variables, min and max.

Whenever cur value of array is less than max then upadate min
do a diff between min and max and update curloss if it is less than curloss.

update max variable if value is greater than or equal to max, dont update curloss variable here.

11 11 0
11 20 0
11 24 0
11 51 0
10 51 -41
10 99 -41
15 99 -84
1 99 -98
1 199 -98
75 199 -124

Gowri Shankar on Nov 29, 2011
1

package asaf;

public class MaxLose {
    public static void main(String[] args) {
        int[] ticks = {5,7,4,2,77,8,9};
        int[] worseSell = new int[ticks.length];
        worseSell[worseSell.length-1] = ticks[ticks.length-1];

        for (int index=ticks.length-2; index>=0; index--) {
            worseSell[index] = Math.min(worseSell[index+1], ticks[index]);
        }

        int lose = 0;
        for (int index = 0; index < ticks.length; index++) {
            lose = Math.max(lose, ticks[index] - worseSell[index]);
        }
        System.out.println(lose);
    }

}

Anonymous on Dec 1, 2011
0

double WorstSell(double *values, int n)
{
    double maxBuySeenSoFar = 0.0;
    double minprofit = 0.0;

    // in-order lose most. we need to buy high and sell low. we can only sell after buying.
    for (int i = 0; i maxBuySeenSoFar)
        {
            maxBuySeenSoFar = values[i];
        }
        else if (maxBuySeenSoFar - values[i] < minprofit)
        {
            minprofit = maxBuySeenSoFar - values[i];
        }
    }

    return minprofit;
}

NoOne on Dec 1, 2011
1

Recursive way to solve this in n logn

public static int[] findMaxLost(int[] prices) {
        return rFindMaxLost(prices, 0, prices.length-1);
    }

    private static int[] rFindMaxLost(int[] prices, int p, int r) {

        if (p == r) {
            int[] ml_pos = new int[2];
        ml_pos[0] = p;
            ml_pos[1] = p;
            return ml_pos;
        }

        int q = (p + r) / 2;
        int[] l_ml_pos = rFindMaxLost(prices, p, q);
        int[] r_ml_pos = rFindMaxLost(prices, q + 1, r);

        /*find the max_min cross the center point q*/
        int[] m_ml_pos = new int[2];
        m_ml_pos[0] = findMax(prices, p, q);
        m_ml_pos[1] = findMin(prices, q + 1, r);

        if ((l_ml_pos[0] - l_ml_pos[1]) >= (m_ml_pos[0] - m_ml_pos[1])
                && (l_ml_pos[0] - l_ml_pos[1]) >= (r_ml_pos[0] - r_ml_pos[1])) {
            return l_ml_pos;
        } else if ((m_ml_pos[0] - m_ml_pos[1]) >= (r_ml_pos[0] - r_ml_pos[1])) {
            return m_ml_pos;
        } else {
            return r_ml_pos;
        }
    }

    private static int findMax(int[] prices, int p, int q) {
        int pos = 0;
        for (int i = p + 1; i prices[i]) {
                pos = i;
            }
        }
        return pos;
    }

Allen on Dec 7, 2011
0

reader writer pointer soution. O(n)

public class MaxLose {
    public static void main(String[] args) {
        MaxLose m = new MaxLose();

        int[] a = new int[]{10, 3, 20, 10, 12, 5, 20, 7, 5, 3};

        int max = m.maxLose(a);
        System.out.println(max);
    }

    private int maxLose(int[] a) {

        int b = 0, max = 0;

        for (int s = 1; s max ? a[b] - a[s] : max;
        }

        return max;
    }
}

vinicius on Dec 8, 2011
0

Most answers here are in correct. Here is the algorithm. You first identify all buy canditaes, and all sell candidates. A buy canditate is: a point which is bigger than everything on its left and also bigger than the next point on its right. A sell candiate is a point that is smaller than everything on its right and also smaller than the point on its left.
Then you match buy canditates to sell candidates, for every buy candidate the matching sell canditate is the first sell candidate on its left. (multiple buy candidates can match multiple sell) After they are matched the pair with maximum difference will give you the max loss. O(n) needed to find candidates, les than O(n) neded to match pairs.

anonymus on Dec 17, 2011
0

Most answers here are in correct. Here is the algorithm. You first identify all buy canditaes, and all sell candidates. A buy canditate is: a point which is bigger than everything on its left and also bigger than the next point on its right. A sell candiate is a point that is smaller than everything on its right and also smaller than the point on its left.
Then you match buy canditates to sell candidates, for every buy candidate the matching sell canditate is the first sell candidate on its right. (multiple buy candidates can match multiple sell) After they are matched the pair with maximum difference will give you the max loss. O(n) needed to find candidates, les than O(n) neded to match pairs.

Anonymous on Dec 17, 2011
0

public static int minPoint(List list){
        if (!list.isEmpty()){
            int minPoint = list.get(0);
            return Math.min(minPoint - findMax(list),minPoint(list.subList(1, list.size()-1)));
        }
        return 0;

    }

    private static int findMax(List list) {
        int max = list.get(0);
        for (int i=1; i max){
                max = list.get(i);
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[] a = new int[]{10, 3, 20, 10, 12, 5, 20, 7, 5, 3};
        List list = new ArrayList();
        for (int i=0; i

Liron on Jan 20, 2012
0

//Given the daily values of a stock, find how you can lose the most with one buy-sell trading.
//A[] -> {5, 8, 6, 3, 9, 3, 2, 7}
//B[] -> {0, 3,-2,-3,6,-6,-1, 5} ? diff A[i] = A[i] - A[i - 1]
//C[] -> {0, 0,-2,-5,0,-6,-7,-2} -> min(0, B[i - 1] + B[i])

public int[] looseMost(int[] A) {
 int minRes = 0;
 int sIdx = 0;
 int eIdx = 0;

 int currRes = 0;
 int csIdx = sIdx;

 int prevB = 0;
 int currB;
 int currC = 0;

 for (int i = 1; i < A.length; i++) {
  currB = A[i] - A[i - 1];
  currC = Math.min(0, currB + prevB);

  if (currC < minRes) {
   sIdx = csIdx;
   eIdx = i;
  }
  else if (currC == 0)
   csIdx = i;

  prevB = currB;
 }

return new int[] {sIdx, eIdx};
}

Georgi Kalchev on Mar 24, 2012
1

If I understand the question correctly, the task is to find the minimum consecutive sum of price differences, which is equivalent to a maximum consecutive sum algorithm (just google it). This can be solved in O(n) using a dynamic programming approach.

Giovanni on Apr 20, 2012
4

The solution is here: http://www.geeksforgeeks.org/archives/6463

Anonymous on Apr 30, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.