https://soulmachine.gitbooks.io/system-design/content/cn/api-rate-limiting.html
https://wizardforcel.gitbooks.io/system-design-primer/4.html#%E7%B3%BB%E7%BB%9F%E8%AE%BE%E8%AE%A1%E4%B8%BB%E9%A2%98%E4%BB%8E%E8%BF%99%E9%87%8C%E5%BC%80%E5%A7%8B
https://www.educative.io/collection/page/5668639101419520/5649050225344512/5668600916475904
敏感词/违禁词过滤
https://cnodejs.org/topic/584514b23ebad99b336b1d92
使用bloom-filter算法,将敏感词打散到内存位数组中,每次将消息放进去看是否匹配到;
细节:特殊字符过滤、换行过滤
文章抄袭检测
构建文本指纹
https://www.infoq.cn/article/how-web-article-utomatically-determine-plagiarism
百度的去重算法最简单,就是直接找出此文章的最长的n句话,做一遍hash签名。n一般取3。 工程实现巨简单,据说准确率和召回率都能到达80%以上。
k-gram字符串匹配算法,逐字符的对比作业文档之间的字符串,当文档间相同的字符串长度达到阈值时,则计入重复度中。
基于编辑距离的句子相似度计算方法
需求分析5W1H8C法
https://www.kancloud.cn/yunhua_lee/oobaodian/110896
How:用例分析法:NEA法
用例的具体写法
https://www.kancloud.cn/yunhua_lee/oobaodian/110897
设计电梯
https://medium.com/system-designing-interviews/design-a-elevator-system-fc5832ca0b8b
Log Structured Merge Trees
Sorted String Tables:
现在小米要举行一次全员野外拉练活动,要求所有员工必须排成一队出去,并且,有的员工要求他必须排在某人的前面或后面,作为组织者的你,收到这样的需求之后,如何给出一个让每个人都满意的排队方式呢?
拓扑排序
系统赠送200钻石,玩家可以把它分成20份并分享给自己的10万个粉丝。假如是你来设计开发这个红包功能,你会怎样解决一下问题?
- 钻石的最小单位是1,如何设计钻石分配算法?
2.红包份数有限,高并发情况下怎么解决固定份数和限额的问题?
3.如果高峰阶段,抢红包的并发请求数可能达到8000次/秒,使用什么样的存储系统可以支持该方案?
1G单词,内存1M,每个词16B以下,返回频率最高的100个。
1.$1M=2^20B / 2^4 = 2^16$ 1M内存只能处理1<<16个单词
2.$1G = 2^30B$ 1G有1<<26个单词
3.所以要把分成至少$2^10$份
4.为了把相同的单词划分到一个小文件 (?)
5.每个文件取top100个
6.归并出top100
多电梯调度 car allocation
341 多层List迭代器
981 key-timestamp-value
输入:inputs = [“TimeMap”,”set”,”get”,”get”,”set”,”get”,”get”], inputs = [[],[“foo”,”bar”,1],[“foo”,1],[“foo”,3],[“foo”,”bar2”,4],[“foo”,4],[“foo”,5]]
输出:[null,null,”bar”,”bar”,null,”bar2”,”bar2”]
解释:
TimeMap kv;
kv.set(“foo”, “bar”, 1); // 存储键 “foo” 和值 “bar” 以及时间戳 timestamp = 1
kv.get(“foo”, 1); // 输出 “bar”
kv.get(“foo”, 3); // 输出 “bar” 因为在时间戳 3 和时间戳 2 处没有对应 “foo” 的值,所以唯一的值位于时间戳 1 处(即 “bar”)
kv.set(“foo”, “bar2”, 4);
kv.get(“foo”, 4); // 输出 “bar2”
kv.get(“foo”, 5); // 输出 “bar2”
1 | class TimeMap { |
729 Calendar1 时间区间有无重叠
1.List<int[]>
两个区间是否重叠s1<e2&&e1>s2
另一种思考
1 | class MyCalendar { |
2.维持一个排序的map(红黑树)二分查找,start当key,end当value
TreeMap
如果不存在,返回小于查询的最大keyfinal Entry<K,V> getFloorEntry(K key)
1
2
3public K floorKey(K key) {
return keyOrNull(getFloorEntry(key));
}
如果不存在,返回大于查询的最小key1
2
3public K ceilingKey(K key) {
return keyOrNull(getCeilingEntry(key));
}
只需要查找query start 的floor的end
query start 的ceil的start1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class MyCalendar {
TreeMap<Integer,Integer> calendar;
public MyCalendar() {
calendar = new TreeMap<>();
}
public boolean book(int start, int end) {
Integer prev = calendar.floorKey(start);
Integer next = calendar.ceilingKey(start);
if((prev==null||calendar.get(prev)<=start)
&&(next==null||end<=next)){
calendar.put(start,end);
return true;
}
return false;
}
}
731 不三重预定的日历
Haversine formula
计算经纬度之间的球面距离
布隆过滤器 url去重
https://blog.csdn.net/v_july_v/article/details/6685894
https://link.springer.com/article/10.1007/s11036-011-0349-8#Sec9
746. Design Tic-Tac-Toe 井字棋
380insert/delete O(1),getRandom O(1)的数据结构
1 | class RandomSet{ |
LFU
gohash
http://redisdoc.com/geo/geoadd.html
redis使用的geohash编码长度为26位。可以精确到0.59m的精度。
将经纬度->字符串,一个字符串表示一个矩形,可以用字符串前缀匹配查找范围
算法步骤:
精确度
https://en.wikipedia.org/wiki/Geohash
https://www.cnblogs.com/LBSer/p/3310455.html
通过对经纬度二分查找不断逼近,将经纬度变成01序列
纬度产生的编码为10111 00011,经度产生的编码为11010 01011。偶数位放经度,奇数位放纬度,把2串编码组合生成新串:11100 11101 00100 01111。
用0-9、b-z(去掉a, i, l, o)这32个字母进行base32编码,将11100 11101 00100 01111转成十进制,对应着28、29、4、15,十进制对应的编码就是wx4g。
实现:
https://github.com/kungfoo/geohash-java
编码部分
Point:1
2
3
4public class Point {
private final double longitude;
private final double latitude;
}
1 | public class GeoHash { |
测试
dr4jb0bn21
dr373nzzdr
f2kjs728301
2
3
4
5
6
7GeoHash hash1 = new GeoHash(40.390943,-75.9375,10);
GeoHash hash2 = new GeoHash(41.390943,-76.9375,10);
GeoHash hash3 = new GeoHash(47.390943,-72.9375,10);
System.out.println(hash1.toBase32());
assert (hash1.toBase32().equals("dr4jb0bn21")):"不等于dr4jb0bn21";
System.out.println(hash2.toBase32());
System.out.println(hash3.toBase32());
加入表示的矩形1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25public class BoundingBox {
private double minLat;
private double maxLat;
private double minLon;
private double maxLon;
public BoundingBox(Point p1, Point p2) {
this(p1.getLatitude(), p2.getLatitude(), p1.getLongitude(), p2.getLongitude());
}
public BoundingBox(double y1, double y2, double x1, double x2) {
minLon = Math.min(x1, x2);
maxLon = Math.max(x1, x2);
minLat = Math.min(y1, y2);
maxLat = Math.max(y1, y2);
}
public Point getUpperLeft() {
return new Point(maxLat, minLon);
}
public Point getLowerRight() {
return new Point(minLat, maxLon);
}
public String toString() {
return getUpperLeft() + " -> " + getLowerRight();
}
}
构造函数最后加上,利用划分最后的经纬度区间setBoundingBox(this, latitudeRange, longitudeRange);
1
2
3
4
5private static void setBoundingBox(GeoHash hash, double[] latitudeRange, double[] longitudeRange) {
hash.boundingBox = new BoundingBox(new Point(latitudeRange[0], longitudeRange[0]), new Point(
latitudeRange[1],
longitudeRange[1]));
}
查询部分:给定senter和半径,查询
算法正确性:
二分法分割空间成01是Peano空间填充曲线。
Peano曲线就是一种四叉树线性编码方式
但是Peano曲线有突变性,0111和1000并不邻近。
解决方法是查询时用周围点一起查询。
数据库只需要存经纬度,查询字符串之后计算距离。
为什么需要空间索引:
http://www.cnblogs.com/LBSer/p/3392491.html
矩形过滤 遍历复杂度高1
select id,name from poi where lng between 116.3284 and 116.3296 and lat between 39.9682 and 39.9694;
对维度建立索引 遍历复杂度变成Log(N)1
alter table lbs add index latindex(lat);
B树其实可以对多个字段进行索引,但这时需要指定优先级,形成一个组合字段,而空间数据在各个维度方向上不存在优先级,我们不能说纬度比经度更重要,也不能说纬度比高程更重要。
其他的空间填充曲线Hilbert最好1
2
3
4
5
6
7
8 0 3 4 5 58 59 60 63
1 2 7 6 57 56 61 62
14 13 8 9 54 55 50 49
15 12 11 10 53 52 51 48
16 17 30 31 32 33 46 47
19 18 29 28 35 34 45 44
20 23 24 27 36 39 40 43
21 22 25 26 37 38 41 42
索引线、折线或者多边形R-tree
弹幕系统
一个直播间:
在线人数100万
1000条弹幕/秒
推送频率:100万*1000条/秒 = 10亿/秒
拉模式:客户端轮询服务端
推模式:长连接 立即推送(时效性)
websocket 将message->frame
go语言携程模型 自带websocket库
604. Design Compressed String Iterator
https://leetcode.com/articles/desing-compressed-string-iterator/
不需要预处理的O(1):1
2
3
4
5
6
7
8
9
10
11
12
13int p=0;
int num=0;
char next(){
if(!hasNext)return ' ';
char ch = s.charAt(p++);
while(p<res.length&&Character.isDigit(s.charAt(p)))
num = num*10+res.charAt(p++)-'0';
num--;
return ch;
}
boolean hasNext(){
return p!=s.length()||num!=0;
}
时间空间复杂度O(n) 压缩编码的长度n
L1e2t1C1o1d1e1
->[1, 2, 1, 1, 1, 1, 1]
->[L, e, t, C, o, d, e]
1 | int[] nums = Arrays.stream(cmprs.substring(1).split("[a-zA-z]")).mapToInt(Integer::parseInt).toArray(); |
next,hasNext
1 | int p=0; |
535 短链接
Base62 编码是由 10 个数字 26 个大些英文字母和 26 个小写英文字母组成base63(md5(str))[6:]
功能要求:
1.过期时间,用户能延长过期时间
2.自定义短链接
非功能要求:
1.系统高可用
2.重定向的延迟
3.连接地址不可预测
扩展:
1.重定向多少次
2.REST api