工程算法，说白了就是leetcode上那些传统算法，常见的应用是……面试。本文分享几例在业务开发中的应用
一、搜索提示
市面上的搜索引擎都有搜索提示功能，基础的功能是前缀匹配，其他还有拼写纠错（如图，值得打成了指的，依然有推荐“值得”）、按照一些统计数据优化推荐（比如搜索量越大的排在越上面）
开发一个面向C端用户的完善的搜索提示要考虑上述很多功能细节，比较麻烦，但是在工作中，我们肯定会接手各种各样的输入框，这些输入框并没有那么关键（总不能是个输入框就按照上面搞一套搜索提示），或者是仅对公司内部人员开放的内部配置平台，给这些输入框添加只支持前缀匹配的搜索提示还是比较简单的。
那么，前缀匹配怎么做呢？
1.1. 方案A: 数据库like查询
这种方案比较直接，不细说了。缺点是数据量大的时候查库比较慢，而且如果这个输入框是个面向C端用户的输入框，那还得考虑如果流量大怎么办、如果流量不大但是被恶意访问导致流量大了怎么办。
另外还有个缺点，数据库不好做拼写纠错
1.2. 方案B: 在内存里构建字典树
另一种方案是在内存中构建一个字典树缓存，输入数据后直接通过字典树做前缀匹配，这种方案的优点是匹配更快，且不用担心流量大的情况，能做拼写纠错（下文详述）。我找了下leetcode还真有这样的面试题，感兴趣的可以尝试下。
1.2.1. 实践中的优化与细节
1.2.1.1. 注意字符集大小
如果自己实现一个R-way Trie（就是每个节点在数组里存储下一个节点）会存在一个问题：空间复杂度是O(NwR)，依赖于字符集的大小R，如果只是26个英文字母还好，而如果是字符集2字节，每个节点就要开辟大小是65536的数组，太耗费空间。
因此实践中我用的是 Apache包下的Patricia Trie。Patricia Trie相对于普通的R-way Trie，一方面把只有单节点的细长分支压缩成了一个节点，另一方面其基于2进制比较，空间复杂度与字符集大小R无关（严格的说是和logR相关），其存储结构大概如图，每个节点只有两个子节点（而普通的Trie里每个节点要开R个空间用来存子节点）
1.2.1.2. 并发安全
大致看了Apache实现里的代码，没做并发安全的处理，因此自己封装了一层读写锁。
1.2.1.3. Patricia Trie做前缀匹配：有些API会遍历所有数据
用之前建议仔细看文档或源码，有些操作prefixMap("xxx").firstKey()是会遍历所有数据的，需要避免使用
1.2.2. Follow Up:内存存不下怎么办？
假如这是一场技术面试，那么到这里自然会产生下一个问题：如果数据太多，内存里存不下整个Trie该怎么办？
解决的思路是把Trie分散放在多台机器上。可以对前两个字符做一致性hash来路由机器，比如以ab开头的词都在机器1，以ac开头的词都在机器3。
当然，假如这是一场技术面试，那么随之而来又会产生新的问题：假如有数据倾斜怎么办，有访问热点怎么办？这里就不展开了，哈哈。
二、拼写纠错
搜索引擎还有个常用功能，如果拼写错了会进行纠错并提示用户，如图。
完善的拼写纠错功能往往使用基于统计的算法，我们的思路还是简单的问题简单解决，不是关键输入框就不搞那么复杂（其实是因为复杂的算法我不会，嘿嘿）这里介绍基于编辑距离的拼写纠错。
2.1. 方案A:计算两个单词的最小编辑距离
首先想到的算法是遍历字典，求输入字符串和字典里每个单词的最小编辑距离，这感觉是很经典的动态规划题目（来来来，复习下动态规划，来写下这道题）
但是这么搞需要对字典里每个单词都求一次，时间复杂度太高。怎么优化呢？
2.2. 方案B:反向编辑距离
如果字典里单词太多，一个优化思路是反过来，即先从查询词生成可能的候选集，找出候选集里在词典出现的词。例如用户输入birthdai，我们发现这个词搜不到东西，那么先来找只需要做一次修改操作就能生成birthdai的词，包括*irthdai,b*rthdai,bi*thdai...birthda* 然后一个一个看他们是否在字典中出现。
2.2.1. 实践中的取舍
2.2.1.0. 使用哪种编辑距离
编辑距离问题有很多种，有的是支持增、删操作，有的是支持增删改操作，鉴于实践中经常把两个字母打错位(比如chain打成了chian)，我选择的是支持增、删、改、交换操作的编辑距离。
2.2.1.1. 把数据都放到内存
全放数据库的话，做一次拼写纠错就要调几百次数据库。
2.2.1.2. 震惊！Apache的Patricia Trie不支持通配符匹配
我写代码写到一半才发现Apache的Patricia Trie不支持通配符匹配……
没办法，简单一点，用丑一点的算法。假设拼写纠错算法只支持由英文字母和下划线构成的字符串，比如用户想打birthday但是输入了birthdai，算法对每一个字符尝试替换、删除、插入、交换，替换只尝试替换为英文字母和下划线。例如尝试把第一位的b替换为acdef...,相应的字符串为airthdai,cirthdai,dirthdai...以此类推。
三、年会上的程序员：抽奖算法怎么写？
年会的时候少不了抽奖环节，抽奖算法怎么写呢？
来来来，请做题：
有50个员工参加年会，抽取一二三等奖，分别有1、2、3人中奖。
有100个员工参加年会，抽取一二三等奖和阳光普照奖，分别有1、2、3、50个员工中奖（我也不知道为啥阳光普照照不到剩下的人）
……
有20万员工，抽取5万人获得阳光普照奖。
有14亿员工，抽取1万人获得阳光普照奖。
有N个员工，抽取K个员工获得阳光普照奖。
应该怎么写才能保证抽奖公平呢？
3.1. hashmap判重呗
把中过奖的员工id存到hashmap里，每次生成一个随机数代表员工id，看看hashmap里有没有，有就重新随机，没有就说明这人中奖了。
3.2. 排序
给每个员工生成一个随机数代表他们的得分，然后找出分值排名在前K个的员工，代表中奖。
3.3. 洗牌算法
《算法导论》介绍过把数组随机打乱的洗牌算法，感兴趣可以复习一下
3.4. 蓄水池抽样
洗牌算法得把整个数组都放内存里，假如在14亿人中抽取1万人发奖（？？）如果14亿人全放内存里太大了，那么可以用蓄水池抽样，内存里只需要放1万人就好了
3.5. 黑名单映射法
每次随机范围缩小，对黑名单建立映射。见
https://leetcode-cn.com/problems/random-pick-with-blacklist/solution/hei-ming-dan-zhong-de-sui-ji-shu-by-leetcode-2
3.6. 填窟窿法
https://leetcode-cn.com/problems/insert-delete-getrandom-o1-duplicates-allowed
你会用哪种算法呢？
