Introduction

I used to have some cheat sheets around to prepare myself for any incoming technical interview, so I thought it would be a better idea to gather them here for a quicker access. It could help someone else to prepare quickly as well!

Important Notes:

  • This work will be always an in-progress work, I will keep updating this guide as I find any relevant materials.
  • The order might not be so relevant. Pick and choose what you need to review.

Long Term Preparation Kit

If I can afford only one book to prepare for my technical interviews, I will definitely buy the Cracking the Coding Interview book by Gayle McDowell, 6th edition. That’s it, good luck!


Short Term Preparation Kit

If I don’t have a long time to prepare, or if I already went through the long term perpetrate kit before, and I want a quick reference, I would follow this kit. Multiple resources and steps are already summarizing some topics from the Cracking the Coding Interview book I referred above, slightly updated by me.

Video Kit: If I have a little more time, I would go through this playlist first, at least once.


Keep in Mind

Keep these data structures, algorithms, and concepts in mind:

  • Data Structures:

    1. Linked Lists
    2. Trees, Tries, and Graphs
    3. Stacks and Queues
    4. Heaps
    5. Vectors and Array Lists
    6. » Hash Tables « (Dictionaries, Maps, …)
  • Algorithms:

    1. Breadth-First Search
    2. Depth-First Search
    3. Binary Search
    4. Merge Sort
    5. Quick Sort
  • Concepts:

    1. Memory (Stacks VS Heaps)
    2. Recursion
    3. Dynamic Programming
    4. Big O Time & Space
    5. Bit Manipulation

7 Steps to Solve Algorithm Problems

  1. Listen (& ask!).

  2. Pick an example which is:

    1. Big (enough)
    2. Is not a special case
  3. Use a brute-force approach (at least to think of the problem).

  4. Optimize your solution.

  5. Walk through your algorithm and know exactly what you are going to do before starting to code, think of needed variables and data structures for instance.

  6. Code! Make sure to have a:

    1. (Consistent) code style: use descriptive variable names, and you may refer for them with abbreviations later.
    2. Modular code: before coding, not after.
  7. TEST!

    1. Don’t use your original example.
    2. Analyze (line by line).
    3. Test with a:
      1. Small test case.
      2. Edge test case.
      3. Big test case.
    4. Test your code, not your algorithm!
    5. Think before fixing bugs (so that you won’t introduce new bugs, or make the code missy or hard).
    6. Don’t panic, you might not solve it from the first round.

3 Algorithm Strategies

  1. B.U.D.
    • Go through your brute-force or best solution right now and look for:
      1. Bottlenecks
      2. Unnecessary Work
      3. Duplicated Work
  2. Space & Time Tradeoffs
    • Always have hash tables at the top of your mind
  3. D.I.Y. (Do it Yourself)
    • Try to solve it in your mind, and write a code that behaves the same.
    • Use a large and generic example.
    • Reverse engineering your thoughts!

Bit Manipulation in a Nutshell

  • Get the ith bit of x –> x & (1 << i)
  • Set the ith bit of x –> x | (1 << i)
  • Clear the ith bit of x –> x & ~(1 << i)

Linked Lists VS Arrays

Case # Operation / Data Structure Arrays Linked Lists
1 get (retrieve) Constant Linear
2 insert and delete (@ start) Linear Constant
3 insert and delete (@ end) Constant Linear

Clarifications:

  • Case #1

    • An array will get any item by index in a constant O(1) time.
    • A linked list need to traverse and count nodes till reaching the needed item and return it, so that it needs a linear O(n) time.
  • Case #2

    • An array will access the needed index in a constant O(1) time and add or delete it, but it needs a linear O(n) to shift all the old nodes to right in the case of adding and to left in the case of removing.
    • A linked list need to traverse a few nodes (since we will add or delete from the start), add or delete the new node and update the pointers, so it needs a constant O(1) time.
  • Case #3

    • An array will access the needed index in a constant O(1) time and add or delete it, and since we are adding or deleting from the end, it needs a constant O(1) to shift the few old nodes to right in the case of adding and to left in the case of removing.
    • A linked list need to traverse almost all nodes (since we will add or delete from the end), add or delete the new node and update the pointers, so it needs a linear O(n) time.

Sort Algorithms

A great website to visualize and understand the different sorting algorithms is visualgo.net .

Algorithm Average Time Complexity Worst Time Complexity Worst Space Complexity Keys / Notes Stability
Best Time:
Quick Sort O(n lg n) O(n^2) O(lg n) Pivot could make things missy Not stable
Merge Sort O(n lg n) O(n lg n) O(n) Divide and conquer Stable
Heap Sort O(n lg n) O(n lg n) O(1) in-place Heapsort is significantly slower than Quicksort and Merge Sort, so Heapsort is less commonly encountered in practice. Not stable
Best Space:
Bubble Sort O(n^2) O(n^2) O(1) in-place Compare every pair and swap if they are not in order Stable
Insertion Sort O(n^2) O(n^2) O(1) in-place Compare every item with all previous items, if a smaller (a larger) item is found, move all items in between to right and insert that item in the correct place. Stable
Selection Sort O(n^2) O(n^2) O(1) in-place Find the smallest (largest) item and add it to the end of the sorted part. Usually worse than insertion sort. The first part is always sorted. Not stable
  • Lower bound for sorting algorithms is O(n lg n).
  • A sorting algorithm is stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted. Informally, stability means that equivalent elements retain their relative positions, after sorting.
  • Read more about different sorting algorithms in HappyCoders.eu .

Search Algorithms

Algorithm Average / Worst Time Complexity Average / Worst Space Complexity Why to use? Notes
Binary Search O(lg n) O(lg n) Best time Works with sorted data only. Extra space is needed for the call stack in the recursive solution.
Linear Search O(n) O(1) in-place Best space Works with any (sorted or unsorted) data.

Trees

Tree Traversals

  • Pre order: root –> left –> right
  • In order: left –> root –> right
  • Post order: left –> right –> root

Binary Trees

Types

  • A binary tree is a tree where every node has a max of 2 children.

  • A perfect binary tree is a binary tree where all levels are full (every node has 2 children).

  • A complete binary tree is a binary tree where all levels are full (every node has 2 children) except (possibly) the last level.

    • Every perfect tree is a complete tree.
  • A balanced binary tree is a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

  • A full binary tree is a binary tree in which every node has either 0 or 2 children.

  • A binary search tree is a binary tree whose internal nodes each store a key greater than all the keys in the node’s left subtree and less than those in its right subtree.

    • An in-order traversal for a binary search tree will give us ascending sorted data.
    • A binary search tree is an ideal way to go with the hierarchical way of storing data.

Useful Computations

In any perfect binary tree:

  • Number of nodes n = 2^(h-1). Where h is the tree height.
  • Height h = lg (n+1). Where n is the number of nodes.
  • Number of the nodes in the last level = number of nodes in all other levels + 1.

Graphs

  • A graph organizes items in an interconnected network.
  • A graph consist of multiple nodes and edges between them.

Classifications

A graph could be:

  • Directed or Undirected
    • The edge is bidirectional in an undirected graph, but has a direction in a directed graph.
  • Cyclic or Acyclic
    • A graph is cyclic if you can start from any node and come back to it in a closed path; acyclic otherwise.
  • Weighted or Unweighted
    • The edge has a certain weight (importance / degree) in a weighted graph. All edges have the same weight in an unweighted graph.

Representations

A graph could be represented with:

  • An edge list
    • A list of all the edges in the graph.
    • Every edge represented by the 2 nodes it connects.
    • An unconnected node (a node with no edges) will not be represented with this form.
  • An adjacency list
    • A list where index represents the node, and the value at that index is a list of the node’s neighbors.
    • Another form of this representation is to use a map (a dictionary) where the key is the node, and the value is a list of neighbors.
  • An adjacency matrix
    • A matrix of 0s and 1s indicating whether a node x connects to node y where 0 means unconnected and 1 means connected.

SOLID Design Principles

Dependency Inversion

  • High level module should not depend on a low level module.
  • Both should depend on abstraction.
  • Abstraction should not depend on details.
  • Details should depend on abstraction.
  • A code example .

Interface Segregation

  • You should add the minimum amount of methods/code to each interface.
  • At no point, the client should need to implement a method they do not need at all.
  • A code example .

Liskov Substitution

  • You should be able to substitute a sub-class for a base class without breaking the logic.
  • A code example .

Open-Closed

  • Your code should be:
    • Open for extension.
    • Closed for modifications.
  • A code example .

Separation of Concerns (Single Responsibility)

  • Every module, class or function should have responsibility over a single part of that program’s functionality, and it should encapsulate that part.
  • A code example .

Sources and References