Woman's CodeSprint 2 - Minimum Loss - after the contest (series 2 of 10)

Nov. 20, 2016

Julia worked on the algorithm in the contest, and then solved the algorithm with full score - 35.

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:

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.

Study all other submissions using C++, Java, C#, JavaScript:

Actionable Items:

1. Read the code line by line, word by word; train myself to understand the code, by reading, by association 

with C#.

2. Study TreeSet - Java - class - memorize all the API, compared to C# Hashset

https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html

My favorite Java code:
https://gist.github.com/jianminchen/3fce12eff5838fa10bff0792547d0779

A small research - TreeSet in Java is implemented as Binary search Tree?
http://stackoverflow.com/questions/4430809/making-binary-search-tree

Find the best solution written in Java:

Discussion of Time Complexity:

1. Brute force solution - O(n^2), choose any two year to compare the price. Will time-out!

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

line 16, 25 are Julia's favorite code - 

Very classical solution using binary search tree, and very clever solution.

Memorize the solution. Warm up the solution sometimes in the future.