########################################################################################## ## How to read this ########################################################################################## Everything below is an outline, and you should tackle the items in order from top to bottom. I put an asterisk * at the beginning of a line when I'm done with it. When all sub-items are done, I put a * at the top level, meaning the entire block is done. Sorry you have to remove all my * to use this the same way. If you search/replace, there are a couple of places to look out for. ########################################################################################## ## Interview Prep: ########################################################################################## * - Videos: * - https://www.youtube.com/watch?v=oWbUtlUhwa8&feature=youtu.be * - https://www.youtube.com/watch?v=qc1owf2-220&feature=youtu.be * - https://www.youtube.com/watch?v=8npJLXkcmu8 * - Articles: * - http://www.google.com/about/careers/lifeatgoogle/hiringprocess/ * - http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html - all the things he mentions that you need to know are listed below * - (very dated) http://dondodge.typepad.com/the_next_big_thing/2010/09/how-to-get-a-job-at-google-interview-questions-hiring-process.html * - http://sites.google.com/site/steveyegge2/five-essential-phone-screen-questions * - Additional (not suggested by Google but I added): * - https://medium.com/always-be-coding/abc-always-be-coding-d5f8051afce2#.4heg8zvm4 * - https://medium.com/always-be-coding/four-steps-to-google-without-a-degree-8f381aa6bd5e#.asalo1vfx * - https://medium.com/@dpup/whiteboarding-4df873dbba2e#.hf6jn45g1 * - http://www.kpcb.com/blog/lessons-learned-how-google-thinks-about-hiring-management-and-culture * - http://www.coderust.com/blog/2014/04/10/effective-whiteboarding-during-programming-interviews/ * - Cracking The Coding Interview Set 1: * - https://www.youtube.com/watch?v=rEJzOhC5ZtQ * - https://www.youtube.com/watch?v=aClxtDcdpsQ * - How to Get a Job at the Big 4: * - https://www.youtube.com/watch?v=YJZCUhxNCv8 ########################################################################################## ## Knowledge: ########################################################################################## You need to know C, C++, or Java to do the coding part of the interview. They will sometimes make an exception and let you use Python or some other language, but the language must be mainstream and allow you write your code low-level enough to solve the problems. You'll see some C, C++ learning included below. There are a few books involved, see the bottom. Some videos are available only by enrolling in a Coursera or EdX class. It is free to do so. * - how computers process a program: * - https://www.youtube.com/watch?v=42KTvGYQYnA * - https://www.youtube.com/watch?v=Mv2XQgpbTNE * - Computer Arch Intro: (first video only - interesting but not required) https://www.youtube.com/watch?v=zLP_X4wyHbY&list=PL5PHm2jkkXmi5CxxI7b3JCL1TWybTDtKq&index=1 * - Parity & Hamming Code: Parity: https://www.youtube.com/watch?v=DdMcAUlxh1M Hamming Code: https://www.youtube.com/watch?v=1A_NcXxdoCc https://www.youtube.com/watch?v=JAMLuxdHH8o Error Checking: https://www.youtube.com/watch?v=wbH2VxzmoZk * - C * - K&R C book (ANSI C) - C++ * - basics * - pointers * - functions * - references * - templates * - compilation * - scope & linkage * - namespaces * - OOP * - STL * - functors: http://www.cprogramming.com/tutorial/functors-function-objects-in-c++.html * - C++ at Google: https://www.youtube.com/watch?v=NOCElcMcFik * - Google C++ Style Guide: https://google.github.io/styleguide/cppguide.html * - Google uses clang-format (there is a command line "style" argument: -style=google) * - Efficiency with Algorithms, Performance with Data Structures: https://youtu.be/fHNmRkzxHWs - C++ Core Guidelines: http://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines - review of C++ concepts: https://www.youtube.com/watch?v=Rub-JsjMhWY * - compilers: * - https://class.coursera.org/compilers-004/lecture/1 * - https://class.coursera.org/compilers-004/lecture/2 * - C++: https://www.youtube.com/watch?v=twodd1KFfGk * - Understanding Compiler Optimization (C++): https://www.youtube.com/watch?v=FnGCDLhaxKU ---------------------------------------------------------------- The Daily Plan: 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 built-in types C++ - using built-in types, like STL's std::list for a linked list Python - without using built-in types and write tests to ensure I'm doing it right, keep it simple with just assert() statements You may do Java or something else, this is just my thing. Each subject does not require a whole day to be able to understand it fully. 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 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) You don't need to memorize the guts of every algorithm. Write code on a whiteboard, not a computer. Test with some sample inputs. Then test it out on a computer to make sure it's not buggy from syntax. ---------------------------------------------------------------- * - Before you get started: The myth of the Genius Programmer: https://www.youtube.com/watch?v=0SARbwvhupQ Google engineers are smart, but many have an insecurity that they aren't smart enough. * - Algorithmic complexity / Big O / Asymptotic analysis - nothing to implement - Harvard CS50 - Asymptotic Notation: https://www.youtube.com/watch?v=iOq5kSKqeR4 - Big O Notations (general quick tutorial) - https://www.youtube.com/watch?v=V6mKVRU1evU - Big O Notation (and Omega and Theta): - https://www.youtube.com/watch?v=ei-A_wy5Yxw&index=2&list=PL1BaGV1cIH4UhkL8a9bJGG356covJ76qN - Skiena: - video: https://www.youtube.com/watch?v=gSyDMtdPNpU&index=2&list=PLOtl7M3yp-DV69F32zdK7YJcNXpTunF2b - slides: http://www3.cs.stonybrook.edu/~algorith/video-lectures/2007/lecture2.pdf - A Gentle Introduction to Algorithm Complexity Analysis: http://discrete.gr/complexity/ - Orders of Growth: https://class.coursera.org/algorithmicthink1-004/lecture/59 - Asymptotics: https://class.coursera.org/algorithmicthink1-004/lecture/61 - Illustrating "Big O": https://class.coursera.org/algorithmicthink1-004/lecture/63 - http://bigocheatsheet.com/ Arrays * - Description: - Arrays: https://www.coursera.org/learn/data-structures/lecture/OsBSF/arrays - Dynamic Arrays: https://www.coursera.org/learn/data-structures/lecture/EwbnV/dynamic-arrays - Resizing arrays: https://class.coursera.org/algs4partI-010/lecture/19 - Implement: * - 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) * - size() - number of items * - capacity() - number of items it can hold * - is_empty() - at(index) - returns item at given index - append(item) - or push(item) - insert(index, item) - prepend(item) - can use insert above at index 0 - delete(index) - remove(item) - find(item) - 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 = size of object * number of items to store linked lists - singly-linked * - Description: https://www.coursera.org/learn/data-structures/lecture/kHhgK/singly-linked-lists * - Lynda.com: - https://www.lynda.com/Developer-Programming-Foundations-tutorials/Introduction-lists/149042/177115-4.html - https://www.lynda.com/Developer-Programming-Foundations-tutorials/Understanding-basic-list-implementations/149042/177116-4.html - https://www.lynda.com/Developer-Programming-Foundations-tutorials/Using-singly-doubly-linked-lists/149042/177117-4.html - https://www.lynda.com/Developer-Programming-Foundations-tutorials/List-support-across-languages/149042/177118-4.html * - C Code: https://www.youtube.com/watch?v=QN6FPiD0Gzo - not the whole video, just portions about Node struct and memory allocation. * - why you should avoid linked lists: - https://www.youtube.com/watch?v=YQs6IC-vgmo - implement (with tail pointer), item is the data item in a node: - push_front - get_front - pop_front - push_back - get_back - pop_back - insert_before(node, item) - insert_after(node, item) - size() - is_empty() - find(item) - assume each item is unique - remove(item) - assume each item is unique - doubly-linked list - Description: https://www.coursera.org/learn/data-structures/lecture/jpGKD/doubly-linked-lists - reverse a singly-linked list stacks - see: https://class.coursera.org/algs4partI-010/lecture - https://www.coursera.org/learn/data-structures/lecture/UdKzQ/stacks queues - see: https://class.coursera.org/algs4partI-010/lecture - https://www.coursera.org/learn/data-structures/lecture/EShpq/queues Vectors heaps - https://www.coursera.org/learn/data-structures/lecture/GRV2q/binary-trees - min heap - max heap Priority Queue - https://www.coursera.org/learn/data-structures/lecture/2OpTs/introduction - see: https://class.coursera.org/algs4partI-010/lecture - https://class.coursera.org/algs4partI-010/lecture/39 - https://en.wikipedia.org/wiki/Priority_queue Disjoint Sets: - https://www.coursera.org/learn/data-structures/lecture/JssSY/overview - https://www.coursera.org/learn/data-structures/lecture/Mxu0w/trees hashtables - https://www.youtube.com/watch?v=C4Kc8xzcA68 - https://class.coursera.org/algs4partI-010/lecture/52 - https://www.coursera.org/learn/data-structures/home/week/3 - see: https://class.coursera.org/algs4partI-010/lecture - https://www.coursera.org/learn/data-structures-optimizing-performance/lecture/m7UuP/core-hash-tables - test: implement with only arrays tries - https://www.coursera.org/learn/data-structures-optimizing-performance/lecture/08Xyf/core-introduction-to-tries Circular buffer/FIFO: - https://en.wikipedia.org/wiki/Circular_buffer Bit operations - count on bits - https://youtu.be/Hzuzo9NJrlc - max run of off bits - bit shifting binary search Sorting - no bubble sort - it's terrible - at least one n*log(n) sorting algorithm, preferably two (say, quicksort and merge sort) - Which algorithms can be used on lists? Which on arrays? Which on both? Is Quicksort stable? - algos: - mergesort - quicksort Caches - LRU cache Trees - https://www.coursera.org/learn/data-structures-optimizing-performance/lecture/ovovP/core-trees - see: https://class.coursera.org/algs4partI-010/lecture - basic tree construction - traversal - manipulation algorithms - binary search trees BSTs - https://www.coursera.org/learn/data-structures/lecture/E7cXP/introduction - applications: - https://class.coursera.org/algs4partI-010/lecture/57 - n-ary trees - trie-trees - at least one type of balanced binary tree (and know how it's implemented): - red/black tree - https://class.coursera.org/algs4partI-010/lecture/50 - splay trees - https://www.coursera.org/learn/data-structures/lecture/O9nZ6/splay-trees - AVL trees - https://www.coursera.org/learn/data-structures/lecture/Qq5E0/avl-trees - https://www.coursera.org/learn/data-structures/lecture/PKEBC/avl-tree-implementation - https://www.coursera.org/learn/data-structures/lecture/22BgE/split-and-merge - 2-3 Search Trees - https://class.coursera.org/algs4partI-010/lecture/49 - B-Trees: - https://class.coursera.org/algs4partI-010/lecture/51 - BFS (breadth-first search) - DFS (depth-first search) - know the difference between - inorder - postorder - preorder Graphs: There are three basic ways to represent a graph in memory: - objects and pointers - matrix - adjacency list - 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 - If you get a chance, try to study up on fancier algorithms: - Dijkstra - A* - when asked a question, look for a graph-based solution first, then move on if none. Other data structures: - You should study up on as many other data structures and algorithms as possible - You should especially know about the most famous classes of NP-complete problems, such as traveling salesman and the knapsack problem, and be able to recognize them when an interviewer asks you them in disguise. - Know what NP-complete means. Recursion - when it is appropriate to use it open-ended problems - manipulate strings - manipulate patterns design patterns: - strategy - singleton - adapter - prototype - decorator - visitor - factory Combinatorics (n choose k) Probability Dynamic Programming Processes, Threads, Concurrency issues - difference: https://www.quora.com/What-is-the-difference-between-a-process-and-a-thread - threads: https://www.youtube.com/playlist?list=PL5jc9xFGsL8E12so1wlMS0r0hTQoJL74M - stopped here: https://www.youtube.com/watch?v=_N0B5ua7oN8&list=PL5jc9xFGsL8E12so1wlMS0r0hTQoJL74M&index=4 - locks - mutexes - semaphores - monitors - how they work - deadlock - livelock Process resource needs Thread resource needs Modern concurrency constructs with multicore processors Context switching - How context switching is initiated by the operating system and underlying hardware Scheduling Weighted random sampling Implement system routines Distill large data sets to single values Transform one data set to another Handling obscenely large amounts of data System design: - features sets - interfaces - class hierarchies - designing a system under certain constraints - simplicity and robustness - tradeoffs Performance analysis and optimization Familiarize yourself with unix-based souped-up code editor: emacs & vi(m) vi(m): - https://www.youtube.com/watch?v=5givLEMcINQ&index=1&list=PL13bz4SHGmRxlZVmWQ9DvXo1fEg4UdGkr - set of 4: - https://www.youtube.com/watch?v=SI8TeVMX8pk - https://www.youtube.com/watch?v=F3OO7ZIOaJE - https://www.youtube.com/watch?v=ZYEccA_nMaI - https://www.youtube.com/watch?v=1lYD5gwgZIA emacs: - https://www.youtube.com/watch?v=hbmV1bnQ-i0 - set of 3: - https://www.youtube.com/watch?v=ujODL7MD04Q - https://www.youtube.com/watch?v=XWpsRupJ4II - https://www.youtube.com/watch?v=paSgzPso-yc - https://www.youtube.com/watch?v=JWD1Fpdd4Pc Testing ------------------------------------------------------------------- Once you're closer to the interview: - Cracking The Coding Interview Set 2: - https://www.youtube.com/watch?v=4NIb9l3imAo - https://www.youtube.com/watch?v=Eg5-tdAwclo - https://www.youtube.com/watch?v=1fqxMuPmGak ------------------------------------------------------------------- Extras that can't hurt: Information theory: - Markov processes: - https://www.coursera.org/learn/data-structures-optimizing-performance/lecture/waxgx/core-markov-text-generation - https://www.coursera.org/learn/data-structures-optimizing-performance/lecture/gZhiC/core-implementing-markov-text-generation - https://www.khanacademy.org/computing/computer-science/informationtheory/moderninfotheory/v/symbol-rate-information-theory - includes Markov chain Bloom Filter - https://www.youtube.com/watch?v=-SuTGoFYjZs - http://blog.michaelschmatz.com/2016/04/11/how-to-write-a-bloom-filter-cpp/ Fast Fourier Transform - http://jakevdp.github.io/blog/2013/08/28/understanding-the-fft/ Machine Learning: - great course: https://www.coursera.org/learn/machine-learning - http://www.analyticsvidhya.com/blog/2016/04/neural-networks-python-theano/ - http://www.dataschool.io/ ------------------------ Be thinking of for when the interview comes: Think of about 20 interview questions you'll get, along the lines of the items below: have 2-3 answers for each Have a story, not just data, about something you accomplished Why do you want this job? What's a tough problem you've solved? Biggest challenges faced? Best/worst designs seen? Ideas for improving an existing Google product. How do you work best, as an individual and as part of a team? Which of your skills or experiences would be assets in the role and why? What did you most enjoy at [job x / project y]? What was the biggest challenge you faced at [job x / project y]? What was the hardest bug you faced at [job x / project y]? What did you learn at [job x / project y]? What would you have done better at [job x / project y]? --------------------------- Have questions for the interviewer. Some of mine (I already may know answer to but want their opinion or team perspective): - How large is your team? - What is your dev cycle look like? Do you do sprints/agile? - How are decisions made in your team? - How many meetings do you have per week? - Do you feel your work environment helps you concentrate? - What are you working on? - What do you like about it? - What is the work life like? ########################################################################################## ## Books: ########################################################################################## Mentioned in Coaching: The Algorithm Design Manual http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/dp/1849967202 Algorithms and Programming: Problems and Solutions: http://www.amazon.com/Algorithms-Programming-Solutions-Alexander-Shen/dp/0817638474 Read first: Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition: http://www.wiley.com/WileyCDA/WileyTitle/productCd-047012167X.html Read second: Cracking the Coding Interview, 6th Edition: - http://www.amazon.com/Cracking-Coding-Interview-6th-Programming/dp/0984782850/ Additional (not suggested by Google but I added): * - C Programming Language, Vol 2 * - C++ Primer Plus, 6th Edition Introduction to Algorithms Programming Pearls: - http://www.amazon.com/Programming-Pearls-2nd-Jon-Bentley/dp/0201657880 If you see people reference "The Google Resume", it was replaced by "Cracking the Coding Interview". Clean Code Code Complete ########################################################################################## ########################################################################################## ## ## ## ## Everything below is my recommendation, not Google's, and ## you may not have enough time to watch or read them all. ## That's ok. I may not either. ## ## ## ########################################################################################## ########################################################################################## ## Videos: ########################################################################################## CSE373 - Analysis of Algorithms (25 videos): - https://www.youtube.com/watch?v=ZFjhkohHdAA&list=PLOtl7M3yp-DV69F32zdK7YJcNXpTunF2b&index=1 6.042: Math for CS (25 videos): - https://www.youtube.com/watch?v=L3LMbpZIKhQ&list=PLB7540DEDD482705B 6.006: Intro to Algorithms (47 videos): - https://www.youtube.com/watch?v=HtSuA80QTyo&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb&nohtml5=False 6.033: Computer System Engineering (22 videos): - https://www.youtube.com/watch?v=zm2VP0kHl1M&list=PL6535748F59DCA484 6.046: Design and Analysis of Algorithms (34 videos): - https://www.youtube.com/watch?v=2P-yW7LQr08&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp 6.851: Advanced Data Structures (22 videos): - https://www.youtube.com/watch?v=T0yzrZL1py0&list=PLUl4u3cNGP61hsJNdULdudlRL493b-XZf Stanford: Programming Paradigms (17 videos) - https://www.youtube.com/watch?v=jTSvthW34GU&list=PLC0B8B318B7394B6F&nohtml5=False ########################################################################################## ## Articles: ########################################################################################## - https://www.topcoder.com/community/data-science/data-science-tutorials/the-importance-of-algorithms/ - http://highscalability.com/blog/2016/4/4/how-to-remove-duplicates-in-a-large-dataset-reducing-memory.html - http://highscalability.com/blog/2016/3/23/what-does-etsys-architecture-look-like-today.html - http://highscalability.com/blog/2016/3/21/to-compress-or-not-to-compress-that-was-ubers-question.html - http://highscalability.com/blog/2016/3/3/asyncio-tarantool-queue-get-in-the-queue.html - http://highscalability.com/blog/2016/2/25/when-should-approximate-query-processing-be-used.html - http://highscalability.com/blog/2016/2/23/googles-transition-from-single-datacenter-to-failover-to-a-n.html - http://highscalability.com/blog/2016/2/15/egnyte-architecture-lessons-learned-in-building-and-scaling.html - http://highscalability.com/blog/2016/2/1/a-patreon-architecture-short.html - http://highscalability.com/blog/2016/1/27/tinder-how-does-one-of-the-largest-recommendation-engines-de.html - http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html - http://highscalability.com/blog/2016/1/13/live-video-streaming-at-facebook-scale.html - http://highscalability.com/blog/2016/1/11/a-beginners-guide-to-scaling-to-11-million-users-on-amazons.html - http://highscalability.com/blog/2015/12/16/how-does-the-use-of-docker-effect-latency.html - http://highscalability.com/blog/2015/12/14/does-amp-counter-an-existential-threat-to-google.html - http://highscalability.com/blog/2015/11/9/a-360-degree-view-of-the-entire-netflix-stack.html ########################################################################################## ## Papers: ########################################################################################## Computing Weak Consistency in Polynomial Time - http://dl.acm.org/ft_gateway.cfm?id=2767407&ftid=1607485&dwn=1&CFID=627637486&CFTOKEN=49290244 How Developers Search for Code: A Case Study - http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/43835.pdf Borg, Omega, and Kubernetes - http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44843.pdf Continuous Pipelines at Google - http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/43790.pdf AddressSanitizer: A Fast Address Sanity Checker - http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37752.pdf ########################################################################################## ## Coding exercises/challenges: ########################################################################################## - https://courses.csail.mit.edu/iap/interview/materials.php LeetCode: https://leetcode.com/ TopCoder: https://www.topcoder.com/ More: HackerRank: https://www.hackerrank.com/ Codility: https://codility.com/programmers/ Project Euler: https://projecteuler.net/index.php?section=problems InterviewCake: https://www.interviewcake.com/ InterviewBit: https://www.interviewbit.com/invite/icjf ########################################################################################## ## Maybe: ########################################################################################## http://www.gainlo.co/ - Mock interviewers from big companies ########################################################################################## ## Code References: ########################################################################################## For review questions in C book: https://github.com/lekkas/c-algorithms ########################################################################################## ## Once you've got the job (this is mainly for me): ########################################################################################## C++ Talks at CPPCon: - https://www.youtube.com/watch?v=hEx5DNLWGgA&index=2&list=PLHTh1InhhwT75gykhs7pqcR_uSiG601oh Compilers: - https://class.coursera.org/compilers-004/lecture Computer and processor architecture: - https://class.coursera.org/comparch-003/lecture Long series of C++ videos: - https://www.youtube.com/playlist?list=PLfVsf4Bjg79Cu5MYkyJ-u4SyQmMhFeC1C ########################################################################################## ## Done. ## ##########################################################################################