我在Reddit上看到了这个问题,并没有提出积极的解决方案,我认为这是一个完美的问题.这是关于面试问题的一个主题:
编写一个采用大小为m的int数组的方法,如果数组由数字n ... n + m-1组成,则返回(True/False),该范围内的所有数字以及该范围内的数字.不保证数组已排序.(例如,{2,3,4}将返回true.{1,3,1}将返回false,{1,2,4}将返回false.
我遇到的问题是我的采访者一直要求我优化(更快的O(n),更少的内存等),他声称你可以在数组的一次传递中使用恒定量的记忆.从未想过那一个.
除了您的解决方案,请指出他们是否认为该阵列包含唯一的项目.同时指出您的解决方案是否假设序列从1开始.(我稍微修改了一下这个问题以允许它变为2,3,4 ......)
编辑:我现在认为在空间算法中不存在处理重复的线性时间和常数.任何人都可以验证吗？
重复问题归结为测试以查看数组是否在O(n)时间,O(1)空间中包含重复项.如果可以这样做,您可以先测试,如果没有重复,则运行算法.那么你可以在O(n)时间O(1)空间中测试欺骗吗？
确定1到N范围内缺失值的常见访谈问题已经完成了一千多次.变化包括2个缺失值,最多K个缺失值.
示例问题:范围[1,10](1 2 4 5 7 8 9 10)= {3,6}
以下是各种解决方案的示例:
简单的面试问题变得更难:给出数字1..100,找到丢失的数字
我的问题是,看到一个缺失值的简单情况是O(n)复杂性,并且较大情况的复杂性收敛于大于O(nlogn)的大小:
通过对范围进行排序(mergesort)并迭代它来观察缺失的元素,难道只是更容易回答这个问题吗？
该解决方案应该不超过O(nlogn),并且能够解决1到N之外的范围的问题,例如10到1000或-100到+100等......
是否有理由相信上述SO链接中的给定解决方案将比基于排序的解决方案更好地存在大量缺失值？
注意:对于这个问题,似乎有很多常见的解决方案,假设只有一个数论的方法.如果在S/E采访中被问到这样一个问题,使用更多的计算机科学/算法方法是不谨慎的,假设该方法与数论解决方案的复杂性相同......
更多相关链接:
我遇到了这篇文章,报道了以下的面试问题:
给定两个数字数组,找出两个数组中的每个数组是否具有相同的整数集？建议一个比NlogN跑得更快但没有额外空间的算法？
我能想到的最好的是以下几点:
(a)对每个数组进行排序,然后(b)沿两个数组移动两个指针并检查是否找到不同的值......但步骤(a)已经有NlogN复杂度:(
(a)扫描最短的数组并将值放入地图中,然后(b)扫描第二个数组并检查是否找到了一个不在地图中的值...这里我们有线性复杂度,但我们使用额外的空间
......所以,我想不出这个问题的解决方案.
想法？
谢谢你的所有答案.我觉得很多都是对的,但我决定选择ruslik的那个,因为它提供了一个我没有想到的有趣选项.