b***y
发帖数: 76 | 1 回报本版，没有包子，发个面筋。
1. 阿三，论文讨论
问的很细，各种刁难，感觉回答的不好
2. 国男
Wildcard match， 没有为难
3. 白男
给两个String array，返回所有只存在于其中一个array中的String
大数据的情况，分布式，如何处理
4. 白男老头
回到1980年代，一台计算机内存1KB, 主频 1MHz, 设计一个在这台机器上跑的时间最长
(但能确定会正常结束)的程序，证明为什么是最长，并计算时长。这题开始完全不知
道在问什么。
5. 无口音亚裔男
BT的BFS
引申题目：对非常大的二叉树做BFS，没见过，现想，规定时间勉强写完，最后没来得
及问面试官心中的最佳解法
面的感觉一般，求bless |
r*****e
发帖数: 792 | 2 bless. 有几题挺难的啊。
【在 b***y 的大作中提到】
: 回报本版，没有包子，发个面筋。
: 1. 阿三，论文讨论
: 问的很细，各种刁难，感觉回答的不好
: 2. 国男
: Wildcard match， 没有为难
: 3. 白男
: 给两个String array，返回所有只存在于其中一个array中的String
: 大数据的情况，分布式，如何处理
: 4. 白男老头
: 回到1980年代，一台计算机内存1KB, 主频 1MHz, 设计一个在这台机器上跑的时间最长
|
c****m
发帖数: 179 | 3 Bless
第四个人的题目是考什么啊？
是要从programming language的角度答还是图灵机的角度?
莫非是总是在01代码里加入一个随机pattern的判断是否终止？ |
b***y
发帖数: 76 | 4 要求是deterministic的，因为后面还要计算理论运行时间，随机pattern貌似不行。
【在 c****m 的大作中提到】
: Bless
: 第四个人的题目是考什么啊？
: 是要从programming language的角度答还是图灵机的角度?
: 莫非是总是在01代码里加入一个随机pattern的判断是否终止？
|
r**h
发帖数: 1288 | 5 感谢lz的面经，bless！
最后一题的思路是什么呢？先做一次preprocessing，用一个额外的指针把同一层叶节
点都串起来，并储存每一层链表的开头节点，然后再按层输出这样可以吗？
【在 b***y 的大作中提到】
: 回报本版，没有包子，发个面筋。
: 1. 阿三，论文讨论
: 问的很细，各种刁难，感觉回答的不好
: 2. 国男
: Wildcard match， 没有为难
: 3. 白男
: 给两个String array，返回所有只存在于其中一个array中的String
: 大数据的情况，分布式，如何处理
: 4. 白男老头
: 回到1980年代，一台计算机内存1KB, 主频 1MHz, 设计一个在这台机器上跑的时间最长
|
b***y
发帖数: 76 | 6 我当时也讨论了这个方法，面试官说不可以修改node class，只有左右child
【在 r**h 的大作中提到】
: 感谢lz的面经，bless！
: 最后一题的思路是什么呢？先做一次preprocessing，用一个额外的指针把同一层叶节
: 点都串起来，并储存每一层链表的开头节点，然后再按层输出这样可以吗？
|
z*********8
发帖数: 2070 | |
r**h
发帖数: 1288 | 8 那用dfs可以吗？大概是O(2n)时间复杂度O(h)空间复杂度
【在 b***y 的大作中提到】
: 我当时也讨论了这个方法，面试官说不可以修改node class，只有左右child
|
c******a
发帖数: 789 | 9 巨大BST是在内存里么？用一般方法BFS，一边把搞过的node删掉？当到了巨大的层的时
候，怎么也删够腾足够内存把这层存进内存了。
如果在disc，就更简单了。 |
r*******e
发帖数: 7583 | 10 非常大的二叉树BFS和一般大的二叉树BFS差别在哪儿
同一层的节点都放不进内存？
最长
【在 r**h 的大作中提到】
: 感谢lz的面经，bless！
: 最后一题的思路是什么呢？先做一次preprocessing，用一个额外的指针把同一层叶节
: 点都串起来，并储存每一层链表的开头节点，然后再按层输出这样可以吗？
|
|
|
r*******e
发帖数: 7583 | 11 给个大概的思路？
【在 b***y 的大作中提到】
: 要求是deterministic的，因为后面还要计算理论运行时间，随机pattern貌似不行。
|
x*********w
发帖数: 533 | |
b***y
发帖数: 76 | 13 这个方法我没讨论，个人认为这个思路没有踩到考点，面试官可能会说BST没有都存在
内存，或不能改变原树结构
【在 c******a 的大作中提到】
: 巨大BST是在内存里么？用一般方法BFS，一边把搞过的node删掉？当到了巨大的层的时
: 候，怎么也删够腾足够内存把这层存进内存了。
: 如果在disc，就更简单了。
|
r**h
发帖数: 1288 | 14 我觉得考点应该是这个？
【在 r*******e 的大作中提到】
: 非常大的二叉树BFS和一般大的二叉树BFS差别在哪儿
: 同一层的节点都放不进内存？
:
: 最长
|
b***y
发帖数: 76 | 15 是的，同一层的节点可能会放不下
【在 r*******e 的大作中提到】
: 非常大的二叉树BFS和一般大的二叉树BFS差别在哪儿
: 同一层的节点都放不进内存？
:
: 最长
|
b***y
发帖数: 76 | 16 牛，茅塞顿开，估计这个是面试官心目中的解法，我当时没想出来，最后写的是NlogN的
【在 r**h 的大作中提到】
: 那用dfs可以吗？大概是O(2n)时间复杂度O(h)空间复杂度
|
b***y
发帖数: 76 | 17 对，考点应该就是这个，同一层的节点存不下，但是树高复杂度的space可以，看来应
该的确是在问用 DFS 实现BFS
【在 r**h 的大作中提到】
: 我觉得考点应该是这个？
|
r*****e
发帖数: 792 | 18 是这个意思吗？
http://leetcode.com/2010/09/binary-tree-level-order-traversal-u
【在 b***y 的大作中提到】
: 对，考点应该就是这个，同一层的节点存不下，但是树高复杂度的space可以，看来应
: 该的确是在问用 DFS 实现BFS
|
b***y
发帖数: 76 | 19 是这个
还是准备的不到位
死在leetcode详细讨论的题目上
【在 r*****e 的大作中提到】
: 是这个意思吗？
: http://leetcode.com/2010/09/binary-tree-level-order-traversal-u
|
c******a
发帖数: 789 | 20 面试那么stressful的情景下要connect这种程度的dot，真的很难啊
【在 b***y 的大作中提到】
: 是这个
: 还是准备的不到位
: 死在leetcode详细讨论的题目上
|
|
|
N*m
发帖数: 128 | 21 肯定是图灵机角度吧，一个内存有限的机器能表达的状态是有限的，其中必须至少有一
个是终止状态（不然就无限循环了）。程序要做的就是保证遍历完所有状态，最后达到
终止状态。
【在 c****m 的大作中提到】
: Bless
: 第四个人的题目是考什么啊？
: 是要从programming language的角度答还是图灵机的角度?
: 莫非是总是在01代码里加入一个随机pattern的判断是否终止？
|
c******a
发帖数: 789 | 22 不能keep住一个内存能表达的最future的年代，sleep1年，醒来check一下，直到
future年代达到？跑个几万年？ |
g*****i
发帖数: 2162 | |
w***t
发帖数: 1474 | 24 狗家面试都是1人1题吗
【在 b***y 的大作中提到】
: 回报本版，没有包子，发个面筋。
: 1. 阿三，论文讨论
: 问的很细，各种刁难，感觉回答的不好
: 2. 国男
: Wildcard match， 没有为难
: 3. 白男
: 给两个String array，返回所有只存在于其中一个array中的String
: 大数据的情况，分布式，如何处理
: 4. 白男老头
: 回到1980年代，一台计算机内存1KB, 主频 1MHz, 设计一个在这台机器上跑的时间最长
|
H****r
发帖数: 2801 | 25 同层， 同高度 的space 难道不是差不多的么？
【在 b***y 的大作中提到】
: 对，考点应该就是这个，同一层的节点存不下，但是树高复杂度的space可以，看来应
: 该的确是在问用 DFS 实现BFS
|
S******n
发帖数: 132 | 26 是啊，worst case也是O(n) space啊，如果所有节点都只有一个child
【在 H****r 的大作中提到】
: 同层， 同高度 的space 难道不是差不多的么？
|
b***y
发帖数: 76 | 27 这个答案貌似踩中了老头的考点
【在 N*m 的大作中提到】
: 肯定是图灵机角度吧，一个内存有限的机器能表达的状态是有限的，其中必须至少有一
: 个是终止状态（不然就无限循环了）。程序要做的就是保证遍历完所有状态，最后达到
: 终止状态。
|
b***y
发帖数: 76 | 28 这个想法挺有意思，不过老头的考点貌似是图灵机
【在 c******a 的大作中提到】
: 不能keep住一个内存能表达的最future的年代，sleep1年，醒来check一下，直到
: future年代达到？跑个几万年？
|
b***y
发帖数: 76 | 29 我的都只问了一题，提前写完的题目顶多问一下复杂度和扩展到大数据的讨论，之后就
聊天了
【在 w***t 的大作中提到】
: 狗家面试都是1人1题吗
|
N*m
发帖数: 128 | 30 有外部时间的输入就有点算是作弊了，毕竟外部时间流逝不随主频变化
【在 b***y 的大作中提到】
: 这个想法挺有意思，不过老头的考点貌似是图灵机
|
|
|
b***y
发帖数: 76 | 31 Good point，我当时没考虑到这种情况，写code中需要求树高时问了面试官树高的空间
复杂度是否可以存的下，面试官说ok。不知道有没有更完美的O(1)space解，哪怕牺牲
写时间复杂度, 坐等高人。
【在 S******n 的大作中提到】
: 是啊，worst case也是O(n) space啊，如果所有节点都只有一个child
|
b***y
发帖数: 76 | 32 面到最后我基本理解老头的考点应该的确是图灵机状态转换，不过这个算法应该怎么写
呢?
【在 N*m 的大作中提到】
: 有外部时间的输入就有点算是作弊了，毕竟外部时间流逝不随主频变化
|
c****m
发帖数: 179 | 33 谢谢有道理，。因为随机跳转也得用有限的状态描述，而图灵机的状态跳转是有限且
deterministic的。
【在 N*m 的大作中提到】
: 肯定是图灵机角度吧，一个内存有限的机器能表达的状态是有限的，其中必须至少有一
: 个是终止状态（不然就无限循环了）。程序要做的就是保证遍历完所有状态，最后达到
: 终止状态。
|
N*m
发帖数: 128 | 34 如果不考虑指令占的内存的话，基本就是用数组表示二进制大整数，实现increase操作
就好了。
考虑指令占的内存的话......感觉就很tricky了......
【在 b***y 的大作中提到】
: 面到最后我基本理解老头的考点应该的确是图灵机状态转换，不过这个算法应该怎么写
: 呢?
|
