由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - G家悲剧,发面经
相关主题
local小公司面试悲剧请教leetcode高频题是哪些题
amazon 1st phone interview求FB 面试 leetcode题目列表
longest valid Parentheses有O(n)算法么amazon居然有这么难得phone interview question
今天计划做20题发点面经回馈下本版的帮助
G intern电面面经回馈大众,汇报找工作经验,已拿到g家油管offer
有人能解释下Generate Parentheses的DP解法么?如何实现binary tree的从下到上的分层打印?
leetcode Different Ways to Add Parentheses 怎么做?求救: 打印binary tree
一道facebook面试题Write an iterative method that finds depth of a (non-balanced) binary tree.
相关话题的讨论汇总
话题: design话题: find话题: each话题: hit话题: function
进入JobHunting版参与讨论
1 (共1页)
x*****3
发帖数: 25
1
电面第一个是烙印面试官
1. reverse a string很简单
2. Assume we have n people. Each one has a starting time and ending
time. For any people, set flag to true if his/her time range overlaps
with anyone else's.
3. Find a connection between two people if there is one, or return
false. Each people has father and mother and the connection means if
there's any common relatives. This problem is to find the common node of
two binary trees.
电面第二个是中国人面试官
1. print a binary tree level by level
2. how to represent a tree in which each node may has more than two
children? and how to print this tree level by level.
3. Some hash function related questions. not very difficult.
on-site interview:
题目太多记不得全部了,只能写记得的那一部分:
1.print all the legal combinations of n parentheses. (()()) is legal; )
(())( is not.
2. how to design data structures for a facebook network and how to
design an algorithm to find connection? How to optimize it if data is
distributed into multiple computers?
3.design a deck class and member function to randomly select a card from
those cards which haven't been selected before. (You can assume the
number of this function call will never be larger than the number of
cards) For example, we have a deck of four card: 1,2,3,4. First it may
select 3, then next time it should randomly select one from 1,2,4... And
design a member function to reset.
4.describe and compare the adjacent lists and matrix representations of
graph.
Design algorithm to find connected component of a given graph.
5.google search design problem. How to distribute data and how to design
backup system
6.write a k-way merge function. How to use binary search tree or linked
list to optimize it
7.design algorithm for a game: suppose we have a n*n board and several
ships are placed on it. Each ship is 1*m or m*1 and placed vertically or
horizontally on the board (no overlap). Then given coordinates of a
missile (x and y), write a function to return miss, hit or sink. Miss
means miss. Hit means hit one ship but not all parts of that ship have
been hit yet. Sink means hit one ship and all the other parts of this
ship have already been hit, so it will sink.
Design different data structures/algorithms and compare the time/space
time complexity.
x*****3
发帖数: 25
2
感觉google的题目不难。但是要求很高,必须一次写出无错代码。 我估计就是悲剧在
这里了。有几道题目我的code有些小问题,随后随后马上纠正了,但是估计也留下了不
好的印象。
另外上周的apple on-site也悲剧了。
大家有没有什么工作信息的,希望能给我发个站内信。谢谢。 本人cs master,刚毕业
d****2
发帖数: 6250
3

idiot company idiot people

【在 x*****3 的大作中提到】
: 感觉google的题目不难。但是要求很高,必须一次写出无错代码。 我估计就是悲剧在
: 这里了。有几道题目我的code有些小问题,随后随后马上纠正了,但是估计也留下了不
: 好的印象。
: 另外上周的apple on-site也悲剧了。
: 大家有没有什么工作信息的,希望能给我发个站内信。谢谢。 本人cs master,刚毕业

r*******y
发帖数: 1081
4
bless
感觉不是 cs科班出身的话去面试 google一定得把 clrs搞透

【在 x*****3 的大作中提到】
: 电面第一个是烙印面试官
: 1. reverse a string很简单
: 2. Assume we have n people. Each one has a starting time and ending
: time. For any people, set flag to true if his/her time range overlaps
: with anyone else's.
: 3. Find a connection between two people if there is one, or return
: false. Each people has father and mother and the connection means if
: there's any common relatives. This problem is to find the common node of
: two binary trees.
: 电面第二个是中国人面试官

d*******r
发帖数: 208
5
cmft~
拿到这两牛公司得onsite已经很牛了,Offer不远了。

【在 x*****3 的大作中提到】
: 感觉google的题目不难。但是要求很高,必须一次写出无错代码。 我估计就是悲剧在
: 这里了。有几道题目我的code有些小问题,随后随后马上纠正了,但是估计也留下了不
: 好的印象。
: 另外上周的apple on-site也悲剧了。
: 大家有没有什么工作信息的,希望能给我发个站内信。谢谢。 本人cs master,刚毕业

m******m
发帖数: 19
6
lz能说说第一轮电面第3题:find the common node of two binary trees.的思路么
brute force:先遍历A树,将所有节点存入hashset,然后遍历B树,check当前节点是否
在hashset
出现,如果是return true.
此外,lz能讲下onsite的最后一题么,不是很明白啊~

【在 x*****3 的大作中提到】
: 电面第一个是烙印面试官
: 1. reverse a string很简单
: 2. Assume we have n people. Each one has a starting time and ending
: time. For any people, set flag to true if his/her time range overlaps
: with anyone else's.
: 3. Find a connection between two people if there is one, or return
: false. Each people has father and mother and the connection means if
: there's any common relatives. This problem is to find the common node of
: two binary trees.
: 电面第二个是中国人面试官

f*****w
发帖数: 2602
7
6.write a k-way merge function. How to use binary search tree or linked
list to optimize it
为啥可以用linked list来优化
我能想得到的是用个heap
f*****w
发帖数: 2602
8
第七题 的那个导弹有很多个吗? 还有是按照什么轨迹运行的?
a**********2
发帖数: 340
9

同问

【在 f*****w 的大作中提到】
: 6.write a k-way merge function. How to use binary search tree or linked
: list to optimize it
: 为啥可以用linked list来优化
: 我能想得到的是用个heap

v*s
发帖数: 946
10
// bless

【在 x*****3 的大作中提到】
: 电面第一个是烙印面试官
: 1. reverse a string很简单
: 2. Assume we have n people. Each one has a starting time and ending
: time. For any people, set flag to true if his/her time range overlaps
: with anyone else's.
: 3. Find a connection between two people if there is one, or return
: false. Each people has father and mother and the connection means if
: there's any common relatives. This problem is to find the common node of
: two binary trees.
: 电面第二个是中国人面试官

相关主题
有人能解释下Generate Parentheses的DP解法么?请教leetcode高频题是哪些题
leetcode Different Ways to Add Parentheses 怎么做?求FB 面试 leetcode题目列表
一道facebook面试题amazon居然有这么难得phone interview question
进入JobHunting版参与讨论
z*******y
发帖数: 578
11
楼主牛,继续加油
谢谢分享面经
g****x
发帖数: 325
12
楼主厉害!!
bless
E*******0
发帖数: 465
13
2. Assume we have n people. Each one has a starting time and ending
time. For any people, set flag to true if his/her time range overlaps
with anyone else's
这道题搂主的算法复杂度是多少阿?
E*******0
发帖数: 465
14
3. Find a connection between two people if there is one, or return
false. Each people has father and mother and the connection means if
there's any common relatives. This problem is to find the common node of
two binary trees.
觉得应该不是树结构,而是图结构。
for example,
f m
|/
son
E*******0
发帖数: 465
15
2. Assume we have n people. Each one has a starting time and ending
time. For any people, set flag to true if his/her time range overlaps
with anyone else's
这道题的算法复杂度可以为n.
E*******0
发帖数: 465
16
3. Find a connection between two people if there is one, or return
false. Each people has father and mother and the connection means if
there's any common relatives. This problem is to find the common node of
two binary trees.
把问题转换为一个图组的DFS,这道题的算法复杂度为n+m。
d*******d
发帖数: 2050
17
那个括号组合怎么弄啊.
我想的是递归,可重复的怎么办?而且复杂度太高了.

【在 x*****3 的大作中提到】
: 电面第一个是烙印面试官
: 1. reverse a string很简单
: 2. Assume we have n people. Each one has a starting time and ending
: time. For any people, set flag to true if his/her time range overlaps
: with anyone else's.
: 3. Find a connection between two people if there is one, or return
: false. Each people has father and mother and the connection means if
: there's any common relatives. This problem is to find the common node of
: two binary trees.
: 电面第二个是中国人面试官

f*****w
发帖数: 2602
18

我感觉递归是唯一的办法。
可以用catalan数的那个递归方程来做一些类似于DP的优化,但是复杂度还是没区别的


【在 d*******d 的大作中提到】
: 那个括号组合怎么弄啊.
: 我想的是递归,可重复的怎么办?而且复杂度太高了.

m**q
发帖数: 189
19
详细说一下?不需要排序么

【在 E*******0 的大作中提到】
: 2. Assume we have n people. Each one has a starting time and ending
: time. For any people, set flag to true if his/her time range overlaps
: with anyone else's
: 这道题的算法复杂度可以为n.

B*M
发帖数: 1340
20
是啊,overlap这题,不排序怎么搞?
我会排序的,

【在 m**q 的大作中提到】
: 详细说一下?不需要排序么
相关主题
发点面经回馈下本版的帮助求救: 打印binary tree
回馈大众,汇报找工作经验,已拿到g家油管offerWrite an iterative method that finds depth of a (non-balanced) binary tree.
如何实现binary tree的从下到上的分层打印?Amazon面经
进入JobHunting版参与讨论
y*******g
发帖数: 6599
21
interval tree 吧,不过还是排序了

【在 B*M 的大作中提到】
: 是啊,overlap这题,不排序怎么搞?
: 我会排序的,

f**********t
发帖数: 1001
22
interval tree的construction也是O(n logn)吧。
这题interval tree是考点么?
t********3
发帖数: 567
23
楼主很强了,加油加油,offer马上就来了
t********3
发帖数: 567
24
一定要递归么。假设有N对括号,前括号用1表示,后括号用2表示。从空序列开始,每
次加入的可以是1,或者2,但是需要保证到目前为止,2的个数不超过1的个数,还有1
的个数不大于N。写一个while循环,不需要什么递归的

【在 f*****w 的大作中提到】
:
: 我感觉递归是唯一的办法。
: 可以用catalan数的那个递归方程来做一些类似于DP的优化,但是复杂度还是没区别的
: 。

b*******8
发帖数: 37364
25
我是这么理解的:
一次写出完全无错误代码几乎不可能。只要写出无太明显错误的代码,面试官也不能很
快错误的话,那就自然达到了公司的水平要求。这个代码有无错误,是根据公司水平浮
动的。这样讲,这个要求很合理很自然,不必担心。

【在 x*****3 的大作中提到】
: 感觉google的题目不难。但是要求很高,必须一次写出无错代码。 我估计就是悲剧在
: 这里了。有几道题目我的code有些小问题,随后随后马上纠正了,但是估计也留下了不
: 好的印象。
: 另外上周的apple on-site也悲剧了。
: 大家有没有什么工作信息的,希望能给我发个站内信。谢谢。 本人cs master,刚毕业

b*******8
发帖数: 37364
26
括号问题,一个左右括号序列(左右括号数相等)是合法匹配的充分必要条件是,任何
一个前缀里左括号数大于等于右括号数。数学归纳法可证,不复杂。
递归的时候,当已经选择的左括号数等于右括号数时,只能选择右括号做下一个,否则
即可以左也可以右边。若左括号已经选满,那当然后面填满右括号就是了。写了个非递
归的C程序,有点复杂,今天晚上测试一下,通过了就贴出来。

【在 f*****w 的大作中提到】
:
: 我感觉递归是唯一的办法。
: 可以用catalan数的那个递归方程来做一些类似于DP的优化,但是复杂度还是没区别的
: 。

i*****f
发帖数: 578
27
括号那题.基本思路是一个stack,遇到(就push,)就pop,如果stack空了,就不能继
续append )。一共给N个(和N个),用完就不能再用。
递归来做.
'''List all legal combination of N pairs of parentheses.'''
def F(B, A0, A1):
if A0>0:
for res in F(B+[1], A0-1, A1):
yield [0]+res
if A1>0 and len(B):
for res in F(B[:-1], A0, A1-1):
yield [1]+res
if A0==A1==0: yield []
#### tests #####
def print_as_parentheses(a):
for b in a:
if b == 0: print '(',
else: print ')',
print
N = 4
for x in F([], N, N):
print_as_parentheses(x)
#### output #####
( ( ( ( ) ) ) )
( ( ( ) ( ) ) )
( ( ( ) ) ( ) )
( ( ( ) ) ) ( )
( ( ) ( ( ) ) )
( ( ) ( ) ( ) )
( ( ) ( ) ) ( )
( ( ) ) ( ( ) )
( ( ) ) ( ) ( )
( ) ( ( ( ) ) )
( ) ( ( ) ( ) )
( ) ( ( ) ) ( )
( ) ( ) ( ( ) )
( ) ( ) ( ) ( )

【在 x*****3 的大作中提到】
: 电面第一个是烙印面试官
: 1. reverse a string很简单
: 2. Assume we have n people. Each one has a starting time and ending
: time. For any people, set flag to true if his/her time range overlaps
: with anyone else's.
: 3. Find a connection between two people if there is one, or return
: false. Each people has father and mother and the connection means if
: there's any common relatives. This problem is to find the common node of
: two binary trees.
: 电面第二个是中国人面试官

g**********y
发帖数: 14569
28
7题:这种比较open的题我经常回答得不好,就抛砖引玉一下,
Assumption: attack不重复,重复的话先清除duplicate
class Stat {
int hit;
int count;
}
HashMap map;
initializeMap();
foreach(Attack a) {
Stat s = map.get(new Point(a.x, a.y));
if (s == null) {
state = MISS;
continue;
}

s.hit++;
state = s.hit==s.count? SINK : HIT;
}
h**********8
发帖数: 267
29
mark
x***i
发帖数: 64
30
有人能讲一下这题的思路吗?
3. Find a connection between two people if there is one, or return
false. Each people has father and mother and the connection means if
there's any common relatives. This problem is to find the common node of
two binary trees.
相关主题
A Google Problemamazon 1st phone interview
这题咋做?longest valid Parentheses有O(n)算法么
local小公司面试悲剧今天计划做20题
进入JobHunting版参与讨论
x****1
发帖数: 118
31
遍历A树应该会是无限走下去。
这道题我觉得应该向下BFS遍历A,遇到B就停止,同时向下BFS遍历B,遇到A停止。因为我们不知道谁是
谁的祖先。

【在 m******m 的大作中提到】
: lz能说说第一轮电面第3题:find the common node of two binary trees.的思路么
: brute force:先遍历A树,将所有节点存入hashset,然后遍历B树,check当前节点是否
: 在hashset
: 出现,如果是return true.
: 此外,lz能讲下onsite的最后一题么,不是很明白啊~

x****1
发帖数: 118
32
1.print a binary tree level by level
1.print all the legal combinations of n parentheses. (()()) is legal; )
(())( is not.
2. how to design data structures for a facebook network and how to
design an algorithm to find connection? How to optimize it if data is
distributed into multiple computers?
3.design a deck class and member function to randomly select a card from
those cards which haven't been selected before. (You can assume the
number of this function call will never be larger than the number of
cards) For example, we have a deck of four card: 1,2,3,4. First it may
select 3, then next time it should randomly select one from 1,2,4... And
design a member function to reset.
这几道是cracking the coding interview 的原题
1 (共1页)
进入JobHunting版参与讨论
相关主题
Write an iterative method that finds depth of a (non-balanced) binary tree.G intern电面面经
Amazon面经有人能解释下Generate Parentheses的DP解法么?
A Google Problemleetcode Different Ways to Add Parentheses 怎么做?
这题咋做?一道facebook面试题
local小公司面试悲剧请教leetcode高频题是哪些题
amazon 1st phone interview求FB 面试 leetcode题目列表
longest valid Parentheses有O(n)算法么amazon居然有这么难得phone interview question
今天计划做20题发点面经回馈下本版的帮助
相关话题的讨论汇总
话题: design话题: find话题: each话题: hit话题: function