Stock Exchange Losses


Easy puzzle, you have a list of values and are looking for the biggest loss possible, i.e the biggest difference between a high value, and a low value which follows it in the list. For this you just have to compute the difference between the current value and the maximum value read yet, and search for the biggest difference.

Difficulty: Medium · Skills: single pass, running maximum, greedy, array scan

What this puzzle tests in a coding interview

Stock Exchange Losses is the inverted twin of the well known maximum profit interview problem. It checks whether you can find the biggest drop from an earlier peak to a later trough in one pass instead of comparing every pair.

How to solve it, step by step

  1. Read all prices from the single input line.
  2. Keep a running peak and a running trough that follows it.
  3. When a new higher peak appears, record the loss of the previous peak and trough, then reset both to the new value.
  4. When a lower price appears, lower the current trough.
  5. After the loop, record the last peak-trough loss and print the largest one as a negative number, or 0 if prices never fell.

Time and memory complexity

One pass over n prices gives O(n) time and O(1) extra memory.

Traps to avoid

Tip for a timed test

State the invariant out loud: best loss so far versus current price minus highest price seen so far. That single line is the whole solution and is easy to verify.

C

Note the usage of strtok and atoi to read all the integer values contained in a string.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>

int main(int argc, char **argv)
{
    // number of stock values
    int N;
    scanf("%d\n", &N);
    
    /* as each stock value is under 2^31 which is roughly 4*10^9,
       15 chars per value is largely enough*/
    char line[15*N];
    fgets(line,15*N,stdin);
    
    /* currentMax and currentMin will store the local minimum and maximum
       stock values, maxLoss will store the maximum loss found yet */
    int stockValue, maxLoss, currentMax, currentMin;
    maxLoss = currentMax = 0;
    currentMin = INT_MAX;
    
    // Uses strtok to read all the stock values
    char *tok;
    tok = strtok(line," ");
    for (int i = 0 ; i < N ; i++) {
        stockValue = atoi(tok);
        
        if (stockValue > currentMax) {
            if (currentMax-currentMin > maxLoss)
                maxLoss = currentMax-currentMin;
            currentMax = currentMin = stockValue;
        } 
        else if (stockValue < currentMin)
            currentMin = stockValue;
            
        tok = strtok(NULL," ");
    }
    
    if (currentMax-currentMin > maxLoss)
        maxLoss = currentMax-currentMin;
        
    printf("%d\n",-maxLoss);
    return EXIT_SUCCESS;
}