Minimum Heap - C# practice

April 23, 2017

Introduction

A minimum heap C# code is needed for the Email everywhere algorithm in a booking woman in tech contest, so Julia googled and found the C# code. She put together with the algorithm and then she scored 30 points with a full score. Learning to use heap is a great mark for Julia, she knows that completely sorting is expensive, if only max and min value is needed, better to use binary tree, not binary search tree. Julia starts to learn using heap when she work on algorithm problem solving.

Code review 

C# code is here. Need to add some test case and do some code review.

Walk through a small test case - median study

April 7, 2017

Problem statement: 

Add 1, 2, 3, 4, 5, and then keep tracking medium value to make sure that it is accessible using time complexity O(1).

Introduction

Julia teaches herself how to analyse step by step and get into the design of data structure this March 2017. First try, her thought thinking process looks naive from this blog but she likes to write down thought process, and continue to work on it. Life is much easy if Julia chooses to start baby step, reexamine things involved, small talks about every concept which should have been considered in the design process.

Julia likes to spend time on a test case rather than thinking about so many ideas/ articles/ practice she had worked on related to search median algorithm, that is a game to test memory. Instead Julia likes to show a better way, from her training of mathematics courses through her universities - SJTU, FAU math and computer science department, nothing can beat a small example and powerful message of problem solving, it is simple process but it brings out a good thought thinking process - maybe showing great mindset. Time is well-spent on the small test case. 

Baby step talk about data structure design 

Julia likes to practice this to get her familiar with heap concepts and also max heap and min heap.

Here we go.

First 1 is coming, put 1 into left side data structure, she is not sure what kind of data structure should be. 

The median is 1, no problem, just to get the first and only number in left side. 

Left side           Right side

1

And then, 2 is coming, Julia likes to put Right side.

Left side    Right side

1              2

Median is (1 + 2)/ 2 = 1.5

Now, 3 is coming, we have to decide 3 goes to which side, why? 

Binary search tree vs binary tree

1 2 3, 2 is the medium, we like to keep 2 at the top of data structure, first we decide to let 3 join which side, left or right? 

To allow first number 1 goes to left side, max heap is used for left side data structure. And there is implicit rule, left side data structure saves left half of the numbers, smaller one.

Repeat, middle element is the root of tree, no need to sort, binary tree, smaller half of numbers is in left side data structure. We can make it a max heap.

Rule 1: Left side data structure saves left half of the numbers - smaller ones

Because it is there is no need to sort everything which costs unnecessary time, using binary tree instead of binary search tree, to make median calculation be O(1), we like to keep the middle element at the root of binary tree. 

Left side - Max heap 

So, 1 is smallest value, go to left side, left data structure uses max heap. 

Left – 1

Right -   2

Right side - Min Heap

  

3, right side is min heap.

Extra rule - left size always not smaller than right side

Keep the left side’s size >= right side

Adjustment - heapify

Move 2 from right side to left side

Left side:  2 1   (starting from root node, and then level by level)

Using array to represent a heap

complete binary tree, 1 2 => node's value is smaller than child's value, swap => 2 1

Right side:  3

The median is 2, since left side’s nodes > right side’s node + 1

Next 4 is coming,  put 4 to right side

Left  side:  2  1

Right side: 3  4

The median is (2 + 3)/ 2 

Next 5 is coming, put 5 to right side because 5 is bigger than left side data structure - max heap's max value. 

Left side:   2  1

Right side: 3  4  5 

And then move 3 to left side:

Left side:

   2                   3

1   3     =>   1     2

Right side:

  5               4

4     =>    5

Actionable Item

Read median algorithm - find the kth element of an unsorted list on computer theory site 

Read the article - how to get unstuck in technical interview?

On the other hand, seeing you find your way out of a difficult situation tells a lot about your character, how you perform under pressure, your ability to think on your feet and your problem solving skills.


1. Not thinking about an algorithm


Make things simpler for yourself. Write down an example on the board and think about just solving that particular instance of the problem by hand.

Small test case -> generalize it back into an algorithm form. 


People tend to bomb their first few sets of interviews. This is mostly because they don’t have sufficient practice with how to handle that pressure of solving an unknown question.


15 mocking interview - systematic way 

A note of thankfulness

Julia likes to write a small note to thank Brooklyn to help her on writing better on this blog's introduction section, who is a graduate of linguistic major from university of Victoria in 2015. Brooklyn gave her comment about blog writing in general, and she said that Julia writes very well now. 

Fraudulent Activity Notification - OpenBracket Code Sprint - HackerRank

Oct. 20, 2016

Julia spent over 8+ hours to work on this algorithm, and finally, at the end of day, she knew that she had to read problem statement again and figured out a new idea. She found the solution and scored 40 of 40.

But, Julia likes to write down her journey, and reminds herself to be smart, be able to find optimal solution in first time.

Here is the problem statement:

https://www.hackerrank.com/contests/openbracket/challenges/fraudulent-activity-notifications

And then, her submissions:

1. First submission:
pass 2 test cases, 5 test cases - runtime error
https://gist.github.com/jianminchen/ed96f667ca20d4ce6e5da61315e17cd5

Over 3 hours work,
1. timeout issue - use binary search to replace linear search, and see if the timeout issue can be solved.
2. Add position/ remove position - try to implement O(1) insertion O(1) deletion algorithm
code has flaws, insert position (p1) / remove position (p2),
p1 >= p2 or p1 < p2.
3. Look into C# bulk copy, Array.Copy, not sure if Array.Copy can be O(1) instead of O(n), using bulk copy, look up stack overflow a few times.

2. Find bugs, and continue to write new code.

https://gist.github.com/jianminchen/3beb1b21d99a62eb607f9f3b40a61bee

add new function called binarySearchAdd

function customizedArrayCopy (line 181 - line 190) - try to fix bugs
discuss different cases - 90 lines of code, hard to write without a bug, and so many cases,
think about cyclomatic complexity, or execution path, how many execution path with this design.

Julia spent hours on this function customizedArrayCopy, and it is hard to spot error/ fix error
on this function.

(Oct. 26, 2016, customizedArrayCopy function - If two case (line 267 - line 288), else, there are
3 nested statement: if/else if/else (line 289 - line 342); so, in total, 5 cases, line 252 - line 346;
This function is breaking SRP - single responsibility principle. The function spanning almost 96 lines
of code, Julia has to take more than 6 hours to write/ debug/ reason. This is not the code for
HackerRank contest!)

..., continuously submitted 9 times, score 0.

9th submission:
https://gist.github.com/jianminchen/0b7fe2b10b324e710066128682992c74

10th submission:  score 40 out of 40, using bucket sort.
https://gist.github.com/jianminchen/5e85135f68bc9be02be7f7390647ae00

Timeline analysis:

7:45am             - start to read problem statement
9:00am - first submission, pass 2 test cases, but timeout on other 5 test cases,
       Binary search can improve time complexity from O(n) to O(logn)
Work on binary search algorithm

10:11am   reviewed binary search function code
10:24am   found bugs related to Add position vs Remove position
10:40am look up Java AddRange, C# bulk copy

...  (Julia likes to play with Array.Copy, and other things - logic thinking if/ else. But to be a competitive programmer, Julia has to learn to sharpen her thoughts, work on optimal solution instead.)

12:00 - 9:30pm - work on the coding, try to write bug-free code, mess with ideas using Array.Copy, naively thinking about bulk copy - Time Complexity O(1)

9:30pm - gave up all the solutions, read problem statement and find a new idea:
9:30pm - 10:07 write a bucket sort algorithm, without too much effort, succeed.

Time complexity:

O(N^2) -> O(NlogN) -> O(N), N is the number of days.

Previous work on distribution sort, bucket sort:

1. Leetcode 164: Maximum Gap - a Distribution sort (bucket, counting, radix) algorithm
http://juliachencoding.blogspot.ca/2015/06/leetcode-maximum-gap-no-164.html

2. Radix Sort - a distribution sort
http://juliachencoding.blogspot.ca/2016/05/radix-sort-distribution-sort.html

3. Leetcode 164: Maximum Gap - a Distribution sort (bucket, counting, radix) algorithm
http://juliachencoding.blogspot.ca/2015/06/leetcode-distribution-sort-algorithm.html

Encouraging ending notes:
Can you give out a summary for the practice?

Answer:
10th submission:  score 40 out of 40, using bucket sort.
https://gist.github.com/jianminchen/5e85135f68bc9be02be7f7390647ae00

line 141 and line 142:

int SIZE = 201; int[] dPriorDays = new int[SIZE]; Just use space to trade off time, reduce time complexity from two loops on n - number of days to one loop on n (2*10^5), and one loop on SIZE (201) which is also constant tim O(1). Basic facts: n^2 will be around 4*10^10, it will be around 40 billion. The time complexity is shortened to 1 of 1000. Things to work on: Spend 2 hours to read this mentoring business in IT business - http://www.theeffectiveengineer.com/blog/secret-to-growing-software-engineering-career http://www.theeffectiveengineer.com/blog/five-key-skills-of-successful-programmers

K largest elements in the array - various ideas

July 29, 2016

Top k values in the array - review the following article: 

http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/

1. sorting the array   O(nlogn)
2. use selection sort O(nk)
3. use sorting
4. use min heap
5. use max heap
6. use temporary array
7. use order statistics

7A. randomized selection algorithm - a dertministic algorithm that runs in O(n) in the worst case

 http://www.cse.ust.hk/~dekai/271/notes/L05/L05.pdf
1. the idea is to divide n items into n/5 sets (denoting m sets), each contains 5 items. O(n)
2. Find the median of each of the m sets. O(n)
3. Take those m medians and put them in another array.  Use Dselection() to recurisively calculate the median of these medians. Call this x. T(n/5)
4. ...

7B. Use QuickSort partition algorithm to partition around the kth largest number O(n).

7C. Sort the k-1 elements (elements greater than the kth largest element) O(klogk). This step is needed only if sorted output is required.

Leetcode 295: Find median from data stream

February 8, 2016

It is always very important to write some code and then get the experience to master a new algorithm. 

Leetcode 295: Find medium median from data stream 

Segmentfault.com article about median algorithm 

- great algorithm discussion about median algorithm design using two heaps - one max heap, one min heap, in Chinese language. 

Julia gist about code

Leetcode 295 solution blog by buttercola


Julia, read Java priorityQueue class and get some ideas about the class design:

programcreek.com priority queue class example

stackoverflow - how do I use a priority queue in java


understand priority queue first, read the lecture notes:

WSU.edu heap lecture notes

To be continued. 

Follow up after 12 months

April 3, 2017

Work on heap as a data structure.