PTT職涯區 / Oversea_Job (海外工作)

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

看板Oversea_Job (海外工作)作者 (miaout17)時間7年前 (2019/04/08 14:34), 7年前編輯推噓7(7推 0噓 9→)
留言16則, 7人參與, 7年前最新討論串4/4 (看更多)
: 推 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
→
04/08 14:43, 7年前 , 1F
討論下去就要去softjob板啦XD
04/08 14:43, 1F
抱歉佔用版面QQ 如不符版規請告知
推
04/08 19:38, 7年前 , 2F
討論串還不錯欸，學到很多XD
04/08 19:38, 2F
推
04/08 19:55, 7年前 , 3F
他是說建樹 不是 traverse
04/08 19:55, 3F
推
04/08 21:13, 7年前 , 4F
你講的是另一題，traverse tree’s inorder with iterati
04/08 21:13, 4F
→
04/08 21:13, 7年前 , 5F
on
04/08 21:13, 5F
推
04/09 00:13, 7年前 , 6F
稍微改一下樹不就建起來了嗎
04/09 00:13, 6F
推
04/09 00:44, 7年前 , 7F
建樹是另外一回事, 除非你另外存在struct不然node不
04/09 00:44, 7F
→
04/09 00:44, 7年前 , 8F
知道自己的parent還有自己是左子還右子
04/09 00:44, 8F
推
04/09 02:18, 7年前 , 9F
...我們討論的是complete binary tree
04/09 02:18, 9F
我的確看錯了原本推文的意思，但這仍是可行的 首先，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.
→
04/09 02:37, 7年前 , 10F
建樹還是要o(log(N))吧
04/09 02:37, 10F
建樹至少要O(N)，因為要寫N個elements
→
04/09 05:41, 7年前 , 11F
我是指暫存
04/09 05:41, 11F
推
04/09 06:43, 7年前 , 12F
他說省下queue的空間, 你其實也是做一樣的事情, 只是
04/09 06:43, 12F
→
04/09 06:43, 7年前 , 13F
把空間移到struct而已
04/09 06:43, 13F
→
04/09 06:45, 7年前 , 14F
換句話講人家用BFS用queue,而 你用不同方式紀錄ptr而已
04/09 06:45, 14F
※ 編輯: yzugsr (24.5.73.164), 04/09/2019 09:42:58
→
04/09 10:07, 7年前 , 15F
建樹當然至少要O(N)
04/09 10:07, 15F
→
04/09 23:43, 7年前 , 16F
如果是指暫存,不計樹本身,那jennya的for loop 應該較好?
04/09 23:43, 16F
‣ 更多 yzugsr 的文章
文章代碼(AID): #1SgkjeAM (Oversea_Job)
Oversea_Job 近期熱門文章
更多 近期熱門文章 >>
PTT職涯區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 yzugsr 的文章
文章代碼(AID): #1SgkjeAM (Oversea_Job)