这是我遇到的一个常见的面试问题,但是我没有按照它要求的方式改进它.
assume we have an int array int[] A, we want to find the first duplicate entry.
几乎每个人都可以想到使用HashSet,并在解析时添加它.这将导致O(n)时间和O(n)空间.在此之后,我被要求在没有其他数据结构的情况下解决它.我说最愚蠢的想法是在O(n ^ 2)时间内比较每一个.然后我被要求改善O(n ^ 2)时间.
为了改进它,我想到使用一个固定大小的数组(假设最大数是n),boolean [] b = new boolean [n]; 但我不允许使用这种方法.
然后我想到使用一个int变量,使用位操作,如果最大数小于32,那么对于n我们可以向左推1到n位并且| 到检查器,然后检查器到阵列中的下一个条目,检查它是否> 0.例如:
int c = A[i];
if(check & (1 << c) > 0) return false;
check |= 1 << c;
但是这也是不允许的.
所以有一个暗示我可以将数组本身用作hashset/hashtable和"线性散列"？
任何帮助？谢谢
这是破解编码访谈的另一个问题,我在阅读之后仍有一些疑问.
9.4 If you have a 2 GB file with one string per line, which sorting algorithm
would you use to sort the file and why?
解
当面试官给出2GB的大小限制时,它应该告诉你一些东西 - 在这种情况下,它表明他们不希望你把所有数据都带入内存.那么我们该怎么办？我们只将部分数据带入内存..算法:
我们有多少内存？假设我们有X MB的内存可用.
将文件分成K个块,其中X*K = 2 GB.将每个块放入内存并使用任何O(n log n)算法照常排序.将行保存回文件.
现在将下一个块放入内存并进行排序.
完成后,将它们逐个合并.
上述算法也称为外部排序.第3步称为N路合并使用外部排序的基本原理是数据的大小.由于数据太大而我们无法将其全部存入内存,因此我们需要采用基于磁盘的排序算法.
怀疑:
在步骤3中,进行合并排序,同时比较2个数组,每次比较时我们是否需要2*X空间？限制是X MB.我们应该把块打成(X/2)*2K = 2GB吗？这样每个块将是X/2 MB,并且将有2K块.或者我只是理解合并排序错误？谢谢!