作者yzugsr (miaout17)
看板Oversea_Job
標題Re: [北美] 徵求software engineer內推
時間Mon Apr 8 14:34:11 2019
: 推 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://webptt.com/m.aspx?n=bbs/Oversea_Job/M.1554705256.A.296.html
※ 編輯: yzugsr (24.5.73.164), 04/08/2019 14:35:01
1F：→ donkilu: 討論下去就要去softjob板啦XD 04/08 14:43
抱歉佔用版面QQ 如不符版規請告知
2F：推 TAMSHUI: 討論串還不錯欸，學到很多XD 04/08 19:38
3F：推 Ninja5566: 他是說建樹 不是 traverse 04/08 19:55
4F：推 sdriver: 你講的是另一題，traverse tree’s inorder with iterati 04/08 21:13
5F：→ sdriver: on 04/08 21:13
6F：推 icecastleo: 稍微改一下樹不就建起來了嗎 04/09 00:13
7F：推 Ninja5566: 建樹是另外一回事, 除非你另外存在struct不然node不 04/09 00:44
8F：→ Ninja5566: 知道自己的parent還有自己是左子還右子 04/09 00:44
9F：推 icecastleo: ...我們討論的是complete binary tree 04/09 02:18
我的確看錯了原本推文的意思，但這仍是可行的
首先，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.
10F：→ jatj: 建樹還是要o(log(N))吧 04/09 02:37
建樹至少要O(N)，因為要寫N個elements
11F：→ jatj: 我是指暫存 04/09 05:41
12F：推 Ninja5566: 他說省下queue的空間, 你其實也是做一樣的事情, 只是 04/09 06:43
13F：→ Ninja5566: 把空間移到struct而已 04/09 06:43
14F：→ Ninja5566: 換句話講人家用BFS用queue,而 你用不同方式紀錄ptr而已 04/09 06:45
※ 編輯: yzugsr (24.5.73.164), 04/09/2019 09:42:58
15F：→ jatj: 建樹當然至少要O(N) 04/09 10:07
16F：→ shaform: 如果是指暫存,不計樹本身,那jennya的for loop 應該較好? 04/09 23:43