# Algorithms

This is by far the biggest area for the tech interview, though
thankfully it’s an area you can study well. It just takes a lot of
time. It should probably be something you are doing on an ongoing
basis. If you are doing this studying for an hour or two a week, plan
**at least six months**.

Whilst “learning” to code these algorithms, remember the goal is to learn, not to discover. Given a puzzle, think about it for 5-10 minutes. If you can’t solve it: LOOK UP THE ANSWER - then fully understand it. The solution you are looking for may have taken someone YEARS to discover. You are attempting to stand on the shoudlers of giants, not grow the height of a giant.

For example, the 8-queens puzzle was first published in in 1848. Franz Nauck published the first solutions in 1850. In 1874, S. Gunther proposed a method using determinants to find solutions. In 1972, Edsger Dijkstra used this problem to illustrate the power of what he called structured programming… You have 15 minutes.

Do not just memorise this. Actually understand the solution in your own terms. Consider understanding it, then coming back to code the problem later, so that you test that understanding.

Your understanding helps you to remember, and needs to be explained in the interview. It will also help with similar problems in the future.

## Time to go to school!

There’s plenty of information out there on this topic, and great sites to practice on, so in someway this is “easy”, just a lot of material to cover.

Remember that a whiteboard is the best environment for final preparation, it’s different without an editor.

- Big-O Cheat Sheet
- Sedgewick Algo CheatSheet (and code)
- LeetCode
- LeetCode Articles
- HackerRank
- GeeksForGeeks (algorithms)
- The Algorithmist
- neetcoder?
- Cracking the Coding Interview
- Programming Pearls (book)

Note that Topcoder and Project Euler are somewhat different to the rest of the sites out there. While being a top 5% TopCoder, or solving the first 100 Project Euler problems means you are very good at what you do, these sites are not so much learning tools, as they are competitive coding environments.

## MIT OpenCourseWare

There’s a few other good videos out there, but by far the best are the series from MIT. Totally worth checking out.

You can find all of these Engineering:Computer-Science:Algorithms-and-Data-Structures with “Video/Audio Lectures” on MIT’s Open Courseware, or MIT CS and AI Lab

- MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005, by Prof. Erik Demaine Prof. Charles Leiserson
- MIT 6.006 Introduction to Algorithms (Fall 2011), by Erik Demaine, Srini Devadas
- MIT 6.851: Advanced Data Structures (Spring’14), Prof. Erik Demaine, with notes as well.
- MIT 6.046J Design and Analysis of Algorithms, Spring 2015

## Topics

Cracking The Coding Interview contains a good selection of topics. I’ve extended that selection with quite a few more below.

Remember, Big-O Complexity is a **must**, but also throw in some basic
math(s):

- Exponent and log rules
- Trigonometry
- Algebra
- Progressions (arithmetic, geometric)
- Permutations and combinations:
`nPr`

,`nCr`

(n choose k).

# Data Structures

You *must* know all of these.

- Arrays, Matrix, Linked List, Strings, Stacks, Queues, Heaps.
- Bitfields/BitSets
- Hashing
- Trees (Suffix/Prefix as well), BSTs (AVL/Red-Black/B+)
- Graphs (3 representations).

# Algorithms

Data structures now seem trivia in comparison to this list:

- String search (KMP, Boyer Moore, Rabin-Karp, Suffix Tree).
- Sorting (Quicksort, Mergesort, Heapsort).
- Binary Search (Array or BST), Quickselect.
- Tree and graph traversal, recursive and iterative. BFS, and {Pre, In, Post} Order DFS.
- Remember to look up balanced tree rotations.

- Greedy Algorithms
- Recursion
- Backtracking (e.g. n-queens).
- Dynamic Programming
- Misc: Bit math, Regexp

Be aware of using augmented data structures, e.g. augmenting a BST:

- Order statistic tree
- Interval tree
- Interval tree is quite a nice solution for some problems.

Parsing is little painful, you could try just suggesting Lex/Yacc (Flex/Bison), though I got one question on this topic:

Better techniques for locating a substring quickly:

- Suffix Tree
- Suffix Array
- Auxiliary LCP Longest Common Prefix Array

Using Khan’s algorithm in graphs:

# Dynamic Programming

They all *love…* them some dynamic programming solutions, and a lot
of problems end up in this space, they are also a lot of fun. It’s
magic when you draw out the tables by hand and see how simple it is to
solve these problems.

- Change/Coin Making Problem.
- Box stacking problem has an LIS solution.
- Coins In a Line
- Egg Dropping
- House Robber

Cheat-sheet technique:

- Recursive solution?
- Able to define the recurrence relation?
- Try to apply top-down Memoization.
- Got Overlapping subproblems?
- Wonder if you can do it bottom-up with DP?

Check that it’s possible:

- Optimal substructure
- i.e. an optimal solution can be found using optimal solutions of subproblems.

Watch these animations from an ex-MIT TA for common problems:

Longest:

- Common subsequence (LCS)
- Increasing subsequence (LIS)
- Can be modified to maximum sum increasing subsequence.

- Edit distance
- Common substring
- Palindromic substring

Finally:

## Advanced Topics

It seems like these topics rarely come up, but you’ve done so much studying now, it’s interesting to go over anyway.

- 3SUM Problems.
- Subset sum
- Partition
- Min Window that contains all
- Minimum Spanning Tree
- Shortest Path
- Activity selection
- Closest pair of points
- Median of two sorted arrays

## Seriously?!?

Phew!

Yes, I really have ready every single link and topic above. I can’t honestly remember all of them, but a good chunk are familiar to me now.