这是我最近在互联网上发现的面试问题:
如果要实现一个以整数数组作为输入并返回最大值的函数,您会使用冒泡排序或合并排序来实现此功能吗？如果阵列大小小于1000怎么办？如果大于1000怎么办？
这就是我的想法:
首先,使用排序来实现上述功能真的很奇怪.你可以通过一次数组找到最大的数组.其次,如果必须在两者之间做出选择,那么冒泡排序更好 - 你不必实现整个冒泡排序程序,而只需要进行第一次传递.它比时间和空间上的合并排序更好.
我的答案有什么错误吗？我错过了什么吗？
这是我最近在互联网上发现的面试问题:
你如何在Facebook上找到两个人之间的分离程度？讨论不同的想法,算法和权衡.(saparation程度的定义:http://en.wikipedia.org/wiki/Six_degrees_of_separation)
这就是我的想法:
我能想到的候选算法是:广度优先搜索(BFS),深度优先搜索(DFS),深度限制搜索(DLS),迭代加深搜索(IDS).
首先,应考虑DFS.甚至当两个人连接时(即,分离度= 1),该算法很可能长时间沿着错误的路径继续搜索.
保证BFS找到最小分离度(因为图不加权).假设最大分支因子是b并且两个目标人之间的实际分离度是d,时间复杂度和空间复杂度都是O(b ^ d).
由于最大可能的分离程度是未知的(尽管它不应该高于6),因此使用DLS可能不是一个好主意.然而,IDS似乎比BFS更好 - 它的时间复杂度也是O(b ^ d)(尽管由于重复访问中间节点,实际时间成本比BFS略高),而其空间复杂度为O( bd),这比O(b ^ d)好很多.
毕竟,我会选择IDS.这在面试中是否可以接受？我在上述推论中是否有任何错误？或者有没有我错过的更好的解决方案？
提前致谢.