如何应对亚马逊面试中提出的这一挑战？
How does one approach this challenge asked in an Amazon Interview?
我正在努力优化过去涉及 DAG 的亚马逊面试问题。
这是我试过的（代码很长，我宁愿解释一下）-
基本上，因为该图是一个 DAG，并且因为它是一种传递关系，所以对每个节点进行简单遍历就足够了。
所以对于每一个节点我都会通过传递性遍历所有的可能性得到结束顶点然后比较这些结束顶点得到
最吵闹的人。
在我的第二步中，我实际上已经找到了一个这样的（也许是唯一的）最吵闹的人，因为他在第 2 步中遍历了所有的顶点。所以我把所有这些都记在一个映射中并且将遍历的顶点标记为已访问。
所以我基本上是在为图维护一个邻接表，一个visited/non访问映射和一个输出映射（每个顶点最嘈杂的人）。
- 通过这种方式，当我得到一个查询时，我将不必重新计算任何东西（在重复查询的情况下）。
以上代码有效，但由于我无法使用测试用例进行测试，因此 may/may 未超过时间限制。有没有更快的解决方案（可能使用 DP）。我觉得我没有充分利用传递和反对称条件。
显然，我不会检查一个人比现在的人富裕的情况。但是例如，如果我有像 - (1,2)(1,3)(1,4)...等这样的对，也许还有 (2,6)(2,7)(7,8) 等，那么如果我我想找到一个比 1 更富有的人，我已经遍历了 1 的每个邻居，然后我猜也是每个邻居的邻居。这只在我存储结果时完成一次。
Question Part 1
Question Part 2
编辑（添加问题文本）-
鲁纳克今年毕业。而且他会变得富有。非常丰富。如此富有以至于他决定拥有
一种衡量他的财富的结构化方法。因此他在城里四处询问人们的财富，
并记下该信息。
如果 Xi 比 Yi 拥有更多财富，Rounaq 会记下这对 (Xi; Yi)。他还记下
每个人的安静程度 Ki。 Rounaq 认为嘈杂的人是一种滋扰。因此，对于
他的每个朋友 Ai，他想确定那些拥有
财富多于艾。
请注意，"has more wealth than" 是一个传递和反对称的关系。因此如果a有更多的财富
比b多，b比c多，那么a比c多。此外，如果 a 的财富多于
b，那么b不可能比a拥有更多的财富。
你在这个问题中的任务是帮助 Rounaq 确定那些吵闹的人中最吵闹的人。
鉴于 Rounaq 从镇上收集的信息，他的每个朋友 ai 都可以获得更多财富。
输入
第一行包含T：测试用例的数量
每个测试用例具有以下格式：
N
K1 K2 K3 K4 : : : Kn
米
X1 Y1
X2 Y2
。 . .
。 . .
XM YM
问
A1
A2
。 . .
。 . .
AQ
N：镇上人数
M: Rounaq获得财富的对数
信息
问：Rounaq 的好友数量
Ki：第i个人的安静程度
习； Yi：Rounaq 记下的对（不同值对）
艾：Rounaq的第i个朋友
对于 Rounaq 的每个朋友，打印一个整数 - 所要求的最吵闹的人的安静程度，或者如果没有比该朋友更富有的人，则为 -1。
对 X、Y 对执行 topological sort。然后从最富有的向下迭代最不富有的，存储目前看到的最吵的人：
less wealthy -> most wealthy
<- person with lowest K so far <-
然后对于每个查询，二分查找第一个比朋友有更多财富的人。我们存储的值是最吵的人比朋友有更多的财富。
更新
看来我们不能依赖允许完整拓扑排序的数据。在这种情况下，遍历从已知最大财富到最小财富的图表部分，为每个访问过的人存储迄今为止看到的最嘈杂的人。您提供的示例可能类似于：
3 - 5
/ |
1 - 2 |
/ |
4 --
遍历：
1 <- 3 <- 5
1 <- 2
4 <- 2
4 <- 5
（输入）
2 1
2 4
3 1
5 3
5 4
8 2 16 26 16
(疑问与解答)
3 4 3 5 5
16 2 16 -1 -1
我正在努力优化过去涉及 DAG 的亚马逊面试问题。
这是我试过的（代码很长，我宁愿解释一下）-
基本上，因为该图是一个 DAG，并且因为它是一种传递关系，所以对每个节点进行简单遍历就足够了。
所以对于每一个节点我都会通过传递性遍历所有的可能性得到结束顶点然后比较这些结束顶点得到 最吵闹的人。
在我的第二步中，我实际上已经找到了一个这样的（也许是唯一的）最吵闹的人，因为他在第 2 步中遍历了所有的顶点。所以我把所有这些都记在一个映射中并且将遍历的顶点标记为已访问。
所以我基本上是在为图维护一个邻接表，一个visited/non访问映射和一个输出映射（每个顶点最嘈杂的人）。
- 通过这种方式，当我得到一个查询时，我将不必重新计算任何东西（在重复查询的情况下）。
以上代码有效，但由于我无法使用测试用例进行测试，因此 may/may 未超过时间限制。有没有更快的解决方案（可能使用 DP）。我觉得我没有充分利用传递和反对称条件。
显然，我不会检查一个人比现在的人富裕的情况。但是例如，如果我有像 - (1,2)(1,3)(1,4)...等这样的对，也许还有 (2,6)(2,7)(7,8) 等，那么如果我我想找到一个比 1 更富有的人，我已经遍历了 1 的每个邻居，然后我猜也是每个邻居的邻居。这只在我存储结果时完成一次。
Question Part 1
Question Part 2
编辑（添加问题文本）-
鲁纳克今年毕业。而且他会变得富有。非常丰富。如此富有以至于他决定拥有 一种衡量他的财富的结构化方法。因此他在城里四处询问人们的财富， 并记下该信息。 如果 Xi 比 Yi 拥有更多财富，Rounaq 会记下这对 (Xi; Yi)。他还记下 每个人的安静程度 Ki。 Rounaq 认为嘈杂的人是一种滋扰。因此，对于 他的每个朋友 Ai，他想确定那些拥有 财富多于艾。 请注意，"has more wealth than" 是一个传递和反对称的关系。因此如果a有更多的财富 比b多，b比c多，那么a比c多。此外，如果 a 的财富多于 b，那么b不可能比a拥有更多的财富。 你在这个问题中的任务是帮助 Rounaq 确定那些吵闹的人中最吵闹的人。 鉴于 Rounaq 从镇上收集的信息，他的每个朋友 ai 都可以获得更多财富。 输入 第一行包含T：测试用例的数量 每个测试用例具有以下格式：
N
K1 K2 K3 K4 : : : Kn
米
X1 Y1
X2 Y2
。 . .
。 . .
XM YM
问
A1
A2
。 . .
。 . .
AQ
N：镇上人数
M: Rounaq获得财富的对数 信息
问：Rounaq 的好友数量
Ki：第i个人的安静程度
习； Yi：Rounaq 记下的对（不同值对）
艾：Rounaq的第i个朋友
对于 Rounaq 的每个朋友，打印一个整数 - 所要求的最吵闹的人的安静程度，或者如果没有比该朋友更富有的人，则为 -1。
对 X、Y 对执行 topological sort。然后从最富有的向下迭代最不富有的，存储目前看到的最吵的人：
less wealthy -> most wealthy
<- person with lowest K so far <-
然后对于每个查询，二分查找第一个比朋友有更多财富的人。我们存储的值是最吵的人比朋友有更多的财富。
更新
看来我们不能依赖允许完整拓扑排序的数据。在这种情况下，遍历从已知最大财富到最小财富的图表部分，为每个访问过的人存储迄今为止看到的最嘈杂的人。您提供的示例可能类似于：
3 - 5
/ |
1 - 2 |
/ |
4 --
遍历：
1 <- 3 <- 5
1 <- 2
4 <- 2
4 <- 5
（输入）
2 1
2 4
3 1
5 3
5 4
8 2 16 26 16
(疑问与解答)
3 4 3 5 5
16 2 16 -1 -1