Sunday, November 20, 2016

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:

Julia's C# solution:


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.


No comments:

Post a Comment