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.

Shortest Job First

July 16, 2017

Plan to study the algorithm called "Shortest Job First". There are a list of jobs with execution and arrival time, shortest job will be processed first, and then average waiting time will be calculated.

Problem statement here is in Chinese.

一个处理器要处理一堆request，一次只能处理一条，如果它有几个积压着的requests，它会先执行持续时间短的那个；对于持续时间相等的requests，先执行最早到达处理器的request。问平均每个request要等多久才能被处理。input：requestTimes[]，每个request到达处理器的时间; durations[] 每个request要处理的持续时间。 两个数组是一一对应的，并已按requestTimes[] 从小到大排序过。

Plan to study code written in Java first. 

Practice

C# practice using SortedSet, the code is here. 

There are seven requests in the following example, every request has two time stamps, request time and execution time. First request can be expressed in the form of (1, 2), where the request time is 1 and execution time is 2. Hopefully it makes clear to the second column with title "Process to Consider", second row (1, 2). 

Fix the bug in previous C# code because the average time should be 3.29. C# code is here, the correction is on line 71. 

Leetcode 239: Sliding Window Maximum

June 30, 2017


Julia is learning C# SortedSet, so she chose the algorithm to practice SortedSet. C# practice is here.

Leetcode 295 Median of stream

May 31, 2017

Leetcode 295. Find median from data stream - discussion panel is here.

C# solution using SortedSet. The C# code to study is here.

C# solution using MinHeap/ MaxHeap - self defined. The study code is here.

Read blog about the discussion again - link is here - the blog on ardendertat.com

Question 69: Median of a stream (Julia's ranking:  10 out of 10  March 31, 2017), book: Code interviews, Harry He. 

Follow up 

June 6, 2017

Julia C# practice using SortedSet, the code is here. 

Julia C# practice using self-defined Heap, the code is here. 

June 29, 2017
Review SortedSet implementation, the code is here. 

Actionable Items

Google search "SortedSet C# example leetcode", work on related algorithm, try to get more practice on SortedSet.