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.
1. 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.
2. Coin Change Problem
The coin change problem is commonly seen in 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 solution using bottom-up dynamic programming with tabularization 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.
3. The Dining Philosophers Problem (Multi-Threading)
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 alternately 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 the 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 who are about to eat.
Reordering the fork pick-up.
Let’s look at the solution that reorders the fork pick-up 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.
4. 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 you can talk through these questions with your interviewer.
5. How To Implement an 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 a 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.
Source: Medium
The Tech Platform