1樓：汪周洋
這個題目其實這些一億條標題，五萬個敏感詞都是唬人的，就是想考你，給你乙個敏感詞表，然後從乙個文字中找出是否有敏感詞，至於替換是順手的事情，標題數量多也是要乙個個做。核心就是根據敏感詞表建乙個樹可以快速的判斷字串是否有敏感詞。這一般是bat這種公司過濾敏感詞的乙個功能，這其實考不了啥的，沒做過的話一下怎麼想的到
2樓：白起
5萬個敏感詞，想辦法構造出乙個正規表示式就可以大大提高速度了。
正規表示式本質上和DFA是等價的，可能就是他們所說的AC自動機。只是這個東西該怎麼構造，得好好想想。
好像能搜到一些正規表示式自動生成的工具的，看看塞進去五萬個敏感詞會發生什麼情況。
3樓：airBNB
先看看敏感詞表的特點，如果大部分敏感詞處於2到3字的長度，直接用hash表做，每次遍歷標題查詢是否在hash表中。對於部分長度超過3個字的，每次遇到做些額外匹配就行。
4樓：圖圖
-------做些完善--------
拋個磚，寫個思路，權當樂呵
敏感詞：0.5*10^5 個(50k)。
顯然，需要替換的詞相對所有詞來說是少了幾個數量級，所以我的思路是要用盡量少的時間複雜度定位敏感詞。
首先考慮hash表，32bit的位址佔200k Byte，考慮1倍餘量要400kM；平均乙個詞2個漢字算，utf-8編碼乙個漢字佔3位元組左右，有50k*2*3=300k。不到1M，完全可以塞進cpu的cache，可行。如果敏感詞更多的話，另當別論。
其次，再hash表前，建立敏感詞的bloom filter，減少比較次數。猜測敏感詞不會太長，如果最長的詞有4個字(更長的敏感詞也不影響時間複雜度)，則遍歷4遍，分別查詢1、2、3、4個字的詞，就能找出所有『』疑似敏感詞『』。疑似敏感詞通過敏感詞組成的hash表或是字典樹，就可以搞定了。
關於bloom filter錯誤率的選擇：
可以選擇11個hash函式，此時空消耗16*50k/8bit=100kByte，錯誤率e=0.5^11=0.05%。
時間消耗：1G*4+(1G*0.05%誤認敏感詞+x真實敏感詞)*1(50k敏感詞，hash表)，大概4G+500k+x。
只在hash表中存在比較運算，不必要的比較次數緊為1G*0.05%，是直接用hash表的0.05%，而多消耗空間僅僅10%多一點，理論上速度會更快。
5樓：AWP996
敏感詞建樹是什麼鬼？要不題主是記錯了，要不面試官是個半瓶子水。@Barty 自動機是正解，自動機對付很多計算機問題真乃神器。
一道程式設計師面試題？
好奇的投資者 看不慣採用二分查詢的各位，怒答。我想對採用二分查詢的各位同學拋兩個問題。一 在二分資料的時候，如何確保 壞資料 在同乙個分塊呢，萬一你分的兩個分塊恰好都有部分錯誤資料呢？如下圖 二 在解決第乙個問題的前提下，如果採用二分查詢，會出現重複計算hash值的情況，此時複雜度肯定大於N。比如每...
一道面試題，這是什麼演算法啊？
朱涵俊 答案應該是2 1 0 0 0 1 0 0 0 6 首先0不可能出現0次。其次第二排加起來不可能超過10，因為總共就10個數字。還有第一排數字跟第二排數字相乘之和不超過10，比如2出現4次，那麼第二排有4個2，根據上面一條，第二排數字相加不大於10。假設0出現x次，x在1至9之間，x出現y次，...
虛構一道面試題 有1 10億數字的亂序陣列，其中少了若干個數（不超過100個），怎麼找到這些少的數呢？
可以對原來的數進行快排或者堆排，從大到小排一遍然後從大到小依次減過來，如果有相減結果不是1的就是說明這裡丟了乙個數字 這裡可以多執行緒計算 不過乙個10億個元素的陣列，佔記憶體也不小呢 柳翔天 先實現高精度計算。將每個數相加，與1 10億的總和相減，得到缺失數之和將每個數的平方相加，與1 10億的平...