工程算法，說白了就是leetcode上那些傳統(tǒng)算法熔任，常見的應(yīng)用是……面試褒链。本文分享幾例在業(yè)務(wù)開發(fā)中的應(yīng)用
一、搜索提示
市面上的搜索引擎都有搜索提示功能疑苔，基礎(chǔ)的功能是前綴匹配甫匹，其他還有拼寫糾錯（如圖，值得打成了指的夯巷，依然有推薦“值得”）赛惩、按照一些統(tǒng)計數(shù)據(jù)優(yōu)化推薦（比如搜索量越大的排在越上面）
開發(fā)一個面向C端用戶的完善的搜索提示要考慮上述很多功能細(xì)節(jié)，比較麻煩趁餐，但是在工作中喷兼，我們肯定會接手各種各樣的輸入框，這些輸入框并沒有那么關(guān)鍵（總不能是個輸入框就按照上面搞一套搜索提示）后雷，或者是僅對公司內(nèi)部人員開放的內(nèi)部配置平臺季惯，給這些輸入框添加只支持前綴匹配的搜索提示還是比較簡單的。
那么臀突，前綴匹配怎么做呢勉抓？
1.1. 方案A: 數(shù)據(jù)庫like查詢
這種方案比較直接，不細(xì)說了候学。缺點(diǎn)是數(shù)據(jù)量大的時候查庫比較慢藕筋，而且如果這個輸入框是個面向C端用戶的輸入框，那還得考慮如果流量大怎么辦梳码、如果流量不大但是被惡意訪問導(dǎo)致流量大了怎么辦隐圾。
另外還有個缺點(diǎn)伍掀，數(shù)據(jù)庫不好做拼寫糾錯
1.2. 方案B: 在內(nèi)存里構(gòu)建字典樹
另一種方案是在內(nèi)存中構(gòu)建一個字典樹緩存，輸入數(shù)據(jù)后直接通過字典樹做前綴匹配暇藏，這種方案的優(yōu)點(diǎn)是匹配更快蜜笤，且不用擔(dān)心流量大的情況，能做拼寫糾錯（下文詳述）盐碱。我找了下leetcode還真有這樣的面試題把兔，感興趣的可以嘗試下。
1.2.1. 實踐中的優(yōu)化與細(xì)節(jié)
1.2.1.1. 注意字符集大小
如果自己實現(xiàn)一個R-way Trie（就是每個節(jié)點(diǎn)在數(shù)組里存儲下一個節(jié)點(diǎn)）會存在一個問題：空間復(fù)雜度是O(NwR)瓮顽，依賴于字符集的大小R县好，如果只是26個英文字母還好，而如果是字符集2字節(jié)趣倾，每個節(jié)點(diǎn)就要開辟大小是65536的數(shù)組聘惦，太耗費(fèi)空間。
因此實踐中我用的是 Apache包下的Patricia Trie儒恋。Patricia Trie相對于普通的R-way Trie，一方面把只有單節(jié)點(diǎn)的細(xì)長分支壓縮成了一個節(jié)點(diǎn)黔漂，另一方面其基于2進(jìn)制比較诫尽，空間復(fù)雜度與字符集大小R無關(guān)（嚴(yán)格的說是和logR相關(guān)），其存儲結(jié)構(gòu)大概如圖炬守，每個節(jié)點(diǎn)只有兩個子節(jié)點(diǎn)（而普通的Trie里每個節(jié)點(diǎn)要開R個空間用來存子節(jié)點(diǎn)）
1.2.1.2. 并發(fā)安全
大致看了Apache實現(xiàn)里的代碼牧嫉，沒做并發(fā)安全的處理，因此自己封裝了一層讀寫鎖减途。
1.2.1.3. Patricia Trie做前綴匹配：有些API會遍歷所有數(shù)據(jù)
用之前建議仔細(xì)看文檔或源碼酣藻，有些操作prefixMap("xxx").firstKey()是會遍歷所有數(shù)據(jù)的，需要避免使用
1.2.2. Follow Up:內(nèi)存存不下怎么辦鳍置？
假如這是一場技術(shù)面試辽剧，那么到這里自然會產(chǎn)生下一個問題：如果數(shù)據(jù)太多，內(nèi)存里存不下整個Trie該怎么辦税产？
解決的思路是把Trie分散放在多臺機(jī)器上怕轿。可以對前兩個字符做一致性hash來路由機(jī)器辟拷，比如以ab開頭的詞都在機(jī)器1撞羽，以ac開頭的詞都在機(jī)器3。
當(dāng)然衫冻，假如這是一場技術(shù)面試诀紊，那么隨之而來又會產(chǎn)生新的問題：假如有數(shù)據(jù)傾斜怎么辦，有訪問熱點(diǎn)怎么辦隅俘？這里就不展開了邻奠，哈哈笤喳。
二、拼寫糾錯
搜索引擎還有個常用功能惕澎，如果拼寫錯了會進(jìn)行糾錯并提示用戶莉测，如圖。
完善的拼寫糾錯功能往往使用基于統(tǒng)計的算法唧喉，我們的思路還是簡單的問題簡單解決捣卤，不是關(guān)鍵輸入框就不搞那么復(fù)雜（其實是因為復(fù)雜的算法我不會，嘿嘿）這里介紹基于編輯距離的拼寫糾錯八孝。
2.1. 方案A:計算兩個單詞的最小編輯距離
首先想到的算法是遍歷字典董朝，求輸入字符串和字典里每個單詞的最小編輯距離，這感覺是很經(jīng)典的動態(tài)規(guī)劃題目（來來來干跛，復(fù)習(xí)下動態(tài)規(guī)劃子姜，來寫下這道題）
但是這么搞需要對字典里每個單詞都求一次，時間復(fù)雜度太高楼入。怎么優(yōu)化呢哥捕？
2.2. 方案B:反向編輯距離
如果字典里單詞太多，一個優(yōu)化思路是反過來嘉熊，即先從查詢詞生成可能的候選集遥赚，找出候選集里在詞典出現(xiàn)的詞。例如用戶輸入birthdai阐肤，我們發(fā)現(xiàn)這個詞搜不到東西凫佛，那么先來找只需要做一次修改操作就能生成birthdai的詞，包括*irthdai,b*rthdai,bi*thdai...birthda* 然后一個一個看他們是否在字典中出現(xiàn)孕惜。
2.2.1. 實踐中的取舍
2.2.1.0. 使用哪種編輯距離
編輯距離問題有很多種愧薛，有的是支持增、刪操作衫画，有的是支持增刪改操作毫炉，鑒于實踐中經(jīng)常把兩個字母打錯位(比如chain打成了chian)，我選擇的是支持增碧磅、刪碘箍、改、交換操作的編輯距離鲸郊。
2.2.1.1. 把數(shù)據(jù)都放到內(nèi)存
全放數(shù)據(jù)庫的話丰榴，做一次拼寫糾錯就要調(diào)幾百次數(shù)據(jù)庫。
2.2.1.2. 震驚秆撮！Apache的Patricia Trie不支持通配符匹配
我寫代碼寫到一半才發(fā)現(xiàn)Apache的Patricia Trie不支持通配符匹配……
沒辦法四濒，簡單一點(diǎn)，用丑一點(diǎn)的算法。假設(shè)拼寫糾錯算法只支持由英文字母和下劃線構(gòu)成的字符串盗蟆，比如用戶想打birthday但是輸入了birthdai戈二，算法對每一個字符嘗試替換、刪除喳资、插入觉吭、交換，替換只嘗試替換為英文字母和下劃線仆邓。例如嘗試把第一位的b替換為acdef...,相應(yīng)的字符串為airthdai,cirthdai,dirthdai...以此類推鲜滩。
三、年會上的程序員：抽獎算法怎么寫节值？
年會的時候少不了抽獎環(huán)節(jié)徙硅，抽獎算法怎么寫呢？
來來來搞疗，請做題：
有50個員工參加年會嗓蘑，抽取一二三等獎，分別有1匿乃、2桩皿、3人中獎。
有100個員工參加年會幢炸，抽取一二三等獎和陽光普照獎业簿，分別有1、2阳懂、3、50個員工中獎（我也不知道為啥陽光普照照不到剩下的人）
……
有20萬員工柜思，抽取5萬人獲得陽光普照獎岩调。
有14億員工，抽取1萬人獲得陽光普照獎赡盘。
有N個員工号枕，抽取K個員工獲得陽光普照獎。
應(yīng)該怎么寫才能保證抽獎公平呢陨享？
3.1. hashmap判重唄
把中過獎的員工id存到hashmap里葱淳，每次生成一個隨機(jī)數(shù)代表員工id，看看hashmap里有沒有抛姑，有就重新隨機(jī)赞厕，沒有就說明這人中獎了。
3.2. 排序
給每個員工生成一個隨機(jī)數(shù)代表他們的得分定硝，然后找出分值排名在前K個的員工皿桑，代表中獎。
3.3. 洗牌算法
《算法導(dǎo)論》介紹過把數(shù)組隨機(jī)打亂的洗牌算法，感興趣可以復(fù)習(xí)一下
3.4. 蓄水池抽樣
洗牌算法得把整個數(shù)組都放內(nèi)存里诲侮，假如在14億人中抽取1萬人發(fā)獎（镀虐？？）如果14億人全放內(nèi)存里太大了沟绪，那么可以用蓄水池抽樣刮便，內(nèi)存里只需要放1萬人就好了
3.5. 黑名單映射法
每次隨機(jī)范圍縮小，對黑名單建立映射绽慈。見
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
你會用哪種算法呢恨旱？
