Minimum Cost algorithm warmup

August 20, 2017

I reviewed the algorithm called minimum cost on Hackerrank in order to prepare for an algorithm in Gold Sachs codesprint.

I spent over 30 minutes to go over the test case. Here are the detail.

            var prices = new Int64[] { 20, 7, 8, 2, 5 };
            var minimumLoss = calculateMinimumLoss(5, prices);

Purchase at price 7, sell at price 5, and the minimum loss is 2.
Go over the test case, and get hands dirty on this test case:

Walk through the test case, backward iterate the array, and add element one by one to the SortedSet object called sortedSet.

First, sortedSet is empty, visit 5, search sortedSet a binary search tree for value from [5 - minLoss + 1, 4], empty set is found. Add 5 to SortedSet object.

Next, visit the element 2, and then search [2 - minLoss + 1, 1], empty set is found. Add 2 to SortedSet object.

Third, visit the element 8, and then search [8 - minLoss + 1, 7], find {2, 5}, get max value 5, then the loss is 3. Minimum loss is updated to 3. Add 8 to SortedSet object.

Fourth, visit the element 7, and then search [7 - 3 + 1, 6], in other words, [5, 6], 5 is found, and then, minimum loss is updated to 2.

Here is the C# code.