图中节点的最长递增序列

Question

最近参加了MSFT对SDET职位的面试。第二轮面试官问了我这个问题:给定一个图的节点值中有一个数字，找出所有连通的递增序列顶点的集合。不能回忆起确切的问题..这家伙似乎非常敌视我的每一个解决方案..任何知道这类问题的人..最后的解决方案是有一个邻接矩阵..仍然不确定这将如何工作..

Answer 1

第一步是将双向边转换为有向边，只对每个边从较小的节点到较大的编号节点。请注意，结果图将是有向无环图(DAG)，因为我们不能从路径中的小-高-小数字开始。从这里开始，我们可以忽略节点编号。

我们现在已经将问题减少到了longest path problem。解决方案(在链接中详细描述)是对图执行拓扑排序，然后使用动态编程来找到最长路径。

所有这些都可以在线性时间内实现。