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. 

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 215: Find kth largest element in the array

May 15, 2016

 Problem statement:
 https://leetcode.com/problems/kth-largest-element-in-an-array/

 Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

 Read some blogs about this problem:

 http://www.jianshu.com/p/f52a88550588

 Julia likes to spend 10 - 20 minutes to review "Quick Select" - the idea, similar to Quick Sort, most important part is to partition.

 Time complexity: O(nlogn) in quicksort, but O(n) in quick select.

 1. Quick sort: Time complexity: O(nlogn)

 2. Use Heap sort, O(klogN)
Java Solution, using priority queue, code to study:
https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/215.kth-largest-element-in-an-array.java

Spend 20 minutes to read the blog:  4:23pm - 4:43 pm
1. http://www.cnblogs.com/yuzhangcmu/p/4164807.html

2. https://en.wikipedia.org/wiki/Introselect (read 10 minutes - 4:30pm - 4:40pm)

3. http://stackoverflow.com/questions/7559608/median-of-three-values-strategy

4. http://www.quora.com/What-is-the-most-efficient-algorithm-to-find-the-kth-smallest-element-in-an-array-having-n-elements

5. http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/ (4:50pm - 5:20pm)

30 minutes to review the solutions, write down short notes:
6 methods:
1. Use bubble k times - O(nk)
Modify bubble sort to run the outer loop at most k times
Like bubble sort, other sorting algorithms like selection sort can also be modified to get the k largest element.

2. Use temporary array
Time complexity: O((n-k)*k)

3. Use sorting
1. Sort the elements in descending order in O(nlogn)
4. Print the first k numbers of the sorted array O(k)
Time complexity: O(nlogn)

4. Use Max Heap
1. Build a Max Heap tree in O(n)
2. Use Extract Max k times to get k maximum elements from the Max Heap O(klogn)
Time complexity: O(n+klogn)

5. Use order statistics:
1) use order statistics algorithm to find the kth largest element.
Julia, take some time to review the article: see the topic selection in worst-case linear time O(n). (10 - 15 minutes)
Write down main ideas using your own words:
Use a deterministic algorithm that runs in O(n) in the worst case.

2)

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.