1

我最近接受了一些采访，被问到一些规模问题是很正常的。例如，您有一个很长的单词列表（dict）和字符列表作为输入，设计一个算法来找出 dict 中包含字符列表中所有字符的最短单词。然后面试官问如何将你的算法扩展到多台机器上。另一个例子是您为城市的一个十字路口设计了一个交通灯控制系统。您如何将此控制系统扩展到具有许多交叉路口的整个城市。我一直对这种“规模”问题一无所知，欢迎提出建议和意见。

4

2 回答 2

1

您的第一个问题与您的第二个问题完全不同。事实上，城市交通信号灯的控制是本地化的操作。附近有可以调整的盒子和检测等候车辆的灯顶部的光学传感器。我想如果您需要针对流的某些目标函数进行优化，您可以将信息路由到服务器进程，那么它可以成为如何在多台机器上扩展该服务器进程。

我不是分布式算法设计方面的专家，它跨越了整个研究领域。但是本科面试的问题通常不是那么专业。毕竟，他们不是在采访专门研究这些领域的研究生。以你的第一个问题为例，它确实很笼统。

通常，这些问题涉及多个数据结构（几个列表和哈希表）交互（连接、迭代等）以解决问题。一旦你制定了一个基本的解决方案，缩放基本上就是在许多机器上复制该解决方案，并同时使用输入的分区运行它们。（当然，在很多情况下，即使不是不可能，这也是很困难的，但面试问题不会那么难）

也就是说，您有许多相同的工作人员分摊输入工作负载并同时工作，但这些工作人员是不同机器中的进程。这带来了通信协议和网络延迟等问题，但我们将忽略这些以了解基础知识。

最常见的扩展方式是让工作人员持有较小数据结构的副本，并让他们将较大的数据结构拆分为工作负载。在您的示例（第一个问题）中，字符列表的大小很小，因此您将为每个工作人员提供列表的副本，以及字典的一部分以使用列表。请注意，反过来是行不通的，因为每个持有字典的工作人员总共会消耗大量内存，并且不会为您节省任何扩展。

如果您的问题变得更大，那么您可能需要更多的拆分层，这也意味着您需要一种方法来组合接受拆分输入的工作人员的输出。这是MapReduce框架及其衍生产品的一般概念和动机。

希望能帮助到你...

于 2016-03-14T05:16:44.970 回答
0

对于第一个问题，如何在不同机器上同时运行的字符列表中搜索包含所有字符的单词。（还不是最短的）。我会map-reduce以此为基础。

首先，这个问题实际上是可以在不同的机器上同时运行。这是因为对于数据库中的每个单词，您可以在另一台机器上检查它（所以要检查另一个单词，您不必等待上一个单词或下一个单词，您可以将每个单词发送到不同的计算机以进行检查）。

使用map-reduce，您可以将map每个单词作为 a 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步骤，您实际上可以使用一些简单的步骤来根据它的长度来减少它。和tada，你得到最短的。

至于第二个问题，我想到了多线程。这实际上是一个彼此无关的问题。我的意思是每个路口都有自己的计时器，对吗？所以为了能够处理大量的交叉点，你应该使用多线程。

简单的术语将使用处理器中的每个内核来控制每个交叉点。而不是逐个循环遍历所有交叉点。您可以将它们分配在每个核心中，以便该过程更快。

于 2016-03-14T06:32:10.323 回答