文件名称：几道大数据面试题.pdf
文件大小：192KB
文件格式：PDF
更新时间：2022-12-24 11:29:20
文档资料
⼏道⼤数据⾯试题 ⼏道⼤数据⾯试题 ⾸先处理⼤数据的⾯试题，有些基本概念要清楚： （1）1Gb = 109bytes（1Gb = 10亿字节）：1Gb = 1024Mb，1Mb = 1024Kb，1Kb = 1024bytes； （2）基本流程是，分解⼤问题，解决⼩问题，从局部最优中选择全局最优；（当然，如果直接放内存⾥就能解决的话，那就直接想办法求解，不需要分解 了。） （3）分解过程常⽤⽅法：hash(x)%m。其中x为字符串/url/ip，m为⼩问题的数⽬，⽐如把⼀个⼤⽂件分解为1000份，m=1000； （4）解决问题辅助数据结构：hash_map，Trie树，bit map，⼆叉排序树（AVL，SBT，红⿊树）； （5）top K问题：最⼤K个⽤最⼩堆，最⼩K个⽤最⼤堆。（⾄于为什么？⾃⼰在纸上写个⼩栗⼦，试⼀下就知道了。） （6）处理⼤数据常⽤排序：快速排序/堆排序/归并排序/桶排序 下⾯是⼏个例题（每个题的解法都不唯⼀，下⾯只列出了众多解法中的⼀种）： 1. 给定a、b两个⽂件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b⽂件共同的url？ 每个url⼤⼩为64bytes，那么可以估计每个⽂件的⼤⼩为5G×64=320G，远远⼤于内存限制的4G，所以不可能将其完全加载到内存中处理，可以采⽤分治的思 想来解决。 Step1：遍历⽂件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个⼩⽂件（记为a0 ,a1 ,...,a999 ，每个⼩⽂件约300M）； Step2: 遍历⽂件b，采取和a相同的⽅式将url分别存储到1000个⼩⽂件（记为b0 ,b1 ,...,b999）； 巧妙之处：这样处理后，所有可能相同的url都被保存在对应的⼩⽂件（a0 vs b0 , a1 vs b1 ,...,a999 vs b999）中，不对应的⼩⽂件不可能有相同的url。然后我们 只要求出这个1000对⼩⽂件中相同的url即可。 Step3：求每对⼩⽂件ai和bi中相同的url时，可以把ai的url存储到hash_set/hash_map中。然后遍历bi的每个url，看其是否在刚才构建的hash_set中，如果是， 那么就是共同的url，存到⽂件⾥⾯就可以了。 草图如下（左边分解A，右边分解B，中间求解相同url）： 2. 有⼀个1G⼤⼩的⼀个⽂件，⾥⾯每⼀⾏是⼀个词，词的⼤⼩不超过16字节，内存限制⼤⼩是1M，要求返回频数最⾼的100个词。 Step1：顺序读⽂件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个⼩⽂件（记为f0 ,f1 ,... ,f4999）中，这样每个⽂件⼤概是200k左右，如果其 中的有的⽂件超过了1M⼤⼩，还可以按照类似的⽅法继续往下分，直到分解得到的⼩⽂件的⼤⼩都不超过1M； Step2：对每个⼩⽂件，统计每个⽂件中出现的词以及相应的频率（可以采⽤trie树/hash_map等），并取出出现频率最⼤的100个词（可以⽤含100个结点的 最⼩堆），并把100词及相应的频率存⼊⽂件，这样⼜得到了5000个⽂件； Step3：把这5000个⽂件进⾏归并（类似与归并排序）； 草图如下（分割⼤问题，求解⼩问题，归并）： 3. 现有海量⽇志数据保存在⼀个超级⼤的⽂件中，该⽂件⽆法直接读⼊内存，要求从中提取某天出访问百度次数最多的那个IP。 Step1：从这⼀天的⽇志数据中把访问百度的IP取出来，逐个写⼊到⼀个⼤⽂件中； Step2：注意到IP是32位的，最多有2^32个IP。同样可以采⽤映射的⽅法，⽐如模1000，把整个⼤⽂件映射为1000个⼩⽂件； Step3：找出每个⼩⽂中出现频率最⼤的IP（可以采⽤hash_map进⾏频率统计，然后再找出频率最⼤的⼏个）及相应的频率； Step4：在这1000个最⼤的IP中，找出那个频率最⼤的IP，即为所求。 草图如下：