一亩三分地

 找回密码 注册账号

扫描二维码登录本站

微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
查看: 1937|回复: 10
收起左侧

巨婴西雅图 Onsite

[复制链接] |只看干货 |面试经验, 码农类general, 美国面经, microsoft
我的人缘0

升级   33.14%


分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (94)
 
 
2% (2)    👎

2019(7-9月) 码农类General 硕士 全职@Microsoft - 内推 - Onsite  | Pass/Offer | 在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
本来内推的湾区opening,内推以后被hr捞到西雅图的Hiring Event去了据HR说 Hiring Event的录取率比1对1的面试高多了
总体面试感觉非常好 跟普通onsite没啥区别 还可以和其他candidate聊聊天 感觉蛮轻松的
就是lunch box有点难吃 还是冷的 还好我吃了brunch去的

OTS完直接给onsite
OTS面经 :  https://www.1point3acres.com/bbs/thread-546454-1-1.html

游客,本帖隐藏的内容需要积分高于 180 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.


觉得有帮助给个大米呀~~


补充内容 (2019-9-2 10:47):
第一题忘了说了 一开始给的input都是leaf node 来点大米呀!~~

评分

参与人数 4大米 +34 收起 理由
whyisyoung + 1 赞一个
清道神君 + 30
dundun1990 + 1 很有用的信息!
BubbIeTea + 2 给你点个赞!

查看全部评分


上一篇:Twitter OA
下一篇:Palantir 2020 new grad OA
我的人缘0

升级   7.86%

JKBro 2019-9-2 08:29:46 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
我刷的题不够多,没看出来第一轮是LC哪个题,不知道楼主是怎么解的,
说说我的思路,基本就是树的BFS。 首先建一个hashtable<TreeNode, int>, 初始值就是所有list里的TreeNode和它的value, 代表以自己为根的子树的和。然后再建一个入度map,也就是list里面每个node有几个children,用BFS的方式,从children为0也就是叶子节点开始把自己为根的子树的和加给自己的parent。BFS结束以后再遍历最开始那个hashtable,找出和target最接近的。时间复杂度O(n),空间复杂度是不是O(3n).
不知道对不对,有没有更好的解法。
回复

使用道具 举报

我的人缘0

升级   46.71%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
JKBro 发表于 2019/09/02 08:29:46
我刷的题不够多,没看出来第一轮是LC哪个题,不知道楼主是怎么解的,
说说我的思路,基本就是树的BFS。 首先建一个hashtable<TreeNode, int>, 初始值就是所有list里的Tre...

有一个不知道是不是问题的问题 如果用bfs的话 叶子结点的高度不一样怎么办? 一个节点要往自己parent加的话 得确保它所有的儿子节点已经加到它上面去了
回复

使用道具 举报

我的人缘0

升级   7.86%

JKBro 2019-9-2 10:00:37 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
kkchenk 发表于 2019-9-2 09:19
有一个不知道是不是问题的问题 如果用bfs的话 叶子结点的高度不一样怎么办? 一个节点要往自己parent加的 ...

没关系吧,每个节点可能有多个kid,他们的高度也可能都不相同,只有它的子节点累计的数字才能往他头上加,而且顺序无所谓,反正是累加,比如root自己的value是1,它有两个个子节点node1, node2,. node1没有子节点,node2下面还有node3. 第一轮入度为0的就是node1和node3. node1加到root,node3的value3加到node2. 这个时候node2的入度变成0,所以第二轮处理node2,把node2的value加到root,这个时候node2的value其实是最初时node2以及他下面所有子节点的value的累加,在这个例子里是value2 + value3. 这轮结束后root的值就是所有节点的value的和了,跟子树高度没有什么关系。

还有在把他所有子节点处理完之前不会轮到处理它,因为它的入度还没有减到0,BFS那个Queue里面只放入度为0的Nodes. 不知道说明白没有。
回复

使用道具 举报

我的人缘0

升级   7.86%

JKBro 2019-9-2 11:58:54 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
刚楼主说输入都是leaf nodes,那么一上来还是要遍历所有的leaf nodes,把tree里的所有点以及他们的indgree找出来,才能继续BFS。

我又想了想,根本不需要建立hashtable,那个想法也是错的因为hashtable不能以node当作key。直接就在tree node里面update,BFS的时候不断update最优,就行了。

不知道楼主当时是怎么处理的呢?谢谢
回复

使用道具 举报

我的人缘0

升级   33.14%

 楼主| 吃不饱小姐 2019-9-3 05:15:54 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (94)
 
 
2% (2)    👎
JKBro 发表于 2019-9-2 11:58
刚楼主说输入都是leaf nodes,那么一上来还是要遍历所有的leaf nodes,把tree里的所有点以及他们的indgree ...

游客,本帖隐藏的内容需要积分高于 300 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
回复

使用道具 举报

我的人缘0

升级   7.86%

JKBro 2019-9-3 06:34:27 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
吃不饱小姐 发表于 2019-9-3 05:15
**** 本内容被作者隐藏 ****

我觉得你这个解法,跟我第一次说的很类似,我的concern是TreeNode是否可以当作map的key。我觉得没有implement CompareTo的class好像都不能当作key,因为没法查询。
回复

使用道具 举报

我的人缘0

升级   33.14%

 楼主| 吃不饱小姐 2019-9-3 06:46:15 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (94)
 
 
2% (2)    👎
JKBro 发表于 2019-9-3 06:34
我觉得你这个解法,跟我第一次说的很类似,我的concern是TreeNode是否可以当作map的key。我觉得没有imple ...

游客,本帖隐藏的内容需要积分高于 300 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
回复

使用道具 举报

我的人缘0

升级   7.86%

JKBro 2019-9-3 09:49:41 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
吃不饱小姐 发表于 2019-9-3 06:46
**** 本内容被作者隐藏 ****

我看了你的回复,知道你用的是pointer,但其他语言怎么办,有通用办法吗?谢谢
回复

使用道具 举报

我的人缘0

升级   46.71%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
JKBro 发表于 2019/09/02 10:00:37


没关系吧,每个节点可能有多个kid,他们的高度也可能都不相同,只有它的子节点累计的数字才能往他头上加,而且顺序无所谓,反正是累加,比如root自己的value是1,它有两个个子节点node1, n...

嗯 按照入度bfs就没有问题了 之前没想到
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

快速回复 返回顶部 返回列表