# Coding Interview Prep

This review sheet is an outline of the core concepts common to most software engineering interviews. It specifically does not cover some concepts which are not commonly asked about (eg. bitwise operators). This is designed to help you spend your preparation time most effectively. For more topics, explanations, and questions see more resources below.

Click on questions to see brief answers. Click here to toggle all the answers.

## Algorithms You Gotta Know

The questions here are not questions you should expect to get an interview. They are designed to check that you understand the algorithms needed to answer most interview questions. You should feel very comfortable answering all these questions before interviewing.

### Binary Search

• When can you use binary search? Binary search can be used on sorted arrays.
• What's its run time? Binary search can find elements in O(logn) by cutting the problem in half on each step.

### Sorting

• What's the generally accepted runtime of sorting an array? Sorting an array generally takes O(nlogn).
• Why is that the limit of how quickly we can sort? Comparison sorts are mathematically bound by O(nlogn), because you would need to do O(nlogn) comparisons to determine the order transitively.
• When can we sort quicker than that? If we are sorting numbers (or something easily converted to numbers) we can use count sort or Radix sort to sort in O(n) or linear time.

#### Merge Sort

• How does merge sort work? Merge sort recursively splits the input array in half into two arrays, until each array is a size of one. It then recombines each pair of sorted arrays into one sorted array. There are O(logn) splits, and since it takes O(n) to combine sorted arrays, the total runtime is O(nlogn).
• What's the best case run time? O(nlogn), even if the array is already sorted
• What's the worst case run time? O(nlogn)
• How long does merge sort take to sort an already sorted list? O(nlogn)

#### Your Favorite Sorting Algorithm - Literally choose a favorite sorting algorithm before your interview

• How does it work?
• What's the best case run time?
• What's the worst case run time?
• Why is it your favorite? You should have an answer for this!
• Explain this sorting algorithm to your mother
• How long does it take to sort an array that's backwards?

### Hashing

• What is a hash function? A hash function is simply a function that converts an input to a number.
• What's a hash set? A hash map? A hash table? The implementation of hash sets, hash maps, etc, can get complicated because of collisions. A hash set is a data structure that uses hashing to quickly check if an element is in a set. Naively, it works by storing elements in an array at the index of their hashed value. Lookups are O(1) by hashing an element and checking that index in the array. Hash maps and tables are similar to hashs sets, but they also keep a pointer to an associated value.
• What are hash collisions? Hash collisions are when two elements hash to the same number.
• How are hash collisions resolved? There are lots of techniques to solving hash collisions: change your hash function, use a bigger array, chaining, nested hash maps
• What's the accepted run time for looking something up in a hash set? Hashing generally takes O(1) or constant time. But, sometimes the runtime of the hash function is non-trivial and is O(k) where k is the size of the element being hashed. It's best to check with your interviewer if you can assume hashing is O(1) or O(k).

### Graphs & Search

• What's BFS? Bread first search searches a tree one level at a time. ie. It uses a queue to visit new nodes.
• What's DFS? Depth first search searches a tree by going as deep as possible before backtracking. ie. It uses a stack to visit new nodes.
• Write a function that takes the urls of two wikipedia pages and returns the fewest number of clicks it takes to get from the first article to the second. Starting at the first article, use BFS to follow links. Return the depth once you get to the second article.

### Data Structures

• What order do elements enter and leave a queue? First in, first out, like the line to get on a rollerqueuester
• What order do elements enter and leave a stack? First in, last out, like a stack of pancakes
• What's the height of a balanced binary tree with n elements? The height of a balanced BST with n elements is log n.

## Personal/Project Questions

You should prepare an answer to each of these questions. Even if you don't get the exact question, you can use the same answer/story/problem.

• What's your favorite project you've worked on?
• What specifically did you do on that project?
• What's a difficult bug you fixed? How did you debug it?
• What's a new technology you've been wanting to try out?
• What'd you do at your last job?
• Tell me about a time you didn't agree with your manager

## Hardware Basics

### Memory

• What's the difference between memory and storage?
• How much memory can you expect on a personal computer? On a server?
• Why is the amount of memory a computer has important?
• What's difficult about sorting a 20 gigabyte file of numbers?

### Networking

• Is it quicker to sort 1000 numbers on one computer or to split it up on to two computers?
• Why?
• Is it quicker to email 100 HD movies from Boston to NY or to rent a U-Haul and drive with DVDs?

## Unix Basics

### Grep

• Find all files in the log directory that contain phone numbers. grep -r "\d{10}" /var/log

### Processes

• Kill the process that's currently listening on port 80. netstat -tulpn | grep 80; kill <pid>

## Intermediate Algorithms to Know

• Linked Lists (implement a LL, reverse a LL)
• Map-Reduce (just a basic understanding)
• Binary Search Trees
• Heaps, Min Heaps, Max Heaps, Heapify
• Quick Sort, Quick Select
• Tree Traversals: in-order, post-order, pre-order

## How to Solve a Problem

1. Make sure you clearly understand the question and clarify edge cases with your interviewer (eg. duplicates, bad input, wrong datatype input)
2. Start by giving a naive solution and then improving it. Do not start thinking of the optimal solution. Start by telling you interviewer a naive solution, eg. "We could check every combination which would take O(n2). We could do it quicker by hashing each element ... which will be O(n) time."
3. Explain your algorithm/solution to your interviewer before writing any code
4. Once you and the interviewer have agreed on the algorithm, then you can start coding
5. Most interviewers don't care what language you work in. Use what you're most comfortable with. (But if it's on your resume, it's fair game.)
6. Feel free to separate your solution into multiple functions to avoid repetition or make the code more legible, eg. cartesianToPolar(x,y) and give your functions and variables meaningful names
7. For a phone interview, practice writing coding solutions on a google doc
8. For an in-person interview, practice writing coding solutions on a whiteboard or a piece of paper
9. After you've written your code, choose a sample input and walk through the code, making sure it runs as expected

## Practice Problems

Find other sources of more problems below

### Basic problems

You should be able to come up with a solution to these problems within 5 minutes and write a working solution in another 10 minutes.
• Combine two sorted lists into one sorted list. Like the merge step of merge sort, we put a pointer at the beginning of each list and choose the smallest element each time. This takes O(n) time.
• Find if two elements in a list add to 100
• Find if array A is a subset of array B
• Write a method that return the 10 largest elements in an array
• Write a function that reverses the letters in each word in a sentence. Eg. "Cool beans!" -> "Looc snaeb!"
How should punctuation be handled? What about newlines? What about two spaces in a row?
• Write a function that reverses the order of the words in a sentence. Eg. "Cool beans!" -> "Beans cool!"
• Write a function that takes two wikipedia pages and returns the fewest number of clicks it takes to get from the first article to the second

## More Resources

If you want a lot of practice problems and more in-depth preparation, the best book is Cracking the Coding Interview. It covers everything including resumes, what to wear, etc.

### Learning Algorithms

Questions, comments, feedback - prep@stripenight.com