九月十月百度，迅雷，华为，阿里巴巴，最新校招笔试面试五十题(4)

　　蜻蜓FM2014校招研发笔试

　　10月11日，腾讯web前端面试

　　一个数组 var arr = ['abc','ddadbc','adbdcd','abcqew'.......] 长度一万， 用最有效率的方法计算出包含被元素出现最多的。

　　单机5G内存，磁盘200T的数据，分别为字符串，然后给定一个字符串，判断这200T数据里面有没有这个字符串，怎么做?

　　如果查询次数会非常的多, 怎么预处理?

　　点评：如果数据是200g且允许少许误差的话，可以考虑用布隆过滤器Bloom Filter：http://blog.csdn.net/v_july_v/article/details/6685894。但本题是200T，得另寻良策。

　　OK，以下是@cy 提供的题解(暴露出的一个问题是题意不是特别明确，因为题解中有不少自己的假设，所以日后各位面试时一定要跟面试官彻底弄清题意再作答，包括各种使用条件)：

　　“①. 内存和数据比是 5GB / 200TB, 约为 1 比 4w, 所以trie啥的就不用想了, 唯一的就是hash.

　　②. 简单的假设每个字符串是相对短的(只要不会超过5GB)

　　1. 几MB, 甚至百MB的字符串也能处理, 但是确实对最终的效果有很大影响, 如果只是部分case特别大,可以特殊处理下.

　　③. 一个字符串块 在内存中需要一个 条目 来标识

　　1. value 需要 8 字节, key约为4字节

　　1. 200TB总共有 200 * 2^40 位, 地址空间至少为48个bit, 存储长度用16bit则一个条目的value 需要8个字节

　　1. 这里的长度是用来存一个 字符串块 的长度, 单位可以优化为KB, 甚至MB, 16bit肯定是够的

　　1. key用4个字节有些紧张, 可以考虑占用部分长度的位

　　1. 长度也可以不在条目中出现, 而是在块头出现, 但这样取块的时候有可能浪费, 也有可能要取多次.

　　2. 所谓一个 字符串块 就是hash值相同的字符串挨个存在一起, 从而得到的字符串块.

　　④. 这样的话, 5GB 可以存放最多 5GB / 8 约为 4亿个条目.

　　⑤. 把原来的200TB字符串挨个的hash, 并按hash排序后, 存起来, 建立索引.

　　1. hash值可以用md5之类的散列到足够开, 然后 mod 4亿值来求

　　⑥. 根据重排后的文件, 建立索引, key为hash值, value为前面说到的, 该hash对应字符串块在文件中的偏移, 和 块的长度.

　　⑦查询时, 根据hash值, 找到该字符串可能在的字符串, 然后将整个字符串读出来, 用kmp比较即可.

　　200TB的数据, 被划到 4亿 个字符块当中, 平均一块应该在 800KB 附近, 考虑到hash不均衡, 一般也就是几MB的样子,

　　比较起来应该还OK.

　　⑧其他的小优化点:

　　1. 不是一个文件, 而是若干个文件, 但是不影响偏移的编号

　　1. 为什么做hash再分块? 避免通用前缀过多,导致分块极不均匀

　　1. 大长的字符串容易导致 字符串块 暴大, 可以考虑分为若干小串, 同时记录原来的位置, 知道是否是一个整串

　　1. 压缩...留一些空间做常用查询串的缓存...

　　⑨再说怎么优化这个预处理的排序过程. 每次读5GB的数据进来, 算好hash分好桶, 这种OK吧, 然后按桶回写到下去, 这里也是批量写的. 处理完继续处理下一个5GB, 全部处理完后, 再做归并, 搞几轮后, 就OK了嘛. 当然, 为了把内存中排序时浪费的IO补回来, 可以 并行做, 一个在算的时候,另一个在读....”。

　　10月12日，百度一面

　　JAVA里面的线程同步机制、异常处理机制、集合类、简单的设计模式、hashmap和hashtable的区别，及HashMap和ConcurrentHashMap的区别。

　　点评：关于hashmap和hashtable的区别，请看上文第13题，其余请自己查阅相关书籍。

　　stat、SDE、PM、DS等相关职位的面试题

　　1、有一组数据，很长，有ID，经纬度，时间4个变量。

　　怎么找出两人是否有一面之缘。怎么找出所有relationship(定义是在100米范围内一起度过1小时以上)。

　　2、怎么找出竞争对手购买了哪些搜索关键词。

　　3、怎么判断两个TB级别的文本是否雷同，是否近似。

　　4、怎么用C实现SQL的join功能。

　　5、怎么最快的在一个大文本里面搜索字符串。

　　6、coding计算斐波那契数列。

　　更多请参看：http://mp.weixin.qq.com/mp/appmsg/show?__biz=MjM5ODIzNDQ3Mw==&appmsgid=10000300&itemidx=1&sign=173a62e0db86cb4c76a0bb1e9c22f3e5。

　　10月12日，网易游戏专业一面

　　1、怎么判断单链表有没有环

　　2、怎么判断两个无环单链表是否相交

　　3、101个硬币中有一个假币，有一个无砝码的天平，称两次，判断假币比真币重还是轻。

　　点评：老掉牙的题，没点评的欲望，原文请看：http://blog.csdn.net/cqsctlsss/article/details/12747631。

　　10月13日，百度笔试题：

　　1、 给出数组A={a_0,a_1,a_2,...,a_n}(n是可变的)，打印出所有元素的组合

　　2、 数组A中任意两个相邻元素大小相差1，现给定这样的数组A和目标整数t，找出t在数组A中的位置。

　　3、 求二叉树的面积(高乘宽)，高为二叉树根到叶子节点的最大距离，宽慰二叉树最多的节点数。

　　4、给了一个百度地图的截图，对于地图上的某一点，需要在地图上标注该点的信息，将信息抽象成一个矩形，可以在该点的左边标记，也可以在该点右边标记。但是任意两点标记后的矩形是不能有覆盖的，否则删除其中一个点

　　问题1，现给一固定区域，有n个点，设计一个算法，要求标记足够多的点

　　问题2，当点足够多时候，算法会遇到性能瓶颈，需要对算法重新优化。

　　更多题目请参见：http://blog.csdn.net/xyanghomepage/article/details/12687771。

　　腾讯笔试题两道

　　1、有100W个关键字，长度小于等于50字节。用高效的算法找出top10的热词，并对内存的占用不超过1MB。

原文转自：http://blog.csdn.net/v_july_v/article/details/11921021