周末读物之聊聊三观

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 2209|回复: 23
收起左侧

脸家实习跪经

[复制链接] |试试Instant~
我的人缘0
Iverson333 发表于 2017-11-1 08:28:54 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩

2018(10-12月) 码农类General 博士 实习@Facebook - 内推 - HR筛选  | Fail | 其他

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

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
发一个不久前的脸家实习跪经吧:第一轮: LC 的 San零Yi 但是不是要求返回list。返回一个结果就可以了。这个题挂在用了两边Stringbuilder 所以复杂度是O(2n) , 面试官要求是O(n)。当时没想出来,所以答的不是很好。
第二轮: 1. 名人 那个题。2. 给一个树(不是二叉树),找最深叶节点的最近公共祖先。

希望大家以后刷题的时候,尽量解法最优。自己多想一些follow up question。多模拟。

评分

参与人数 1大米 +5 收起 理由
greenmania + 5 很有用的信息!

查看全部评分


上一篇:口袋宝石OA 4 面经
下一篇:有人做了autoX的OA了吗

本帖被以下淘专辑推荐:

我的人缘0
alex.chan 发表于 2017-11-1 09:21:24 | 显示全部楼层
本楼: 【顶】   50% (1)
 
 
50% (1)   【踩】
全局: 顶  95% (124)
 
 
4% (6)  踩
301 one  pass  的怎么做啊??谢谢
回复

使用道具 举报

我的人缘0
by_lilei 发表于 2017-11-1 10:04:32 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (30)
 
 
0% (0)  踩
Iverson333 发表于 2017-11-1 09:47
它要求的返回一个res就可以。不是one pass。时间是O(2n), 他让我空间只用O(n)。我卡在空间就是O(2n) 了 ...

是可以用两个stack来做吗?stack1用来存open parenthesis index ,stack2存close的index。如果来了一个是open,直接push 到stack1。 如果是close则pop stack1,如果stack1 是空的,则push 到stack2。最后两个stack上存的是不匹配的open close 的index,然后用一个StringBuilder remove相应不合法的parenthesis。最多有n个同时在两个stack 上,所以space complexity应该是O(n), time complexity 也是O(n).
回复

使用道具 举报

我的人缘0
mmymichael 发表于 2017-11-1 08:39:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  67% (304)
 
 
32% (146)  踩
请问楼主第二轮第二题是怎么写的?
回复

使用道具 举报

我的人缘0
 楼主| Iverson333 发表于 2017-11-1 09:43:12 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
mmymichael 发表于 2017-11-1 08:39
请问楼主第二轮第二题是怎么写的?

BFS找 deepest leaf node 的list。然后他们的lowest common ancestor 其实就是第一个leaf和最后一个leaf的lowest common ancestor 然后按类似LC236那么写就可以了。

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
 楼主| Iverson333 发表于 2017-11-1 09:47:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
haifengc 发表于 2017-11-1 09:21
301 one  pass  的怎么做啊??谢谢

它要求的返回一个res就可以。不是one pass。时间是O(2n), 他让我空间只用O(n)。我卡在空间就是O(2n) 了。
回复

使用道具 举报

我的人缘0
alex.chan 发表于 2017-11-1 09:57:58 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (124)
 
 
4% (6)  踩
Iverson333 发表于 2017-11-1 09:47
它要求的返回一个res就可以。不是one pass。时间是O(2n), 他让我空间只用O(n)。我卡在空间就是O(2n) 了 ...
-google 1point3acres
嗯,谢谢。
回复

使用道具 举报

我的人缘0
qq274880049 发表于 2017-11-1 10:00:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  68% (288)
 
 
31% (135)  踩
Iverson333 发表于 2017-11-1 09:47
它要求的返回一个res就可以。不是one pass。时间是O(2n), 他让我空间只用O(n)。我卡在空间就是O(2n) 了 ...

简化版301的最优空间复杂度是 O(1)吧!
O(n)的是栈,应该。

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘0
derek09 发表于 2017-11-1 10:37:30 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (55)
 
 
1% (1)  踩
by_lilei 发表于 2017-11-1 10:04
是可以用两个stack来做吗?stack1用来存open parenthesis index ,stack2存close的index。如果来了一个是 ...

Good idea,但是,用两个stack来做,如何保证第二次pass的时候,开闭parenthesis的顺序性呢?
回复

使用道具 举报

我的人缘0
吸猫不如刷题 发表于 2017-11-1 13:06:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  0% (0)
 
 
0% (0)  踩
想问下楼主第二轮第二题是怎么得到那一串list 是像bst level order traversal那样bfs用queue poll 一排一排存然后update最下面那排嘛.
回复

使用道具 举报

我的人缘0
jiaruomi 发表于 2017-11-1 14:20:33 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  75% (18)
 
 
25% (6)  踩
括号这题最近考的真频繁,我全职面基也考的这个

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
by_lilei 发表于 2017-11-1 21:55:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (30)
 
 
0% (0)  踩
derek09 发表于 2017-11-1 10:37
Good idea,但是,用两个stack来做,如何保证第二次pass的时候,开闭parenthesis的顺序性呢?

one pass 就可以了,一遍之后就知道哪几个index对应的parenthesis是需要移除的,直接移除就可以了-google 1point3acres

补充内容 (2017-11-1 22:07):
刚才又想了下移除多个的时候还是直接取substring,否则stringbuilder在移除一个字符之后,通过stack 找出的其他index 可能受影响
回复

使用道具 举报

我的人缘0
ps333 发表于 2017-11-2 01:09:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
请问“名人”那个题是什么意思呀?谢谢
回复

使用道具 举报

我的人缘0
jaedong 发表于 2017-11-2 05:15:27 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
Iverson333 发表于 2017-11-1 09:43
BFS找 deepest leaf node 的list。然后他们的lowest common ancestor 其实就是第一个leaf和最后一个leaf ...
. visit 1point3acres for more.
楼主,假如最深叶节点只有一个的话,你这个方法是不是还要特殊处理一下?否则按照LC234返回的应该是叶节点本身而不是lowest common ancestor.
回复

使用道具 举报

我的人缘0
 楼主| Iverson333 发表于 2017-11-2 06:26:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
ps333 发表于 2017-11-2 01:09
请问“名人”那个题是什么意思呀?谢谢

就是名人谁都不认识。大家都认识他的那个。
回复

使用道具 举报

我的人缘0
 楼主| Iverson333 发表于 2017-11-2 06:28:42 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
jaedong 发表于 2017-11-2 05:15
楼主,假如最深叶节点只有一个的话,你这个方法是不是还要特殊处理一下?否则按照LC234返回的应该是叶节 ...

嗯 和那个题很类似 但不是完全一样的。感觉FB也不怎么出LC原题了。
回复

使用道具 举报

我的人缘0
ps333 发表于 2017-11-2 13:54:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
Iverson333 发表于 2017-11-2 06:26
就是名人谁都不认识。大家都认识他的那个。
.本文原创自1point3acres论坛
啊懂了~谢谢
回复

使用道具 举报

我的人缘0
kzh88 发表于 2017-11-4 18:19:47 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (11)
 
 
8% (1)  踩
onepass 用prefix 就可以了吧,碰到不满足的情况时候 删掉那个括号 继续recursion
回复

使用道具 举报

我的人缘0
nhqgoal 发表于 2017-11-6 09:10:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  82% (58)
 
 
17% (12)  踩
楼主都做出来还挂了?
回复

使用道具 举报

我的人缘0
ARUI35 发表于 2017-11-25 11:14:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (73)
 
 
2% (2)  踩
在第二次用stringBuilder的时候还是用第一次定义的stringBuilder,只不过先调用一下stringBuilder.clear()可以吗?
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-9-23 12:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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