Re: [北美] 徵求software engineer內推

[yzugsr (miaout17)]

: 推 jennya: 1.陣列建二元樹：(X) 不必使用BFS，使用for迴圈將陣列跑一  04/07 01:55
: → jennya: 遍就可以做到，省下bfs queue的空間                       04/07 01:55
: 推 Ninja5566: 樓上第一題怎麼用for 建complete b-tree?我還真想不到   04/07 02:04
: → Ninja5566: 而且還是在不用額外記憶體的情況下                     04/07 02:04
: 推 Ninja5566: 利用pre or inorder traversal建還是需要暫存parent     04/07 02:07
: → Ninja5566: 不然要怎麼返回parent node?                           04/07 02:07
: 推 jennya: @Ninja5566 你說的對。我原本的想法像是這樣：             04/07 02:44
: → jennya: https://www.paste.org/97946                             04/07 02:44
: → jennya: 但是仔細一想這的確和BFS差不多。這部分我的確是嗆原PO嗆   04/07 02:44
: → jennya: 錯了。謝謝~~                                            04/07 02:44

忍不住認真一下…
其實這是可行的，所以jennya大並沒有嗆錯（疑？）

這就這很像幫array-based tree寫一個iterator
順手寫了一下code，沒有仔細改，可能不是很concise
https://pastebin.com/AidafGZP

這其實是在工作中可能會出現，很實際的需求：
你在開發一個micro-controller程式，這個環境沒有heap，只有超小的stack
memory中已存在一個以array表示的binary search tree
請寫一個function在O(N)時間及O(1)空間做完in-order traversal
(N=number of elements)

Notes:
* O(1)空間表示嚴格來說不能用recursion，否則是O(log(N))
* 我的算法走訪每個edge兩次，所以是時間O(N)
* 以array表示binary tree是很實繼的做法，尤其當資料是immutable時
  比為了每個node分別在heap配置空間節省很多

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 24.5.73.164
※ 文章網址: https://www.ptt.cc/bbs/Oversea_Job/M.1554705256.A.296.html
※ 編輯: yzugsr (24.5.73.164), 04/08/2019 14:35:01
→ donkilu: 討論下去就要去softjob板啦XD
抱歉佔用版面QQ 如不符版規請告知
推 TAMSHUI: 討論串還不錯欸，學到很多XD
推 Ninja5566: 他是說建樹 不是 traverse
推 sdriver: 你講的是另一題，traverse tree’s inorder with iterati
→ sdriver: on
推 icecastleo: 稍微改一下樹不就建起來了嗎
推 Ninja5566: 建樹是另外一回事, 除非你另外存在struct不然node不
→ Ninja5566: 知道自己的parent還有自己是左子還右子
推 icecastleo: ...我們討論的是complete binary tree
我的確看錯了原本推文的意思，但這仍是可行的

首先，Tree Node可以包含parent, left, right三個指標
這裡有些trade-off，例如：
* 不放parent省空間，但中序走訪會如果要O(1) space就要O(N*log(N)) time
* 放了parent比較佔空間，但中序走訪會是O(N) time, O(1) space
此外許多tree mutating (e.g. rotate) 沒有parent pointer很難做

大多數實作(E.g. SGI STL)包含了parent
這是我們每天日常使用iterator over a tree的背後實作

剩下就是把tree traversal改成同時走訪array-based tree
一樣，順手寫了一下（帶簡單測試），code talks
https://pastebin.com/Jfwq6TL8
O(N) time. 不算新建的樹的話O(1) space.

→ jatj: 建樹還是要o(log(N))吧
建樹至少要O(N)，因為要寫N個elements
→ jatj: 我是指暫存
推 Ninja5566: 他說省下queue的空間, 你其實也是做一樣的事情, 只是
→ Ninja5566: 把空間移到struct而已
→ Ninja5566: 換句話講人家用BFS用queue,而 你用不同方式紀錄ptr而已
※ 編輯: yzugsr (24.5.73.164), 04/09/2019 09:42:58
→ jatj: 建樹當然至少要O(N)
→ shaform: 如果是指暫存,不計樹本身,那jennya的for loop 應該較好?