C# sortedDictionary - Minimum Cost Algorithm - an idea to write code (series 5 of 10)

Nov. 20, 2016

1. Introduction:
Julia spent time to write a C# solution in HackerRank - woman codesprint #2, using Dictionary<Int64, int> in the contest, here are the detail:

Here is the problem statement:
https://www.hackerrank.com/contests/womens-codesprint-2/challenges/minimum-loss

Julia's C# solution:

https://gist.github.com/jianminchen/af474846d81b96f4e70fc1a5866dca15

The ideas used in the algorithm:

Sort the array with house price.

Use bucket sort similar idea to go through each bucket, compare to previous if the current is less than minimum loss or not. Each bucket keeps the two value - max/ min value.

2. C# solution - Go deep to search for ideas to improve and strength the skill:

1. There is a solution written in C#, much simpler and smarter than Julia's C# code:

https://gist.github.com/jianminchen/c382bc1b40e47c2740a25abcaeffb846

Based on the assumption that housing price is different for each year, but I did not find the word in the problem statement.

2. Using Binary search - therefore, it is easy to find the minimum price, O(nlogn)
Maintain a binary search tree!

Study this C# solution using Binary search tree:

https://gist.github.com/jianminchen/c910f5d1f37309c70b489e6c75b0678c

3. Performance comparison among Java TreeSet, C# SortedSet, SortedDictionary:

Now, she likes to write a C# solution similar to C++14 using Set, Java 8 using TreeSet. Now she will write using SortedDictionary.

C# solution using SortedDictionary, timeout, only score 17.5 of 20.
https://gist.github.com/jianminchen/3e978465798afbd7d611e90a8ad7af0c

using C# SortedSet, timeout, score 17.5 of 20.
https://gist.github.com/jianminchen/63c1ed68999f78a72250372eb58a6953

Look up on stackoverflow.com
http://stackoverflow.com/questions/14675108/sortedset-sortedlist-with-better-linq-performance

Java TreeSet code: Perfect solution, score 20
https://gist.github.com/jianminchen/3fce12eff5838fa10bff0792547d0779

Test code here:
https://www.hackerrank.com/contests/womens-codesprint-2/challenges/minimum-loss

Use LINQ only, no SortedSet, timeout
https://gist.github.com/jianminchen/83f0079acbcfc4b6de3f5b1aff6aa131

Dec. 1, 2016
StackExchange.com Code Review
Julia came out the idea to get help from top talent in the world, she chose stackexchange.com code review and posted a code review request, a few people gave out their contribution, one on LINQ, one on SortedSet, then, Julia learned the solution. The question was posted on Nov. 30, 2016, and then, it was solved on Dec. 2, 2016. Less than 3 days.

Using List<T> BinarySearch
Using List<Int64>, BinarySearch and Insert APIs. Score 24 ( maximum score 35).

https://gist.github.com/jianminchen/d6c675533578d50049c636e566695830

The stackexchange.com code review link:
http://codereview.stackexchange.com/a/148714/123986

Using SortedSet<T> GetViewBetween(), score 30 (maximum score: 30)
http://codereview.stackexchange.com/a/148727/123986

C# submission:
https://gist.github.com/jianminchen/2fda6d1d11b19d6b59f3d44822115927