/* 百度面试： 1.用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，使用 x 次天平， 最多可以从 y 个小球中找出较轻的那个，求 y 与 x 的关系式。 2.有一个很大很大的输入流，大到没有存储器可以将其存储下来， 而且只输入一次，如何从这个输入流中随机取得 m 个记录。 3.大量的 URL 字符串，如何从中去除重复的，优化时间空间复杂度 */ /* 1.记住是唯一较轻的，只有一个 每次分三份，a，b，c 称ab；如果a=b,则轻的在c中，否则在ab小的那堆中 所以y=3^x 2. 所有的个数N，N<m，保存所以的， N>m: 用一个N，rand的随机数，R=rand（N),如果R在[0,m]区间，置换，否则丢弃不管 ； 或者 用大小为m的数组arr[0:m-1]来保存随机抽取的元素 arr[0:m-1]逐步初始化为输入流的前m个元素的一个随机排列。 对于输入流中的第k (k>m)个元素，后面元素，随机生成一个[0,k-1]区间内的整数i， 如果此随机整数i小于等于m，那么就用第k个元素覆盖掉arr[i-1]， 否则，丢弃第k个元素。 3.用hash 1. 内存够用，非常大，将URL存入hash链表，每个URL读入到hash链表中，遇到重复的就舍弃， 否则加入到链表里面，最后遍历得到所有不重复的URL。 空间复杂度M，时间复杂度为O(N+N/M)，M为不重复的URL，N为总URL数 2. 为了解决内存可能不足的问题，需要把hash链表变化成普通的hash表， 每个hash表元素指向一个文件， 这个文件记录了所有该hash值对应的无重复的URL， 那么在加入URL的时候就遍历对应文件中的URL，没有重复则加入到文件中。 但是每次都要读写文件，消耗的时间应该是上一种方式的三倍（依赖于io速度）， 而对内存的要求比较小。一个改进是加入URL的时候进行排序，这样能减少比对的次数。 */