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.

- How To Prepare
- Algorithms You Gotta Know
- Personal & Project Questions
- Hardware Basics
- Unix Basics
- Intermediate Algorithms
- How to Solve a Problem
- Practice Problems
- More Resources

- Make sure you understand the basic algorithms in Algorithms You Gotta Know and can answer all of those questions
- Go over How to Solve a Problem
- If you can answer the questions in Algorithms You Gotta Know, do lots of practice problems
- If you want to understand those algorithms better, check out more_resources
- You should know the topics in Hardware Basics, Unix Basics, and Intermediate Algorithms, but they're less important

- 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.

- 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.

- 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)

- 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?

- 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).

- 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.

- 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.

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

- 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?

- 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?

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

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

- 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

- Make sure you clearly understand the question and clarify edge cases with your interviewer (eg. duplicates, bad input, wrong datatype input)
**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(n^{2}). We could do it quicker by hashing each element ... which will be O(n) time."- Explain your algorithm/solution to your interviewer before writing any code
- Once you and the interviewer have agreed on the algorithm, then you can start coding
- 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.)
- 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
- For a phone interview, practice writing coding solutions on a google doc
- For an in-person interview, practice writing coding solutions on a whiteboard or a piece of paper
- After you've written your code, choose a sample input and walk through the code, making sure it runs as expected

- 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

- Again, for lots of practice problems check out Cracking the Coding Interview

- If you want a better understanding of the basic algorithms, a great concise book is Problem Solving with Algorithms and Data Structures Using Python. It's a quick read that explains the need-to-know algorithms well and gives simple python code
- You can also find Problem Solving with Algorithms and Data Structures Using Python for free online
**The**textbook on algorithms is CLRS Introduction to Algorithms. It's big, but it covers everything and is a great reference book.

Questions, comments, feedback - prep@stripenight.com

© stripenight.com - This material may not be reproduced without permission