Studying for a Tech Interview: Part 3

Studying for a Tech Interview Sucks, so Here’s a Cheat Sheet to Help

This list is meant to be a both a quick guide and reference for further research into these topics. It’s basically a summary of that comp-sci course you never took or forgot about, so there’s no way it can cover everything in depth. It also will be available as a gist on Github for everyone to edit and add to.

Efficient Sorting Basics

Merge Sort

Definition:

• A comparison based sorting algorithm
• Divides entire dataset into groups of at most two.
• Compares each number one at a time, moving the smallest number to left of the pair.
• Once all pairs sorted it then compares left most elements of the two leftmost pairs creating a sorted group of four with the smallest numbers on the left and the largest ones on the right.
• This process is repeated until there is only one set.

What you need to know:

• This is one of the most basic sorting algorithms.
• Know that it divides all the data into as small possible sets then compares them.

Big O efficiency:

• Best Case Sort: Merge Sort: O(n)
• Average Case Sort: Merge Sort: O(n log n)
• Worst Case Sort: Merge Sort: O(n log n)

Quicksort

Definition:

• A comparison based sorting algorithm
• Divides entire dataset in half by selecting the average element and putting all smaller elements to the left of the average.
• It repeats this process on the left side until it is comparing only two elements at which point the left side is sorted.
• When the left side is finished sorting it performs the same operation on the right side.
• Computer architecture favors the quicksort process.

What you need to know:

• While it has the same Big O as (or worse in some cases) many other sorting algorithms it is often faster in practice than many other sorting algorithms, such as merge sort.
• Know that it halves the data set by the average continuously until all the information is sorted.

Big O efficiency:

• Best Case Sort: Merge Sort: O(n)
• Average Case Sort: Merge Sort: O(n log n)
• Worst Case Sort: Merge Sort: O(n^2)

Bubble Sort

Definition:

• A comparison based sorting algorithm
• It iterates left to right comparing every couplet, moving the smaller element to the left.
• It repeats this process until it no longer moves and element to the left.

What you need to know:

• While it is very simple to implement, it is the least efficient of these three sorting methods.
• Know that it moves one space to the right comparing two elements at a time and moving the smaller on to left.

Big O efficiency:

• Best Case Sort: Merge Sort: O(n)
• Average Case Sort: Merge Sort: O(n^2)
• Worst Case Sort: Merge Sort: O(n^2)

Merge Sort Vs. Quicksort

• Quicksort is likely faster in practice.
• Merge Sort divides the set into the smallest possible groups immediately then reconstructs the incrementally as it sorts the groupings.
• Quicksort continually divides the set by the average, until the set is recursively sorted.