algorithm - 对这个面试问题感到困惑：在内存限制下在单处理器上调度计算图

Question

我最近参加了一家知名公司的 SWE/CS 职位面试。它不是专门的“编码轮”，而是标题为“领域面试”的会议，所以我假设面试官对与问题相关的讨论/高级解决方案感兴趣。

问题：

您将获得一个计算图，其中节点表示计算，边表示依赖关系，边上的值表示该边的数据大小（以 MB 为单位）（输入或输出）。X您希望将此图安排在内存MB有限的单处理器上。要执行节点/计算，输入和输出数据都应该适合处理器的 X 内存。它是针对每个节点的输入/输出数据总和 <= X 给出的。如果在任何时候数据需要存储的总数据超过 X，那么从磁盘获取数据的每 MB 数据都会产生额外的成本。（这可能发生在节点 n1 产生了需要由 n2 使用的输出，但并非 n2 的所有前辈都已运行）。你会如何安排这个图表？

我的方法/我讨论的内容：

• 我回答说“通常”这个问题对于多处理器系统是难以处理的（NP-complete），并且由于内存限制，对于单处理器系统也可能也是如此。
• 然后我提出了一种贪婪的方法，该方法基于在给定时间跟踪所有“就绪”节点，这些节点可以在其前任已执行时执行。
• 可以基于尝试最小化与内存约束相关的成本（即寻求调度具有与数据传输相关的最小成本的节点）来从几个可用/准备好的节点中调度下一个特定节点。
• 如果有多个与数据传输相关的最小成本相同的节点，则选择其中输入+输出内存需求最大的节点。

面试过程中，面试官没有提出很多建议，也没有给出任何提示或方向，他可能希望我引导哪些方向，所以结果是非常开放的。

他大部分时间都在做笔记，几乎是中立的或非常轻微的相机/紧闭的微笑。

由于问题的棘手性，我无法准确判断面试官可能一直在寻找什么——很难在你的脑海中想出一个通用的最佳算法。

后来我才知道我收到了本次会议的“否”决定。

问题：

这让我很困惑。如果我没有正确处理它，或者面试官希望人们谈论我提到的其他事情，我一直在绞尽脑汁。

我错过了什么最佳或直接的东西吗？

面试官可能一直在寻找一些通常期望知道的特定算法吗？

在会议期间，我认为鉴于问题的限制，我提供了一个合理的解决方案，并且可以深入研究面试官可能要求我做的任何方向。

但是在会议期间没有得到面试官的任何回击或建议，我很想知道我错过了什么或者我应该如何解决这个问题。

标签： algorithmgraphparallel-processingmultiprocessingscheduling