algorithm - 回答这种调度算法场景的最佳方式是什么？

Question

这是我在面试中遇到的问题。解释起来有点困难，请耐心等待。

想象一下铁路售票柜台。

• 最初有 3 个计数器。
• 有一名保安人员检查人员，以免有人越线。
• 每个柜台有 2 个人在排队等候。排队等候的人按照字母顺序进来了。
• 第 4 个新柜台正在营业。并且有两个新人 G 和 H 即将加入该行。

您是保安，现在您可以选择可以在新柜台处理的人员。

计数器标记为 1、2、3 和 4(蓝色框)。排队等候的人被标记为A、B、C等。这里 A 先来，然后是 B，然后是 C，依此类推。

我被要求给出答案以及答案背后的逻辑。面试官对我的回答不断提出更多问题。

例如 - 当我说，

• 我会叫 D 和 E 搬到第 4 个柜台；
• G站在A后面，H站在B后面

面试官争辩说E和G怎么得到相同的偏好(优先级)。

经过几分钟这样的争论，我告诉我这似乎是一个简单的调度问题，如果有一个公共(public)队列并且保安人员将队列中的下一个人发送到 FCFS 之后的空柜台，则可以轻松解决。

然而，面试官并没有留下深刻的印象。

有没有我错过的不同方法？回答此类问题的正确方法是什么？

PS:这一轮我没过关:(

Answer 1

考虑到我在该主题方面的背景以及我在该行业的多年经验，我在这里承认...:-) ...我有一个关于为什么你没有进入下一轮的假设:事实并非如此很多程序设计问题都是行为问题。

这类面试问题通常不是关于解决方案，而是关于您解决问题的方法。我(面试官)给了你一个有几种开放可能性的问题。首先，这“显然”是操作系统多处理情况的隐喻。我想要一个理想的候选人

1. 质疑计票器范式对操作系统情况的适用性:现实世界中存在哪些不适用于进程队列的假设？
2. 确定评估解决方案的标准。
3. 询问有关允许的操作的更多信息。
4. 询问服务时间、到达时间等的分布情况，以展示对调度范式的了解。
5. 询问成本和权衡。

有了对问题的更好描述，现在我希望您通过解决方案工作，始终让您的客户(我)参与一般方法和细节。例如，这是敏捷方法的关键部分。另外，我想看看你如何解释我不明白的事情。

请注意，第 2 项非常重要:如果您的真正客户是腐败的保安人员，在轮类结束时退休，那么正确的解决方案可能是举行贿赂竞标战进入开放柜台。

这是你下次面试的作业:要使你给定的解决方案成为一个好的解决方案，需要哪些假设？您如何与客户一起验证这些假设？

我的直接问题包括上述问题，以及......

• 什么是好的解决方案？最佳解决方案？ Not Acceptable ？
• 将一个人从他们所在的地方转移到另一个地方的费用是多少？
  • 我可以将某人从窗口队列中带出并重新加入队列吗？
  • 我可以更改队列中的顺序(即“队列”的常见用法而不是规范的数据结构)吗？
  • 我可以将某人从一个窗口线直接切换到另一个窗口线吗？
• 我必须服务每一位客户吗？
• 这是整个队列，还是一个连续的过程？

这是我的打字 catch 我的思维过程的地方，一个合理的停止点。