憋死了 - 未名空间MITBBS历史存档

d*k2016-03-31 07:03

1 楼

刚挂完电话，新鲜出炉
问了Array, ArrayList, LinkedList, HashMap都有什么properties,读写的时间复杂度
是多少，由于前两天刚考过，答出来了。
但是又说了，hashtable有可以有conflict,这些读写就不是常数了，问我有没有什么办
法解决，我没答上来。
问了问inheritance 和 composition的概念，这个容易。
最后编成题，给定一个tree,一个node可以有多个children,要求实现一个iterator
class。具体要求是可以pass tree head到constructor,然后有一个getNext的function
来return next node.返回顺序不做要求，全部遍历完以后，就返回null.
我用BFS作的，中间还出了一个bug。（太丢人了，居然查了几遍都没有查出来，还是他
提醒的）
然后说children很多的时候会占用很多空间，我说可以改进成为DFS.
说了一下思路，没有要我实现。

d*g2016-03-31 07:03

2 楼

有些人的性格就是憋不住。好比我。有话不说憋死了。一讲起来，口若悬河，啰里啰嗦
。庞证博引，各种引申。一个问题能讲２０分钟。
我要是当老师，肯定老拖堂，还完不成进度。碰上个跟不上我思路的娃，更是两两抓狂
，互相折磨，歇斯底里，鸡飞狗跳。
痛定思痛，正在练习憋功。怎么练呢？好比从微信时代退回到电子邮件时代，或者再退
回到物理邮件时代。一句话，要憋三天。
所以三天前我儿子说1/5+1/5=2/10=1/5。三天已过，今天晚上我终于可以
对娃敞开心扉了。吓吓。。
当然娃没大错，他是说我的五分之一和你的五分之一加起来是我们的五分之一。没系
统的教过娃概念，娃自己感觉，结果朴素的表达出来，雷倒一片。
所以等了三天不白等。等三天憋出来的话，希望能恰当些，精准些，能把不直奔主题的
话过滤一些。
可就是磨炼我这脾气。在北美，出于无奈而自己推娃，不容易啊。。

d*k2016-03-31 07:03

3 楼

另外面试官很nice
很和蔼可亲的样子

function

【在 d**k 的大作中提到】

: 刚挂完电话，新鲜出炉
: 问了Array, ArrayList, LinkedList, HashMap都有什么properties,读写的时间复杂度
: 是多少，由于前两天刚考过，答出来了。
: 但是又说了，hashtable有可以有conflict,这些读写就不是常数了，问我有没有什么办
: 法解决，我没答上来。
: 问了问inheritance 和 composition的概念，这个容易。
: 最后编成题，给定一个tree,一个node可以有多个children,要求实现一个iterator
: class。具体要求是可以pass tree head到constructor,然后有一个getNext的function
: 来return next node.返回顺序不做要求，全部遍历完以后，就返回null.
: 我用BFS作的，中间还出了一个bug。（太丢人了，居然查了几遍都没有查出来，还是他

M*s2016-03-31 07:03

4 楼

我跟你一个毛病，容易被別人看不顺眼放黑枪中弹受伤，可就是这个毛病啊！呜呜呜。
。。现在我学精了，有的话可以吞回去，因为不是一路人我急什么？至于自家娃，那是
一定要说的，像你这样等一等，没了火药味儿再和颜悦色的谆谆教导，推，温柔的推

【在 d****g 的大作中提到】

: 有些人的性格就是憋不住。好比我。有话不说憋死了。一讲起来，口若悬河，啰里啰嗦
: 。庞证博引，各种引申。一个问题能讲２０分钟。
: 我要是当老师，肯定老拖堂，还完不成进度。碰上个跟不上我思路的娃，更是两两抓狂
: ，互相折磨，歇斯底里，鸡飞狗跳。
: 痛定思痛，正在练习憋功。怎么练呢？好比从微信时代退回到电子邮件时代，或者再退
: 回到物理邮件时代。一句话，要憋三天。
: 所以三天前我儿子说1/5+1/5=2/10=1/5。三天已过，今天晚上我终于可以
: 对娃敞开心扉了。吓吓。。
: 当然娃没大错，他是说我的五分之一和你的五分之一加起来是我们的五分之一。没系
: 统的教过娃概念，娃自己感觉，结果朴素的表达出来，雷倒一片。

h*t2016-03-31 07:03

5 楼

hash table有conflict，用open hash或closed hash解决？
想请教下，电面考编程，是怎么个操作法呢？
是用skype或类似的工具，共享屏幕吗？

i*e2016-03-31 07:03

6 楼

u will get used to it
gradually, u will be great at it :)

d*k2016-03-31 07:03

7 楼

google 告诉我
seperate chaining
or
open addressing
不懂，坐等高人解答

【在 h**t 的大作中提到】

: hash table有conflict，用open hash或closed hash解决？
: 想请教下，电面考编程，是怎么个操作法呢？
: 是用skype或类似的工具，共享屏幕吗？

n*f2016-03-31 07:03

8 楼

还是心态问题。
我如果问个算个问题，我儿子答不上来，我就认为他没有ready, 不会再提起。

【在 d****g 的大作中提到】

: 有些人的性格就是憋不住。好比我。有话不说憋死了。一讲起来，口若悬河，啰里啰嗦
: 。庞证博引，各种引申。一个问题能讲２０分钟。
: 我要是当老师，肯定老拖堂，还完不成进度。碰上个跟不上我思路的娃，更是两两抓狂
: ，互相折磨，歇斯底里，鸡飞狗跳。
: 痛定思痛，正在练习憋功。怎么练呢？好比从微信时代退回到电子邮件时代，或者再退
: 回到物理邮件时代。一句话，要憋三天。
: 所以三天前我儿子说1/5+1/5=2/10=1/5。三天已过，今天晚上我终于可以
: 对娃敞开心扉了。吓吓。。
: 当然娃没大错，他是说我的五分之一和你的五分之一加起来是我们的五分之一。没系
: 统的教过娃概念，娃自己感觉，结果朴素的表达出来，雷倒一片。

d*k2016-03-31 07:03

9 楼

共享browser window
比如说这个
https://coderpad.io/

【在 h**t 的大作中提到】

: hash table有conflict，用open hash或closed hash解决？
: 想请教下，电面考编程，是怎么个操作法呢？
: 是用skype或类似的工具，共享屏幕吗？

s*g2016-03-31 07:03

10 楼

主页看到这个帖子。
“我的五分之一和你的五分之一加起来是我们的五分之一”这话其实太对了，比如说一
班1/5是亚裔小孩，二班也是1/5的亚裔小孩，两个班在一起不还是1/5的亚裔小孩？一
点问题没有。

g*72016-03-31 07:03

11 楼

Iterate 整个tree， DFS 和 BFS 的 space complexity 是一样的阿，楼主能说说 DFS
如果节省空间的吗？

function

【在 d**k 的大作中提到】

: 刚挂完电话，新鲜出炉
: 问了Array, ArrayList, LinkedList, HashMap都有什么properties,读写的时间复杂度
: 是多少，由于前两天刚考过，答出来了。
: 但是又说了，hashtable有可以有conflict,这些读写就不是常数了，问我有没有什么办
: 法解决，我没答上来。
: 问了问inheritance 和 composition的概念，这个容易。
: 最后编成题，给定一个tree,一个node可以有多个children,要求实现一个iterator
: class。具体要求是可以pass tree head到constructor,然后有一个getNext的function
: 来return next node.返回顺序不做要求，全部遍历完以后，就返回null.
: 我用BFS作的，中间还出了一个bug。（太丢人了，居然查了几遍都没有查出来，还是他

t*l2016-03-31 07:03

12 楼

我觉得心态的作用不是无限的，根本问题上还是得物质决定意识，关键还是避免萌哥玛
丽的 a bridge too far 的情况。
当然，另一方面，成败常常也在于细节。老牌英帝对信息通讯新生事物还是不够重视。
如果不搞出所有通讯器材伞降完毕就统统报废这种历史玩笑的话，那么桥头堡英军伞兵
能得到空中补给，能转移阵地藏猫猫后还能继续得到补给，能呼叫皇家空军和美帝空军
让 Panzer 在路上先脱三层皮，那这 bridge 也不一定 too far。萌哥玛丽同学说不定
也能笑到最后。

：还是心态问题。
：

j*32016-03-31 07:03

13 楼

你最近面很多啊

c*x2016-03-31 07:03

14 楼

这么有热情，不做老师可惜了。

【在 d****g 的大作中提到】

: 有些人的性格就是憋不住。好比我。有话不说憋死了。一讲起来，口若悬河，啰里啰嗦
: 。庞证博引，各种引申。一个问题能讲２０分钟。
: 我要是当老师，肯定老拖堂，还完不成进度。碰上个跟不上我思路的娃，更是两两抓狂
: ，互相折磨，歇斯底里，鸡飞狗跳。
: 痛定思痛，正在练习憋功。怎么练呢？好比从微信时代退回到电子邮件时代，或者再退
: 回到物理邮件时代。一句话，要憋三天。
: 所以三天前我儿子说1/5+1/5=2/10=1/5。三天已过，今天晚上我终于可以
: 对娃敞开心扉了。吓吓。。
: 当然娃没大错，他是说我的五分之一和你的五分之一加起来是我们的五分之一。没系
: 统的教过娃概念，娃自己感觉，结果朴素的表达出来，雷倒一片。

d*k2016-03-31 07:03

15 楼

他不需要遍历整个
只要记住当前的遍历到的位置就可以

DFS

【在 g*******7 的大作中提到】

: Iterate 整个tree， DFS 和 BFS 的 space complexity 是一样的阿，楼主能说说 DFS
: 如果节省空间的吗？
:
: function

c*x2016-03-31 07:03

16 楼

确实不是无限的，研究表明好像是90%。有没有听说过一个“费斯汀格”法则？
美國社會心理學傢費斯汀格（Festinger），他創立瞭一個著名的法則，被人們稱為“
費斯汀格法則”：生活中的10％是由發生在你身上的事情組成，而另外的90％則是由你
對所發生的事情如何反應所決定。換言之，生活中有10%的事情是我們無法掌控的，而
另外的90%卻是我們能掌控的。

【在 t******l 的大作中提到】

: 我觉得心态的作用不是无限的，根本问题上还是得物质决定意识，关键还是避免萌哥玛
: 丽的 a bridge too far 的情况。
: 当然，另一方面，成败常常也在于细节。老牌英帝对信息通讯新生事物还是不够重视。
: 如果不搞出所有通讯器材伞降完毕就统统报废这种历史玩笑的话，那么桥头堡英军伞兵
: 能得到空中补给，能转移阵地藏猫猫后还能继续得到补给，能呼叫皇家空军和美帝空军
: 让 Panzer 在路上先脱三层皮，那这 bridge 也不一定 too far。萌哥玛丽同学说不定
: 也能笑到最后。
:
: ：还是心态问题。
: ：

d*k2016-03-31 07:03

17 楼

哈哈
屡战屡败屡败屡战

【在 j**********3 的大作中提到】

: 你最近面很多啊

t*l2016-03-31 07:03

18 楼

属实。就好比天才是 99% 的汗水加 1% 的灵感。
但另一方面，很多炮灰就眼睁睁地倒在 1% 上了。

：
：【在 timefall (时光崩塌) 的大作中提到: 】

z*e2016-03-31 07:03

19 楼

第一个
最简单的就是调整prime大小
把prime调大，这样碰撞就少了
tradeoff是key占用的空间可能会增加

t*l2016-03-31 07:03

20 楼

玩笑归玩笑，但实在的说，这个就是 quantity vs quality 的争论。
举一个极端的例子，阿发狗经常让人感觉就差那么一步就能赢狗了。。。但问题在于如
果总是就差那么一步。。。

：属实。就好比天才是 99% 的汗水加 1% 的灵感。
：

z*e2016-03-31 07:03

21 楼

比如n层
dfs每一层就保留一个在linkedlist里面，最大是n
bfs第一层1个，第二层2个，第三层4个，第四层8个，第五层16个……是2^(n-1)

DFS

【在 g*******7 的大作中提到】

: Iterate 整个tree， DFS 和 BFS 的 space complexity 是一样的阿，楼主能说说 DFS
: 如果节省空间的吗？
:
: function

M*s2016-03-31 07:03

22 楼

你这么肉，你孩子可以永远不ready，反正吃你靠你嘛

【在 n****f 的大作中提到】

: 还是心态问题。
: 我如果问个算个问题，我儿子答不上来，我就认为他没有ready, 不会再提起。

r*s2016-03-31 07:03

23 楼

这个不就是让你用stack来iterate tree吗？

DFS

【在 g*******7 的大作中提到】

: Iterate 整个tree， DFS 和 BFS 的 space complexity 是一样的阿，楼主能说说 DFS
: 如果节省空间的吗？
:
: function

y*z2016-03-31 07:03

24 楼

不知道1／5+1／5有那么重要吗？
放宽心～～

s*q2016-03-31 07:03

25 楼

LZ面的SDE吗，不是说NEW GRAD的SDE招满了吗？可否SHARE一下如何拿到这个面试的。
另外编程题里不可以implement iterator interface是吧？

function

【在 d**k 的大作中提到】

: 哈哈
: 屡战屡败屡败屡战

d*g2016-03-31 07:03

26 楼

主要是对老美数学教育不放心。。。我们还不舍得花钱出去上班儿。。。所以才盯的这
么仔细。。
至于1／5+1／5!=2/10。。。这个挺重要的，是个数学语言的使用问题。。恰
恰是老美忽视的地方。
昨天讲了，应该是（1/5+1/5）／(1+1)=１／５。
另:为啥等三天？因为我现在是一二三娃每天５道题，我不许插嘴，有话只能周四周五
说。哈哈。。

【在 y***z 的大作中提到】

: 不知道1／5+1／5有那么重要吗？
: 放宽心～～

d*k2016-03-31 07:03

27 楼

俺不是new grad阿！！！！

【在 s********q 的大作中提到】

: LZ面的SDE吗，不是说NEW GRAD的SDE招满了吗？可否SHARE一下如何拿到这个面试的。
: 另外编程题里不可以implement iterator interface是吧？
:
: function

B*e2016-03-31 07:03

28 楼

20分钟你还口若悬河萝莉啰嗦旁征博引。。。
这是吹牛失败的例子

【在 d****g 的大作中提到】

: 有些人的性格就是憋不住。好比我。有话不说憋死了。一讲起来，口若悬河，啰里啰嗦
: 。庞证博引，各种引申。一个问题能讲２０分钟。
: 我要是当老师，肯定老拖堂，还完不成进度。碰上个跟不上我思路的娃，更是两两抓狂
: ，互相折磨，歇斯底里，鸡飞狗跳。
: 痛定思痛，正在练习憋功。怎么练呢？好比从微信时代退回到电子邮件时代，或者再退
: 回到物理邮件时代。一句话，要憋三天。
: 所以三天前我儿子说1/5+1/5=2/10=1/5。三天已过，今天晚上我终于可以
: 对娃敞开心扉了。吓吓。。
: 当然娃没大错，他是说我的五分之一和你的五分之一加起来是我们的五分之一。没系
: 统的教过娃概念，娃自己感觉，结果朴素的表达出来，雷倒一片。

s*k2016-03-31 07:03

29 楼

弱问一下， Array, ArrayList, LinkedList, HashMap的properties 是指的啥?

function

【在 d**k 的大作中提到】

: 俺不是new grad阿！！！！

d*g2016-03-31 07:03

30 楼

哈哈。

【在 B********e 的大作中提到】

: 20分钟你还口若悬河萝莉啰嗦旁征博引。。。
: 这是吹牛失败的例子

s*k2016-03-31 07:03

31 楼

这个编程题能给一个答案吗，多谢了。。。

function

【在 d**k 的大作中提到】

: 俺不是new grad阿！！！！

M*a2016-03-31 07:03

32 楼

最后的编程题愣是没看懂。

s*k2016-03-31 07:03

33 楼

那个高手给个答案

i*e2016-03-31 07:03

34 楼

hash colliction 解决方法：
http://mindlee.net/2011/08/06/solve-hash-conflict-links-method-
其实对于具体问题还有一些解决方法，比如无冲突的hash alg