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.