美文网首页
面试问答题

面试问答题

作者: 什锦甜 | 来源:发表于2018-07-19 01:07 被阅读12次

问:

有1000亿条记录,每条记录由url,ip,时间组成,设计一个系统能够快速查询以下内容
1.给定url和时间段(精确到分钟)统计url的访问次数
2.给定ip和时间段(精确到分钟)统计ip的访问次数

答:

首先,1000亿条记录全部放到内存肯定不够,那就是分成小文件了,然后整合;
公共的时间段,因为精确到分钟,我们把这每一分钟建成一个小文件,每个小文件肯定会有许多重复的ip,url;

现在统计每个小的文件中url的访问量和ip的访问次数,方法就是建立索引;
(建立索引的目的是为了减少查询次数,但是随着索引级数增多也会造成花更多的时间在建立索引上);

建立url的索引,假如是www.nowcoder.com/question,可以分别给www.nowcoder.com和question建立索引,那么来了一条url,先看一级索引是不是匹配,匹配再看二级索引,相同的话就是我们要的url目标;

ip的索引也是一样,ip分成4段建立索引;
所以这里影响效率的就是在索引建立这块,索引建立好那就是查询的事了的,就会变得非常快。
假定给定了某个时间段,找出url的访问量,那么先找到给定的时间段,对应着刚开始分割的小的文件(每一个分钟)中搜索,通过索引找到相同的url之后,开始统计,直到搜索完所有的给定时间段内的所有的小的文件;

求ip的访问次数也是一样,按照给定的时间段,找到对应的小的文件,通过索引找到相同的ip后统计,直到搜索完了给定时间段内的所有的小的文件。

问:

海量数据处理 - 10亿个数中找出最大的10000个数(top K问题)

答:

先拿10000个数建堆,然后一次添加剩余元素,如果大于堆顶的数(10000中最小的),将这个数替换堆顶,并调整结构使之仍然是一个最小堆,这样,遍历完后,堆中的10000个数就是所需的最大的10000个。建堆时间复杂度是O(mlogm),算法的时间复杂度为O(nmlogm)(n为10亿,m为10000)。

优化的方法:可以把所有10亿个数据分组存放,比如分别放在1000个文件中。这样处理就可以分别在每个文件的10^6个数据中找出最大的10000个数,合并到一起在再找出最终的结果。

以上就是面试时简单提到的内容,下面整理一下这方面的问题:
top K问题

在大规模数据处理中,经常会遇到的一类问题:在海量数据中找出出现频率最好的前k个数,或者从海量数据中找出最大的前k个数,这类问题通常被称为top K问题。例如,在搜索引擎中,统计搜索最热门的10个查询词;在歌曲库中统计下载最高的前10首歌等。

针对top K类问题,通常比较好的方案是分治+Trie树/hash+小顶堆(就是上面提到的最小堆),即先将数据集按照Hash方法分解成多个小数据集,然后使用Trie树活着Hash统计每个小数据集中的query词频,之后用小顶堆求出每个数据集中出现频率最高的前K个数,最后在所有top K中求出最终的top K。

相关文章

  • 面试问答题

    问: 有1000亿条记录,每条记录由url,ip,时间组成,设计一个系统能够快速查询以下内容1.给定url和时间段...

  • 俩天小记

    001经历了一场面试 今天去新的公司面试,面试官随和,没架子。出了三道题 速算题24乘26 97乘98 问答题 窨...

  • 猿学-Java程序员的10道XML面试题

    本文将看到10道常见的XML面试问答题。这些问题大部分在Java面试中会问到,同时在C,C++,Scala或其他语...

  • Spring面试问答题

    1. 什么是Spring? Spring 是个 java 企业级应用的开源开发框架。Spring 主要用来开发 J...

  • 产品经理面试问答题

    超实用“产品经理”岗位面试问答题,自己也是摸爬滚打过来的,同时也做了一些记录和总结,这里分享给各位还在面试产品经理...

  • 学历不高,该如何进行职业规划?

    其实这是一道知乎问答题 www.zhihu.com/question/56048209,也是我面试公关专员的一道测...

  • Java基础面试高频问答题

    1、什么导致线程阻塞 一般线程中的阻塞: Socket客户端的阻塞: Socket服务器的阻塞: 什么导致线程阻塞...

  • 软件测试常规面试题问答题(附带答案)—问答基础篇01

    软件测试面试题 一、问答题 1、编写测试用例有哪些? 答:等价类、边界值、错误推测法、场景法,我个人常用的方法就是...

  • scipy计算二列相关

    1.问题描述 某次考试中,有10名考生成绩如下表,包括总分和一道问答题,试求该道问答题的区分度(问答题6分及6分以...

  • iOS与Android移动端设计对比

    写这篇文章的起因是秋招来袭,很多同学需要准备面试笔试题,自己也在限时笔试中遇到过这这道问答题,做的不是很好,很想以...

网友评论

      本文标题:面试问答题

      本文链接:https://www.haomeiwen.com/subject/whkzpftx.html