勃失敗2016-11-14 21:57:20

幾乎所有程式設計師演算法水平的最高點就是在他們準面電話面試的時候。

知乎使用者2016-11-14 22:56:42

學校裡，計算機系老師一開始就會說 程式 = 資料結構 + 演算法。

但是畢業工作後，對大部分程式設計師來說，程式 = 資料結構 + 邏輯。

資料結構的合理選擇和使用是開發人員的基本要求。因為錯誤的選擇資料結構，很容易影響程式效率以及空間複雜度，還容易給團隊其他成員造成一些不必要的麻煩。

而邏輯通常指軟體開發中系統功能邏輯，說白了就是開發人員要清晰理解業務需求並做出完善的功能邏輯設計，儘量避免異常和bug。

至於演算法，除了專門的演算法工程師以及很多遊戲開發者，大部分開發人員並不是天天會碰見的。即便碰見一些基本的演算法使用，通常語言類庫本身也已經有很好的實現了。

再說一點，確實有這麼一個事實，就是廣大程式設計師的演算法知識最熟練的時候就是他們上學考試的時候以及每次面試前半年的時候（一般是準備大公司面試時）。

張克炎2016-11-16 07:57:22

謝邀。很多 candidate 不喜歡演算法與資料結構相關的面試，覺得演算法面試中的內容是與日常工作無關的刁鑽考察；與其相反，我認為 （良好設計的） 演算法面試是對日常 engineering 工作的一層抽象 （abstraction）。如果你在工作中不需要解決類似演算法面試中的難題，也許是因為你的工作不夠有趣？：D

舉個例子。你要在網頁上放一張北京市的地圖，然後把每個知乎使用者所在的位置都用小紅點標示出來。如果這個地圖不支援任何互動的操作也不會隨時間變化，那麼你可以簡單的用一個數組 （array） 來儲存每個使用者的位置以及個人資訊；渲染時遍歷這個陣列，把每一個小紅點新增到地圖上。這個操作的時間複雜度是 O（n），聽起來還不錯。

但如果我們要支援用滑鼠框選的操作，並顯示選中範圍內的使用者資訊呢？我們可以拿到滑鼠位置變化的數值，但我們的資料結構並不瞭解使用者間的相對位置資訊。因此，每一次的選區變化都迫使我們重新遍歷這個陣列，檢查每個使用者是否在選區內。這明顯不是個高效的操作——想像一下有幾千名使用者出現在地圖中時，這個操作的效能會怎樣。

什麼是更好的解決方案？我們可以換用一個四叉樹 （Quadtree - Wikipedia） 來儲存每個使用者的位置資訊。簡單來說，這個四叉樹把地圖分成四個象限；每一個象限可以再被分解為四個子象限 （以此類推），然後每個點根據 （x， y） 的位置被放進相應的子象限中。這樣，我們儲存下了使用者間的相對位置關係；當滑鼠選區變化時，我們更可以只在 Quadtree 中搜索新舊選區間所增減的部分。

上面所描述的就是北美某司的一道面試題。給定需要實現的需求 （在地圖上渲染資料點並支援框選），設計並在白板上寫出所需要的資料結構。

小測驗：這個操作的時間複雜度是多少？

知乎使用者2016-11-26 09:16:41

其實還是看專案 像最近BuckleScript編譯器的專案 幾乎所有常用的圖演算法都自己寫了一遍

原因是兩個 其一通用的庫效率太低了 沒有自己定製的高校

其二 別人的庫一堆dependencies 還有license的問題 所以不如自己寫得快

編譯器做累了寫寫經典演算法 就當是种放松吧……

程式設計師吳師兄2019-01-15 09:59:39

寫一個跟前端有關的例子吧。

從一個需求談起

在我之前的專案中，曾經遇到過這樣一個需求，編寫一個級聯選擇器，大概是這樣：

圖中的示例使用的是Ant-Design的Cascader元件。

要實現這一功能，我需要類似這樣的資料結構：

var data = ［{

“value”： “浙江”，

“children”： ［{

“value”： “杭州”，

“children”： ［{

“value”： “西湖”

}］

}］

}， {

“value”： “四川”，

“children”： ［{

“value”： “成都”，

“children”： ［{

“value”： “錦裡”

}， {

“value”： “方所”

}］

}， {

“value”： “阿壩”，

“children”： ［{

“value”： “九寨溝”

}］

}］

}］

一個具有層級結構的資料，實現這個功能非常容易，因為這個結構和元件的結構是一致的，遞迴遍歷就可以了。

但是，由於後端通常採用的是關係型資料庫，所以返回的資料通常會是這個樣子：

var data = ［{

“province”： “浙江”，

“city”： “杭州”，

“name”： “西湖”

}， {

“province”： “四川”，

“city”： “成都”，

“name”： “錦裡”

}， {

“province”： “四川”，

“city”： “成都”，

“name”： “方所”

}， {

“province”： “四川”，

“city”： “阿壩”，

“name”： “九寨溝”

}］

前端這邊想要將資料轉換一下其實也不難，因為要合併重複項，可以參考資料去重的方法來做，於是我寫了這樣一個版本。

‘use strict’

/**

* 將一個沒有層級的扁平物件，轉換為樹形結構（{value， children}）結構的物件

* @param {array} tableData - 一個由物件構成的陣列，裡面的物件都是扁平的

* @param {array} route - 一個由字串構成的陣列，字串為前一陣列中物件的key，最終

* 輸出的物件層級順序為keys中字串key的順序

* @return {array} 儲存具有樹形結構的物件

*/

var transObject = function（tableData， keys） {

let hashTable = {}， res = ［］

for（ let i = 0； i < tableData。length； i++ ） {

if（！hashTable［tableData［i］［keys［0］］］） {

let len = res。push（{

value： tableData［i］［keys［0］］，

children： ［］

}）

// 在這裡要儲存key對應的陣列序號，不然還要涉及到查詢

hashTable［tableData［i］［keys［0］］］ = { $$pos： len - 1 }

}

if（！hashTable［tableData［i］［keys［0］］］［tableData［i］［keys［1］］］） {

let len = res［hashTable［tableData［i］［keys［0］］］。$$pos］。children。push（{

value： tableData［i］［keys［1］］，

children： ［］

}）

hashTable［tableData［i］［keys［0］］］［tableData［i］［keys［1］］］ = { $$pos： len - 1 }

}

res［hashTable［tableData［i］［keys［0］］］。$$pos］。children［hashTable［tableData［i］［keys［0］］］［tableData［i］［keys［1］］］。$$pos］。children。push（{

value： tableData［i］［keys［2］］

}）

}

return res

}

var data = ［{

“province”： “浙江”，

“city”： “杭州”，

“name”： “西湖”

}， {

“province”： “四川”，

“city”： “成都”，

“name”： “錦裡”

}， {

“province”： “四川”，

“city”： “成都”，

“name”： “方所”

}， {

“province”： “四川”，

“city”： “阿壩”，

“name”： “九寨溝”

}］

var keys = ［‘province’， ‘city’， ‘name’］

console。log（transObject（data， keys））

還好keys的長度只有3，這種東西長了根本沒辦法寫，很明顯可以看出來這裡面有重複的部分，可以透過迴圈搞定，但是想了很久都沒有思路，就擱置了。

後來，有一天晚飯後不是很忙，就跟旁邊做資料的同事聊了一下這個需求，請教一下該怎麼用迴圈來處理。他看了一下，就問我：“你知道trie樹嗎？”。我頭一次聽到這個概念，他簡單的給我講了一下，然後說感覺處理的問題有些類似，讓我可以研究一下trie樹的原理並試著最佳化一下。

講道理，trie樹這個資料結構網上確實有很多資料，但很少有使用JavaScript實現的，不過原理倒是不難。嘗試之後，我就將

transObject

的程式碼最佳化成了這樣。（關於trie樹，還請讀者自己閱讀相關材料）

var transObject = function（tableData， keys） {

let hashTable = {}， res = ［］

for （let i = 0； i < tableData。length； i++） {

let arr = res， cur = hashTable

for （let j = 0； j < keys。length； j++） {

let key = keys［j］， filed = tableData［i］［key］

if （！cur［filed］） {

let pusher = {

value： filed

}， tmp

if （j ！== （keys。length - 1）） {

tmp = ［］

pusher。children = tmp

}

cur［filed］ = { $$pos： arr。push（pusher） - 1 }

cur = cur［filed］

arr = tmp

} else {

cur = cur［filed］

arr = arr［cur。$$pos］。children

}

}

}

return res

}

這樣，解決方案就和keys的長短無關了。

這大概是我第一次，真正將資料結構的知識和前端專案需求結合在一起。

如果你想了解Trie的知識點，可以看看我的這篇帖子

看動畫輕鬆理解「Trie樹」