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

发表于:2013-10-23来源:Csdn作者:v_JULY_v点击数: 标签:软件测试面试题
蜻蜓FM2014校招研发笔试 10月11日,腾讯 web 前端面试 一个数组 var arr = [abc,ddadbc,adbdcd,abcqew.......] 长度一万, 用最有效率的方法计算出包含被元素出现最多的

  蜻蜓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