竞技世界大数据岗一面(已凉)

给定a、b 两个文件,各存放 50 亿个 URL,每个 URL 各占 64B,内存限制是 4G。请找出 a、b 两个文件共同的 URL。

每个URL 占 64B,那么 50 亿个 URL占用的空间大小约为 320GB。5, 000, 000, 000 * 64B ≈ 5GB * 64 = 320GB

由于内存大小只有4G,因此,我们不可能一次性把所有 URL 加载到内存中处理。对于这种类型的题目,一般采用分治策略 ,即:把一个文件中的URL 按照某个特征划分为多个小文件,使得每个小文件大小不超过 4G,这样就可以把这个小文件读到内存中进行处理了。

思路如下 :

首先遍历文件a,对遍历到的 URL 求 hash(URL) % 1000 ,根据计算结果把遍历到的URL 存储到 a0, a1, a2, ..., a999,这样每个大小约为 300MB。使用同样的方法遍历文件 b,把文件 b 中的 URL 分别存储到文件 b0, b1, b2, ..., b999 中。这样处理过后,所有可能相同的 URL 都在对应的小文件中,即 a0 对应 b0, ..., a999 对应 b999,不对应的小文件不可能有相同的 URL。那么接下来,我们只需要求出这 1000 对小文件(a0,b0)中相同的URL 就好了。

接着遍历ai( i∈[0,999] ),把 URL 存储到一个 HashSet 集合中。然后遍历 bi 中每个 URL,看在 HashSet 集合中是否存在,若存在,说明这就是共同的 URL,可以把这个 URL 保存到一个单独的文件中。

方法总结

1.分而治之,进行哈希取余;

2.对每个子文件进行HashSet 统计。

 

就这个问题你还有其他解决办法吗

我不知道说用数据库其实太***了不过用数据库也能解决依然十分是分而治之的思想依然可以把文件通过hash来取余然后通过redis的set()数据结构来统计然后对比a,b文件来判断就好了我面试的时候回答的是存在mysql之中太蠢了

面试官说的解决方法利用java的bitmap自行 百度bitmap非常使用处理这个问题自己真是孤陋寡闻

 

三、你在hash的时候会碰到hash碰撞请问有什么方法解决

我的回答再hash以及建立链表面试官觉得不够说java拉链,(拉链法其实就是但地址搞成链表

避免Hash碰撞策略

1.开放地址法(再散列法)

开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1) 其中,m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1,称线性探测再散列。如果di取1,则每次冲突之后,向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…kk,-kk(k<=m/2),称二次探测再散列。如果di取值可能为伪随机数列。称伪随机探测再散列。

2.再哈希法Rehash

当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。缺点:计算时间增加。比如上面第一次按照姓首字母进行哈希,如果产生冲突可以按照姓字母首字母第二位进行哈希,再冲突,第三位,直到不冲突为止.这种方法不易产生聚集,但增加了计算时间。

3.链地址法(拉链法)

将所有关键字为同义词的记录存储在同一线性链表中.基本思想:将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。对比JDK 1.7 hashMap的存储结构是不是很好理解。至于1.8之后链表长度大于6rehash 为树形结构不在此处讨论。

拉链法的优缺点

优点:

①拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;②由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;③开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;④在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表,删除结点不能简单地将被删结 点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。

缺点:

指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

4.建立一个公共溢出区

假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表,另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。

 

四、红黑树和平衡二叉树区别各自优缺点

平衡二叉树

AVL树是带有平衡条件的二叉查找树,一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡,左右子树树高不超过1,和红黑树相比,AVL树是严格的平衡二叉树,平衡条件必须满足(所有节点的左右子树高度差的绝对值不超过1)。不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡,而旋转是非常耗时的,由此我们可以知道AVL树适合用于插入与删除次数比较少,但查找多的情况

缺点由于维护这种高度平衡所付出的代价比从中获得的效率收益还大,故而实际的应用不多,更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然,如果应用场景中对插入删除不频繁,只是对查找要求较高,那么AVL还是较优于红黑树。

红黑树

一种二叉查找树,但在每个节点增加一个存储位表示节点的颜色,可以是红或黑(非红即黑)。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍,因此,红黑树是一种弱平衡二叉树(由于是弱平衡,可以看到,在相同的节点情况下,AVL树的高度低于红黑树),相对于要求严格的AVL树来说,它的旋转次数少,所以对于搜索,插入,删除操作较多的情况下,我们就用红黑树

2.性质

1. 每个节点非红即黑

2. 根节点是黑的;

3. 每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的;

4. 如图所示,如果一个节点是红的,那么它的两儿子都是黑的;

5. 对于任意节点而言,其到叶子点树NULL指针的每条路径都包含相同数目的黑节

3.应用

1广泛用于C ++的STL中,地图和集都是用红黑树实现的;

2着名的Linux的的进程调度完全公平调度程序,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间;

3IO多路复用的epoll的的的实现采用红黑树组织管理的的的sockfd,以支持快速的增删改查;

4Nginx的的的中用红黑树管理定时器,因为红黑树是有序的,可以很快的得到距离当前最小的定时器;

5,Java的的的中TreeMap中的中的实现;

 

五、你做过什么机器学习的项目你是怎么解决的

 

六、Dota2游戏ai知道吗你知道他的原理方法吗

(别问 问就是我不知道下面都是百度的

DeepMind AlphaGO

原理就是马尔可夫决策过程(自行百度)

个马尔可夫决策过程(Markov Decision Processes,MDPs)通常包括以下几个要素:

1.状态集合  ,包含MDPs可能处在的各个状态。

2.动作集合  ,包含MDPs在各个状态上可采取的动作。

3.转换概率  ,表示在状态  上采取动作  后,下一个状态的概率分布。

4.回报函数  ,  表示状态  的回报。

MDPs的核心问题是如何找到一个对所有状态都适用的最优策略,按照此策略来选择动作,使总回报的期望最大化。在总回报中加入折扣因子后,为使总回报的期望最大化,须尽可能的将正向回报提前,负向回报推迟。

回想一下围棋的对弈,起始状态是一个空的棋盘,棋手根据棋面(状态)选择落子点(动作)后,转换到下一个状态(转换概率为:其中一个状态的概率为1,其他状态的概率为0),局势的优劣是每个状态的回报。棋手需要根据棋面选择合适落子点,建立优势并最终赢下游戏,因此,围棋可以看作是一个MDPs问题。(达观数据)

七、为什么要去北京工作
面试官估计见我太菜了就想结束面试了吧让我反问
我就问了第一题什么其他的解决方法面试官意思就是我认知不到位没有深入思考建议我多看看数据结构最近我真的心态有点爆炸投的岗位也是乱七八糟的六月份手粉碎性骨折住院手术提前批一个没去八月末开始找工作过去三周了一个保底offer都没今年感觉过得好难受。。。

#面试复盘##面经##竞技世界#
全部评论
额,bitmap应该是只能比较整数形式,怎么映射url?
点赞 回复
分享
发布于 2021-10-12 08:33
请问笔试题都考了什么呀?
点赞 回复
分享
发布于 2023-09-04 23:20 广东
乐元素
校招火热招聘中
官网直投

相关推荐

4 12 评论
分享
牛客网
牛客企业服务