HackerRank Stryker Code Sprint Grind (IV) - Kth Zero - Second Try

Sept. 18, 2016

Continued to work on the algorithm, tried to solve the time out issues.

Here is the C# code:

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

Timeline of Julia bug fixing, aiming more points successfully:

/*
         5:48pm - start to work on time out issue
         * 6:52pm - bug fix:
         * stack over flow
         * Are arrays or lists passed by default by refrence in C#?
         * Need to pass ref
        */

The idea to solve timeout is to using O(n) time to copy the array instead of using O(nlogn) to sort the array.

Summary: 

1. 25 minutes to do analysis
    5:48pm - 6:07pm
2. 45 minutes to modify code 
   Worked on coding 6:07pm -  6:52pm
2.  and then, created a new bug, and then fix
Are arrays or lists passed by default by reference in C#?

Score 52/60, two test cases time out due to 3s
Julia's comment: Haha..., Julia, you could not figure out why? Read the study code #1, then figure out why.  (worked on it again on Sept. 19, 2016)

Study code:  (worked on it again on Sept. 19, 2016)
1. C#
https://gist.github.com/jianminchen/9cdbdcefd84e3cb8e709eabf705ce4b0

Julia learned the lesson after she studied the above code:
In her solution, a hashset is used to get access O(1) for those zero numbers in the array. However, the hash function can not guarantee to perform as good as O(1).

Because the size of array is 10^5, it is the same thing to access O(1) if using binary search, which is log(N) = log(10^5) = 5 = O(1).
(Sept. 20, 2016 correction: log(N)=log(10^5) = 5 * log10 =5 *3.xx = O(1), since log 8 = 3. )

The fix of the bug is to remove the Hashset in the solution, call Array.BinarySearch to find the value. 

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


2.
https://gist.github.com/jianminchen/63172e67001956e75abae02d079c668d

Google search using keyword: 
C# sortedList analog in C++

Found the articles to read:
http://landenlabs.com/code/containers/index.html

The SortedList<TKey,TValue> is the other sorted associative container class in the generic containers. Once again SortedList<TKey,TValue>, like SortedDictionary<TKey,TValue>, uses a key to sort key-value pairs. Unlike SortedDictionary, however, items in a SortedList are stored as sorted array of items. This means that insertions and deletions are linear - O(n) - because deleting or adding an item may involve shifting all items up or down in the list. Lookup time, however is O(log n) because the SortedList can use a binary search to find any item in the list by its key. So why would you ever want to do this? Well, the answer is that if you are going to load the SortedList up-front, the insertions will be slower, but because array indexing is faster than following object links, lookups are marginally faster than a SortedDictionary. Once again I'd use this in situations where you want fast lookups and want to maintain the collection in order by the key, and where insertions and deletions are rare.

Continuous work:
1. remove hashset from solution, C# solution, still time out on last 2 test cases.
https://gist.github.com/jianminchen/a865fd512e176ecf973338036db563c7

2. A lot of C++ solutions - use bit manipulation, binary tree, segment tree, more complicated than I thought.

1. Segment tree - read the blog 10+ minutes 

http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/