我最近接受了一些面试，被问到一些规模问题是很正常的。例如，您有一个长单词（字典）列表和字符列表作为输入，设计一个算法来找出一个最短的单词，该单词在dict中包含字符列表中的所有字符。然后面试官问如何将你的算法扩展到多台机器上。另一个例子是，您已经为城市的十字路口设计了一个交通灯控制系统。您如何将此控制系统扩展到具有许多十字路口的整个城市。对于这种"规模"问题，我始终一无所知，欢迎任何建议和意见。
你的第一个问题与第二个问题完全不同。事实上，城市交通信号灯的控制是地方操作。附近有可以调谐的盒子和光学传感器，可以在灯上检测等待的汽车。我想如果你需要优化流的一些目标函数，你可以将信息路由到服务器进程，然后它可以成为如何在多台机器上扩展这个服务器进程。
我不是分布式算法设计方面的专家，分布式算法跨越了整个研究领域。但本科生面试中的问题通常不是那么专业。毕竟，他们不是在采访专门从事这些领域的研究生。以你的第一个问题为例，它确实很笼统。
通常，这些问题涉及多个数据结构（多个列表和哈希表）交互（连接，迭代等）以解决问题。一旦你制定了一个基本的解决方案，扩展基本上就是在许多机器上复制该解决方案，并同时使用输入的分区运行它们。（当然，在许多情况下，如果不是不可能的话，这很困难，但面试问题不会那么难）
也就是说，您有许多相同的工作线程同时拆分输入工作负载和工作，但这些工作线程是不同计算机中的进程。这带来了通信协议和网络延迟等问题，但我们将忽略这些以获得基础知识。
最常见的扩展方法是让工作人员持有较小数据结构的副本，并让他们将较大的数据结构拆分为工作负载。在您的示例（第一个问题）中，字符列表的大小很小，因此您将为每个工作人员提供列表的副本，以及字典的一部分来处理列表。请注意，反之则行不通，因为每个持有字典的工作线程总共会消耗大量内存，并且不会为您节省任何扩展。
如果你的问题变得更大，那么你可能需要更多的分割层，这也意味着你需要一种方法来组合来自接受分割输入的工作线程的输出。这是MapReduce框架及其衍生物的一般概念和动机。
希望对你有帮助...
对于第一个问题，如何搜索包含字符列表中所有字符的单词，这些单词可以在不同计算机上同时运行。（还不是最短的）。我会以map-reduce为基础来做。
首先，这个问题实际上是可以同时在不同的机器上运行。这是因为对于数据库中的每个单词，您可以在另一台机器上检查它（因此要检查另一个单词，您不必等待上一个单词或下一个单词，您可以将每个单词发送到不同的计算机进行检查）。
使用 map-reduce ，您可以将每个单词map为value，然后检查它是否包含字符列表中的每个字符。
Map(Word, keyout, valueout){
//Word comes from dbase, keyout & valueout is input for Reduce
if(check if word contain all char){
sharedOutput(Key, Word)//Basically, you send the word to a shared file.
//The output shared file, should be managed by the 'said like' hadoop
}
}
运行此Map后，您可以从共享文件中的数据库中获取所需的所有 Word。至于reduce步骤，您实际上可以使用一些简单的步骤来根据其长度来减少它。还有多达，你得到最短的。
至于第二个问题，我想到了多线程。这实际上是一个彼此无关的问题。我的意思是每个十字路口都有自己的计时器，对吧？因此，为了能够处理大量的交叉点，您应该使用多线程。
简单的术语是使用处理器中的每个内核来控制每个交叉点。而不是一个一个地循环遍历所有交叉点。您可以将它们重新定位在每个内核中，以便过程更快。