竞技世界大数据岗一面(已凉)
一、给定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的的进程调度完全公平调度程序,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间;
3、IO多路复用的epoll的的的实现采用红黑树组织管理的的的sockfd,以支持快速的增删改查;
4、Nginx的的的中用红黑树管理定时器,因为红黑树是有序的,可以很快的得到距离当前最小的定时器;
5,Java的的的中TreeMap中的中的实现;
五、你做过什么机器学习的项目,你是怎么解决的
六、Dota2游戏ai知道吗?你知道他的原理方法吗
(别问 问就是我不知道,下面都是百度的)
DeepMind AlphaGO
原理就是:马尔可夫决策过程(自行百度)
个马尔可夫决策过程(Markov Decision Processes,MDPs)通常包括以下几个要素:
1.状态集合 ,包含MDPs可能处在的各个状态。
2.动作集合 ,包含MDPs在各个状态上可采取的动作。
3.转换概率 ,表示在状态 上采取动作 后,下一个状态的概率分布。
4.回报函数 , 表示状态 的回报。
MDPs的核心问题是如何找到一个对所有状态都适用的最优策略,按照此策略来选择动作,使总回报的期望最大化。在总回报中加入折扣因子后,为使总回报的期望最大化,须尽可能的将正向回报提前,负向回报推迟。
回想一下围棋的对弈,起始状态是一个空的棋盘,棋手根据棋面(状态)选择落子点(动作)后,转换到下一个状态(转换概率为:其中一个状态的概率为1,其他状态的概率为0),局势的优劣是每个状态的回报。棋手需要根据棋面选择合适落子点,建立优势并最终赢下游戏,因此,围棋可以看作是一个MDPs问题。(达观数据)
#面试复盘##面经##竞技世界#