calvinfeng/study-guide

This is an outline of important algorithms and data structures for software engineers

Study Guide for Technical Interviews

By now it should be week 14 for those who are reading this guide. This study guide outlines the major data structures and algorithms needed to succeed in technical interviews. The official guide was first written by Haseeb Qureshi, titled How To Break Into The Tech Industry - a Guide to Job Hunting and Interviews on his personal blog site. This guide focuses on implementation details of the materials. However, please read Haseeb's guide at least once and follow his advice.

Key Resources

• Cracking the Coding Interview 6th Edition
• Effective JavaScript
• Coursera - Princeton Lectures on Algorithms (1 & 2)
• Algorithm Design Manual

Optional Resources (Podcast & Blog)

• Software Engineering Daily
• The Bike Shed
• Hacker News
• High Scalability

System Designs

• Scalability Lecture & More
• Real Life Architectures
• Interview Tips

Data Structures

• Stack & Queue
• LinkedList
• HashMap
• LRU Cache (Using LinkedList & HashMap)
• Dynamic Array (Ring Buffer)
• Binary Heap (Without decrease-key)
• Binary Search Tree
  • Optional: AVL, 2-3 Tree, Red-Black Tree
• Directed & Undirected Graphs
• Tries
• Suffix Tree

Algorithms

Search

• Binary Search
• Breadth-first Search
• Depth-first Search

Sorting

• Quick Sort (Partition Subroutine)
• Merge Sort
• Radix Sort
• Heap Sort

Graphs

• Tree Traversals (Pre-order, In-order, Post-order)
• Objected-oriented Adjacency List
• Adjacency Matrix
• Topological Sort (Kahn's Algorithm)
• Topological Sort (Tarjan's Algorithm)
• Dijkstra's Algorithm (Use PriorityQueue without decrease-key)

Dynamic Programming & Recursion

• Longest Common Subsequence(Use matrices)
• Fibonacci Sequence
• Knapsack Problem (work in progress)

Timeline

Coursera might have taken down the algorithm lectures. Use this link https://www.youtube.com/user/Rabynovych/playlists

Week 1

Topics

• Dynamic Array or ArrayList(Java)
• Stack and Queue
• StackQueue
• LinkedList
• HashMap
• LRU Cache
• Binary Search
• Quick Sort
• Merge Sort
• Coursera - Algorithms Part 1
  • Stacks & Queues
  • Elementary Sorts
  • Merge Sort
  • Quick Sort
  • Hash Functions & Linear Probing

Week 2

Topics

• Binary Heap
• Heap Sort
• Binary Search Tree
• Graph, Adjacency List, and Adjacency Matrix
• Breadth-first Search
• Depth-first Search
• Tree Traversals
• Topological Sort
• Coursera - Algorithms Part 1
  • Binary Heaps
  • Heap Sort
  • Binary Search Tree
  • 2-3 Search Tree
  • Red-Black Tree

Week 3

Topics

• Dijkstra's Algorithm
• Suffix Tree
• Trie or Prefix Tree
• Radix
• Dynamic Programming
• Manacher's Algorithm
• Finite State Automata
• Bit Manipulation
• Coursera - Algorithms Part 2
  • Graphs (undirected)
  • Connected Components
  • Digraphs (directed)
  • Radix Sort
  • R-way Tries