# Introduction

Hi there, my name is Mahmoud (My LinkedIn) and I am a software engineer. Over the last 10 years, I interviewed at several companies (including Google, Facebook and Amazon) and conducted many interviews (mostly at Amazon). The following is the list I use to prepare for the coding portion of the technical interview.

# Methodology

Here is how I think one should approach a coding question:

- Think of all possible cases. Start with an obvious sample case then move to corner cases and finally tricky cases.
- Think of a brute force solution first then try to optimize.
- Think of runtime and space complexity.
- You can usually optimize using pre-computations and memorizing partial solutions.
- Once you have a candidate solution, run the algorithm on some sample cases.
- Write minimal pseudo code and run the sample cases through it.
- Implement the solution.

# Arrays

#### Facts:

- The middle of a sub-array defined by start and end indexes is: start + ((end – start) / 2).

#### Tips:

- When operating recursively on arrays use a helper method and pass the start and end indexes.
- When looking for 2 values in a sorted array that satisfy a condition, use two pointers (low and high) and handle duplicates.

#### Questions:

##### Easy:

##### Medium:

##### Hard:

# Linked Lists

#### Tips:

- Use two pointers to traverse the list if needed.
- Move pointers at different speeds.
- Move one pointer of two pointers a specific number of nodes ahead.

#### Questions:

##### Easy:

- Implement a Linked List data structure that supports these operations: Insert, Delete, Traverse, Search.
- Find middle
- Find out if Linked List is circular

##### Medium:

- Remove N-th node from the end
- Convert a Binary Tree into a Linked List
- Convert a Sorted Linked List to a Binary Search Tree.
- Reverse a Linked List
- LRU cache using a Linked List

##### Hard:

# Stack

#### Tips:

- Combining two data structures of one type can sometimes mimic the behavior of a different type. Think about organizing data in one data structure to mimic the organization of a different data structure.
- When using integers, you can store a flag (or even another integer) within the same integer.
- Use the stack as a temporary storage when evaluating expressions. It could either store integers if performing the calculations or the operators if performing a conversion.

#### Questions:

##### Easy:

- Implement a Stack data structure that supports these operations: Push, Pop, Peek.
- Reverse string using stack
- Implement Stack using two queues
- Min stack

##### Medium:

# Queue

#### Questions:

##### Easy:

- Implement a queue data structure that supports these operations: Enqueue, Dequeue, getFront.
- Implement Queue using two Stacks

##### Medium:

# Priority Queue

#### Facts:

- An abstract data type that allows additions of values in O(log(n)), access to the highest value in O(1) and remove of the highest value in O(log(n)).
- It is implemented using a max binary heap data structure. The heap itself is implemented using an array.

#### Questions:

##### Easy:

- Implement a Priority Queue data structure that supports the following operations: add, getHighestPriority(), removeHighestPriority().
- Kth largest element in an array

##### Medium:

# Binary Tree

#### Facts:

- DFS traversal consists of 3 steps: go left, go right and process node value. The order of the node value processing step determines whether it’s preorder, inorder or postorder.
- In preorder traversal, you add to the end of the list. In postorder travesal, you add to the beginning of the list.

#### Tips:

- Use 2 queues or stacks for level order traversals of a binary tree.

#### Questions:

##### Easy:

- Implement a Binary Tree data structure using pointers (then an array).
- Implement methods within the data structure that return the following: number of nodes, tree height and number of levels.
- Implement methods that check whether a tree is: full, complete and height-balanced.
- Implement DFS Traversals: preorder, inorder and postorder.
- Implement BFS both recursively and iteratively.
- Symmetric tree
- Print tree paths
- Path sum

##### Medium:

- Print tree level order traversal
- Lowest common ancestor
- ZigZag tree level traversal
- Reconstruct binary tree from preorder and inorder traversal
- Flatten binary tree to linked list

##### Hard:

# Binary Search Tree

#### Facts:

- Definition: for each given node, ALL the nodes to left are smaller and ALL the nodes to the right bigger.

#### Tips:

- When recursively building a tree split left and right processing. Do it recursively then assign it to the newly created node: N = new N(); N.left = processL(); N.right = processR();

#### Questions:

##### Easy:

- Implement a Binary Search Tree data structure that supports the following operations: insert, search and delete.
- Convert sorted array to binary search tree
- Lowest common ancestor

##### Medium:

- Validate binary search tree
- Kth smallest element

##### Hard:

- Construct binary search tree from preorder traversal

# Heap

#### Facts:

- When using an array representation of the heap, you insert at the end of the array then perform upheap. You delete then return the root (min or max) and replace it with the element at the end of the array then perform downheap.
- Disadvantages of heaps: O(n) for search, O(nlog(n)) for printing.
- Binomial offers O(1) amortized inserts but has O(log(n)) find-min
- Fibonacci heaps offers O(1) amortized inserts, find-min and decrease-key.
- Fibonacci heaps are used to implement priority queues.
- Heaps are better than binary search trees for implementing priority queues because they use less space (no pointers), are slightly faster (for inserts/deletes), and there are special heaps with better performance.

#### Questions:

##### Easy:

- Implement Min Heap data structure that supports the following operations: insert and deleteMin (try array implementation).
- Implement a priority queue using a min heap.
- What’s a binomial heap?
- What’s a Fibonacci heap?
- K-th largest element in a stream

##### Hard:

# Trie

#### Facts:

- Advantages: access running time is better than hash tables in the worst case. No need for a hash function or collision management. It can return stored items in alphabetical order. It supports prefix look-ups for string.
- Drawbacks: it’s slower than hash tables if data is accessed on disk. Some data is not meaningful in a trie (like floating points). It may require more space than a hash table because of one pointer per character instead of the whole string.
- Suffix tree of a string is a compressed trie of all suffixes of the string with an end of line marker.

#### Questions:

##### Easy:

- Implement a Trie data structure that support the following operations: insert, delete, search.
- What’s a suffix tree?

##### Medium:

##### Hard:

# B-tree

#### Facts:

- A B-tree is a structure for keys used to speed up search and sequential traversal.
- It is a multi-way search tree where each node with N keys has N+1 pointers to children.
- It packs several pointers in one node to avoid jumping between nodes (which translates to disk seeks).
- A B+ tree is a B-tree that holds data at the leaf nodes.
- B+ trees are used for databases and file systems.

#### Questions:

##### Medium:

- Describe how the following operations work in a B-tree: insert and search.

# Graphs

#### Facts:

- A tree with N nodes has N-1 edges (if seen as a graph).

#### Tips:

- Use BFS if the solution is close to the root of the search tree.
- Use BFS if the search tree is deep and solutions are rare.
- Use DFS to figure out whether a graph has a cycle.
- Use DFS if solutions are frequent but are deep in the search tree.
- Use DFS instead of BFS if the search tree is wide because BFS will require a lot of memory.

#### Questions:

##### Easy:

- Implement a Graph data structure using an adjacency matrix and an adjacency list.
- Implement both BFS and DFS on the Graph data structure.

##### Medium:

- Implement minimum spanning tree on the Graph data structure.
- Implement topological sort on the Graph data structure.
- Word search
- Course schedule
- Minimum height trees
- Is graph bipartite?

##### Hard:

# Hash Map

#### Facts:

- Associative arrays are an abstract data type that stores key-value associations. They can be implemented either with hash tables or search trees.
- Hash tables operations run in O(1) in the average case and O(n) in the worst case whereas search trees operations run in O(log(n)) in both the worst and average cases.
- There are two main techniques to handle collisions: separate chaining and open addressing. Separate chaining performance grows linearly (vs exponentially for open addressing) even when the load factor is bigger than 1. However, it’s slower than open addressing for small load factors because of the need to follow pointers. Open addressing tables generally use less memory and are easier to serialize.

#### Tips:

- The hash function should be: deterministic, uniform and has a defined range.
- Choose a hash function that results in a uniform distribution of values. In order to keep values within the array range, you can either use modulo or bitmask in case the size of array is a power of 2.

#### Questions:

##### Easy:

- Implement a Hash Table data structure and handle collisions.
- Implement an Associative Array data structure using a search tree.

##### Medium:

- Top k most frequent elements
- Top k frequent words
- Design Twitter
- Repeated DNA sequences
- Valid Sudoku
- Group anagrams
- Subarray sum equal k

# Sorting

#### Tips:

- Quick sort is preferred for arrays and merge sort is preferred for linked lists.
- The median of an unsorted array can be found using the Quick Sort logic by stopping the sorting process early.

#### Questions:

##### Easy:

- Implement bubble sort
- Implement insertion sort
- Implement merge sort

##### Medium:

- Implement quick sort
- Implement heap sort
- K-th largest element in an array
- Largest number
- Wiggle sort II
- Reorganize string

##### Hard:

# Dynamic Programming

#### Tips:

- When you have F(i, j) = Some logic around F(i – 1, j – 1), use regular nested loops (for i = 0 .. n and j = 0 .. n)
- When you have F(i, j) = Some logic around F(i + 1, j – 1), use a regular loop nested in a reversed loop (for i = n .. 0 and j = 0 .. n)

#### Questions:

##### Easy:

##### Medium:

- Word break
- Combination Sum
- Combination Sum II
- Unique binary search trees II
- Coin change
- Perfect squares
- Longest palindromic substring
- Palindromic substrings
- Longest increasing subsequence
- Maximal square
- Target sum
- Combination Sum IV
- Partition equal subset sum
- Range sum query 2D immutable