1.如何对网页进行Load test. 负载测试
要进行负载测试，先要确定对性要求最高的场景！！！
web 负载测试的对象： 相应时间， 资源利用率，。。
创造成千上万的虚拟用户，模拟并发的情况！！！ 需要编写Multi-threading program, 建立millions of Threads! 然后利用程序来测量responding time.
2.涉及扩展性与存储限制！！！如果涉及一个网络爬虫，该怎么避免陷入无限循环？？？什么时候会出现无限循环？？？ web-->web-->web 如果构成一个cycle。为了避免无限循环，只要检查有没有cycle。 可以build a list, 访问过页面后，将hash[v] set Trueimagine its a tree. Doing BFS, mark visted. 不过web v 是什么？ 是根据内容还是url来定义的？most cases, www.google/image 和www.google/article是不一样的两个东西。不过也有可能后缀不影响。给100亿个网站，如何检查出重复的文件？ 重复表示2个URL完全一样。首先100亿url占用多少空间？ =4TB. 内存绝对放不进去。***永远先想想simplied version of the problem. 最简化的问题。 假设可以放的进内存，对List items找重复项。 但是肯定是没办法放进内存的。所以我们可以将部分数据移入硬盘，or放在机器上If on disk. 需要两次扫描Scan entire dataset, 分成4000组，每组1GB。简单的做法是把每个url u 取名.txt x=hash(u)
这样一来，所有hash value一样的都会在一个文件里。
第二次扫描，将每个文件Load 进内存， 创建网址的hash-list. 找重复的。
3. System design Facebook/Linkedin.
设计一种算法展示两个人之间的关系
我——> tom-->Amy-->你
先移除一些限制条件，解决该问题的简化版本。
先忘记要应对几百万的用户，针对简单情况设计算法
构建一个图，每个人一个node，如果两个node有line, 表示为朋友。
class Person{
Person[] friends;
}
要找两个人的链接，从其中一个人开始，BFS. Now，把百万用户的限制条件加入：
Facebook和linkedin这种规模的服务，不可能所有数据存放在一个机器上。也就是说简单数据结构不管用
因为我们在一个机器上do DFS,很有可能找不到人。
把朋友列表改为他们ID的列表，追踪。
针对每个朋友的ID，找出机器的位置。 int machine_index = getMachineIDForUser(person ID)
转到编号的machine上
在那台机器上，执行Person friend = getPersonWithID(person_ID)
在这个机器上找人。
非常重要的优化：
减少机器间的跳转次数
批量尝试跳转动作。如果5个朋友都在同一台机器上，就应该一次性找出来。
4. 给定一个输入文件，包含40亿Non-Negative Integer.产生一个不在该文件中的整数
设定你有1GB内存来做
Followup: 如果只有10MB
5. 假设你有一个20GB的文件， 每一行一个string, 将如何对这个文件进行排序？
当看到20GB这么大的限制，就应该想到这是一个套路。 也就是不能全部将数据load 进内存里。所以，只是将部分文件load进内存。 将整个文件分成许多快。 每个快x MB, 各个块完成排序以后，将他们合并在一起。 这个是一个External Sort. [implementation 也是略麻烦]
6. 实现一个搜索引擎。 Search Engine.
这个搜索系统有一百台机器来相应搜索查询， 响应查询的机器是随机挑选的， 因此两个一样的请求，【比如都是搜索 which school is the best】，不一定由同一台机器响应。请这几一种cache 缓存机制，缓存最近几次查询的结果。
因为Process Search cost a lot.
答：缓存机制需要有一个功能： 旧数据会过期，让它被新的数据代替。那么如何实现cache? 可以使用List， 只要把新的搜索放在list head， 当list长度超过一定大小的时候，删除List 末尾元素。
然后我们还需要引入Hash 的idea，这样会使得搜索变得非常快。O(1).
所以，这里实际上就是implement a cache.
上述是最简单的情况，假设只有一台机器。 如果我们有很多台机器，每个机器也许都应该有自己的缓存。这种做法很容易实现，但是问题也很多。比如说search "A" 对于机器1来讲是在缓存里的，要是不小心由机器2来处理，也许就不是缓存里的东西了。那就需要花很多时间，浪费在本身是重复的东西上。
我们也可以让每台机器都有一个total cache copy. 大家都知道完整版的cache是什么样。 这的问题是 每一次update cache要发送给所有的机器。如果机器数量1万台，每次要update一万台机器。 这个有点恐怖。而且total cache的capacity也会少很多很多。
还有一种选择是把cache 分隔开，每台机器存放cache的不同部分。 当机器要找某次查询的结果，只要找哪台机器有这个value。 这里就可以使用hash(query) % N的方法。
7. 设计一个算法，给定10亿个数字，找出最小的100万个数字。 假设计算机内存足以容纳全部10亿个数字。
这道题有很多种1. sorting. 因为memory可以load 所有数字，所以可以直接排序 O(nlogm) 然后数前100万个数字
解法2. Heap: 先给前100万个数字创建一个max Heap. 最大的在顶部。 然后iterate whole array。将每个元素插入max heap 并且删掉最大的元素. 当10亿个数字全扫过一遍后，留下来的是最小的100万个元素，因为大的都给删掉了。 O(nlogm)
做一个Priority Queue， size 100万也是一样的。
解法3. 选择排序法: selection sort [高级]
可以在Linear time 找到数组中第i 小的元素。
一旦找到第i 小的，我们可以iterate entire array,找到所有小于等于该元素的值。 O(n)
