作者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/cn.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