READ THIS FIRST - The 5 Commandments of Interview Camp
Here are our 5 commandments we want you to understand well. Please read these all the way.
1. Focus on Less , Not More
Are you overwhelmed by the sheer number of problems you need to solve? Without that, do you worry if you’ll ever get a shot at Google or Facebook? Don’t worry. It’s a misleading thought.
When you start your prep, focus on 100-150 core problems. Focus on Mastering them completely. What does mastery mean? It means you should be able to finish coding them in 2-3 minutes. Sounds too ambitious? That’s because you’re probably focusing on 500 problems at once. If you focus on less problems and repeat them, you get so familiar that they become second nature to you. And that’s where the magic starts.
Once you’ve mastered these problems, you’ve mastered Depth. Now, you can focus on Breadth - looking at a large number of problems. And the best part - after these 100 problems, you won’t need to implement new problems - you can just find the solution and move on. That’s because you’re already good at translating solutions to code - you did that when you mastered those 100 problems.
80% of the value is in mastering Depth. It’s where most people go wrong. They keep solving Leetcode problems to no end, and they never develop mastery.
2. Study One Resource at a time
Are you overwhelmed by all the resources to study? Don’t be.
It’s very easy to get distracted with all the resources out there. Ask anyone how they’re preparing and they’ll name at least 3 resources. Most of the time, they keep jumping from one to another. Tired of a book? Start looking at some Youtube videos. Tired of Youtube? Try doing problems online.
It becomes a never-ending quest of you trying to please your distracted mind.
And then, here’s the feeling everyone gets: After a couple of months, you feel like you’ve barely made progress.
Let’s take an alternate reality. Let’s say you focused on one resource only. In 2 months, you probably would’ve finished it. You would’ve learned everything it had to offer.
Don’t jump around resources. Finish one all the way, then move to the next.
3. Don’t run code on Leetcode
Are you constantly frustrated because your code doesn’t pass on Leetcode? Don’t be.
This is one of the biggest time suckers in your prep. When you run code on Leetcode, you’re trying to pass every small test case, which won’t matter in a real interview. Interviewers don’t expect your code to pass every test case. They expect you to go over a good set of cases, but that’s at most 7-10 cases, not the 100 or so Leetcode wants you to pass!
And it’s stressful! You’re constantly frustrated about your code not passing!
Why is this a time sucker? Because for every Leetcode problem, you can spend a good 30 minutes trying to get every test case to pass. Now, do that for 100 problems - that’s 3000 minutes (or 50 hours) down the drain.
Note: The only exception is if you’re given a pre-screening test like HackerRank, which will run all cases. You can always practice that later, once you’ve mastered depth. No need to prematurely waste time debugging exhaustive test cases.
4. Repeat Code Twice Right Away
Are you stressed because when you come back to a problem you’ve solved before, you can’t solve it again? Here’s how to fix that.
As soon as you write code for a solution, write it again. Yes, the same code.
The first time you’re coding a problem, your mind is thinking in a lot of things -
Am I solving the problem right so far?
What’s the next step for this algorithm?
How do I code this line?
During this time, you don’t even know if your code will work. You’re focusing on translating logic to code. Once you’re done verifying it, all the ambiguity is gone. You know this thing works. Now is the time to solidify it in your brain. How do you do that? Just by coding it again. And no need to hide the code you wrote, feel free to look at it. When you code it the second time, you start getting used to the function structure. You appreciate why it works.
Now, code it a third time. By now, it has become second nature to you.
This is the single technique that can completely change the game for you. We’ve recommended this again and again to our students, and it has worked marvels.
5. Spaced Repetition
Repeating code is great. But if you really want to retain this knowledge long term, come back to the same problem in 3 days. Code it again. Code it twice if you want to. Doesn’t matter. It’s easy now.
Then, come back to it in 7 days. You’ll notice that you’re just good at this stuff.
Then, come back in 2 weeks. You’ll see the difference. You’ll be way more confident, and you’ll start seeing patterns in similar problems.
Those were our 5 Commandments. We really hope this dispels many myths that are prevalent in interview prep today. In many ways, the industry has sadly become predatory - all about doing as many problems as you can. The truth is, you need to be organized and focus on the important things - instead of blindly solving problems.
The Building Blocks Approach. Guide to Problem Levels: Easy, Medium, Hard
What are Building Blocks?
Problems in this course are divided into Building Blocks . You might have seen these before, but identifying them separately makes you focus on those and master them. This makes it easier to reuse them in the interview. This also makes it easier to apply them to a problem you haven’t seen before.
For example, take Binary Search , a fundamental building block. Once you know it at the tip of your fingers, you can make small modifications to solve related problems. You can also use it in more complex problems. We will show you how.
Another building block is the Linked Hash Table . You can use it to solve the LRU Cache Problem, but once you know it, you can also use the same technique to solve problems like Finding the Skyline. If you don’t know those right now, its fine. You will learn them later.
How to solve each problem in this course
Regardless of a problem’s level, you should understand each problem deeply . Even if you get an easy problem, simply coding it will not be enough. You should be able to discuss it and solve similar problems.
What does deeply mean?
Deeply means that you not only understand how an algorithm works, you can teach it as well. You need to be comfortable with it. Here is how you accomplish that:
-
Practice on Paper: Practicing on paper makes a huge difference. Try it out. Write a solution 3 times on paper, and you’ll see the difference. If you have a whiteboard, that works too. Later on, you can code it on a computer if you like.
-
Practice each technique 3-5 times: You can carry a notebook anywhere with you. Repeat a solution you implemented a few days ago. Don’t memorize it, just implement it. You will start seeing patterns and develop muscle memory for these algorithms.
So, even for Easy problems, practice the code at least 3 times.
Why 3 times? The first time is a struggle. The second time, you are getting comfortable with it. By the third time, it becomes second nature to you.
But how many Problems should I practice deeply?
There’s 2 approaches:
-
Practice each Building Block’s solution deeply.
-
Practice each Building Block’s solution deeply AND each Homework Problem deeply.
Do approach 2 if you have the time. Otherwise, approach 1 is good enough. This will give you a solid foundation of each Block.
Question Levels - Easy, Medium, Hard
You should assume the following distribution of questions in your interviews:
20% Easy
60% Medium
20% Hard
This is typical of companies like Google and Facebook. Even if you’re interviewing elsewhere, I would recommend you anticipate this distribution. Why? Because it has a good balance of all levels.
Easy
If you don’t know how to do an easy question, start from there, and practice them.
If you have seen a question in the past, use it to practice explaining the solution. Solve it again, and in your head, explain it to the interviewer.
Medium
These are questions that you should focus on the most. Medium level questions are most likely to come up in most interviews. People over focus on Hard problems. In reality, if they were really good at Medium problems, they’d be getting most job offers anyway, because these are the most asked.
Hard
There is a tendency online to focus on problems that are way too hard. For example, String search using the Boyer-Moore Algorithm. Or some really complicated graph algorithm. Those might come in programming competitions, not coding interviews.
Unfortunately, it makes people believe that you need to learn these ridiculously hard problems to get into Google. Not so.
Hard problems in this course are problems that actually show up in interviews. If you are comfortable with all our Hard and Medium problems (which means you can solve them easily) you are probably ready for the interview.
Two ways to go over this course (Both these approaches are fine, follow your comfort level)
-
Do video solutions first for the week, then go back and do homework problems for the week.
-
Do video solutions and immediately do homework problems for that video.
A Note on Dynamic Programming (DP)
DP is the most feared topic. We think it gets disproportionate amount of attention.
Consider this:
First of all, DP is a dying class of problems in interviews. Google and Facebook actively discourage DP-only problems. These are problems that can only be solved well using DP.
We estimated that around 3% questions in top tech companies will need dynamic programming. That is 1 interview in 30.
In reality, it is ok if in one interview, your solution is suboptimal. As long as you do well in other interviews, it wouldn’t matter.
Unfortunately, I hear people make statements like this:
“I am great at all topics, but I screw up complicated DP problems, and that is holding me back”
If you were really good at all topics except DP, you would be getting offers left and right. In most cases, there are more basic problems with the candidate. Either they stumble when they see a new problem, or something is wrong in their interview approach and communication.
Here is how I would approach it: Go through our DP section and learn to do common DP problems. This will give you a good idea about how it works. Focus on completing other sections first, and then start doing more complicated DP problems.
Understanding the Interview Process
Some Truths:
At the end, there will be an overall review
After the onsite, response from all the interviews is collected and analyzed by a committee. This can be either the interviewers or an independent group.
Response from all interviews is considered. An exception, of course, is the phone interview, which can be a single point of failure if it doesn’t go well.
Phone interviews are a single point of failure
A lot of people take phone interviews lightly. Sadly, though, they can be critical. If an onsite interview doesn’t go well, you can make up for it with other interviews. Not so with phone interviews.
Likeability is very important
We have seen candidates rejected because of lack of enthusiasm or interest. At the end of the day, interviewers are trying to see if they would like working with you. Being likeable is no substitute for skill, but it sure goes a long way.
Some Myths:
Why should I prepare? Isn’t that cheating?
Not at all. In fact, companies expect you to prepare. If you don’t, they are not able to judge you properly, and that leads to rejections.
Compare this to an open book test. The book has concepts. The questions should test your application of those concepts.
What if a question comes straight from the book? Well, that is the examiner’s fault, they are supposed to come up with their own questions.
Not preparing is like not bringing the book to an open book test.
If the interviewers seemed happy, it means I did well
Interviewers are instructed to be nice to the candidate and make the candidate feel comfortable, regardless of your performance.
All interviews went well except for one, that is why I was rejected
We have heard this countless times, and it’s just an excuse. Companies understand that you might not do well in one interview. As long as there is consensus among other interviews, this is not a problem.
I didn’t go to an Ivy league college, or I work for a unknown company
Bias for elite universities not common in the industry nowadays. In fact, Google has repeatedly discouraged it: http://qz.com/180247/why-google-doesnt-care-about-…
However, this might be an issue while getting the interview. Direct employee referrals are prioritized by companies, and if you don’t have an employee referral, you might fall backwards in the queue.
Also, experience from well known companies is generally better recognized because people understand the work done. Fortunately though, a significantly larger weight is given to the interview performance.
I am a senior hire with several years of experience, I won’t be asked algorithm questions
Not true. If you are a senior hire, you might get more questions about your experience, your expertise and system design. However, unless you are interviewing for a non-technical manager role, you will most likely get some problem solving questions. You should also confirm this with your recruiter.
I am older, that puts me at a disadvantage
If you are haven’t touched these topics in a while, you definitely have to prepare for them, just like any college student who has never designed a real system has to prepare for those.
However, we have never seen anyone being discriminated on the basis of their age.
Summary of the process:
The Interview process is similar for most companies. It consists of 1 or 2 rounds of phone interviews and 3-5 onsite interviews, all 45-60mins long.
This is a well established sequence:
- 5-10 mins - Experience related questions
- 30-40 mins - Algorithm and System Design questions
- last 5-10 mins - Questions for the interviewer
Some companies might be more focused on algorithms, while others more on system design or experience. You can count on them to be a mix of those, even for people with a lot of experience.
You should go to glassdoor.com and careercup.com to verify the interview process and questions asked by each company.
You should also check the recruiter’s communications to make sure the company does not have a wildly different process. For example, there are some companies that do coding projects. Almost all of those will also do interviews, but there might be the rare company that relies only on the project.
You should confirm with the recruiter if there will be a domain specific interview. For example, if you are applying for an iOS engineer position, there might be something iOS specific. Unfortunately, we cannot cover those in this course.
1. Algorithm Questions
The interviewer will ask you to solve a problem and write code on a whiteboard (or on a laptop).
For example: Given two sorted arrays, merge them into a single array. (This is a banned question at most big companies since it’s easy and very commonly asked).
The problem is vaguely described on purpose
On the job, you will get vague problems and you will need to narrow down. Same applies here. You should ask questions about the problem.
Is the array sorted? Will it have only integers? Can it have duplicates? Can you allocate another array for the result?
They are actively judging your thought process, not just the code
Did you consider corner cases? Did you consider runtime? Did you consider memory usage? Did you arrive at the solution systematically?
An ideal candidate will clarify the problem, walk through examples, find a solution, analyze the solution and then code it.
You are supposed to verify your own code and find bugs
You should be able to examine your code, walk through it and find any issues with it.
2. System or Object Oriented Design Questions
These questions are open ended and generally involve discussion. Again, you have to show that you can be systematic when designing. First, design a simple system, and then add complications.
For example, let’s say the question asks you to design Facebook. First, explain the design for a simple social network, let’s say as a graph with users as nodes and connections as edges. Then, add the complication of scale, or features. These questions often judge the candidate’s knowledge of scalable systems, which we will cover in the course.
The discussion can take any direction as desired by the interviewer. For example, during the question above, the interviewer might ask you thoughts on designing the Home Feed.
We have explained many of these questions in the course.
3. Experience Questions
These become important when you have a domain expertise or years of experience. Anything on your resume is fair game for the interviewer.
4. Reverse Interview Questions
Questions for the interviewer: You will get the chance to ask questions about the job. This is a chance for the interviewer to sell the job.
Programming Language Concepts - Java
Let us go over some key Java concepts you should understand. No need to memorize these, except for the number of bytes in each data type. The same applies to any language you use. Know the datatypes and how much memory they take.
How does Java work? How is it Platform Independent?
When you compile a C++ program, you generate an executable that runs on a target platform, like Windows or Linux. For example, on Windows, you generate a .exe file.
When you compile a Java program, you use the JVM compiler (called javac) to generate a bytecode file (with extension .class). These files can be run on any platform with Java Virtual Machine installed.
[2]
javac is the Java Compiler: It compiles Java code (.java files) into Bytecode (.class files).
JVM is the Java Virtual Machine: It translates Bytecode into Native Machine Code.
JRE is the Java Runtime Environment: It is software to run Java applications. It contains JVM and other libraries.
JDK is the Java Development Kit: It is software to run and develop Java applications. It contains the JRE along with compilers and debuggers.
Just In Time (JIT) Compiler
In very early days, JVM would compile bytecode into machine code all at once. Now, Java has a JIT compiler, which compiles a lot of the bytecode dynamically when needed.
Advantage: The JIT has access to dynamic runtime information, so it can make optimizations based on that.
[3]
Java also has a garbage collector (GC), which runs as a background thread and clears up unused allocated memory.
Advantage is that you don’t have to worry about freeing up variables.
Disadvantage is that this can affect performance in memory constrained systems.
More about garbage collection in later lectures.
Java data types
You should know how many bytes each data type takes. Other columns can be calculated from the bytes.
Numbers to remember:
2^10 = 1024
2^32 = approx. 4 billion
How to come up with range?
If there are 16 bits, we can represent 2^16 numbers. But we need both -ve and +ve numbers. So we split it halfway (2^15). 0 is included in positive numbers, so the range is from -2^15 to 2^15 - 1.
Computers use a technique called Two’s Complement to represent negative numbers in binary. You probably don’t need to remember details about two’s complement, most engineers don’t.
Strings are immutable
Strings are immutable in Java. This means they cannot be modified once created.
String foo = “Hello”; foo = “Hi”;
“Hello” and “Hi” are two different objects. Variable foo was reassigned to object “Hi”.
Advantages:
- Security: Strings are often used as identifiers, for example, as a key in a HashMap or a path of a file. If you could modify them, the key would change and other users of this key will need to stay updated. This would also pose a security threat. Imagine if some user modified the String identifier. Now other users cannot use it.
- Thread Safety: Since they cannot be modified, they can be shared between threads freely, without the need to synchronize.
Access Modifiers
Each variable and class are given an access specifier. If no specifier is given, the default specifier is used.
public - Visible to the world
protected - Visible to classes within same package, or a subclass
default(no specifier) - Visible only to classes within the same package
private - Visible only to the containing class
[4]
These can be used for security. For example, let’s say you have a Car class with the function start(). The car class will need to check if there is enough battery power available, through a variable called batteryPower . This variable does not need to be accessed by outside classes, so it can be private. This way no outside class can maliciously modify the battery level of the car.
Lambda Expressions
These were introduced in Java 8, and bring functional programming to Java. It is rare to be asked about them, and if you haven’t touched them before, it is safe to tell your interviewer.
Generics
Most people don’t use Generics in the interview, and that’s fine. However, if you are good at writing Java with generics, we recommend using them. It will stand out to the interviewer.
[1] Jeffrey S. Carroll, CMU (www.cs.cmu.edu/~jcarroll/15-100-s05/supps/basics/h…)
[2] O’Reilly “Client-Server Web Apps with JavaScript and Java” (www.safaribooksonline.com/library/view/client-serv…)
[3] Web Based Programming Tutorials (www.webbasedprogramming.com/Java-Unleashed-Second-…)
[4] Java Modifiers | Let’s Programming (http://key-to-programming.blogspot.com/2015/09/jav…)
Big O for Beginners
The Big O notation is the most common measure of an algorithm’s performance. In interviews, you will have to calculate an algorithm’s time complexity and space complexity. The Big O notation is the way to describe your time and space complexity.
Let us first discuss time complexity. We will go over space complexity later.
Measure of Growth
The first thing to note is that the complexity is a measure of growth. Time complexity measures the following: as the size of input grows, how will the algorithm’s execution time grow? For example, let us take the following function:
void print(int[] a) {
for (int i = 0; i < a.length; i ++) {
print "Next Number:"
print a[i]
}
}
Here, the execution time is directly dependent on the size of the input array a []. If a double’s in size, the execution time will double. This is a directly proportional relationship. In terms of Big O, we call it O(n) time complexity.
To see how we came up with O(n) , let’s assume that each statement takes 1ms to execute. The execution time of the function will be:
a.length * 2 , because we execute 2 print statements for each element in a.
So, the execution is O(a.length2)* . But, we drop any constant multipliers from it, because we only care about how the execution time grows with a.length. So, the time complexity becomes O(a.length) or O(n) if the length of the array is n.
So, O(C*n) = O(n) , where C is a constant.
Now, lets add a couple lines to the function above:
function print(int[] a) {
print "Start"
for (int i = 0; i < a.length; i ++) {
print "Next Number:"
print a[i]
}
print "End"
}
Now, the run time is O(a.length2 + 2)* . Again, we drop any constant additions to the runtime, because they are unaffected by growth in the input array. So the time complexity remains O(n) .
From what we learned above, let’s try to find the time complexities of the following functions:
Simple nested loop:
function print(int[] a) {
print "Start"
for (int i = 0; i < a.length; i ++) {
for (int j = 0; j < a.length; j++) {
print a[i]
}
}
print "End"
}
Answer: O(n^2 + 2) , which is just O(n^2)
function print(int[] a) {
print "Start"
for (int i = 0; i < a.length; i ++) {
for (int j = 0; j < a.length; j++) {
print a[i]
}
print a[i]
}
print "End"
}
Answer: O(n^2 + n + 2) , which is O(n^2) . Why? While adding, we not only drop constants, we also drop any smaller degree variable. In this case, n^2 is greater than n , so we drop the n that was added. This is because as the input size (n) grows, n^2 will dominate the growth and n will not matter.
Here are some time complexities, which get larger as we go down:
O(1)
O(log(n))
O(n)
O(n * log(n))
O(n^2)
O(n^2 * log(n))
O(n^3)
.
.
O(2^n)
O(n^n)
… and s o on
Note: The log(n) here is base 2. We usually use log base 2 in time complexities. This is because a lot of algorithms divide tasks into 2, which leads to Log base 2 complexities. We will see those later in the course.
Applying what we learned above, we have the following results:
O(n + n) =O(n)
O(nlogn + n^2) = O(n^2)
O(nlogn + n^2 + n + logn) = O(n^2)
Worst Case
We usually care about the worst case time. What does that mean? Let’s take this function which searches for a value in an array:
boolean find(int[] a, int target) {
for (int i = 0; i < a.length; i++) {
if (a[i] == target) {
return true;
}
}
return false;
}
Here, if target is the first element in a, we will only execute the loop once. So in the best case, the algorithm will run in 1 time. In the worst case, we will have to go through all the elements in the array, which will take a.length time. This is the time we care about. The worst case tie complexity is hence O(n) .
Space Complexity
Space Complexity is very similar to Time Complexity, except that we consider the amount of memory used. If we allocate a constant amount of memory in a function, and the memory allocated (variables created) don’t depend on the size of the input, then that is constant space - or O(1) space.
On the other hand, if the amount of memory we use depends on the size of the input, it is not constant space. Let’s look at the following example:
int[] reverseArray(int[] a) {
int[] result = new int[a.length];
for (int i = 0; i < a.length; i++) {
result[a.length - 1 - i] = a[i];
}
return result;
}
In this example, we allocate memory equal to the size of the input. The higher the input size, the more space this function will take. The space complexity is hence O(n) .
Let’s modify the function above:
int[] reverseArray(int[] a) {
int[] result = new int[a.length];
for (int i = 0; i < a.length; i++) {
result[a.length - 1 - i] = a[i];
}
int[][] 2DArray = new int[a.length][a.length/2];
// do something with 2DArray
return result;
}
The function above has O(n^2) space complexity. Why? The function takes O(n + n(n/2))* space -> O( n ) on the result array and O( n(n/2)* ) on 2DArray. O(n + n(n/2))* is O(n + n^2/2) . Since we drop smaller added values, it becomes O(n^2/2). Since we drop any constants multiplied to it, it becomes O(n^2).
We can also reverse the array by modifying its contents. This will take O(1) space:
int[] reverseArray(int[] a) {
for (int i = 0; i < a.length/2; i++) {
int temp = a[i];
a[i] = a[a.length - 1 - i];
a[a.length - 1 - i] = temp;
}
return a;
}
In the function above, we did not allocate any space dependent on the size of a . This is hence constant or O(1) space. Note that this function modified the input, while the previous one did not.
Now that you know the basics, you can get better by practicing complexities of problems we cover in the course.
Practice the ESTCV Approach
5 Step Approach to leave your interviewer starstruck
The biggest mistake we see candidates make is not approaching the problem properly.
If I see you perform the following steps well, I will advocate to hire you. And most interviewers will too.
- Write Examples and Clarify the Question : You need to write examples, and in the process, ask questions that unearth the actual problem the interviewer wants you to solve.
- Come up with Solutions Come up with solutions and explain them to the interviewer, and once the interviewer seems to settle on one, write down simple steps, not more than a few lines. Doing this makes it clear (to both of you) what you will code for the rest of the interview.
- Write down Test cases When an interviewer sees you do this, they know you are legit. Quickly jot down key test cases.
- Write Code Write the actual code. Make liberal use of helper functions.
- Verify code and test cases Once you are done, make sure you step through the code and make sure it works.
Going through this approach proves that you are professional and a systematic problem solver.
If you find it easier, use the acronym E.S.T.C.V (Examples, Solutions, Test Cases, Code, Verify).
We walk through this entire process in the " Traversing Array In Reverse (Using ESTCV Approach) Section "
Which Language to Use?
You are free to use any language to solve interview questions. However, you should note a few points:
- If the position is technology specific , you should use a language that shows that experience. For example, you shouldn’t use C++ for a web front-end interview.
- If your language is less mainstream (like Ruby or Kotlin), interviewers might have a hard time judging your code.
- In low level languages like C, it takes more work to implement algorithms like graph search. This is because of lack of standard data structure libraries and in-built memory management. C++ is ok though.
We recommend using the Big 4 - Java , Python, C++ or JavaScript as your language. They are universally known, and have enough abstraction for solving interview questions in good time.
Behavior Tips
Here are some basic tips to remember. These might seem small, but often are the deciding factor in hiring you.
- Talk while coding - Long gaps are bad, especially in phone interviews. Rule of thumb: don’t have silences longer than 1 minute.
- Ask lots of questions - The interviewer expects you to ask questions that clarify requirements. That is a basic skill they are trying to assess.
- Be very humble - If the interviewer suggests something, show that you are open to suggestions and improvement. If you don’t know stuff, say it. That’s ok.
- Your tone should be polite and slow - The interviewer should want to work with you, and should be able to clearly understand you.
- Do not over advocate your solution - A lot of times interviewers have a particular solution in mind and are not able to grasp other solutions. Thats their fault, we know. However, if you argue too much, it is usually a red flag. They are in a position of power after all. Instead, be open to other solutions, and suggest that yours could work too with concrete examples
- Slow down - you don’t need to hurry into the solution, no one is timing you. Yes, you want to finish coding in good time, but if you don’t plan out your solution first, you will end up implementing the wrong solution - and that’s worse.
- Ask questions about the job - Ask about the work culture, team structure, technologies used, hierarchy, etc. You can also ask personal questions to the interviewer like - how long have you been here, what do you like about the company, etc. The interviewer should know that you are genuinely interested in working with them and the company.
Why Sharding is the Swiss Army Knife of System Design Interviews
Sharding is the Swiss Army Knife of Scaling things. You can use it to scale a lot of things.
Sharding essentially means splitting things into small pieces and making them work together. You put each piece on a different machine and figure out some logic to determine which piece is in which machine.
Why do we call this Horizontal Scaling? Because we are scaling by adding more machines. Vertical Scaling means scaling by adding more memory or processing power to a single machine.
What can you scale using Sharding?
Distributed Database
Distributed Cache
Distributed Hash Table
Distributed Key-Value Stores
Even Relational Databases can be scaled by splitting into shards
So if an interviewer asks you to scale a social networking application, you can scale the database (User Profiles, Friend Relationships, etc.) by using sharding.
Or if they ask you how you will scale the in-memory cache, you can use the same concepts.
Or if they ask how you can distribute the processing of your algorithm over many machines, you can use the same concepts as well. We describe one such approach in the MapReduce section.
Optional Article: Distributed Caching Using Memcached
Memcached is one of the best ways of speeding up lookups. Most good systems have memcached or some sort of distributed cache. In later weeks, we use this knowledge to design faster web applications.
Here is the original Memcached article that was written for the Linux Journal. It is narrated in a casual way, and it shows how the author made sharding decisions and how it improved his site.
Feel free to skim through it, a lot of details are not relevant for interviews:
http://www.linuxjournal.com/article/7451
DP Myths
Why are we talking about DP myths?
Because DP is often overrated by candidates.
We hear candidates make the following statement:
"I am good at all topics except for hard Dynamic Programming (DP) problems. That is the reason I am not ready for interviews".
First, DP is a dying class of problems in interviews. Google and Facebook actively discourage DP-only problems.
DP-Only problems: By DP problems, we mean problems that can only be solved (reasonably) using DP. As you’ll see later, DP is a very broad concept.
For other companies that still ask them, we estimate that around 3% of algorithm questions will be DP-only. That is 1 interview in 30. The reality is - if you implement one solution in a suboptimal way, you will still get an offer if you do well in other interviews. So if you were really good at all other topics, you should be getting offers left and right.
Myth #1: Hard DP problems are commonly asked.
When people think of Dynamic Programming, they are usually talking about hard DP problems. These are not very common.
Because these problems are hard, they are feared. So people spend a lot of time working on them.
The fact is, DP covers a lot of grounds. Anytime we save a subproblem and re-use it, we are using DP. We often use DP without realizing it. For example, here are problems in other sections of this course that use DP:
1. Any DFS Problem: Yes, Depth First Search uses DP! Who knew! When we check the state of each node, we are storing and re-using the same subproblem.
2. Subarray Sum Problems Question #1: Given an array of integers, find the contiguous subarray with the maximum sum. The array can contain both negative and positive integers.
3. Max Diff Homework #1: How much money could you have made with 2 trades?
4. Backtracking Problems Question #2: Maze with 4 directional Movement
5. Topological Sort Homework #1: Diameter of Graph: Given a graph, find the length of the longest path among any two vertices.
In addition, a lot of “DP problems” can be solved without DP. Would you categorize those as DP problems? Hard to say.
Even if you solve those problems using a non-DP approach, write good code and communicate well, you’ll get a good score. And sure, if you can use DP for better performance, that’s icing on the cake.
Myth #2: Advanced Problem Fallacy
This is the belief that practicing really hard problems will somehow make it easier to solve interview problems.
After all, if I can solve problems that are harder than Google and Facebook problems, then interviews are a piece of cake, right? Wrong. Those extra hard problems usually have nothing to do with interview-level problems. And they take up a lot of time. If you are intellectually curious, that’s fine. But if you think it will help you land your dream job, you should reconsider it.
Unfortunately, websites like Geeks4Geeks thrive by showing extra hard problems. The more people stay on their website, the more they benefit. But it’s not reflective of what the industry asks in interviews.
Myth #3: Optimization Snobs
Unfortunately, we see people in LeetCode forums obsess over small performance gains with a particular solution. Way too many people obsess over nitty-gritty details of algorithms instead of coming up with a well-performing working solution. This takes time away from practicing more algorithms.
So what should we do?
For DP, we recommend going over this section and practicing its problems. After that, you will encounter problems throughout this course that use DP. You will get comfortable with it. Then, you can go over other common problems online. Only then do we suggest looking at advanced DP problems.