HackerRank NCR codesprint review

Nov. 7, 2016

Codesprint:
https://www.hackerrank.com/contests/ncr-codesprint/challenges


Julia was so motivated to spend 2 days in the weekend to work on the codesprint, she only did one shopping trip to Burnaby crystal mall, less than 2 hours. Rest of weekend, she worked on the problem solving.

Julia reviewed the article about HackerRank contest and how to play better:

https://goo.gl/IHeEoi

Her favorite note in the above blog, item 4:

Even if you are not world class competitive programmer, you still have a chance to get into top 50 or even higher. The minimum goal is to get into top100, which is like usually about top 2–3% of all competitors. Being in top100 is great and sounds really good. 

The major factor to achieve the goal is a combination of problem solving skills, online research, dedication and persistence. First read all the problems and start solving them one by one from the easiest one. First solve the ones you can tackle without any research or long thinking, just to mark them as done and get motivation to tackle harder ones.

Julia did some research on this NCR contest, in top 100, even around 100, some of them are ICPC contest winner, score range is around 200 out of 430. 

Julia's score is 62.76, 480 out of 2621. 

Facts:
1. Julia likes to work on those hard algorithms, last 3 of 8 algorithms. She thought that she could make 10 from each of them. But it was too late when she read the problem statement. She only had 3 hour left to 12:00am in the middle night of Sunday. 

Lessons learned: 

Do not work on ideas taking a lot of time to code; even prototype is questionable. Treat it as a contest, play to win, not play to learn. 

48 hours contest, a lot of algorithms - 8 of them, total time to work on is 16 hours, 8 hours a day. So, give each algorithm 2 hours a time. 

Spent 6-8 hours to score 6 out of 20 on spiral message. Simple mistake of understanding problem statement, and base test case: one line, one row failure. 

Should be more confident on hard algorithm - game of numbers. Less than 1 hour to score 15 of 50, but gave up bug fix. So close to perfect solution. 
So, if Julia has more experience to play HackerRank contest, she should try to make it at least 100 of 430. And also, she can spend less hours to work on the contest, and spend 1 - 2 hours a day on sport activities in the day time. 

Do not think about past contest - Warlmart codesprint, 24 hour contest, Julia spent time to bet on a hard problem (score: 100) until 4:00am, and scored 0 of 100. 

A great #quote from a #Champion.#Focus #Motivational pic.twitter.com/kMdOIl2l3R

— Tennis Coaching™️ (@tennisdothow) September 22, 2016

Count inversions - Extended merge sort - 3 Lecture Notes Study

August 5, 2016 

Choose topic: extended merge sort
Algorithm: count inversions

count inversions - extended merge sort
1. http://jane4532.blogspot.ca/2013/06/zz-google-onsite-interview.html
2. http://www.geeksforgeeks.org/counting-inversions/
3. http://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec08-inversions.pdf
4. https://www.cp.eng.chula.ac.th/~piak/teaching/algo/algo2008/count-inv.htm

5.  https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/05DivideAndConquerI.pdf
6. http://www.cs.colostate.edu/~cs320/Slides/05_inv.pdf


problem statement:

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. 
Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Example:
The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

Lecture Notes -

1. First lecture study:

http://www.cs.colostate.edu/~cs320/Slides/05_inv.pdf

1. How many inversions at most in the array n?

n(n-1)/2, special case, like {n, n-1, ..., 1}, any two nodes in the array is one inversion pair.

or: What is the maximum number of inversions for a list of length n? 

n(n-1)/2

2. If each inversion is counted once, then the time of the algorithm is O(n^2), n is the number of elements in the array. Not optimal, we should not count each inversion.

3. Ideas to solve the algorithm:

Bubble sort? 

Selection sort?

Insertion sort? 

These are O(n^2)

Bubble and insertion sort count each individual inversion. To do better we must not count each individual inversion. 

So, better algorithm is to beat O(n^2), using merge sort, nlogn - divide and conquer - sort and count inversion in the same time.

In merge sort we do not swap all elements that are out of order with each other, we make larger distance "swaps". 

Questions: Sorting and counting inversion - merge part how to count the inversions.

Keywords in the lecture notes (7):

Collaborative filtering 

inversions 

Meta-search tools
Rank analysis
Recurrence Analysis  - T(n) = 2 T(n/2) + cn 

similarity/ dissimilarity / in the middle 

the number of out of place rankings 

Actionable Items: 

1. Merging part with diagram:   <- Julia, can you draw a diagram as well 

2. Count Inversions: Algorithm pseudo code - write down here: 

2. 2nd Lecture Notes Study: 

https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/05DivideAndConquerI.pdf

Julia, write down favorite notes one sentence a time, on page 16, 17 

------- 

Counting inversions: how to combine two subproblems?
Q. How to count inversions (a,b) with a ∈ A and b ∈ B? 
A. Easy if A and B are sorted!

Warmup algorithm. 

Sort A and B. 

For each element b ∈ B, 

- binary search in A to find how elements in A are greater than b. 

list A                               list B

7    10    18  3  14           17    23    2  11  16

sort A                              sort B
3   7    10  14  18            2   11    16  17  23

binary search to count inversions (a, b) with a ∈ A and b ∈ B

3   7    10  14  18            2   11    16  17  23
                                       5    2      1     1   0
-------

3. 3rd Lecture Notes Study:  (Inversions Count)

http://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec08-inversions.pdf

Play to win; stop Recognize when you are using negative self-talks and replace it with positive; when in doubt, remember: Play to win.

Great tips for sports coaching, https://t.co/6m29a8l1z0

— jianmin chen (@jianminchen) July 22, 2016

Memorize 8 tips to help you to perform to your highest potential in Tennis (? code practice, etc.):
1. Let go of what others think
2. Perform for yourself, not to impress or to "not disappoint" others
3. Accept that you will make mistakes, and let them go
4. Focus on what you can control
5. Recognize when you are using negative self-talk and replace it with positive
6. Rather than performing perfectly, perform to see improvement
7. Be objective about your performance, not subjective
8. Focus on the Journey, not the Destination

Play not to lose or Play to win - Julia plays to win! 

Some people play not to lose. I play to win each and every second I'm on court. #SpeedTakes aggression. pic.twitter.com/ae5xlriogs

— Simona Halep (@Simona_Halep) July 2, 2016

JavaScript Array developer.Mozilla.org - 3+ hours study

July 2, 2016

First thing in the morning, read JavaScript Array webpage, and then, start to work on the target:

1. Memorize all the content on the page.  (Estimated time to understand every term on the page: 10+ hours)

https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/prototype

2. List all concepts to learn
3. Questions about the content

Training on JavaScript - start from memorizing JavaScript Array APIs

Time spent:
3 hours (July 2, 2016)

https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/prototype

Design drills to memorize the JavaScript function names:

1. Properties

Array.prototype
Array.length

Method   (33 methods)

Array.from()
Array.isArray()
Array.of()

Array.prototype.concat()
Array.prototype.copyWithin()
Array.prototype.entries()
Array.prototype.every()
Array.prototype.fill()

Array.prototype.filter()
Array.prototype.find()
Array.prototype.findIndex()
Array.prototype.forEach()
Array.prototype.includes()

Array.prototype.indexOf()
Array.prototype.join()
Array.prototype.keys()
Array.prototype.lastIndexOf()
Array.prototype.map()

Array.prototype.pop()
Array.prototype.push()
Array.prototype.reduce()
Array.prototype.reduceRight()
Array.prototype.reverse()

Array.prototype.shift()
Array.prototype.slice()
Array.prototype.some()
Array.prototype.sort()
Array.prototype.splice()

Array.prototype.toLocaleString()
Array.prototype.toSource()
Array.prototype.toString()
Array.prototype.unshift()
Array.prototype.values()

Inheritance:

Function -> properties ->   (5, please remember: c, d, l, n, p)
Functon.caller
Function.displayName
Function.length
Function.name
Function.prototype

Function -> Methods -> (6, please remember: a, b, c, i, t, t)
Function.prototype.apply()
Function.prototype.bind()
Function.prototype.call()
Function.prototype.isGenerator()
Function.prototype.toSource()
Function.prototype.toString()

Object

Methods

Object.prototype.__defineGetter__()
...

2. Study notes (July 2, 2016):

a global object,
list-like objects
Access(index into) an Array item
Loop over an array - forEach
push - Add to the end of an Array
pop  -  Remove from the end of an Array
shift - Remove from the front of an Array
unshift - Add to the front of an array
     Adds one or more elements to the front of an array and returns the new length of the array.
push - find the index of an item in the Array
pop  - Remove an item by Index Position
splice - Remove an item by Index Position
slice  - Copy an Array
    julia's comment: slice or dice, slice is just to get part of array, can be the whole array. 
           function syntax, startIndex, endIndex, arr.slice([begin[, end]])
from - Array.from(), creates a new Array instance from an array-like or iterable object. 
isArray - Array.isArray(), returns true if a variable is an array, if not false. 
of  - Array.of(), creates a new Array instance within a variable number of arguments, regardless of number or type of the arguments. 

Mutator methods - modify the array
copyWithin - Copies a sequence of array elements with the array
fill - Fills all the elements of an array from a start index to an end index with a static value.

splice - Adds and/or removes elements from an array.
join - joins all elements of an array into a string.

Iteration methods:
forEach()
entries()
every()
some()
filter()
find()
findIndex()
keys()
map()
reduce()
reduceRight()
values()

Question: Syntax - what kind of definition? [ <- optional argument?

traversal and mutation operations 
Arrays can be stored at non-contiguous locations in the array, JavaScript arrays are not guaranteed to be dense.
Questions: When to use typed arrays? 
   JavaScript arrays are not guaranteed to be dense, so typed arrays are guaranteed to be dense. (? Look into it later)

Questions: an associated array - what is "associated" meaning? 

zero-indexed - 
using bracket notation - renderer['ed].setTexture(model, 'character.png')  - works properly
with dot notation - cannot be referenced with dot notation, must be accessed using bracket notation. 

Array.length talk -     A JavaScript array's length property and numerical properties are connected. Several of the built-in array methods (e.g., join, slice, indexOf, etc.) take into account value of an array's length property when they are called. Other methods (e.g., push, splice, etc.) also result in updates to an array's length property. 
  Questions: built-in array methods ? Array.prototype.join, those functions are defined for all iterable object. 

Good reading with one example, two lines of JavaScript code: 
Creating an array using the result of a match
RegExp.exec, String.match, and String.replace (? study later)

Memorize this example - one regular express a time

// Match one d followed by one or more b's followed by one d
// Remember matched b's and the following d
// Ignore case

var myRe = /d(b+)(d)/i; 
var myArray = myRe.exec('cdbBdbsbz')

Question: review regular expression in JavaScript?

Array instances 
All array instances inherit from Array.prototype. 

Some people play not to lose. I play to win each and every second I'm on court. #SpeedTakes aggression. pic.twitter.com/ae5xlriogs

— Simona Halep (@Simona_Halep) July 2, 2016