Coding Interview University
I originally created this as a short todo list of study topics for becoming a software engineer, but it grew to the large list you see today. After going through this study plan, I got hired as a Software Development Engineer at Amazon! You probably won’t have to study as much as I did. Anyway, everything you need is here.
The items listed here will prepare you well for in an interview at just about any software company, including the giants: Amazon, Facebook, Google or Microsoft.
Best of luck to you!
Translations:  中文版本  Tiếng Việt  Vietnamese  translations in progress:  Español  हिन्दी  עברית  Bahasa Indonesia  Arabic  Turkish  French  Russian  Ukrainian  Brazilian Portuguese  Korean  Telugu  Polish  German  Urdu  Thai  Greek  Italian
What is it?
This is my multimonth study plan for going from web developer (selftaught, no CS degree) to software engineer for a large company.
This is meant for new software engineers or those switching from software/web development to software engineering (where computer science knowledge is required). If you have many years of experience and are claiming many years of software engineering experience, expect a harder interview.
If you have many years of software/web development experience, note that large software companies like Google, Amazon, Facebook and Microsoft view software engineering as different from software/web development, and they require computer science knowledge.
If you want to be a reliability engineer or systems engineer, study more from the optional list (networking, security).
Table of Contents
 What is it?
 Why use it?
 How to use it
 Don’t feel you aren’t smart enough
 About Video Resources
 Interview Process & General Interview Prep
 Pick One Language for the Interview
 Book List
 Before you Get Started
 What you Won’t See Covered
 Prerequisite Knowledge
 The Daily Plan
 Algorithmic complexity / BigO / Asymptotic analysis
 Data Structures
 More Knowledge
 Trees
 Trees  Notes & Background
 Binary search trees: BSTs
 Heap / Priority Queue / Binary Heap
 balanced search trees (general concept, not details)
 traversals: preorder, inorder, postorder, BFS, DFS
 Sorting
 selection
 insertion
 heapsort
 quicksort
 merge sort
 Graphs
 directed
 undirected
 adjacency matrix
 adjacency list
 traversals: BFS, DFS
 Even More Knowledge
 Recursion
 Dynamic Programming
 ObjectOriented Programming
 Design Patterns
 Combinatorics (n choose k) & Probability
 NP, NPComplete and Approximation Algorithms
 Caches
 Processes and Threads
 Papers
 Testing
 Scheduling
 Implement system routines
 String searching & manipulations
 Tries
 Floating Point Numbers
 Unicode
 Endianness
 Networking
 System Design, Scalability, Data Handling (if you have 4+ years experience)
 Final Review
 Coding Question Practice
 Coding exercises/challenges
 Once you’re closer to the interview
 Your Resume
 Be thinking of for when the interview comes
 Have questions for the interviewer
 Once You’ve Got The Job
————— Everything below this point is optional —————
 Additional Books
 Additional Learning
 Compilers
 Emacs and vi(m)
 Unix command line tools
 Information theory
 Parity & Hamming Code
 Entropy
 Cryptography
 Compression
 Computer Security
 Garbage collection
 Parallel Programming
 Messaging, Serialization, and Queueing Systems
 A*
 Fast Fourier Transform
 Bloom Filter
 HyperLogLog
 LocalitySensitive Hashing
 van Emde Boas Trees
 Augmented Data Structures
 Nary (Kary, Mary) trees
 Balanced search trees
 AVL trees
 Splay trees
 Red/black trees
 23 search trees
 234 Trees (aka 24 trees)
 Nary (Kary, Mary) trees
 BTrees
 kD Trees
 Skip lists
 Network Flows
 Disjoint Sets & Union Find
 Math for Fast Processing
 Treap
 Linear Programming
 Geometry, Convex hull
 Discrete math
 Machine Learning
 Additional Detail on Some Subjects
 Video Series
 Computer Science Courses
Why use it?
When I started this project, I didn’t know a stack from a heap, didn’t know BigO anything, anything about trees, or how to traverse a graph. If I had to code a sorting algorithm, I can tell ya it wouldn’t have been very good. Every data structure I’ve ever used was built into the language, and I didn’t know how they worked under the hood at all. I’ve never had to manage memory unless a process I was running would give an “out of memory” error, and then I’d have to find a workaround. I’ve used a few multidimensional arrays in my life and thousands of associative arrays, but I’ve never created data structures from scratch.
It’s a long plan. It may take you months. If you are familiar with a lot of this already it will take you a lot less time.
How to use it
Everything below is an outline, and you should tackle the items in order from top to bottom.
I’m using Github’s special markdown flavor, including tasks lists to check progress.
Create a new branch so you can check items like this, just put an x in the brackets: [x]
Fork a branch and follow the commands below
git checkout b progress
git remote add jwasham https://github.com/jwasham/codinginterviewuniversity
git fetch all
Mark all boxes with X after you completed your changes
git add .
git commit m "Marked x"
git rebase jwasham/master
git push force
More about Githubflavored markdown
Don’t feel you aren’t smart enough
 Successful software engineers are smart, but many have an insecurity that they aren’t smart enough.
 The myth of the Genius Programmer
 It’s Dangerous to Go Alone: Battling the Invisible Monsters in Tech
About Video Resources
Some videos are available only by enrolling in a Coursera, EdX, or Lynda.com class. These are called MOOCs. Sometimes the classes are not in session so you have to wait a couple of months, so you have no access. Lynda.com courses are not free.
I'd appreciate your help to add free and alwaysavailable public sources, such as YouTube videos to accompany the online course videos.
I like using university lectures.
Interview Process & General Interview Prep
[ ] Whiteboarding
[ ] Cracking The Coding Interview Set 1:
[ ] How to Get a Job at the Big 4:
[ ] Prep Course:
 [ ] Software Engineer Interview Unleashed (paid course):
 Learn how to make yourself ready for software engineer interviews from a former Google interviewer.
 [ ] Python for Data Structures, Algorithms, and Interviews! (paid course):
 A Python centric interview prep course which covers data structures, algorithms, mock interviews and much more.
 [ ] Software Engineer Interview Unleashed (paid course):
Pick One Language for the Interview
You can use a language you are comfortable in to do the coding part of the interview, but for large companies, these are solid choices:
 C++
 Java
 Python
You could also use these, but read around first. There may be caveats:
 JavaScript
 Ruby
You need to be very comfortable in the language and be knowledgeable.
Read more about choices:  http://www.bytebybyte.com/choosetherightlanguageforyourcodinginterview/  http://blog.codingforinterviews.com/bestprogramminglanguagejobs/
You’ll see some C, C++, and Python learning included below, because I’m learning. There are a few books involved, see the bottom.
Book List
This is a shorter list than what I used. This is abbreviated to save you time.
Interview Prep
 [ ] Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition
 answers in C++ and Java
 this is a good warmup for Cracking the Coding Interview
 not too difficult, most problems may be easier than what you’ll see in an interview (from what I’ve read)
 [ ] Cracking the Coding Interview, 6th Edition
 answers in Java
If you have tons of extra time:
 [ ] Elements of Programming Interviews (C++ version)
 [ ] Elements of Programming Interviews (Java version)
Computer Architecture
If short on time:
 [ ] Write Great Code: Volume 1: Understanding the Machine
 The book was published in 2004, and is somewhat outdated, but it’s a terrific resource for understanding a computer in brief.
 The author invented HLA, so take mentions and examples in HLA with a grain of salt. Not widely used, but decent examples of what assembly looks like.
 These chapters are worth the read to give you a nice foundation:
 Chapter 2  Numeric Representation
 Chapter 3  Binary Arithmetic and Bit Operations
 Chapter 4  FloatingPoint Representation
 Chapter 5  Character Representation
 Chapter 6  Memory Organization and Access
 Chapter 7  Composite Data Types and Memory Objects
 Chapter 9  CPU Architecture
 Chapter 10  Instruction Set Architecture
 Chapter 11  Memory Architecture and Organization
If you have more time (I want this book):
 [ ] Computer Architecture, Fifth Edition: A Quantitative Approach
 For a richer, more uptodate (2011), but longer treatment
Language Specific
You need to choose a language for the interview (see above). Here are my recommendations by language. I don’t have resources for all languages. I welcome additions.
If you read though one of these, you should have all the data structures and algorithms knowledge you’ll need to start doing coding problems. You can skip all the video lectures in this project, unless you’d like a review.
Additional languagespecific resources here.
C++
I haven’t read these two, but they are highly rated and written by Sedgewick. He’s awesome.
 [ ] Algorithms in C++, Parts 14: Fundamentals, Data Structure, Sorting, Searching
 [ ] Algorithms in C++ Part 5: Graph Algorithms
If you have a better recommendation for C++, please let me know. Looking for a comprehensive resource.
Java
 [ ] Algorithms (Sedgewick and Wayne)
 videos with book content (and Sedgewick!):
OR:
 [ ] Data Structures and Algorithms in Java
 by Goodrich, Tamassia, Goldwasser
 used as optional text for CS intro course at UC Berkeley
 see my book report on the Python version below. This book covers the same topics.
Python
 [ ] Data Structures and Algorithms in Python
 by Goodrich, Tamassia, Goldwasser
 I loved this book. It covered everything and more.
 Pythonic code
 my glowing book report: https://startupnextdoor.com/bookreportdatastructuresandalgorithmsinpython/
Optional Books
Some people recommend these, but I think it’s going overboard, unless you have many years of software engineering experience and expect a much harder interview:
[ ] Algorithm Design Manual (Skiena)
 As a review and problem recognition
 The algorithm catalog portion is well beyond the scope of difficulty you’ll get in an interview.
 This book has 2 parts:
 class textbook on data structures and algorithms
 pros:
 is a good review as any algorithms textbook would be
 nice stories from his experiences solving problems in industry and academia
 code examples in C
 cons:
 can be as dense or impenetrable as CLRS, and in some cases, CLRS may be a better alternative for some subjects
 chapters 7, 8, 9 can be painful to try to follow, as some items are not explained well or require more brain than I have
 don’t get me wrong: I like Skiena, his teaching style, and mannerisms, but I may not be Stony Brook material.
 pros:
 algorithm catalog:
 this is the real reason you buy this book.
 about to get to this part. Will update here once I’ve made my way through it.
 class textbook on data structures and algorithms
 Can rent it on kindle
 Half.com is a great resource for textbooks at good prices.
 Answers:
 Errata
[ ] Introduction to Algorithms
 Important: Reading this book will only have limited value. This book is a great review of algorithms and data structures, but won’t teach you how to write good code. You have to be able to code a decent solution efficiently.
 Half.com is a great resource for textbooks at good prices.
 aka CLR, sometimes CLRS, because Stein was late to the game

 The first couple of chapters present clever solutions to programming problems (some very old using data tape) but that is just an intro. This a guidebook on program design and architecture, much like Code Complete, but much shorter.
“Algorithms and Programming: Problems and Solutions” by Shen A fine book, but after working through problems on several pages I got frustrated with the Pascal, do while loops, 1indexed arrays, and unclear postcondition satisfaction results.
 Would rather spend time on coding problems from another book or online coding problems.
Before you Get Started
This list grew over many months, and yes, it kind of got out of hand.
Here are some mistakes I made so you’ll have a better experience.
1. You Won’t Remember it All
I watched hours of videos and took copious notes, and months later there was much I didn’t remember. I spent 3 days going through my notes and making flashcards so I could review.
Read please so you won’t make my mistakes:
Retaining Computer Science Knowledge
2. Use Flashcards
To solve the problem, I made a little flashcards site where I could add flashcards of 2 types: general and code. Each card has different formatting.
I made a mobilefirst website so I could review on my phone and tablet, wherever I am.
Make your own for free:
 Flashcards site repo
 My flash cards database (old  1200 cards):
 My flash cards database (new  1800 cards):
Keep in mind I went overboard and have cards covering everything from assembly language and Python trivia to machine learning and statistics. It’s way too much for what’s required.
Note on flashcards: The first time you recognize you know the answer, don’t mark it as known. You have to see the same card and answer it several times correctly before you really know it. Repetition will put that knowledge deeper in your brain.
An alternative to using my flashcard site is Anki, which has been recommended to me numerous times. It uses a repetition system to help you remember. It’s userfriendly, available on all platforms and has a cloud sync system. It costs $25 on iOS but is free on other platforms.
My flashcard database in Anki format: https://ankiweb.net/shared/info/25173560 (thanks @xiewenya)
3. Review, review, review
I keep a set of cheat sheets on ASCII, OSI stack, BigO notations, and more. I study them when I have some spare time.
Take a break from programming problems for a half hour and go through your flashcards.
4. Focus
There are a lot of distractions that can take up valuable time. Focus and concentration are hard.
What you won’t see covered
These are prevalent technologies but not part of this study plan:
 SQL
 Javascript
 HTML, CSS, and other frontend technologies
The Daily Plan
Some subjects take one day, and some will take multiple days. Some are just learning with nothing to implement.
Each day I take one subject from the list below, watch videos about that subject, and write an implementation in:  C  using structs and functions that take a struct * and something else as args.  C++  without using builtin types  C++  using builtin types, like STL’s std::list for a linked list  Python  using builtin types (to keep practicing Python)  and write tests to ensure I’m doing it right, sometimes just using simple assert() statements  You may do Java or something else, this is just my thing.
You don’t need all these. You need only one language for the interview.
Why code in all of these?  Practice, practice, practice, until I’m sick of it, and can do it with no problem (some have many edge cases and bookkeeping details to remember)  Work within the raw constraints (allocating/freeing memory without help of garbage collection (except Python))  Make use of builtin types so I have experience using the builtin tools for realworld use (not going to write my own linked list implementation in production)
I may not have time to do all of these for every subject, but I’ll try.
You can see my code here:  C  C++  Python
You don’t need to memorize the guts of every algorithm.
Write code on a whiteboard or paper, not a computer. Test with some sample inputs. Then test it out on a computer.
Prerequisite Knowledge
[ ] Learn C
 C is everywhere. You’ll see examples in books, lectures, videos, everywhere while you’re studying.
 [ ] C Programming Language, Vol 2
 This is a short book, but it will give you a great handle on the C language and if you practice it a little you’ll quickly get proficient. Understanding C helps you understand how programs and memory work.
 answers to questions
[ ] How computers process a program:
Algorithmic complexity / BigO / Asymptotic analysis
nothing to implement
[ ] Big O Notation (and Omega and Theta)  best mathematical explanation (video)
[ ] Skiena:
[ ] TopCoder (includes recurrence relations and master theorem):
[ ] Cheat sheet
If some of the lectures are too mathy, you can jump down to the bottom and watch the discrete mathematics videos to get the background knowledge.
Data Structures

Arrays
 Implement an automatically resizing vector.
 [ ] Description:
 [ ] Implement a vector (mutable array with automatic resizing):
 [ ] Practice coding using arrays and pointers, and pointer math to jump to an index instead of using indexing.
 [ ] new raw data array with allocated memory
 can allocate int array under the hood, just not use its features
 start with 16, or if starting number is greater, use power of 2  16, 32, 64, 128
 [ ] size()  number of items
 [ ] capacity()  number of items it can hold
 [ ] is_empty()
 [ ] at(index)  returns item at given index, blows up if index out of bounds
 [ ] push(item)
 [ ] insert(index, item)  inserts item at index, shifts that index’s value and trailing elements to the right
 [ ] prepend(item)  can use insert above at index 0
 [ ] pop()  remove from end, return value
 [ ] delete(index)  delete item at index, shifting all trailing elements left
 [ ] remove(item)  looks for value and removes index holding it (even if in multiple places)
 [ ] find(item)  looks for value and returns first index with that value, 1 if not found
 [ ] resize(new_capacity) // private function
 when you reach capacity, resize to double the size
 when popping an item, if size is ^{1}⁄_{4} of capacity, resize to half
 [ ] Time
 O(1) to add/remove at end (amortized for allocations for more space), index, or update
 O(n) to insert/remove elsewhere
 [ ] Space
 contiguous in memory, so proximity helps performance
 space needed = (array capacity, which is >= n) * size of item, but even if 2n, still O(n)

Linked Lists
 [ ] Description:
 [ ] C Code (video)  not the whole video, just portions about Node struct and memory allocation.
 [ ] Linked List vs Arrays:
 [ ] why you should avoid linked lists (video)
 [ ] Gotcha: you need pointer to pointer knowledge: (for when you pass a pointer to a function that may change the address where that pointer points) This page is just to get a grasp on ptr to ptr. I don’t recommend this list traversal style. Readability and maintainability suffer due to cleverness.
 [ ] implement (I did with tail pointer & without):
 [ ] size()  returns number of data elements in list
 [ ] empty()  bool returns true if empty
 [ ] value_at(index)  returns the value of the nth item (starting at 0 for first)
 [ ] push_front(value)  adds an item to the front of the list
 [ ] pop_front()  remove front item and return its value
 [ ] push_back(value)  adds an item at the end
 [ ] pop_back()  removes end item and returns its value
 [ ] front()  get value of front item
 [ ] back()  get value of end item
 [ ] insert(index, value)  insert value at index, so current item at that index is pointed to by new item at index
 [ ] erase(index)  removes node at given index
 [ ] value_n_from_end(n)  returns the value of the node at nth position from the end of the list
 [ ] reverse()  reverses the list
 [ ] remove_value(value)  removes the first item in the list with this value
 [ ] Doublylinked List
 Description (video)
 No need to implement

Stack
 [ ] Stacks (video)
 [ ] Using Stacks LastIn FirstOut (video)
 [ ] Will not implement. Implementing with array is trivial.

Queue
 [ ] Using Queues FirstIn FirstOut(video)
 [ ] Queue (video)
 [ ] Circular buffer/FIFO
 [ ] Priority Queues (video)
 [ ] Implement using linkedlist, with tail pointer:
 enqueue(value)  adds value at position at tail
 dequeue()  returns value and removes least recently added element (front)
 empty()
 [ ] Implement using fixedsized array:
 enqueue(value)  adds item at end of available storage
 dequeue()  returns value and removes least recently added element
 empty()
 full()
 [ ] Cost:
 a bad implementation using linked list where you enqueue at head and dequeue at tail would be O(n) because you’d need the next to last element, causing a full traversal each dequeue
 enqueue: O(1) (amortized, linked list and array [probing])
 dequeue: O(1) (linked list and array)
 empty: O(1) (linked list and array)

Hash table
[ ] Videos:
[ ] Online Courses:
 [ ] Understanding Hash Functions (video)
 [ ] Using Hash Tables (video)
 [ ] Supporting Hashing (video)
 [ ] Language Support Hash Tables (video)
 [ ] Core Hash Tables (video)
 [ ] Data Structures (video)
 [ ] Phone Book Problem (video)
 [ ] distributed hash tables:
[ ] implement with array using linear probing
 hash(k, m)  m is size of hash table
 add(key, value)  if key already exists, update value
 exists(key)
 get(key)
 remove(key)
More Knowledge

Binary search
 [ ] Binary Search (video)
 [ ] Binary Search (video)
 [ ] detail
 [ ] Implement:
 binary search (on sorted array of integers)
 binary search using recursion

Bitwise operations
 [ ] Bits cheat sheet  you should know many of the powers of 2 from (2^1 to 2^16 and 2^32)
 [ ] Get a really good understanding of manipulating bits with: &, , ^, ~, >>, <<
 [ ] words)
 [ ] Good intro: Bit Manipulation (video)
 [ ] C Programming Tutorial 210: Bitwise Operators (video)
 [ ] Bit Manipulation
 [ ] Bitwise Operation
 [ ] Bithacks
 [ ] The Bit Twiddler
 [ ] The Bit Twiddler Interactive
 [ ] 2s and 1s complement
 [ ] count set bits
 [ ] round to next power of 2:
 [ ] swap values:
 [ ] absolute value:
Trees

Trees  Notes & Background
 [ ] Series: Core Trees (video)
 [ ] Series: Trees (video)
 basic tree construction
 traversal
 manipulation algorithms
 BFS (breadthfirst search)
 MIT (video)
 level order (BFS, using queue) time complexity: O(n) space complexity: best: O(1), worst: O(n/2)=O(n)
 DFS (depthfirst search)
 MIT (video)
 notes: time complexity: O(n) space complexity: best: O(log n)  avg. height of tree worst: O(n)
 inorder (DFS: left, self, right)
 postorder (DFS: left, right, self)
 preorder (DFS: self, left, right)

Binary search trees: BSTs
 [ ] Binary Search Tree Review (video)
 [ ] Series (video)
 starts with symbol table and goes through BST applications
 [ ] Introduction (video)
 [ ] MIT (video)
 C/C++:
 [ ] Binary search tree  Implementation in C/C++ (video)
 [ ] BST implementation  memory allocation in stack and heap (video)
 [ ] Find min and max element in a binary search tree (video)
 [ ] Find height of a binary tree (video)
 [ ] Binary tree traversal  breadthfirst and depthfirst strategies (video)
 [ ] Binary tree: Level Order Traversal (video)
 [ ] Binary tree traversal: Preorder, Inorder, Postorder (video)
 [ ] Check if a binary tree is binary search tree or not (video)
 [ ] Delete a node from Binary Search Tree (video)
 [ ] Inorder Successor in a binary search tree (video)
 [ ] Implement:
 [ ] insert // insert value into tree
 [ ] get_node_count // get count of values stored
 [ ] print_values // prints the values in the tree, from min to max
 [ ] delete_tree
 [ ] is_in_tree // returns true if given value exists in the tree
 [ ] get_height // returns the height in nodes (single node’s height is 1)
 [ ] get_min // returns the minimum value stored in the tree
 [ ] get_max // returns the maximum value stored in the tree
 [ ] is_binary_search_tree
 [ ] delete_value
 [ ] get_successor // returns nexthighest value in tree after given value, 1 if none

Heap / Priority Queue / Binary Heap
 visualized as a tree, but is usually linear in storage (array, linked list)
 [ ] Heap)
 [ ] Introduction (video)
 [ ] Naive Implementations (video)
 [ ] Binary Trees (video)
 [ ] Tree Height Remark (video)
 [ ] Basic Operations (video)
 [ ] Complete Binary Trees (video)
 [ ] Pseudocode (video)
 [ ] Heap Sort  jumps to start (video)
 [ ] Heap Sort (video)
 [ ] Building a heap (video)
 [ ] MIT: Heaps and Heap Sort (video)
 [ ] CS 61B Lecture 24: Priority Queues (video)
 [ ] Linear Time BuildHeap (maxheap)
 [ ] Implement a maxheap:
 [ ] insert
 [ ] sift_up  needed for insert
 [ ] get_max  returns the max item, without removing it
 [ ] get_size()  return number of elements stored
 [ ] is_empty()  returns true if heap contains no elements
 [ ] extract_max  returns the max item, removing it
 [ ] sift_down  needed for extract_max
 [ ] remove(i)  removes item at index x
 [ ] heapify  create a heap from an array of elements, needed for heap_sort
 [ ] heap_sort()  take an unsorted array and turn it into a sorted array inplace using a max heap
 note: using a min heap instead would save operations, but double the space needed (cannot do inplace).
Sorting
[ ] Notes:
 Implement sorts & know best case/worst case, average complexity of each:
 no bubble sort  it’s terrible  O(n^2), except when n <= 16
 [ ] stability in sorting algorithms (“Is Quicksort stable?”)
 [ ] Which algorithms can be used on linked lists? Which on arrays? Which on both?
 I wouldn’t recommend sorting a linked list, but merge sort is doable.
 Merge Sort For Linked List
 Implement sorts & know best case/worst case, average complexity of each:
For heapsort, see Heap data structure above. Heap sort is great, but not stable.
[ ] Sedgewick  Mergesort (5 videos)
 [ ] 1. Mergesort
 [ ] 2. Bottom up Mergesort
 [ ] 3. Sorting Complexity
 [ ] 4. Comparators
 [ ] 5. Stability
[ ] Sedgewick  Quicksort (4 videos)
 [ ] 1. Quicksort
 [ ] 2. Selection
 [ ] 3. Duplicate Keys
 [ ] 4. System Sorts
[ ] UC Berkeley:
[ ] Merge sort code:
[ ] Quick sort code:
 [ ] Implementation ©
 [ ] Implementation ©
 [ ] Implementation (Python)
[ ] Implement:
 [ ] Mergesort: O(n log n) average and worst case
 [ ] Quicksort O(n log n) average case
 Selection sort and insertion sort are both O(n^2) average and worst case
 For heapsort, see Heap data structure above.
[ ] Not required, but I recommended them:
As a summary, here is a visual representation of 15 sorting algorithms. If you need more detail on this subject, see “Sorting” section in Additional Detail on Some Subjects
Graphs
Graphs can be used to represent many problems in computer science, so this section is long, like trees and sorting were.
Notes:
 There are 4 basic ways to represent a graph in memory:
 objects and pointers
 adjacency matrix
 adjacency list
 adjacency map
 Familiarize yourself with each representation and its pros & cons
 BFS and DFS  know their computational complexity, their tradeoffs, and how to implement them in real code
 When asked a question, look for a graphbased solution first, then move on if none.
 There are 4 basic ways to represent a graph in memory:
[ ] Skiena Lectures  great intro:
 [ ] CSE373 2012  Lecture 11  Graph Data Structures (video)
 [ ] CSE373 2012  Lecture 12  BreadthFirst Search (video)
 [ ] CSE373 2012  Lecture 13  Graph Algorithms (video)
 [ ] CSE373 2012  Lecture 14  Graph Algorithms (con’t) (video)
 [ ] CSE373 2012  Lecture 15  Graph Algorithms (con’t 2) (video)
 [ ] CSE373 2012  Lecture 16  Graph Algorithms (con’t 3) (video)
[ ] Graphs (review and more):
 [ ] 6.006 SingleSource Shortest Paths Problem (video)
 [ ] 6.006 Dijkstra (video)
 [ ] 6.006 BellmanFord (video)
 [ ] 6.006 Speeding Up Dijkstra (video)
 [ ] Aduni: Graph Algorithms I  Topological Sorting, Minimum Spanning Trees, Prim’s Algorithm  Lecture 6 (video)
 [ ] Aduni: Graph Algorithms II  DFS, BFS, Kruskal’s Algorithm, Union Find Data Structure  Lecture 7 (video)
 [ ] Aduni: Graph Algorithms III: Shortest Path  Lecture 8 (video)
 [ ] Aduni: Graph Alg. IV: Intro to geometric algorithms  Lecture 9 (video)
 [ ] CS 61B 2014 (starting at 58:09) (video)
 [ ] CS 61B 2014: Weighted graphs (video)
 [ ] Greedy Algorithms: Minimum Spanning Tree (video)
 [ ] Strongly Connected Components Kosaraju’s Algorithm Graph Algorithm (video)
Full Coursera Course:
I’ll implement:
 [ ] DFS with adjacency list (recursive)
 [ ] DFS with adjacency list (iterative with stack)
 [ ] DFS with adjacency matrix (recursive)
 [ ] DFS with adjacency matrix (iterative with stack)
 [ ] BFS with adjacency list
 [ ] BFS with adjacency matrix
 [ ] singlesource shortest path (Dijkstra)
 [ ] minimum spanning tree
 DFSbased algorithms (see Aduni videos above):
 [ ] check for cycle (needed for topological sort, since we’ll check for cycle before starting)
 [ ] topological sort
 [ ] count connected components in a graph
 [ ] list strongly connected components
 [ ] check for bipartite graph
You’ll get more graph practice in Skiena’s book (see Books section below) and the interview books
Even More Knowledge

Recursion
 [ ] Stanford lectures on recursion & backtracking:
 when it is appropriate to use it
 how is tail recursion better than not?

Dynamic Programming
 This subject can be pretty difficult, as each DP soluble problem must be defined as a recursion relation, and coming up with it can be tricky.
 I suggest looking at many examples of DP problems until you have a solid understanding of the pattern involved.
 [ ] Videos:
 the Skiena videos can be hard to follow since he sometimes uses the whiteboard, which is too small to see
 [ ] Skiena: CSE373 2012  Lecture 19  Introduction to Dynamic Programming (video)
 [ ] Skiena: CSE373 2012  Lecture 20  Edit Distance (video)
 [ ] Skiena: CSE373 2012  Lecture 21  Dynamic Programming Examples (video)
 [ ] Skiena: CSE373 2012  Lecture 22  Applications of Dynamic Programming (video)
 [ ] Simonson: Dynamic Programming 0 (starts at 59:18) (video)
 [ ] Simonson: Dynamic Programming I  Lecture 11 (video)
 [ ] Simonson: Dynamic programming II  Lecture 12 (video)
 [ ] List of individual DP problems (each is short): Dynamic Programming (video)
 [ ] Yale Lecture notes:
 [ ] Coursera:
 [ ] The RNA secondary structure problem (video)
 [ ] A dynamic programming algorithm (video)
 [ ] Illustrating the DP algorithm (video)
 [ ] Running time of the DP algorithm (video)
 [ ] DP vs. recursive implementation (video)
 [ ] Global pairwise sequence alignment (video)
 [ ] Local pairwise sequence alignment (video)

ObjectOriented Programming
 [ ] Optional: UML 2.0 Series (video)
 [ ] ObjectOriented Software Engineering: Software Dev Using UML and Java (21 videos):
 Can skip this if you have a great grasp of OO and OO design practices.
 OOSE: Software Dev Using UML and Java
 [ ] SOLID OOP Principles:
 [ ] Bob Martin SOLID Principles of Object Oriented and Agile Design (video)
 [ ] SOLID Principles (video)
 [ ] S  Single Responsibility Principle  Single responsibility to each Object
 [ ] O  Open/Closed Principal  On production level Objects are ready for extension but not for modification
 [ ] L  Liskov Substitution Principal  Base Class and Derived class follow ‘IS A’ principal
 [ ] I  Interface segregation principle  clients should not be forced to implement interfaces they don’t use
 [ ] D Dependency Inversion principle  Reduce the dependency In composition of objects.

Design patterns
 [ ] Quick UML review (video)
 [ ] Learn these patterns:
 [ ] strategy
 [ ] singleton
 [ ] adapter
 [ ] prototype
 [ ] decorator
 [ ] visitor
 [ ] factory, abstract factory
 [ ] facade
 [ ] observer
 [ ] proxy
 [ ] delegate
 [ ] command
 [ ] state
 [ ] memento
 [ ] iterator
 [ ] composite
 [ ] flyweight
 [ ] Chapter 6 (Part 1)  Patterns (video)
 [ ] Chapter 6 (Part 2)  AbstractionOccurrence, General Hierarchy, PlayerRole, Singleton, Observer, Delegation (video)
 [ ] Chapter 6 (Part 3)  Adapter, Facade, Immutable, ReadOnly Interface, Proxy (video)
 [ ] Series of videos (27 videos)
 [ ] Head First Design Patterns
 I know the canonical book is “Design Patterns: Elements of Reusable ObjectOriented Software”, but Head First is great for beginners to OO.
 [ ] Handy reference: 101 Design Patterns & Tips for Developers
 [ ] Design patterns for humans

Combinatorics (n choose k) & Probability
 [ ] Math Skills: How to find Factorial, Permutation and Combination (Choose) (video)
 [ ] Make School: Probability (video)
 [ ] [Make School: More Pro