近期 FAANG 面试中最难的 5 道编程题
编程面试似乎越来越难，准备起来也绝非易事。面试中可能会遇到各种各样的问题，而且很多问题都不容易。“最难”的问题因人而异。对你来说轻而易举的问题，对别人来说可能难如登天，反之亦然。
无论你认为“最难”的问题是什么，做好编程面试的准备都至关重要。我们采访了一些初级和高级开发人员，了解他们对最难编程面试题的看法，并整理出了排名前五的难题。今天，我们将更详细地探讨这些难题，并为你提供一些准备技巧。
我们将涵盖以下内容：
如何设计垃圾收集器
如果你从未听说过垃圾回收问题，那么它确实非常棘手。垃圾回收是大多数人在学校里不会学到的知识，而且相关资料极其晦涩难懂。学习垃圾回收涉及大量的理论知识，这可能会让人感到不知所措。无论你使用哪种编程语言，要想有效地解决这个问题，都必须深入了解你所使用语言的方方面面。
在解决这个问题时，不要害怕向面试官提问。记住，面试官是来帮助你的，他们希望看到你表现出色。面试官通常会提供一些线索，引导你朝着正确的方向前进。
注意：垃圾回收问题在 Java 核心和高级面试中特别常见，但对于其他编程语言来说，了解垃圾回收也很重要。
找零问题
找零问题经常出现在 Facebook 和亚马逊的面试中。题目会给出不同面额的硬币和一个总金额。你需要编写一个函数，计算出凑齐这个金额所需的最少硬币数量。如果无法用任何硬币组合凑齐给定的金额，则返回错误-1。
以下是解决此问题的三种方法：
- 蛮力
- 自顶向下动态规划与记忆化
- 基于表格的自底向上动态规划
让我们来看一下 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;
}
在内层循环的每次迭代中，我们都会获取包含参数的解denoms[j]并将其存储在变量中x。同时，我们也会获取不包含参数的解并将denoms[j]其存储在变量中y。通过这种方式，我们可以引用之前的解，从而避免重复计算。
对于该面额的每种硬币，只有两种可能：包含或排除。我们知道，如果硬币denom[j]大于amount，则x设置为 0，因为不可能将其纳入考虑范围。
时间复杂度为 *O(金额 * 词缀长度)，即 for 循环迭代次数。
注意：这三种方法都包含时间复杂度，这意味着理解时间复杂度是解决找零问题的重要概念。
哲学家就餐问题（多线程）
哲学家就餐问题常用于并发算法设计中，以演示同步问题及其解决方法。该问题描述五位哲学家围坐在一张圆桌旁，他们必须交替进行思考和用餐。
每位哲学家面前都有一碗食物，他们需要双手各拿一把叉子才能进食。然而，只有五把叉子可用。你需要设计一个解决方案，使每位哲学家都能吃完食物，且不会造成死锁。
开发者在面对这个问题时，常常会忽略一个关键点：它并非真正考察一个真实世界的场景，而是为了说明在多线程程序执行和/或锁管理不善的情况下可能遇到的问题。其目的是引导你思考限制因素以及完成任务的正确顺序，从而以最高效的方式完成任务。
为了准备回答这个问题，你应该深入了解同步、并发控制和信号量。
以下是解决此问题的两种可能方法：
- 限制即将进食的哲学家
- 重新排列叉车拾取装置
让我们来看看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();
}
}
在这个解决方案中，你需要让任意一位哲学家先拿起左边的叉子，而不是右边的。选择哪位哲学家作为左撇子并让他们先拿起左边的叉子都无所谓。在我们的解决方案中，我们选择了 id=3 的哲学家作为左撇子哲学家。
为什么要使用这些编程最佳实践？
学习编程时，你通常会学到一些“最佳实践”。最高效的开发者会将某些实践融入到他们的编码过程中，这有助于他们确保代码在功能和形式上都达到最佳状态。
多年的编程经验让你往往知道哪些做法应该避免，哪些做法应该采纳。你可能大致明白为什么有些做法比其他做法更好，但当需要解释其中的原因时，却往往语塞。
以下是一些最佳实践示例：
- 经常给你的代码添加注释
- 识别并删除重复代码
- React 中的按特征分组
- 避免在 Ruby 中使用隐藏结构
准备这些问题的最佳方法是回顾一下哪些做法是有益的，哪些做法是可避免的，以及它们背后的原因。记住，面试时你可以和面试官讨论这些问题。
实现 LRU 缓存
最少使用（LRU）缓存的实现问题在谷歌、微软和亚马逊的一些面试中会被问到，但并不常见。这类问题需要你深入思考，并将两种或多种现有的数据结构结合起来。
仔细阅读题目并确保理解题目要求非常重要。这类问题通常会要求你完成几项任务。仔细阅读题目后，你可以请面试官确认你的思路是否正确。
在着手解决这些问题之前，请确保您理解缓存的概念。LRU 是一种常见的缓存策略，它定义了当缓存已满时，如何从缓存中移除元素以腾出空间存放新元素的策略。这意味着它会优先丢弃最近最少使用的数据项。
接下来需要做的面试准备工作
我们今天讨论的问题只是众多棘手的编程面试题中的一小部分。这些问题本来就很难，甚至可能难倒最有经验的开发者。因此，尽早开始面试准备至关重要，这样你才有机会做好充分的准备。以下是一些更难的问题：
- 从数据流中找出中位数
- 在旋转排序数组中搜索
- 骑士最少步数
- 还有更多
立即使用 Educative 的文字版面试准备课程，开始备战您的编程面试。我们的专家团队精心挑选了顶尖科技公司最常问的面试题，并将其融入一系列精心设计的场景中，供您学习。您可以在浏览器中直接使用实际的编程环境进行练习。我们的编程面试课程已帮助众多开发者成功通过了 Netflix、Facebook、微软、亚马逊和谷歌等顶尖科技公司的面试。
到最后，你就能自信地参加面试了！
学习愉快！