主要是聊基礎(chǔ)算法知識和代碼題。
又到安利Python的時(shí)間， 最終代碼不超過30行（優(yōu)化前），加上優(yōu)化也不過40行。
第一步. 構(gòu)造Trie（用dict登記結(jié)點(diǎn)信息和維持子結(jié)點(diǎn)集合）：
-- 思路：對詞典中的每個(gè)單詞，逐詞逐字母拓展Trie，單詞完結(jié)處的結(jié)點(diǎn)用None標(biāo)識。
def make_trie(words):
trie = {}
for word in words:
t = trie
for c in word:
if c not in t: t[c] = {}
t = t[c]
t[None] = None
return trie
第二步. 容錯(cuò)查找（容錯(cuò)數(shù)為tol）：
-- 思路：實(shí)質(zhì)上是對Trie的深度優(yōu)先搜索，每一步加深時(shí)就消耗目標(biāo)詞的一個(gè)字母。當(dāng)搜索到達(dá)某個(gè)結(jié)點(diǎn)時(shí)，分為不消耗容錯(cuò)數(shù)和消耗容錯(cuò)數(shù)的情形，繼續(xù)搜索直到目標(biāo)詞為空。搜索過程中，用path記錄搜索路徑，該路徑即為一個(gè)詞典中存在的詞，作為糾錯(cuò)的參考。
-- 最終結(jié)果即為諸多搜索停止位置的結(jié)點(diǎn)路徑的并集。
def check_fuzzy(trie, word, path='', tol=1):
if word == '':
return {path} if None in trie else set()
else:
p0 = set()
if word[0] in trie:
p0 = check_fuzzy(trie[word[0]], word[1:], path+word[0], tol)
p1 = set()
if tol > 0:
for k in trie:
if k is not None and k != word[0]:
p1.update(check_fuzzy(trie[k], word[1:], path+k, tol-1))
return p0 | p1簡單測試代碼 ------
構(gòu)造Trie：
words = ['hello', 'hela', 'dome']
t = make_trie(words)
In [11]: t
Out[11]:
{'d': {'o': {'m': {'e': {'$': {}}}}},
'h': {'e': {'l': {'a': {'$': {}}, 'l': {'o': {'$': {}}}}}}}
容錯(cuò)查找：
In [50]: check_fuzzy(t, 'hellu', tol=0)
Out[50]: {}
In [51]: check_fuzzy(t, 'hellu', tol=1)
Out[51]: {'hello'}
In [52]: check_fuzzy(t, 'healu', tol=1)
Out[52]: {}
In [53]: check_fuzzy(t, 'healu', tol=2)
Out[53]: {'hello'}
似乎靠譜~
---------------------------分--割--線--------------------------------------
以上是基于Trie的approach，另外的approach可以參看@黃振童鞋推薦Peter Norvig即P神的How to Write a Spelling Corrector
雖然我已有意無意模仿P神的代碼風(fēng)格，但每次看到P神的源碼還是立馬跪...
話說word[1:]這種表達(dá)方式其實(shí)是有淵源的，相信有的童鞋對(cdr word)早已爛熟于心...（呵呵
------------------------分-----割-----線-----二--------------------------------------
回歸正題.....有童鞋說可不可以增加新的容錯(cuò)條件，比如增刪字母，我大致對v2方法作了點(diǎn)拓展，得到下面的v3版本。
拓展的關(guān)鍵在于遞歸的終止，即每一次遞歸調(diào)用必須對參數(shù)進(jìn)行有效縮減，要么是參數(shù)word，要么是參數(shù)tol~
def check_fuzzy(trie, word, path='', tol=1):
if tol < 0:
return set()
elif word == '':
results = set()
if None in trie:
results.add(path)
# 增加詞尾字母
for k in trie:
if k is not None:
results |= check_fuzzy(trie[k], '', path+k, tol-1)
return results
else:
results = set()
# 首字母匹配
if word[0] in trie:
results |= check_fuzzy(trie[word[0]], word[1:], path + word[0], tol)
# 分情形繼續(xù)搜索（相當(dāng)于保留待探索的回溯分支）
for k in trie:
if k is not None and k != word[0]:
# 用可能正確的字母置換首字母
results |= check_fuzzy(trie[k], word[1:], path+k, tol-1)
# 插入可能正確的字母作為首字母
results |= check_fuzzy(trie[k], word, path+k, tol-1)
# 跳過余詞首字母
results |= check_fuzzy(trie, word[1:], path, tol-1)
# 交換原詞頭兩個(gè)字母
if len(word) > 1:
results |= check_fuzzy(trie, word[1]+word[0]+word[2:], path, tol-1)
return results好像還是沒有過30行……注釋不算（
本答案的算法只在追求極致簡潔的表達(dá)，概括問題的大致思路。至于實(shí)際應(yīng)用的話可能需要很多Adaption和Tuning，包括基于統(tǒng)計(jì)和學(xué)習(xí)得到一些詞語校正的bias。我猜測這些拓展都可以反映到Trie的結(jié)點(diǎn)構(gòu)造上面，比如在結(jié)點(diǎn)處附加一個(gè)概率值，通過這個(gè)概率值來影響搜索傾向；也可能反映到更多的搜索分支的控制參數(shù)上面，比如增加一些更有腦洞的搜索分支。（更細(xì)節(jié)的問題這里就不深入了逃
----------------------------------分-割-線-三----------------------------------------
童鞋們可能會關(guān)心時(shí)間和空間復(fù)雜度的問題，因?yàn)樯鲜鲞@種優(yōu)（cu）雅（bao）的寫法會導(dǎo)致產(chǎn)生的集合對象呈指數(shù)級增加，集合的合并操作時(shí)間也指數(shù)級增加，還使得gc不堪重負(fù)。而且，我們并不希望搜索算法一下就把所有結(jié)果枚舉出來（消耗的時(shí)間亦太昂貴），有可能我們只需要搜索結(jié)果的集合中前三個(gè)結(jié)果，如果不滿意再搜索三個(gè)，諸如此類...
那腫么辦呢？................是時(shí)候祭出yield小魔杖了? ??)ノ
下述版本姑且稱之為lazy，看上去和v3很像（其實(shí)它倆在語義上是幾乎等同的
def check_lazy(trie, word, path='', tol=1):
if tol < 0:
pass
elif word == '':
if None in trie:
yield path
# 增加詞尾字母
for k in trie:
if k is not None:
yield from check_lazy(trie[k], '', path + k, tol - 1)
else:
if word[0] in trie:
# 首字母匹配成功
yield from check_lazy(trie[word[0]], word[1:], path+word[0], tol)
# 分情形繼續(xù)搜索（相當(dāng)于保留待探索的回溯分支）
for k in trie:
if k is not None and k != word[0]:
# 用可能正確的字母置換首字母
yield from check_lazy(trie[k], word[1:], path+k, tol-1)
# 插入可能正確的字母作為首字母
yield from check_lazy(trie[k], word, path+k, tol-1)
# 跳過余詞首字母
yield from check_lazy(trie, word[1:], path, tol-1)
# 交換原詞頭兩個(gè)字母
if len(word) > 1:
yield from check_lazy(trie, word[1]+word[0]+word[2:], path, tol-1)不借助任何容器對象，我們近乎聲明式地使用遞歸子序列拼接成了一個(gè)序列。
[新手注釋] yield是什么意思呢？就是程序暫停在這里了，返回給你一個(gè)結(jié)果，然后當(dāng)你調(diào)用next的時(shí)候，它從暫停的位置繼續(xù)走，直到有下個(gè)結(jié)果然后再暫停。要理解yield，你得先理解yield... Nonono，你得先理解iter函數(shù)和next函數(shù)，然后再深入理解for循環(huán)，具體內(nèi)容童鞋們可以看官方文檔。而yield from x即相當(dāng)于for y in x: yield y。
給剛認(rèn)識yield的童鞋一個(gè)小科普，順便回憶一下組合數(shù)C(n,m)的定義即
C(n, m) = C(n-1, m-1) + C(n-1, m)
如果我們把C視為根據(jù)n和m確定的集合，加號視為并集，利用下面這個(gè)generator我們可以懶惰地逐步獲取所有組合元素：
def combinations(seq, m):
if m > len(seq):
raise ValueError('Cannot choose more than sequence has.')
elif m == 0:
yield ()
elif m == len(seq):
yield tuple(seq)
else:
for p in combinations(seq[1:], m-1):
yield (seq[0],) + p
yield from combinations(seq[1:], m)
for combi in combinations('abcde', 2):
print(combi)可以看到，generator結(jié)構(gòu)精準(zhǔn)地反映了集合運(yùn)算的特征，而且蘊(yùn)含了對元素進(jìn)行映射的邏輯，可讀性非常強(qiáng)。
OK，代碼到此為止。利用next函數(shù)，我們可以懶惰地獲取查找結(jié)果。
In [54]: words = ['hell', 'hello', 'hela', 'helmut', 'dome']
In [55]: t = make_trie(words)
In [57]: c = check_lazy(t, 'hell')
In [58]: next(c)
Out[58]: 'hell'
In [59]: next(c)
Out[59]: 'hello'
In [60]: next(c)
Out[60]: 'hela'話說回來，lazy的一個(gè)問題在于我們不能提前預(yù)測并剔除重復(fù)的元素。你可以采用一個(gè)小利器decorator，修飾一個(gè)generator，保證結(jié)果不重復(fù)。
from functools import wraps
def uniq(func):
@wraps(func)
def _func(*a, **kw):
seen = set()
it = func(*a, **kw)
while 1:
x = next(it)
if x not in seen:
yield x
seen.add(x)
return _func這個(gè)url打開的文件包含常用英語詞匯，可以用來測試代碼：
In [10]: import urllib
In [11]: f = urllib.request.urlopen("https://raw.githubusercontent.com/eneko/data-repository/master/data/words.txt")
# 去除換行符
In [12]: t = make_trie(line.decode().strip() for line in f.readlines())
In [13]: f.close()----------------------分-割-線-四-----------------------------
最后的最后，Python中遞歸是很昂貴的，但是遞歸的優(yōu)勢在于描述問題。為了追求極致性能，我們可以把遞歸轉(zhuǎn)成迭代，把去除重復(fù)的邏輯直接代入進(jìn)來，于是有了這個(gè)v4版本：
from collections import deque
def check_iter(trie, word, tol=1):
seen = set()
q = deque([(trie, word, '', tol)])
while q:
trie, word, path, tol = q.popleft()
if word == '':
if None in trie:
if path not in seen:
seen.add(path)
yield path
if tol > 0:
for k in trie:
if k is not None:
q.appendleft((trie[k], '', path+k, tol-1))
else:
if word[0] in trie:
q.appendleft((trie[word[0]], word[1:], path+word[0], tol))
if tol > 0:
for k in trie.keys():
if k is not None and k != word[0]:
q.append((trie[k], word[1:], path+k, tol-1))
q.append((trie[k], word, path+k, tol-1))
q.append((trie, word[1:], path, tol-1))
if len(word) > 1:
q.append((trie, word[1]+word[0]+word[2:], path, tol-1)) 可以看到，轉(zhuǎn)為迭代方式后我們?nèi)匀豢梢宰畲蟪潭缺Ａ暨f歸風(fēng)格的程序形狀，但也提供了更強(qiáng)的靈活性（對于遞歸，相當(dāng)于我們只能用棧來實(shí)現(xiàn)這個(gè)q）?；谶@種迭代程序的結(jié)構(gòu)，如果你有詞頻數(shù)據(jù)，可以用該數(shù)據(jù)維持一個(gè)最優(yōu)堆q，甚至可以是根據(jù)上下文自動(dòng)調(diào)整詞頻的動(dòng)態(tài)堆，維持高頻詞匯在堆頂，為詞語修正節(jié)省不少性能。這里就不深入了。
【可選的一步】我們在對單詞進(jìn)行糾正的時(shí)候往往傾向于認(rèn)為首字母是無誤的，利用這個(gè)現(xiàn)象可以減輕不少搜索壓力，花費(fèi)的時(shí)間可以少數(shù)倍。
def check_head_fixed(trie, word, tol=1):
for p in check_lazy(trie[word[0]], word[1:], tol=tol):
yield word[0] + p最終我們簡單地benchmark一下：
In [18]: list(check_head_fixed(trie, 'misella', tol=2))
Out[18]:
['micellar',
'malella',
'mesilla',
'morella',
'mysell',
'micelle',
'milla',
'misally',
'mistell',
'miserly']
In [19]: %timeit list(check_head_fixed(trie, 'misella', tol=2))
1.52 ms ± 2.84 μs per loop (mean ± std. dev. of 7 runs, 1000 loops each)在Win10的i7上可以在兩毫秒左右返回所有結(jié)果，可以說令人滿意。
面試題各公司不盡相同。一般而言，都會考一些最基礎(chǔ)的東西，來看你學(xué)的扎不扎實(shí)。
比如，我經(jīng)歷過的面試題里，最經(jīng)常遇到的就是畫出星三角接線圖。相信專業(yè)人員都會知道，但真的讓你在紙上畫出來，你真的能完全無誤的畫好嗎？
再就是最基礎(chǔ)的PLC小功能程序編寫，很常見的小程序，如果，寫不出來，那么被錄用的機(jī)會很小。
算法工程師各種待遇按工作時(shí)間，資歷，等不同，差異很大，基本從4500元到15000元不等。
因?yàn)樽罱紖⒓恿撕脦准夜镜囊纛l算法工程師面試主要總結(jié)一下
1.自我介紹
2.會根據(jù)你自我介紹的內(nèi)容針對性的提問
3.講一下AEC都有哪些步驟
4.講一下自適應(yīng)濾波的原理
5.NLP的步驟
6.噪聲估計(jì)的方法有幾種
基礎(chǔ)知識題：這類題目會測試應(yīng)聘者對硬件工程基礎(chǔ)知識的掌握程度，如電路理論、數(shù)字邏輯、微處理器架構(gòu)等。
請解釋什么是歐姆定律，并給出其在電路設(shè)計(jì)中的應(yīng)用。
描述一下你在數(shù)字電路設(shè)計(jì)中常用的幾種邏輯門電路，并解釋它們的工作原理。
專業(yè)技能題：這些問題會針對應(yīng)聘者的專業(yè)技能進(jìn)行測試，如PCB設(shè)計(jì)、嵌入式系統(tǒng)開發(fā)、硬件調(diào)試等。
你使用過哪些PCB設(shè)計(jì)軟件？請描述一下你設(shè)計(jì)PCB板的流程。
請談?wù)勀阍谇度胧较到y(tǒng)開發(fā)方面的經(jīng)驗(yàn)，包括你使用過的工具和編程語言。
實(shí)踐經(jīng)驗(yàn)題：這類題目會詢問應(yīng)聘者在過去的項(xiàng)目或工作中遇到的實(shí)際問題以及他們的解決方案。
請描述一個(gè)你在硬件調(diào)試過程中遇到的最困難的問題，以及你是如何解決的。
在你的職業(yè)生涯中，有沒有一個(gè)項(xiàng)目讓你特別自豪？為什么？請談?wù)勀阍谶@個(gè)項(xiàng)目中的貢獻(xiàn)。
解決問題能力題：這類題目會提供一個(gè)假設(shè)的場景，要求應(yīng)聘者展示他們?nèi)绾畏治龊徒鉀Q問題。
假設(shè)你在設(shè)計(jì)一個(gè)新的電路板時(shí)，發(fā)現(xiàn)某個(gè)元件的性能不穩(wěn)定，你會如何定位并解決這個(gè)問題？
如果你在一個(gè)緊迫的項(xiàng)目中遇到了一個(gè)技術(shù)難題，而你的團(tuán)隊(duì)成員對此都沒有經(jīng)驗(yàn)，你會怎么做？
行業(yè)知識題：這些問題會測試應(yīng)聘者對硬件工程行業(yè)的了解程度，包括最新的技術(shù)趨勢、市場動(dòng)態(tài)等。
你認(rèn)為目前硬件工程領(lǐng)域最大的技術(shù)挑戰(zhàn)是什么？為什么？
請談?wù)勀銓ξ锫?lián)網(wǎng)（IoT）在硬件工程中的應(yīng)用和未來發(fā)展的看法。
算法工程師是處理數(shù)據(jù)的專業(yè)人士，他們研究并開發(fā)可用于計(jì)算機(jī)程序的算法。原理是基于數(shù)學(xué)和計(jì)算機(jī)科學(xué)的基礎(chǔ)理論，結(jié)合各種技術(shù)來實(shí)現(xiàn)數(shù)據(jù)處理、模型構(gòu)建和性能優(yōu)化等任務(wù)。算法工程師的工作需要了解常用算法的原理，需要掌握數(shù)據(jù)結(jié)構(gòu)、算法復(fù)雜度分析等知識，以及具備編程能力。算法工程師的工作職責(zé)是識別問題、設(shè)計(jì)解決方案，實(shí)現(xiàn)這些方案并優(yōu)化算法的性能。算法的使用和優(yōu)化是算法工程師的核心任務(wù)，他們需要保證算法的準(zhǔn)確性、高效性以及可擴(kuò)展性，以使計(jì)算機(jī)程序能夠高效地進(jìn)行數(shù)據(jù)處理和分析。
答：算法工程師簡稱是cuda。
利用算法處理事物的人
算法（Algorithm）是一系列解決問題的清晰指令，也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。如果一個(gè)算法有缺陷，或不適合于某個(gè)問題，執(zhí)行這個(gè)算法將不會解決這個(gè)問題。
不同的算法可能用不同的時(shí)間、空間或效率來完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來衡量。算法工程師就是利用算法處理事物的人。
我認(rèn)為算法工程師的核心競爭力是對模型的理解，對于模型不僅知其然，還得知其所以然。
于是我把目標(biāo)檢測的經(jīng)典論文翻來覆去地看，將各種目標(biāo)檢測模型分解成了N個(gè)模塊，針對每個(gè)模塊，反復(fù)比對各篇論文處理方式的異同，思考各種處理方式各自的優(yōu)缺點(diǎn)，以及有沒有更好的處理方式，比如：
深度卷積神經(jīng)網(wǎng)絡(luò)中的降采樣總結(jié)了降采樣的各種方式；
深度卷積神經(jīng)網(wǎng)絡(luò)中的升采樣梳理了升采樣的諸多方法；
關(guān)于物體檢測的思考簡述了anchor free與anchor based的異同、one stage和two stage的區(qū)別與聯(lián)系；
深度學(xué)習(xí)高效網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)和高效卷積神經(jīng)網(wǎng)絡(luò)一覽總結(jié)了高效網(wǎng)絡(luò)的設(shè)計(jì)思路與具體細(xì)節(jié)；
在anchor free檢測器炙手可熱的時(shí)候，Why anchor?分析了anchor free和anchor based的歷史由來，以及各自利弊。
同時(shí)對目標(biāo)檢測實(shí)踐中一些開放式的問題也有一些自己的思考，比如：
關(guān)于感受野的總結(jié)詳述了感受野的計(jì)算方式和在應(yīng)用時(shí)需要注意的地方；
目標(biāo)檢測網(wǎng)絡(luò)train from scratch問題猜想了一下目標(biāo)檢測能夠train from scratch的關(guān)鍵，在這篇文章里我質(zhì)疑了DSOD和DropBlock這兩篇論文對train from scratch問題下的結(jié)論（當(dāng)時(shí)何愷明那篇討論train from scratch的paper還沒出來，從何愷明后來paper的實(shí)驗(yàn)看來，我的質(zhì)疑是對的）。
上面是把模型揉碎了看，最近開始有更多時(shí)間與精力接觸除了目標(biāo)檢測以外的任務(wù)，于是思考如何將各個(gè)計(jì)算機(jī)視覺任務(wù)統(tǒng)一起來，最近有了一點(diǎn)小的想法，該想法形成了一篇簡短的文章。
第二階段
這一階段我認(rèn)為算法工程師的核心競爭力在于代碼功底好，一則知道各個(gè)模型的實(shí)現(xiàn)細(xì)節(jié)，二則能即快又好地實(shí)現(xiàn)idea。于是我用pytorch手?jǐn)]了Yolov2和Yolov3。同時(shí)看了不少優(yōu)秀的開源代碼，比如darknet、mmdetection等等。最近正在用pytorch仿照mmdetection擼一個(gè)語意分割的訓(xùn)練框架。
第三階段
最近開始接觸各個(gè)行業(yè)對計(jì)算機(jī)視覺的需求，我發(fā)現(xiàn)一名優(yōu)秀的算法工程師僅僅對模型理解不錯(cuò)、代碼功底不錯(cuò)是不夠的，還需要對有計(jì)算機(jī)視覺業(yè)務(wù)需求的行業(yè)有著較深入的理解。恰好最近看了一篇阿里云機(jī)器智能首席科學(xué)家閔萬里的專訪文章，專訪里這幾段話我深以為然：
在阿里云的時(shí)候，我就親自打造了一個(gè)崗位：DTC：Data Technology Consultant。DT有兩個(gè)含義，一個(gè)是數(shù)據(jù)技術(shù)Data Technology，一個(gè)是數(shù)字化轉(zhuǎn)型Digital Transformation，一語雙關(guān)。他們像大夫，望聞問切，跟客戶一起梳理出業(yè)務(wù)流程中的痛點(diǎn)，找到優(yōu)化方式。DTC不只是對行業(yè)整體的判斷，還要對賽道中的選手體檢，有開藥的能力。可以把對方的難言之隱梳理出來，定量、優(yōu)先級排序，然后從整體到細(xì)節(jié)，一層層結(jié)構(gòu)化分解，最后進(jìn)入具體執(zhí)行。你要在傳統(tǒng)行業(yè)創(chuàng)造新價(jià)值，就要搞清楚：什么東西制約了你的產(chǎn)能，制約了你的效率，制約了你的利潤率。技術(shù)人員今天往產(chǎn)業(yè)走，我相信整體遇到的障礙就是如何把技術(shù)思維變成以業(yè)務(wù)需求為導(dǎo)向的技術(shù)思維、技術(shù)分解思維。
雖然閔萬里這幾段話里的主體是技術(shù)咨詢師，但我覺得這也是成為一名優(yōu)秀算法工程師的必備品質(zhì)。
總結(jié)一段話就是：
算法工程師往產(chǎn)業(yè)里走，需要把技術(shù)思維轉(zhuǎn)變?yōu)橐詷I(yè)務(wù)需求為導(dǎo)向的技術(shù)思維、技術(shù)分解思維；
算法工程師需要像大夫一樣望聞問切，跟客戶一起梳理出業(yè)務(wù)流程中的痛點(diǎn)，找到優(yōu)化方式；
算法工程師不僅需要有對行業(yè)整體的判斷，還需要對客戶有體檢、開藥的能力，可以把客戶的難言之隱梳理出來，定量、優(yōu)先級排序，然后整體到細(xì)節(jié)，一層層結(jié)構(gòu)化分解，最后進(jìn)入具體執(zhí)行；
要在傳統(tǒng)行業(yè)創(chuàng)造新價(jià)值就要搞清楚什么東西制約了產(chǎn)能、效率、利潤率。
僅僅輸出模型的算法工程師比較容易被替代，更高的追求是輸出一整套端到端的系統(tǒng)方案，從與客戶一起梳理業(yè)務(wù)痛點(diǎn)、硬件選型、模型部署環(huán)境的規(guī)劃與搭建、數(shù)據(jù)采集和標(biāo)注標(biāo)準(zhǔn)制定、模型選型與設(shè)計(jì)等等。
面試流媒體工程師的流程1、自我介
面試的流程 1、自我介紹 2、你做過最自豪的項(xiàng)目 3、SQL題目 4、互相交流 這是一般的面試流程，自我介紹部分基本是我在說，面試官在聽，項(xiàng)目介紹自我感覺一般，說了之前一個(gè)媒體業(yè)務(wù)的項(xiàng)目；SQL題目考察的是留存的寫法；最后是交流一下公司的工作時(shí)間，常做的工作等等。
