It seems like coding interviews are only getting harder, and preparing for them isn’t an easy task. There’s no limit to the kind of questions that may be presented to you in an interview, and many of them aren’t easy. The “hardest” questions will be different for each person. What comes easily to you may be extremely difficult for someone else, and vice versa.
No matter what your “hardest” questions are, it’s crucial to prepare yourself for your coding interview. We talked to junior and senior developers for their take on the hardest coding interview questions, and we compiled the top five into a list. Today, we’ll explore that list in more detail and give you some tips on how to prepare.
We’ll cover:
- How to design a garbage collector
- Coin change problem
- Dining philosophers problem (multithreading)
- Why use these programming best practices
- Implement LRU cache
- Next steps to prepare for interviews
How to design a garbage collector
If you’ve never heard of it, the garbage collector problem is known to be very difficult. Garbage collection is a topic that most people don’t learn about in school, and the related material is extremely dense. Learning about garbage collection involves a lot of theory, which can be overwhelming. No matter what language you work in, it’s crucial to know the ins and outs of your preferred language to solve this problem effectively.
Don’t be afraid to ask your interviewer questions as you work through this problem. Remember that your interviewer is there to help you and wants to see you do well. It’s common for interviewers to give you little seeds of information to help push you in the right direction.
Note: Garbage collection questions are especially common in core and advanced Java interviews, but they are also important to know for other programming languages.
Coin change problem
The coin change problem is commonly seen at Facebook and Amazon interviews. You’re given coins of different denominations and a total amount of money. From that, you need to write a function to compute the fewest number of coins that you need to make up that amount. If you can’t reach the given amount of money with any combination of the coins, you return -1.
Here are three ways you could solve this problem:
- Brute force
- Top-down Dynamic Programming with Memoization
- Bottom-up Dynamic Programming with Tabularization
Let’s take a look at the bottom-up dynamic programming with tabularization solution in C++:
#include <iostream>
using namespace std;
int countChange(int denoms[], int denomsLength, int amount) {
// Edge cases
if(amount <= 0 || denomsLength <= 0)
return 0;
int i, j, x, y;
// We need n+1 rows as the table
// is constructed in bottom up
// manner using the base case 0
// value case (n = 0)
int lookupTable[amount + 1][denomsLength];
// Fill the enteries for 0
// value case (n = 0)
for (i = 0; i < denomsLength; i++)
lookupTable[0][i] = 1;
// Fill rest of the table entries
// in bottom up manner
for (i = 1; i < amount + 1; i++) {
for (j = 0; j < denomsLength; j++) {
// Count of solutions including denoms[j]
x = (i - denoms[j] >= 0) ? lookupTable[i - denoms[j]][j] : 0;
// Count of solutions excluding denoms[j]
y = (j >= 1) ? lookupTable[i][j - 1] : 0;
// total count
lookupTable[i][j] = x + y;
}
}
return lookupTable[amount][denomsLength - 1];
}
// Driver Code
int main() {
int denoms[4] = {25,10,5,1};
cout << countChange(denoms, 4, 10) << endl;
}
For each iteration of the inner loop, we get the solution with denoms[j] and store it in x. We also get the solution without denoms[j] and store it in y. By doing this, we’re able to reference earlier solutions to avoid duplicate computations.
For each coin in the denomination, there can only be two possibilities: to include it or exclude it. We know that if the coin, denom[j], is larger than amount, then x is set to 0 since including it into consideration is impossible.
The time complexity is *O(amount * denomsLength), which is the number of for loop iterations.
Note: Each of these three methods includes time complexity, meaning that time complexity is an important concept to understand to succeed at the coin change problem.
Dining philosophers problem (multithreading)
The dining philosophers problem is commonly used in concurrent algorithm design to demonstrate issues with synchronization and the techniques to solve them. The problem states that there are five philosophers sitting around a circular table. The philosophers must alternatively think and eat.
Each philosopher has a bowl of food in front of them, and they require a fork in each hand to eat. However, there are only five forks available. You need to design a solution where each philosopher can eat their food without causing a deadlock.
With this problem, it’s common for developers to overlook the idea that it’s not really asking about a real-world scenario, but rather illustrating the kinds of problems you could run into in threaded program executions and/or negligent handling of locks. The idea is to get you to think about limitations and proper ordering to accomplish this task in the most efficient way.
To prepare for this question, you should dive deeper into synchronization, concurrency control, and semaphores.
Here are two possible ways to solve this problem:
- Limiting the philosophers that are about to eat
- Reordering the fork pick-up
Let’s look at the reordering the fork pick-up solution in Java:
public class DiningPhilosophers2 {
private static Random random = new Random(System.currentTimeMillis());
private Semaphore[] forks = new Semaphore[5];
public DiningPhilosophers2() {
forks[0] = new Semaphore(1);
forks[1] = new Semaphore(1);
forks[2] = new Semaphore(1);
forks[3] = new Semaphore(1);
forks[4] = new Semaphore(1);
}
public void lifecycleOfPhilosopher(int id) throws InterruptedException {
while (true) {
contemplate();
eat(id);
}
}
void contemplate() throws InterruptedException {
Thread.sleep(random.nextInt(500));
}
void eat(int id) throws InterruptedException {
// We randomly selected the philosopher with
// id 3 as left-handed. All others must be
// right-handed to avoid a deadlock.
if (id == 3) {
acquireForkLeftHanded(3);
} else {
acquireForkForRightHanded(id);
}
System.out.println("Philosopher " + id + " is eating");
forks[id].release();
forks[(id + 1) % 5].release();
}
void acquireForkForRightHanded(int id) throws InterruptedException {
forks[id].acquire();
forks[(id + 1) % 5].acquire();
}
// Left-handed philosopher picks the left fork first and then
// the right one.
void acquireForkLeftHanded(int id) throws InterruptedException {
forks[(id + 1) % 5].acquire();
forks[id].acquire();
}
}
In this solution, you make any one of the philosophers pick up the left fork first instead of the right one. It doesn’t matter which philosopher you choose to be left-handed and made to pick up their left fork first. In our solution, we chose the philosopher with id=3 as our left-handed philosopher.
Why use these programming best practices
While learning about programming, you typically learn some “best practices.” The most efficient developers implement certain practices into their coding process, which helps them ensure that their code is the best it can be in both function and form.
After years of experience with programming, you tend to know the practices you should avoid and the ones you should adopt. You may have a general idea of why some practices are better than others, but stumble when it’s time to explain the reasoning.
A few examples of best practices include:
- Comment your code often
- Recognize and remove duplicate code
- Group by features in React
- Avoid hidden structures in Ruby
The best way to prepare yourself for these questions is to refresh your memory on useful versus avoidable practices and the reasoning behind them. Remember that during your interview, you can talk through these questions with your interviewer.
Implement LRU cache
The Least Recently Used (LRU) cache implementation question is asked in some Google, Microsoft, and Amazon interviews, but it’s not a very common question. This question requires you to think deeper and combine two or more existing data structures.
It’s important to read the problem slowly and make sure you understand what’s being asked of you. These questions typically ask you to do a few things. Once you’ve read the problem thoroughly, you can ask your interviewer to confirm that you’re going in the right direction.
Before tackling one of these problems, make sure you understand what cache is. LRU is a common caching strategy that defines the policy to remove elements from the cache to make room for new ones when the cache is full. This means that it discards the least recently used items first.
Next steps to prepare for interviews
The questions we covered today are just a few of the many difficult coding interview questions. The questions are supposed to be difficult, and they can even stump the most seasoned developers. It’s important to begin your interview prep early, so you have the opportunity to prepare as much as possible. A few more difficult problems include:
- Find the median from a data stream
- Search in rotated sorted array
- Minimum knight moves
- And many more
Begin preparing for your coding interview today with Educative’s text-based interview prep course. Our team of experts has incorporated the most commonly asked interview questions at top tech companies into a carefully crafted set of scenarios for you to learn from. You can practice as you learn with hands-on coding environments directly inside your browser. Our coding interview course has helped developers prepare for interviews with top tech companies like Netflix, Facebook, Microsoft, Amazon, and Google.
By the end, you’ll be ready to interview with confidence!
Happy learning!
Top comments (1)
Good overview of how to solve these questions, but remember lesson 0 is always "Read the problem statement carefully."
There's no pennies here in Canada, so remove that from the denominations list and try to return 12 cents: