Let me start with good news. Decode and Conquer (D&C) sales have been scorching ? this month! If you've been following who gets job offers from Facebook ? and Google, you know that candidates prefer D&C over other PM interview prep books. Google's recruiters are also big fans of D&C. Business Insider revealed that Google's recruiters prescribe my CIRCLES Method™ as the #1 method when preparing for product design questions. Google recruiters also recommend my on-demand, coding interview prep materials too.
Speaking of Google, I'm honored to share a brand new Google PM interview cheat sheet with all of you. It's fun, colorful, and Googley. More importantly, it covers all the different question types you'd encounter at the interview including product design, technical, analytical, and strategy. Crocosmia leaf. This cheat sheet is based on my latest book, Secrets of the Product Manager Interview.
Four steps to Crack the System Design Interview. Breaking down a complex task into small chunks helps us handle the problem at a better pace and in a more actionable way. Clarify Requirements and Specs. First things first, the ultimate goals should always be clear. System design interview back of the envelope calculation. Gft Apr 5, 2019 11 Comments Bookmark; function; Hey guys, I do not have much experience in large scale system design. Currently I am going through GTSDI and other system design materials for my fb onsite. I am getting familiar with most of SD concepts but still.
Google PM candidates erroneously believe that they the reason they didn't get a Google PM offer is because they failed the whiteboard coding interview. That's incorrect. #1 reason why candidates fail: poor responses to product design questions. What are product design questions? Here are two examples from actual Google interviews:
How would you design a better smoke detector?
Design an new iPad app for Google spreadsheet.
Deezer 5.11. Product design questions aren't covered by the standard MBA curriculum nor consulting case interview prep. There are a few reasons why product design questions are so challenging:
Phone Interview Cheat Sheet Pdf
Suffocating time pressure. Great products, such as the iPhone are not built in a day, let alone a 45-minute interview.
Limited domain knowledge. How can candidates suggest smoke detector innovations if they don't know how they work?
No support. Real-life innovation happens in teams; team members can build on each other's ideas. No such support system exists in a solitary closet-sized interview room.
To do well requires lots of practice. And the best place to start is the CIRCLES Method™.
If I had a Google PM interview, and I could only bring one cheat sheet..this would be it. Print out the high-resolution version of this cheat sheet, available in both JPG and PDF. Conquer those interviews, Lewis C. Lin
This blog post is a coding and system design interview cookbook/cheatsheet compiled by me with code pieces written by me as well. There is no particular structure nor do I pretend this to be a comprehensive guide. Also there are no explanations as the purpose is just to list important things. Moreover, this blog post is work-in-progress as I’m planning to add more things to it.
As always, opinions are mine.
Binary Search
Breadth First Search
Depth First Search
Just replace the queue in BFS with stack and you are done:
Backtracking
Generally a recursive algorithm attempting candidates and either accepting them or rejecting (“backtracking”) based on some condition. Below is an example of permutations generation using backtracking:
Dynamic Programming
Technique to determine result using previous results. You should be able to reason about your solution recursively and be able to deduce dp[i] using dp[i-1]. Generally you would have something like this:
Dynamic Programming: Knapsack
Union Find
When you need to figure out if something belongs to the same set you can use the following:
Binary Tree Traversals
Inorder: left-root-right
Postorder: left-rigth-root
Preorder: root-left-right
Plus each one of them could have reverse for right and left
Below are recursive and iterative versions of inorder traversal
Segment Tree
Djikstra
Simplest way to remember Djikstra is to imagine it as BFS over PriorityQueue instead of normal Queue, where values in queue are best distances to nodes pending processing.
Multi-threading: Semaphore
Multi-threading: Runnable & synchronized
Cheat Sheet For Interview Questions
Strings: KMP
Hopefully no one asks you this one. It would be too much code here, but the idea is not that difficult: build LPS (example “AAABAAA” -> [0,1,2,0,1,2,3]); use LPS to skip when comparing as if you were doing it in brute-force.
Strings: Rolling Hash (Rabin-Karp)
Let’s imagine we have window of length k and string s, then the hash for the first window will be:
H(k) = s[0]*P^(k-1) + s[1]*P^(k-2) + … + s[k]*P^0
Moving the window by one, would be O(1) operation:
H(k+1) = (H(k) – s[0]*P^(k-1)) * P + s[k+1]*P^0
Here is some sample code:
Unit Testing
JUnit User guide: https://junit.org/junit5/docs/current/user-guide/
Data Structures
Many interview problems can be solved by using right data structure.
hashmap
stack
queue
priority queue
trees
linked list
…
Actually, better to go here: https://www.geeksforgeeks.org/data-structures/
System Design Topics
requirements gathering
capacity planning
high level design
components design
database design
API design
queue
map reduce
long poll and push models
load balancing
partitioning
replication
consistency
caching
distributed caching
networking
Some System Design Problems
TinyURL
Coming up with good encoding or better pre-building keys
Handling collisions (if encoding or if different users have to have different key)
Use distributed caching, CDN, LB
Consider API throttling, eviction (maybe not), capacity
HTTP 302
Pastebin
Separate data from metadata and store separately
Otherwise similar to TinyURL
Instagram
Data partitioning is important here
Pull vs push (via long polling) applied based on number of following
Separate servers for viewing and posting for stability
Generating feed of images requires sorting, consider timestamp for photoId
Dropbox
Client and Server
Splitting files into chunks
Saving metadata about chunks
Local metadata database for the client
Queues for load handling
Data deduplication (user has same file in 100 places)
Facebook Messenger
poll vs push model with long polling
push notifications
Dedicate chat servers per user
“seeing into the future” problem solving with seq number
active status
Twitter
prebuild feed
handle celebrities differently
caching
monitoring
Youtube or Netflix
Splitting files into chunks (time and quality) via MapReduce
Distribution of content
Thumbnail generator & distribution
Store metadata separately (likes, views, comments, etc)
CDN
Typeahead Suggestion
Trie
For frequencies store them in nodes with suggestions
Propagate suggestions independently from queries (mapreduce)
Client implementation should delay request allowing for typing
Client having local history
API Rate Limiter
DDoS
Client identifier
Sliding window with counters
HTTP 429
Web Crawler
BFS
Facebook’s Newsfeed
Different feed components stored separately but joined
Yelp
Quad-Tree
Uber
Dynamic Quad-Tree
HashMap
Ticketmaster
Relational DB design
Concurrency handling
Interview Cheat Sheet Template
Resources
Well, internet is just full of all kinds of resources and blog posts on how to prepare for the technical interview plus there are numerous books and websites available. LeetCode is probably the most known of practicing websites. “Cracking The Coding Interview” is probably the most known book. I can also recommend “Guide to Competitive Programming”. As of system design, preparation resources are not so readily available. One good resource is “Grokking System Design Interview”, but it would be more valuable to practice designing large distributed systems. I also found the book “Designing Data-Intensive Applications” to be extremely helpful.
Asking for help
System Design Interview Cheat Sheet Pdf
What are other “must know” algorithms and important system design topics to be listed in this post?