HackerRank Stryker Code Sprint Grind (III) - Kth Zero - First Try

Sept. 18, 2016

Problem statement:
https://www.hackerrank.com/contests/stryker-codesprint/challenges/kth-zero

Julia observed that more than 80% successful rate on this algorithm, so she chose to work this one (fourth one) first instead of "The Hidden Message" (3rd question).

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

Here are the time line Julia worked on the problem solving:

/*
         * 3:46pm - 4:36pm
         * Read the question, and figure out the design:
         * Like database table using index, need to prepare index.
         * Only update query -
         *  1: case 1: replace the position which has value 0;
         *  2. additional element with value zero in the array
         *  Just put Hash table to the array, and then, sort the array O(nlogn).
         *  Maintain a hash table and array for value 0 in the array
         *  Otherwise, time complexity should be ok.
         *  To make sort minimum - only sort when next query of kth zero comes in,
         *  also set isDirty to track if update is need or not.
         */
         /*
         * 4:36pm start to write code
          *5:30pm conduct testing.
          *5:48pm, timeout, and score 26/40 points
         */

Summary: 
2.5 hours to work on first try.
1. 50 minutes reading time
2. 56 minutes to write first try
3. 20 minutes to conduct testing

Score 26/40 points, need to work on timeout issue