ARTS 打卡 Week3

Algorithm

• 编辑距离 - 提交记录 - 力扣（LeetCode）
  

Go 版本实现如下

• 思路：动态规划

• 具体实现：编辑距离：s1->s2 最短距离

  dp[i][j] 表示 s1[0..i] 和 s2[0..j] 的最小编辑距离，i 表示 s1 中前 i 个元素，j 表示 s2 中前 j 个元素

  base case：dp[i][0]= i; dp[0][j] = j; 很好理解：s2 为空，s1 有多少字符就删多少，s1 为空，s2 有多少字符，s1 就加多少。

• 当 s1[i-1] == s2[j-1]时，dp[i][j]等于 dp[i-1][j-1]编辑距离跳过 i,j 字符。

• 当 s1[i-1] != s2[j-1]时，dp[i][j]等于 dp[i][j-1]编辑距离即 s1[0:i]已经转成 s2[0:j-1]了。然后在 i 后面增一个 s2[j-1]字符或者 dp[i-1][j]编辑距离然后删掉 s1[i-1]或者 dp[i-1][j]编辑距离然后 s1[i-1]替换 s2[j-1]。

  注意：始终要记得:dp[i][j]表示 s1 前 i 个字符经过操作后到 s2 的前 j 个字符。

func minDistance(word1 string, word2 string) int {    m, n := len(word1), len(word2)    if len(word1) == 0 {        return n    }    if len(word2) == 0 {        return m    }    dp := make([][]int, m+1)    for i := 0; i <= m; i++ {        dp[i] = make([]int, n+1)        dp[i][0] = i    }    for j := 0; j <= n; j++ {        dp[0][j] = j    }    for i := 1; i <= m; i++ {        for j := 1; j <= n; j++ {            if word1[i-1] == word2[j-1] {                dp[i][j] = dp[i-1][j-1]            } else {                dp[i][j] = min(dp[i][j-1], min(dp[i-1][j-1], dp[i-1][j])) + 1            }        }    }    return dp[m][n]}
func min(i, j int) int {    if i < j {        return i    }    return j}

Review

• Books/grok_system_design_interview.pdf at main · WaitBright/Books (github.com)
  

• 继续学习系统设计，阅读了 Grokking the System Design Interview 第二章，总结如下

1. 这一章要求设计一个 URL 变短的服务。首先要明确该项目的意义，有两条：节省空间和减少用户打错链接的几率。

2. 然后要明确需求目标和范围，包括三个方面：功能性需求、非功能性需求和其他需求。

功能性需求：

1. 输入原始 url 输出短+唯一 url

2. 用户访问短 url，重定向到原始 url

3. 支持用户自定义短 url 唯一性

4. 设置默认过期时间，且用户也能设置过期时间

• 非功能性需求：

1. 高可用，不用出现所以链接重定向问题

2. 实时重定向

3. 短连接不能轻易猜到

其他需求：

1. 数据统计：比如重定向发生了多少次

2. 提供三方接口：http

3. 最后就是具体实现，内容比较多，学习了前两点。

4. 资源评估：首先确定这个服务是 read-heavy 类型的，访问量大，读写比假设 100:1。然后进行流量评估：1).假设读写比：100:1 产生 5 亿 urls/month 短连接。2).则读即重定向 500 亿/month。则 QPS=50 000 000 000/ (30 * 24 * 3600) = 20000 q/s。再进行存储评估：假设存 5 年 则 5 * 12 * 5 亿 = 300 亿 url 对象(包括原始和短链接) 每个对象 500B 则 150 000 亿 B = 15TB 即 15T 存储。接着作带宽评估：写 qps = 20000/100 = 200，则写带宽 200 * 500B = 100 KB/s 读(重定向) 10MB/s。最后要内存评估：2-8 准则，80%流量访问 20%资源。20% url 要 cache。一天流量：20 K/s * 3600 * 24=17 亿 次请求，则只存 17 亿请求中对应的 20% 资源即 17 亿 * 500B * 0.2 = 170GB 对象，当然 17 亿请求肯定大量都是重复的对象，所以存储实际没有这么多，按照 HLE(高水平评估)来做。

5. 系统 API 设计：这里要考虑三个点：1)url 创建接口：createURL(api_dev_key, original_url, custom_alias=None, user_name=None, expire_date=None)。2) url 删除接口：deleteURL(api_dev_key, url_key)。3)怎样防止用户恶意生成 url key：主要采取限制用户生成短 url 个数和某时间段重连接次数这两种方式。

Technique/Tips

• 几个提升Go语言开发效率的小技巧 - 掘金 (juejin.cn)
  

继续学习 Go 的相关技巧，这次学习的内容包括：可变长参数、不定长数组、init 函数、忽略导包、json 序列化等技巧。学习素材如上。

• 可变长参数：需要知道的有三点：函数参数列表最后一个、当切片处理和类型相同。

• 不定长数组：不想写数组长度时使用...声明数组来填充元素值，其他交给编译器处理。

• init 函数：实现了sync.Once，无论包被导入多少次，init 函数只会被执行一次；init 函数执行过程如下：

从当前包开始，如果当前包包含多个依赖包，则先初始化依赖包，层层递归初始化各个包，在每一个包中，按照源文件的字典序从前往后执行，每一个源文件中，优先初始化常量、变量，最后初始化init函数，当出现多个init函数时，则按照顺序从前往后依次执行，每一个包完成加载后，递归返回，最后在初始化当前包！

• 忽略导包：只想初始化包里的init函数，而不会使用包内的任何方法，这时就可以使用 _ 操作符号重命名导入一个不使用的包。

• json 序列化：要关注两个点：1)struct 字段不想序列化用"-"。2) 忽略空值在 tag 中加入 omitempty。

Share

• 09 | 答疑解惑：渴望、热情和选择 (geekbang.org)
  

• 这次想分享的话题是：怎样选择自己的人生和职业发展？参考皓哥的这边文章谈下自己的看法。

• 首先要知己知彼，要知道自己的兴趣所在，这是最重要也是要最早解决的问题。人生是有限的，不可能所有的东西都有时间学，所以要把时间花费在感兴趣的事上才会没有遗憾。同时要对自己有一定的认识，怎么来认识自己呢？多去和周围环境碰撞吧。想知道自己技术怎么样，那就去面试吧；想知道自己交际能力怎么样，那就去和同行、兴趣相同的人、陌生人交流吧。

• 然后要注重长期主义。当前所遇到的问题可能会觉得非常难，感到非常痛苦，而拉长时间，从 5 年后、10 年后的角度看啥也不是，多用这种心态看问题会放松很多。