Mission F.A.N.G

An Elaborate Study plan to get placed into Great Companies. From Interview Prep to Projects to System Design, I'm gonna delve deep. Come with me, it's gonna be an adventure.

Table of Contents

• What?
• Why?
• How?
• Language for the Interview
• Video Resources
• Books
• Flash Cards
• The Plan
• Prerequisite Knowledge
• Algorithmic complexity / Big-O / Asymptotic Analysis
• Data Structures
  • Arrays
  • Stack
  • Queue
  • Linked Lists
  • Trees
    • Binary Search Trees: BSTs
    • Heap / Priority Queue / Binary Heap
    • Balanced Search Trees
    • Traversals
  • Graphs
  • Tries
  • Hash Table
• Concepts & Algorithms
  • Bit Manipulation
  • Searching
    • Binary search
  • Sorting
    • Selection Sort
    • Insertion Sort
    • Heap Sort
    • Quick Sort
    • Merge Sort
  • String Searching & Manipulations
  • Recursion
  • Dynamic Programming
  • Graph Algorihtms
  • Math and Logic Puzzles
  • NP, NP-Complete and Approximation Algorithms
• Databases
• Networking
• System Design, Scalability & Data Handling
• Other Stuff
  • Programming Paradigms
  • Object-Oriented Programming
  • Functional Programming
  • Design Patterns
  • Caches
  • Processes and Threads
  • Papers
  • Testing
  • Scheduling
  • Implement System Routines
  • Floating Point Numbers
  • Unicode
  • Endianness
• Final Review
• Interview Process & General Interview Prep
• Behavioral Questions
• Technical Questions
• Projects
• Your Resume
• Have questions for the interviewer
• Once You've Got The Job

What

A multi-month study plan for going from a noob to first class software engineer for a large company.

Target Jobs/Positions :

Why

I've always been an underacheiver and more often than not I've had excuses for it. I know stuff but haven't been able to use it effectively. I wanted to break free of this endless cycle of underacheiving and self-pitying. This is my attempt to break this cycle and I expect to be a changed man after I'm done with this little project of mine.

Some links for when self doubt kicks in :

• 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
• Believe you can change
• Think you're not smart enough to work at Google? Well, think again

How

Fork a branch and follow the commands below

Mark all boxes with X after you completed your changes

Language For the Interview

I'll be using:

• Java
• JavaScript
• Python

I'll need to be very comfortable in the language and be knowledgeable.

More about choices:

• http://www.byte-by-byte.com/choose-the-right-language-for-your-coding-interview/
• http://blog.codingforinterviews.com/best-programming-language-jobs/

Video Resources

I'll add relevant video resources with the content itself. Other video resources I'll list here.

I'd appreciate your help to add free and always-available public sources, such as YouTube videos to accompany the online course videos.

Book List

The list of books I'm gonna use:

• Programming Interviews Exposed: Coding Your Way Through the Interview, 4nd Edition
• Cracking the Coding Interview, 6th Edition
• Introduction to Algorithms

I'll be adding language specific books, system design books etc.

Flash Cards

During my GRE Preparations I found flashcards to be of great utility. Here's a list of flashcard I'll be using:

• My Quizlet Flashcards
• Jwasham's Extreme in Quizlet
• Jwasham's Flashcards Site Repo
• Jwasham's Flashcards Database (old - 1200 cards):
• Jwasham's Flashcards Database (new - 1800 cards):

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.

The Plan

Each day I'll take one subject from the list below, watch videos about that subject, and write an implementation in:

• Java
• JavaScript
• Python
• and write tests to ensure I'm doing it right, sometimes just using simple assert() statements

Why I would 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)
• Make use of built-in types so I have experience using the built-in tools for real-world 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.

My Practice Code:

• Java
• JavaScript
• Python

I don't think I need to memorize the guts of every algorithm.

I'll write code on a whiteboard or paper, not a computer. Test with some sample inputs. Then test it out on a computer.

Prerequisite Knowledge

Algorithmic complexity / Big-O / Asymptotic Analysis

Data Structures

• Arrays

  • Description:
    • Arrays (video)
    • UC Berkeley CS61B - Linear and Multi-Dim Arrays (video) (Start watching from 15m 32s)
    • Basic Arrays (video)
    • Multi-dim (video)
    • Dynamic Arrays (video)
    • Jagged Arrays (video)
    • Jagged Arrays (video)
    • Resizing arrays (video)
  • Implementation : A Dynamic Array:
    • Practice coding using Arrays.
    • Use Generics (Java).
    • size() - number of items
    • capacity() - number of items it can hold
    • isEmpty()
    • 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(newCapacity) // 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)
  • Solve Questions from CtCI and Programming Interview Exposed.

• Linked Lists

  • Description:
    • Singly Linked Lists (video)
    • CS 61B - Linked Lists 1 (video)
    • CS 61B - Linked Lists 2 (video)
  • Linked List vs Arrays:
    • Core Linked Lists Vs Arrays (video)
    • In The Real World Linked Lists Vs Arrays (video)
  • 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.
    • Pointers to Pointers
  • Doubly-linked List
    • Description (video)
  • Implementation : LinkedList(with & without tail pointer), DoublyLinkedList:
    • size() - returns number of data elements in list
    • empty() - bool returns true if empty
    • valueAt(index) - returns the value of the nth item (starting at 0 for first)
    • pushFront(value) - adds an item to the front of the list
    • popFront() - remove front item and return its value
    • pushBack(value) - adds an item at the end
    • popBack() - 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
    • valueNFromEnd(n) - returns the value of the node at nth position from the end of the list
    • reverse() - reverses the list
    • removeValue(value) - removes the first item in the list with this value
  • Solve Questions from CtCI and Programming Interview Exposed.

• Stack

  • Description:
    • Stacks (video)
    • Using Stacks Last-In First-Out (video)
  • Implementation : Using Array.
    • push(item) - adds an item in the stack.
    • pop() - removes an item from the stack.
    • peek() - returns top element of stack.
    • isEmpty() - returns true if stack is empty, else false.
  • Solve Questions from CtCI and Programming Interview Exposed.

• Queue

  • Description :
    • Using Queues First-In First-Out(video)
    • Queue (video)
    • Circular Buffer/FIFO
    • Priority Queues (video)
  • Implementation using linkedList, with tail pointer & fixed-sized Array:
    • enqueue(value) - adds value at position at tail
    • dequeue() - returns value and removes least recently added element (front) - 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)

• Trees

  • Description

    • Series: Core Trees (video)
    • Series: Trees (video)
    • BFS(breadth-first search) and DFS(depth-first search) (video)
      • BFS notes:
        • level order (BFS, using queue)
        • time complexity: O(n)
        • space complexity: best: O(1), worst: O(n/2)=O(n)
      • DFS 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

    • Description :
      • Binary Search Tree Review (video)
      • Series (video)
        • starts with symbol table and goes through BST applications
      • Introduction (video)
      • MIT (video)
    • Implementation:
      • insert(value) - insert value into tree
      • getNodeCount() - get count of values stored
      • printValues() - prints the values in the tree, from min to max
      • deleteTree()
      • contains(value) - returns true if given value exists in the tree
      • getHeight() - returns the height in nodes (single node's height is 1)
      • getMin() - returns the minimum value stored in the tree
      • getMax() - returns the maximum value stored in the tree
      • isBinarySearchTree()
      • deleteValue()
      • getSuccessor(value) // returns next-highest value in tree after given value, -1 if none

  • Heap / Priority Queue / Binary Heap

    • Description :
    • 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 (max-heap)
    • Implement a MaxHeap:
      • insert(value)
      • getMax() - returns the max item, without removing it
      • getSize() - return number of elements stored
      • isEmpty() - returns true if heap contains no elements
      • extractMax() - returns the max item, removing it
      • remove(i) - removes item at index x
      • heapify() - create a heap from an array of elements, needed for heap_sort
      • heapSort() - take an unsorted array and turn it into a sorted array in-place using a max heap
        • note: using a min heap instead would save operations, but double the space needed (cannot do in-place).

  • Balanced Search Trees

    • Description :
    • Implementation :

  • Traversals

    • Description :
    • Implementation :

• Graphs

  • Description:

    • 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 graph-based solution first, then move on if none.
    • CSE373 2012 - Lecture 11 - Graph Data Structures (video)
    • Breadth-First Search
    • Depth-First Search

  • Implementation:

    • 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
    • Single-Source Shortest Path (Dijkstra)
    • Minimum Spanning Tree

• Tries

  • Note there are different kinds of tries. Some have prefixes, some don't, and some use string instead of bits to track the path.
  • Description :
    • Sedgewick - Tries (3 videos)
      • 1. R Way Tries
      • 2. Ternary Search Tries
      • 3. Character Based Operations
    • Notes on Data Structures and Programming Techniques
    • Short course videos:
      • Introduction To Tries (video)
      • Performance Of Tries (video)
      • Implementing A Trie (video)
    • The Trie: A Neglected Data Structure
    • TopCoder - Using Tries
    • Stanford Lecture (real world use case) (video)
    • MIT, Advanced Data Structures, Strings (can get pretty obscure about halfway through) (video)
  • Implementation:

• Hash table

  • Description:

    • Hashing with Chaining (video)
    • Table Doubling, Karp-Rabin (video)
    • Open Addressing, Cryptographic Hashing (video)
    • PyCon 2010: The Mighty Dictionary (video)
    • (Advanced) Randomization: Universal & Perfect Hashing (video)
    • (Advanced) Perfect hashing (video)

  • 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:
      • Instant Uploads And Storage Optimization In Dropbox (video)
      • Distributed Hash Tables (video)

  • Implementation : 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)