分类 算法 下的文章

前几天面试了字节跳动,记录下面试遇到的算法题

题目

输入: 用户日志(time, user_id, login | logout)
输出:同时在线人数的峰值,精确到秒

一开始,想了一分钟左右,想到了一个比较简单粗暴的方式。

使用位图的思想,将一天 分成 86400 秒,每秒单独统计,最后遍历一遍,找最大的值所对应的秒数

总的来说简单粗暴,也是比较容易想到的方式。只是由于按照每秒来统计了,所以写入到这个位图的效率是很低的。如果用户一天都在线, 那么就要写86400 次,明显是很慢的。

面试官一看这么粗暴,问了句,有没有优化的方案?

按照套路来,要么动态规划把历史记录一下,要么二分一下。动态规划明显不适用,二分的思想好像是可行的。

先将一天分成24小时,按照上面的方法统计一遍,找到峰值的小时,然后从这小时里面按照分钟统计一遍,找到峰值的分钟,再将分钟分成60秒,再统计一遍

理论上,每个用户跨越的时间越长,这样统计起来应该是会比第一种方式优秀很多。

但是面试官的问题来了,如果有多个峰值怎么办,最坏情况下每秒都是峰值,这种方式会比第一种方式慢得多

那就得继续想呗,想了几分钟,面试官看我想不出来就放弃了,我的心也凉了下,感觉没戏了

面试结束之后,继续想了下这个问题有没有更好的解法

毕竟同一个坑不能栽进去两次对不对。

可能是最优解的解法来了

跳开之前的统计所有秒数的想法,这个问题的解法就简单多了

我们先来想一下什么时候会有峰值,肯定是在线人数最多的时候。那么某个时间点在线的人数怎么算呢,很明显是 所有在这个时间点之前登入的 - 在这个时间点之前所有登出的。

那么算法也很简单,

  1. 定义三个变量,其中一个记录当前在线人数(currentVal),一个最大值(maxVal),最后一个记录其对应的秒数的数组(seconds)。
  2. 将日志分成 登录,登出 两种状态,并且根据时间进行正向排序
  3. 遍历步骤2得到的日志,如果是登录则 currentVal + 1 并且跟 maxVal 对比,如果比 maxVal 大,则将 maxVal 设置为 currentVal, seconds 设置为 当前秒数, 如果 maxVal == currentVal, 则 seconds 增加当前秒数。如果是登出,则 currentVal - 1 (不过更完美点应该判断下当前是不是maxVal, 如果是则将上一次峰值的秒数,到当前秒数的区间写入到 seconds
  4. 遍历完成之后得到的 maxVal 就是 峰值, seconds 就是对应的秒数列表

比如说,日志长这样

uid        登录时间         登出时间
uid1       00:00:01        00:00:10
uid2       00:00:02        00:00:05
uid3       00:00:03        00:00:05

步骤2中,将其变成

uid     action      时间     
uid1    登入     00:00:01    
uid2    登入     00:00:02
uid3    登入     00:00:03    
uid2    登出     00:00:05  // 到这里的时候需要 将上一次峰值到当前值(00:00:03 到 00:00:04 )写入到 seconds
uid3    登出     00:00:05
uid1    登出     00:00:10

步骤三

`currentVal` -> 1   -> 2   -> 3   -> 2   -> 1   -> 0
`maxVal`     -> 1   -> 2   -> 3   -> 3   -> 3   -> 3
`seconds`    -> [1] -> [2] -> [3] -> [3,4] -> [3,4] -> [3,4] 

最后,好像虽然做不出来,面试还是过了,感谢面试官抬一手。 如果有更好的解法,或者这个解法有问题,也方便留言。

1. 简单实现

一般能想到的实现应该是记录一个 current index, 再取mod, 存在的问题是请求不够平滑。
例如, 要对3台机器进行 加权轮询负载均衡, 权重分别是 1,2,3

机器权重
0011
0022
0033

那么结果是

次数indexmod结果命中机器
100001
211002
322002
433003
544003
655003
750001

...

存在的问题,请求会不平滑, 同一台机器的请求会比较集中,比如上面的结果,后面3次集中在 003 的机器。

2. 更好的算法

每个后端peer都有三个权重变量,先解释下它们的含义。

(1) weight

配置文件中指定的该后端的权重,这个值是固定不变的。

(2) current_weight

后端目前的权重,一开始为0,之后会动态调整。那么是怎么个动态调整呢?

每次选取后端时,会遍历集群中所有后端,对于每个后端,让它的current_weight增加它的effective_weight,

同时累加所有后端的weight,保存为total。

如果该后端的current_weight是最大的,就选定这个后端,然后把它的current_weight减去total。

如果该后端没有被选定,那么current_weight不用减小。

 

弄清了三个weight字段的含义后,加权轮询算法可描述为:

1 对于每个请求,遍历集群中的所有可用后端,对于每个后端peer执行:

  peer->current_weight += peer->effecitve_weight。
  同时累加所有peer的effective_weight,保存为total。

2 从集群中选出current_weight最大的peer,作为本次选定的后端。

3 对于本次选定的后端,执行:peer->current_weight -= total。

还是上面 3台机器 , 权重分别是 1,2,3

机器权重
0011
0022
0033

那么结果是
WXWorkCapture_15764984078276.png

请求就稍微平滑些了

参考:
Dubbo加权轮询负载均衡的源码和Bug,了解一下?
Nginx的负载均衡 - 加权轮询 (Weighted Round Robin) 上篇

原文:https://juejin.im/post/5cd823f9e51d453abb1397d7

一、前言

最近有个需求,要计算出客户坐标附近5公里的所有门店,并按照步行距离排序。
最直接的方法就是遍历该城市下的所有门店,但是该方法明显不可取,因为在门店数量巨大,且还需要计算步行距离并排序的情况下,时间复杂度过高。
突然想到当年做图像遇见一个问题:给定一个视频中连续的三千帧,但是已经乱序,告诉你第一帧,将这三千帧进行排序。遍历图像的所有像素点同样不可取,当时的解决方案是利用感知哈希计算出所有图像的指纹,接着利用明氏距离计算距离第一张最近的图像作为第二张,然后计算距离第二张最近的作为第三张,以此类推。
同样,肯定也有哈希方法可将地理位置转换成某种编码,并且编码可用于地理计算。它就是 GeoHash




- 阅读剩余部分 -

原文:如何判断一个元素在亿级数据中是否存在?

Bloom Filter 原理

官方的说法是:它是一个保存了很长的二级制向量,同时结合 Hash 函数实现的。

听起来比较绕,但是通过一个图就比较容易理解了。
bloom filter原理

如图所示:

  • 首先需要初始化一个二进制的数组,长度设为 L(图中为 8),同时初始值全为 0 。
  • 当写入一个 A1=1000 的数据时,需要进行 H 次 hash 函数的运算(这里为 2 次);与 HashMap 有点类似,通过算出的 HashCode 与 L 取模后定位到 0、2 处,将该处的值设为 1。
  • A2=2000 也是同理计算后将 4、7 位置设为 1。
  • 当有一个 B1=1000 需要判断是否存在时,也是做两次 Hash 运算,定位到 0、2 处,此时他们的值都为 1 ,所以认为 B1=1000 存在于集合中。
  • 当有一个 B2=3000 时,也是同理。第一次 Hash 定位到 index=4 时,数组中的值为 1,所以再进行第二次 Hash 运算,结果定位到 index=5 的值为 0,所以认为 B2=3000 不存在于集合中。

整个的写入、查询的流程就是这样,汇总起来就是:

对写入的数据做 H 次 hash 运算定位到数组中的位置,同时将数据改为 1 。当有数据查询时也是同样的方式定位到数组中。
一旦其中的有一位为 0 则认为数据肯定不存在于集合,否则数据可能存在于集合中。

所以布隆过滤有以下几个特点:

  1. 只要返回数据不存在,则肯定不存在。
  2. 返回数据存在,但只能是大概率存在。
  3. 同时不能清除其中的数据。

第一点应该都能理解,重点解释下 2、3 点。
为什么返回存在的数据却是可能存在呢,这其实也和 HashMap 类似。
在有限的数组长度中存放大量的数据,即便是再完美的 Hash 算法也会有冲突,所以有可能两个完全不同的 A、B 两个数据最后定位到的位置是一模一样的。
这时拿 B 进行查询时那自然就是误报了。
删除数据也是同理,当我把 B 的数据删除时,其实也相当于是把 A 的数据删掉了,这样也会造成后续的误报。
基于以上的 Hash 冲突的前提,所以 Bloom Filter 有一定的误报率,这个误报率和 Hash 算法的次数 H,以及数组长度 L 都是有关的。