[八我司] Expedia一年半遊:这是一個特別適合養老待退的地方

一亩三分地论坛

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

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 2113|回复: 23
收起左侧

脸家实习跪经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
Iverson333 发表于 2017-11-1 08:28:54 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

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

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

评分

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

查看全部评分


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

本帖被以下淘专辑推荐:

我的人缘0
alex.chan 发表于 2017-11-1 09:21:24 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
301 one  pass  的怎么做啊??谢谢
回复 支持 1 反对 1

使用道具 举报

我的人缘0
by_lilei 发表于 2017-11-1 10:04:32 | 显示全部楼层
  此人我要顶:
 
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).
回复 支持 1 反对 0

使用道具 举报

我的人缘0
mmymichael 发表于 2017-11-1 08:39:34 | 显示全部楼层
  此人我要顶:
 
52% (12) 【我投】
  此人我要踩:
 
48% (11) 【我投】
请问楼主第二轮第二题是怎么写的?
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

我的人缘0
 楼主| Iverson333 发表于 2017-11-1 09:47:09 | 显示全部楼层
  此人我要顶:
 
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% (暂未有人投票) 【我投】
Iverson333 发表于 2017-11-1 09:47
它要求的返回一个res就可以。不是one pass。时间是O(2n), 他让我空间只用O(n)。我卡在空间就是O(2n) 了 ...

嗯,谢谢。
回复 支持 反对

使用道具 举报

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

简化版301的最优空间复杂度是 O(1)吧!
O(n)的是栈,应该。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
derek09 发表于 2017-11-1 10:37:30 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
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% (暂未有人投票) 【我投】
想问下楼主第二轮第二题是怎么得到那一串list 是像bst level order traversal那样bfs用queue poll 一排一排存然后update最下面那排嘛.
回复 支持 反对

使用道具 举报

我的人缘0
jiaruomi 发表于 2017-11-1 14:20:33 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
括号这题最近考的真频繁,我全职面基也考的这个
回复 支持 反对

使用道具 举报

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

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

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

使用道具 举报

我的人缘0
ps333 发表于 2017-11-2 01:09:56 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
请问“名人”那个题是什么意思呀?谢谢
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
 楼主| Iverson333 发表于 2017-11-2 06:26:17 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
ps333 发表于 2017-11-2 01:09. From 1point 3acres bbs
请问“名人”那个题是什么意思呀?谢谢

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

使用道具 举报

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

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

使用道具 举报

我的人缘0
ps333 发表于 2017-11-2 13:54:15 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Iverson333 发表于 2017-11-2 06:26
就是名人谁都不认识。大家都认识他的那个。

啊懂了~谢谢
回复 支持 反对

使用道具 举报

我的人缘0
kzh88 发表于 2017-11-4 18:19:47 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
onepass 用prefix 就可以了吧,碰到不满足的情况时候 删掉那个括号 继续recursion
回复 支持 反对

使用道具 举报

我的人缘0
nhqgoal 发表于 2017-11-6 09:10:55 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主都做出来还挂了?
回复 支持 反对

使用道具 举报

我的人缘0
ARUI35 发表于 2017-11-25 11:14:38 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
在第二次用stringBuilder的时候还是用第一次定义的stringBuilder,只不过先调用一下stringBuilder.clear()可以吗?
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

一亩三分地推荐上一条 /3 下一条

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

custom counter

GMT+8, 2018-6-19 18:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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