一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 1815|回复: 23
收起左侧

脸家实习跪经

[复制链接] |试试Instant~ |关注本帖
Iverson333 发表于 2017-11-1 08:28:54 | 显示全部楼层 |阅读模式

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

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

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

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

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

评分

1

查看全部评分

本帖被以下淘专辑推荐:

haifengc 发表于 2017-11-1 09:21:24 | 显示全部楼层
301 one  pass  的怎么做啊??谢谢
回复 支持 1 反对 1

使用道具 举报

by_lilei 发表于 2017-11-1 10:04:32 | 显示全部楼层
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

使用道具 举报

mmymichael 发表于 2017-11-1 08:39:34 | 显示全部楼层
请问楼主第二轮第二题是怎么写的?
回复 支持 反对

使用道具 举报

 楼主| Iverson333 发表于 2017-11-1 09:43:12 | 显示全部楼层
mmymichael 发表于 2017-11-1 08:39
请问楼主第二轮第二题是怎么写的?

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

使用道具 举报

 楼主| Iverson333 发表于 2017-11-1 09:47:09 | 显示全部楼层
haifengc 发表于 2017-11-1 09:21
301 one  pass  的怎么做啊??谢谢

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

使用道具 举报

haifengc 发表于 2017-11-1 09:57:58 | 显示全部楼层
Iverson333 发表于 2017-11-1 09:47.鏈枃鍘熷垱鑷1point3acres璁哄潧
它要求的返回一个res就可以。不是one pass。时间是O(2n), 他让我空间只用O(n)。我卡在空间就是O(2n) 了 ...

嗯,谢谢。
回复 支持 反对

使用道具 举报

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

简化版301的最优空间复杂度是 O(1)吧!. 鍥磋鎴戜滑@1point 3 acres
O(n)的是栈,应该。
回复 支持 反对

使用道具 举报

derek09 发表于 2017-11-1 10:37:30 | 显示全部楼层
by_lilei 发表于 2017-11-1 10:04
是可以用两个stack来做吗?stack1用来存open parenthesis index ,stack2存close的index。如果来了一个是 ...

. Waral 鍗氬鏈夋洿澶氭枃绔,Good idea,但是,用两个stack来做,如何保证第二次pass的时候,开闭parenthesis的顺序性呢?
回复 支持 反对

使用道具 举报

吸猫不如刷题 发表于 2017-11-1 13:06:24 | 显示全部楼层
想问下楼主第二轮第二题是怎么得到那一串list 是像bst level order traversal那样bfs用queue poll 一排一排存然后update最下面那排嘛.
回复 支持 反对

使用道具 举报

jiaruomi 发表于 2017-11-1 14:20:33 | 显示全部楼层
括号这题最近考的真频繁,我全职面基也考的这个
回复 支持 反对

使用道具 举报

by_lilei 发表于 2017-11-1 21:55:25 | 显示全部楼层
derek09 发表于 2017-11-1 10:37
Good idea,但是,用两个stack来做,如何保证第二次pass的时候,开闭parenthesis的顺序性呢?

one pass 就可以了,一遍之后就知道哪几个index对应的parenthesis是需要移除的,直接移除就可以了
. more info on 1point3acres.com
补充内容 (2017-11-1 22:07):
刚才又想了下移除多个的时候还是直接取substring,否则stringbuilder在移除一个字符之后,通过stack 找出的其他index 可能受影响
回复 支持 反对

使用道具 举报

ps333 发表于 2017-11-2 01:09:56 | 显示全部楼层
请问“名人”那个题是什么意思呀?谢谢
回复 支持 反对

使用道具 举报

jaedong 发表于 2017-11-2 05:15:27 | 显示全部楼层
Iverson333 发表于 2017-11-1 09:43
BFS找 deepest leaf node 的list。然后他们的lowest common ancestor 其实就是第一个leaf和最后一个leaf ...
. From 1point 3acres bbs
楼主,假如最深叶节点只有一个的话,你这个方法是不是还要特殊处理一下?否则按照LC234返回的应该是叶节点本身而不是lowest common ancestor.
回复 支持 反对

使用道具 举报

 楼主| Iverson333 发表于 2017-11-2 06:26:17 | 显示全部楼层
ps333 发表于 2017-11-2 01:09
请问“名人”那个题是什么意思呀?谢谢

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

使用道具 举报

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

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

使用道具 举报

ps333 发表于 2017-11-2 13:54:15 | 显示全部楼层
Iverson333 发表于 2017-11-2 06:26. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
就是名人谁都不认识。大家都认识他的那个。

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

使用道具 举报

kzh88 发表于 2017-11-4 18:19:47 | 显示全部楼层
onepass 用prefix 就可以了吧,碰到不满足的情况时候 删掉那个括号 继续recursion
回复 支持 反对

使用道具 举报

nhqgoal 发表于 2017-11-6 09:10:55 | 显示全部楼层
楼主都做出来还挂了?
回复 支持 反对

使用道具 举报

ARUI35 发表于 2017-11-25 11:14:38 | 显示全部楼层
在第二次用stringBuilder的时候还是用第一次定义的stringBuilder,只不过先调用一下stringBuilder.clear()可以吗?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2018-1-23 19:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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