cs_notes.txt

Hash tables
Linked lists
Breadth-first search, depth-first search
Quicksort, merge sort
Binary search
2D arrays
Dynamic arrays
Binary search trees
Dynamic programming
Big-O analysis

The first observation is that answering system design questions requires some specific knowledge. Obviously no one actually 
expects you to design Google maps (that took a lot of people a long time). But they do expect you to have some insight into 
aspects of such a design. The good news is that these questions usually focus on web backends, so you can make a lot of 
progress by reading about this area. An incomplete list of things to understand is: 

HTTP (at the protocol level)
Databases (indexes, query planning)
CDNs
Caching (LRU cache, memcached, redis)
Load balancers
Distributed worker systems



You need to understand these concepts. But more importantly, you need to understand how they fit together to form real systems. 
The best way to learn this is to read about how other engineers have used the concepts. The blog High Scalability is a great 
resource for this. It publishes detailed write-ups of the back-end architecture at real companies. You can read about how every 
concept on the list above is used in real systems. 

Once you’ve done this reading, answering system design questions is a matter of process. Start at the highest level, and move 
downward. At each level, ask your interviewer for specifications (should you suggest a simple starting point, or talk about what 
a mature system might look like?) and talk about several options (applying the ideas from your reading). Discussing tradeoffs in 
your design is key. Your interviewer cares less about whether your design is good in itself, and more about whether you are able 
to talk about the trade-offs (positives and negatives) of your decisions. Practice this.

1. Constraints and Use Cases
 * What kind of inputs must we handle?
2. Abstract Design
3. Understanding bottlenecks
4. Scaling the abstract design

https://www.palantir.com/2012/09/how-to-ace-a-phone-interview/
* Find a quiet, comfortable place to work.
* Make sure your phone works.
  Use a headset that allows you to talk comfortably while typing or writing. Make sure
you have an internet connection if you need one.
* Be prepared.
  Do your research--check out the website, read some of the interviewing tips, discover the company culture,
  perhaps try a demo. Have a pen and paper ready.
  
1. Think out loud.
2. Don't be afraid to ask questions.
Start simple and then expand.

https://www.palantir.com/2011/10/the-coding-interview/

Code should be *clean* as well as correct.

Before you start coding:
* Make sure you understand the problem.
  Don't hesitate to ask questions. Specifically, if any of the problem requirements seem loosely defined or otherwise unclear, ask your interviewer to make things more concrete. There is no penalty for asking for clarifications, and you don’t want to miss a key requirement or proceed on unfounded assumptions.

* Work through simple examples>
* Make a plan
  Be wary of jumping into coding without thinking about a program's high-level structure. Don't wowork out every last detail.
* Choose a language:
  Have a firm grasp of the fundamentals (decomposition, object-oriented design, etc.).
  
While Coding:
* Think out loud
* Break the problem down and define abstractions.
  One crucial skill is the ability to handle complexity by breaking problems into manageable sub-problems.
  For anything non-trivial, avoid writing one giant, monolithic function. Feel free to define helper functions,
  helper classes, and other abstractions to reach a working solution. You can leverage design patterns or other programming itdioms
  as well. The solution should be well-factored and as a result easy to read, understand, and prove correct.
* Delay the implementation of helper functions.
  Write out the signature, make sure you understand the contract your helper will enforce.
* Don't get caught up in trivialities.
  If you can't remember exactly how to do something in your chosen language, make something up and explain to your interviewer 
  that you would look up the specifics in the documentation. Likewise, if you use an abstraction or programming idiom
  which admits a trivial implementation, don't be afraid to just write out the interface and omit the 
  implementation so you can concentrate on more important aspects of the problem. (e.g., "I'm going to use
  a circular buffer here with the following interface without writing out the full implementations").
 
ONCE YOU HAVE A SOLUTION
* Think about edge cases
  One way to search for edge-case bugs is to...
* Step through your code.
  One of the best ways to check your work is to simulate how your code executes against a sample input.
  Take one of your earlier examples and make sure your code produces the correct result.
* Explain the shortcuts you took.
  IF you skip things for reasons of expedience that you would otherwise do ina "reql world" scenario, p, let your interview know you did and why.
  
  https://www.palantir.com/2011/09/how-to-ace-an-algorithms-interview/

Start writing on the board. This may sound obvious, but I've had dozens of candidates get stuck while staring at a blank wall. Maybe they're not visual people, but still I think it's more productive to stare at some examples of the problem than to stare at nothing. If you can think of a picture that might be relevant, draw it. If there's a medium-sized example you can work through, go for it. (Medium-sized is better than small, because sometimes the solution to a small example won't generalize.) Or just write down some propositions that you know to be true. Anything is better than nothing.
Talk it through. And don't worry about sounding stupid. If it makes you feel better, tell your interviewer, "I'm just going to talk out loud. Don't hold me to any of this." I know many people prefer to quietly contemplate a problem, but if you're stuck, talking is one way out of it. Sometimes you'll say something that clearly communicates to your interviewer that you understand what's going on. Even though you might not put much stock in it, your interviewer may interrupt you to tell you to pursue that line of thinking. Whatever you do, please DON'T fish for hints. If you need a hint, be honest and ask for one.
Think algorithms. Sometimes it's useful to mull over the particulars of the problem-at-hand and hope a solution jumps out at you (this would be a bottom-up approach). But you can also think about different algorithms and ask whether each of them applies to the problem in front of you (a top-down approach). Changing your frame of reference in this way can often lead to immediate insight. Here are some algorithmic techniques that can help solve more than half the problems we ask at Palantir:
Sorting (plus searching / binary search)
Divide-and-conquer
Dynamic programming / memoization
Greediness
Recursion
Algorithms associated with a specific data structure (which brings us to our fourth suggestion...)
Think data structures. Did you know that the top 10 data structures account for 99% of all data structure use in the real world? Probably not, because I just made those numbers up — but they're in the right ballpark. Yes, on occasion we ask a problem whose optimal solution requires a Bloom filter or suffix tree, but even those problems tend to have a near-optimal solution that uses a much more mundane data structure. The data structures that are going to show up most frequently are:
Array
Stack / Queue
Hashset / Hashmap / Hashtable / Dictionary
Tree / binary tree
Heap
Graph
You should know these data structures inside and out. What are the insertion/deletion/lookup characteristics? (O(log n) for a balanced binary tree, for example.) What are the common caveats? (Hashing is tricky, and usually takes O(k) time when k is the size of the object being hashed.) What algorithms tend to go along with each data structure? (Dijkstra's for a graph.) But when you understand these data structures, sometimes the solution to a problem will pop into your mind as soon as you even think about using the right one.

Think about related problems you’ve seen before and how they were solved. Chances are, the problem you've been presented is a problem that you've seen before, or at least very similar. Think about those solutions and how they can be adapted to specifics of the problem at hand. Don't get tripped up by the form that the problem is presented - distill it down to the core task and see if matches something you've solved in the past.
Modify the problem by breaking it up into smaller problems. Try to solve a special case or simplified version of the problem. Looking at the corner cases is a good way to bound the complexity and scope of the problem. A reduction of the problem into a subset of the larger problem can give a base to start from and then work your way up to the full scope at hand. Looking at the problem as a composition of smaller problems may also be helpful. For example, “find a number in a sorted array which has been shifted cyclically by an unknown constant k” can be solved by (1) first figuring out “k” and then (2) figuring out how to perform binary search on a shifted array).
Don't be afraid to backtrack. If you feel like a particular approach isn't working, it might be time to try a different approach. Of course you shouldn't give up too easily. But if you've spent a few minutes on an approach that isn't bearing any fruit and doesn't feel promising, back up and try something else. I've seen more candidates who overcommit than undercommit, which means you should (all else equal) be a little more willing to abandon an unpromising approach.

https://www.palantir.com/2011/10/how-to-rock-a-systems-design-interview/
Concurrency: Threads, deadlocks, starvation. Consistency and coherence.
Networking: IPC and TCP/IP. Difference between throughput and latency.
Abstraction: Levels of caching in a modern OS. How file systems and databases work.
Real-World Performance: Relative performance of RAM, disk, and SSD
Estimation: Helps eliminate infeasible solutions.
Availability and reliability: How can things fail, especially in a distributed environment? Ho
How to you design a system to cope with network failures? What is durability?

How to practice:
* Do mock design sessions
* Work on an actual system;
  Treat your projects as more than just academic exercises--actually focus on the architecture
  and the tradeoffs behind each decision.
* Do back-of-the-envelope calculations for something you're building and then write micro benchmarks
to verify them.
* Dig into the performance characteristics of an open source system. 
  For example, take a look at LevelDB. Read about the implementation to understand how it stores its data on disk
  and how it compacts the data into levels. Ask about tradeoffs: which kinds of data and sizes are optimal,
  and which degrade read/write performance? (Hint: think about random vs sequential qrites.)
  * Learn how databases and operating systems work under the hood.
    
https://swizec.com/blog/google-sent-me-a-what-to-know-in-on-site-interviews-email-here-it-is/swizec/4251

Design a service to generate unique 64 bit IDs

10000 cameras, 100 hours of video each. 30 fps. Police need to input a plate number and find the path of a suspicious vehicle. (Estimate the size of the video, e.g., blueray disc is 2 hours and 20 GB. No need to scan all of the videos. Estimate the time that a vehicle can be seen between 2 traffic cameras, e.g., 0.3 miles and 30 miles per hour, then select 1 out of 100). Web client, load balancer, servers, db.