一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1213|回复: 21
收起左侧

NYC G家onsite

[复制链接] |试试Instant~ |关注本帖
leixiang5 发表于 2016-11-11 14:53:35 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 猎头 - Onsite |Failfresh grad应届毕业生

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

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

x
来来来..今天收到拒信...作业写完了..放松了..分享个G的面经给大家...上周五面的...面的MTV的位置..但是懒得飞去加州..很累..就叫recruiter改到NYC了..所以在NYC面的...面试前一晚. 跟朋友吃的太high. 吃的太辣. 拉肚子了. 所以大家不要太high...哎..面试老毛病..一面试就紧张. 早上6点半就醒了. 8点20到G office. 傻傻的坐到了9点45...坐在酒店里非常不安..就去office了..以为能带我参观参观..结果是干干的坐在门口等着..coordinator带你到你的房间. 会问你要不要水, 要不要用厕所之类的. 刚进房间. coordinator就在黑板上写时间表. 几点几点面第几轮. 貌似还写了Google username.总共四轮...上午三轮...然后吃饭..然后下午再一轮..

第一轮:
Leetcode Sentence Screen Fitting. input是个string...不是String[]...其他的没区别..没截过这道..给美国姐姐说了第一个解法..姐姐说ok...然后就写...写完了问complexity多少..回答:L*W....问能不能improve..然后就说了个更好的...姐姐说..不错..写吧...又擦掉...再写...问Big-O...回答..L*S...姐姐说..ok...然后回答问题..

第二轮面试官进来. 貌似是中国人? 但是英文好到跟老外没区别.
问简历..
第二轮题目: given a list of execution logs, print the logs in this format: function_name function_elasped_time. Nested functions need to have spaces before it.
input 例子:
main t1 enter
foo t2 enter
foo t3 exit
bar t4 enter
bar t5 exit
main t6 exit

每个entry可以由下面的来代表.
class LogItem {
        String name;
        long t;
        bool is_enter;
}

output:
main t6-t1
   foo t3-t2 (注意要有spaces before foo, 如果foo calls foo2, 那foo2有4个spaces, so on so forth). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
   bar t5-t4

说了我的算法..国人哥哥ok...能写code么..写了之后.. 问我你觉得对了吗? 你觉得对的话. 我们可以move on了. 检查了下. 有bug. 他就说exactly. 幸好我说检查. 不然就傻逼了. 就口述了下如何改.
然后就讨论如何优化Space...没多少时间讨论如何优化...国人哥哥说没事..做得挺好的. 你基本上都写出来了. 只是优化而已...你基本的data structures都掌握的不错..

第三轮. 带个帽子的. 貌似是个犹太人? 非常的picky!!!!!!非常!!!! 抱着一个notes. 里面夹着超多超多的面试题目...
说了名字. 没寒暄. 直接问问题.
Leetcode 271.
你写啥. 他问啥. 写code的时候各种问你问题. 说这个干吗的. 这个怎么来的. 非常的picky. 我当时完全忘记 string 里的indexOf('/', i);..我用了indexof('/'). 但是没想到indexof可以帮我skip characters...因为忘记这个了.然后就利用substring来达到indexof这个效果。当时就担心substring会create new string. 面试叔叔一脸骄傲的表示. java underlying system其实是不会create的. 那我就说. 不会的话那就太好了. 写完了之后. 就一直找edge case 来break我的code. 没看出来. 她就说. 如果给你一个random string 来 decode。 你就fail了。我说是啊。然后就跟他说可以在哪里哪里 加check statements. 结束之后. 出了道Rot-13的问题.. 其实没太懂..不知道为啥没什么时间了...还出这种需要解释的题目...给他大概解释了我的解法...她应该没懂..然后他主动放我吃饭...我心里默念:大哥。我想留着给你讲解啊...

吃饭轮:
一个为了女朋友。从加拿大来ny工作的小哥。真爱啊....感觉ny食堂还行吧. 比fb的总部小好多....但是感觉比fb的好吃....view蛮不错的..
吃完就坐在房间外面跟小哥聊天. 面试开始前几分钟. 小哥就放我回去了.

第四轮面试官已经早早的坐在房间等我了. 貌似俄罗斯人. . 1point3acres.com/bbs
第四轮:
这轮算是我面试人生中..最难最难最难的一轮. 面完这轮. 感觉4年cs白学了.. From 1point 3acres bbs
一听他说话. 就知道完蛋了. 这人肯定很难聊. 冷面虎. 口音很重.
说..我给你出道distributed algorithm. (I was like WTF? Seriouslly?). 我听完他的描述.然后我说. 然后叻? 题目是啥? - -..然后仔细回想了下她的description..猜到了他要问什么..
Imagine each computer is a node. Each node has a number. Each node can send message to other node. The system uses asynchronous messaging. Now implement the following to find the max value in the network.

class Node {
        List<ID> neighbors;
鏉ユ簮涓浜.涓夊垎鍦拌鍧.         int value;. 鍥磋鎴戜滑@1point 3 acres
. 1point 3acres 璁哄潧
        void start() {...}
        send(ID, ...);
        onMsg(ID, ...) {...}
        void done(int max) -> call this method when network max is known.
        ...
}.1point3acres缃
-google 1point3acres
... 代表的是我要写的. 你可以给Node 加states. send, onMsg里的payload 你都可以自己加. 智商完全受到了碾压. 我就跟她说了大概这样这样解. 问他这样对吗? 他说这是你的算法. 你觉得对么. 我一脸囧...写的时给N个hints. 各种表现的自己很牛逼. 说你这里有问题. 那里有问题. 这个东西不需要. 利用这个就可以解决了. 各种更改- -. 改的我自己都不知道我写了什么了. 然后他就说. ok. 你的code almost perfect. 还差2点. 然后我就自己看- -. 完全看不出来. 他就说这里怎么样怎么样. 改了之后. 她就说. 还差一点. 我就一脸懵逼- -. 然后她就说这个cycle graph的时候会怎么样. 然后我就说噢. 对. 这个会fail. 然后盯着code....然后改了...当时时间超过了..面试官来句..没事..你慢慢改..这是你最后一轮了...你有的是时间 (侮辱我的智商..)..写完了之后. 我说. 你肯定在Google搞分布系统.对不对! 他来了句. 没有. 我是infra的. 但是分布我还是懂的...他跟我说. It's okay. You did well. (安慰我幼小的心灵么.). 他说她面谁都出这个问题. 我在上distributed systems. 只能说. 只恨自己没好好听课...他就送我下楼了- -. 问我如果拿到offer. 直接来吗? 我就说我一年后毕业. ..老头真会做人.....
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
礼拜四..recruiter约电话...然后说hc 不move forward了..但是问我对application engineer有没有兴趣....跟她说...我考虑下...挂了电话之后...给hr来封拒信...说我没兴趣..懒得面试了..

anyway. move on~..最后来句..亚麻才是王道! good luck to everyone...Hope every one gets a dream job.~...继续搜寻我的dream company..


评分

2

查看全部评分

samuelling 发表于 2016-11-11 15:07:57 | 显示全部楼层
Patpat 群主,我最后一轮也被一个口音很重的厄瓜多尔人给坑了。。。
回复 支持 反对

使用道具 举报

 楼主| leixiang5 发表于 2016-11-11 15:14:58 | 显示全部楼层
samuelling 发表于 2016-11-11 15:07
Patpat 群主,我最后一轮也被一个口音很重的厄瓜多尔人给坑了。。。

-.- 也不能说被他坑了吧...感觉就算他写个no hire...其他人写hire...怎么样也会过的...说明其他人的feedback写的也不咋的..
. 1point 3acres 璁哄潧
补充内容 (2016-11-11 15:15):
面完本来想给hr说下的..但是想想算了.....毕竟老头看起来不差...
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-11 15:48:43 | 显示全部楼层
第二轮那个题是用stack吗?
回复 支持 反对

使用道具 举报

 楼主| leixiang5 发表于 2016-11-11 15:59:54 | 显示全部楼层
wtcupup 发表于 2016-11-11 15:48
第二轮那个题是用stack吗?
. 1point3acres.com/bbs
自己试着写一下吧~。stack 并不能给你output
回复 支持 反对

使用道具 举报

EmilyMMMM 发表于 2016-11-17 16:11:25 | 显示全部楼层
群主666,NYC office是狗家最难面的一个了…………
回复 支持 反对

使用道具 举报

 楼主| leixiang5 发表于 2016-11-18 12:05:13 | 显示全部楼层
EmilyMMMM 发表于 2016-11-17 16:11. visit 1point3acres.com for more.
群主666,NYC office是狗家最难面的一个了…………

office还有影响的么......既然面了..就算了...当参观下office~
回复 支持 反对

使用道具 举报

a9887688zboy 发表于 2016-11-19 22:35:24 | 显示全部楼层
弱问下楼主,application engineer是什么?是以前的residency program吗?
回复 支持 反对

使用道具 举报

singku 发表于 2016-11-20 00:00:53 | 显示全部楼层
第二题感觉 可以用stack 记录匹配顺序,用ordered_map记录输出顺序
比如 [main_in, [foo_in, [foo2_in, foo2_out, foo_in, foo_out], foo_out], bar_in, bar_out]. visit 1point3acres.com for more.
stack 里面可以记录in及其打印顺序和in的时间,
顺序一开始从低到高是 main_1->foo_2->foo2_3,
遇到foo2 弹出栈顶, 写到ordered_map里 <3, {foo2, start, end, stack_size=2}>
遇到foo_in 栈变成 main_1->foo_2->foo_4 遇到foo_out 写到ordered_map <4, {foo, start, end, stack_size=2}>
遇到foo_out 弹出栈顶, 写 <2, {foo, start, end, stack_size=1}>
遇到bar_in 进 main_1->bar_5, 遇到bar_out <5, {bar, start, end, stack_size=1}>. 鍥磋鎴戜滑@1point 3 acres
遇到main_out <1, {main, start, end, stack_size=0}>

然后按ordered_map的顺序输出map的内容
stack_size决定前面有几个spaces.
需要一个变量记录当前打印顺序,每个function的打印顺序和start都随栈记录
.鐣欏璁哄潧-涓浜-涓夊垎鍦
需要2n的额外空间, 时间复杂度取决于ordered_map的排序 是nlogn
如果想达到n的时间的话 可以用vector/array,但是要预处理一下 找到一共有多少个function的执行。
回复 支持 反对

使用道具 举报

singku 发表于 2016-11-20 00:26:25 | 显示全部楼层
最后那题,因为每个节点只有固定的邻居,对于每个节点,要知道全网最大值,必须通过邻居节点收集其他所有节点的值,然后把自己手里没告诉邻居的值告诉邻居。
所以我觉得每个节点首先应该有一个数组 或者hash_set记录目前收集到的值,自己的不记录的话 应该是n-1的大小,当hash_set的size达到 n-1的时候就可以call done了。
然后需要记录告诉了哪些邻居哪些值,这里可以用map<neighbor, set<val>> 因为邻居不是所有的其他节点,当然最差的空间复杂度应该是n^2 如果是个全联通的graph的话。
但是因为邻居是固定的,可以收到一个值就告诉所有邻居,可以退化成存set<val> 表示已经告诉了邻居哪些值。

send函数的话 应该是 send(neighborID, nodeID, nodeValue) 告诉某个邻居 某个node的值是多少, 只要直接发送就行
onMsg的话 应该是onMsg(neighborID, nodeID, nodeValue) 某个邻居告诉我 某个node的值是多少,收到这个msg后,如果发现已经给邻居广播过了
就不管了。如果没有 就遍历除了neighborID的其他邻居,调用send
start的话 也是遍历所有邻居 send自己的数值。

这样的话 每个节点最多只会给邻居发送一次不同的值, 发送总量应该是n(n-1)。每个值最多会收到n-1次 收量应该也是n(n-1) 全网信息量最多应该是n^2 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
回复 支持 反对

使用道具 举报

 楼主| leixiang5 发表于 2016-11-20 01:14:16 | 显示全部楼层
a9887688zboy 发表于 2016-11-19 22:35
弱问下楼主,application engineer是什么?是以前的residency program吗?

不清楚。你可以上他们网站看看
回复 支持 反对

使用道具 举报

 楼主| leixiang5 发表于 2016-11-20 01:36:09 | 显示全部楼层
singku 发表于 2016-11-20 00:00
第二题感觉 可以用stack 记录匹配顺序,用ordered_map记录输出顺序
比如 [main_in, [foo_in, [foo2_in, fo ...

hmmmmm....这道题其实有蛮多解法的...现在看了下你的...貌似可以根据stack size * 2..就可以知道前面print多少个spaces.....但是我当时是maintain 一个map..遇到每个func 查看stack peek上的func有多少个spaces..然后+2...
当时面试官好像说..queue + stack 就可以解决...但是还是看不出来如何解决...
回复 支持 反对

使用道具 举报

 楼主| leixiang5 发表于 2016-11-20 01:38:22 | 显示全部楼层
singku 发表于 2016-11-20 00:26
最后那题,因为每个节点只有固定的邻居,对于每个节点,要知道全网最大值,必须通过邻居节点收集其他所有节 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
hmmmm....最终的perfect solution是...自己加的states是O(1)....
然后你的send和onMsg....还差个东西....neighborID不需要的..
回复 支持 反对

使用道具 举报

knight0clk 发表于 2016-11-21 14:29:02 | 显示全部楼层
哈哈哈上课没好好听,这是不是可以用bully做啊
回复 支持 反对

使用道具 举报

 楼主| leixiang5 发表于 2016-11-21 15:02:24 | 显示全部楼层
knight0clk 发表于 2016-11-21 14:29
哈哈哈上课没好好听,这是不是可以用bully做啊
.1point3acres缃
bully 只是选leader - -..跟这个无关...
回复 支持 反对

使用道具 举报

lll_2013 发表于 2016-11-21 15:15:00 | 显示全部楼层
最后一题选择任意一个node,用bfs,然后访问过的记录一下,最后返回的是bfs过的node & 对应的val
回复 支持 反对

使用道具 举报

 楼主| leixiang5 发表于 2016-11-21 15:16:53 | 显示全部楼层
lll_2013 发表于 2016-11-21 15:15
最后一题选择任意一个node,用bfs,然后访问过的记录一下,最后返回的是bfs过的node & 对应的val

- -这是distributed algo...
原理上来说...直接bfs or dfs找最大值就对了...但是因为在不同的machine上...implement会困难许多..。
回复 支持 反对

使用道具 举报

lll_2013 发表于 2016-11-21 19:36:55 | 显示全部楼层
leixiang5 发表于 2016-11-21 02:16
- -这是distributed algo.... Waral 鍗氬鏈夋洿澶氭枃绔,
原理上来说...直接bfs or dfs找最大值就对了...但是因为在不同的machine上. ...

distributed不懂,不过网络设备不是应该有sender和receiver吗?还有server和client?receiver收到的是一个串,从node_0 to node_n的一个path,然后它本身作为下一级send到下一个node,每次receiver还会把自己信息反馈给server,server里面保存了所有client信息。
回复 支持 反对

使用道具 举报

 楼主| leixiang5 发表于 2016-11-21 23:26:27 | 显示全部楼层
lll_2013 发表于 2016-11-21 19:36
distributed不懂,不过网络设备不是应该有sender和receiver吗?还有server和client?receiver收到的是一 ...

没事..基本可以无视这道题目了...这道题太独特了...不会考到的...
回复 支持 反对

使用道具 举报

jokebill 发表于 2016-11-26 13:07:24 | 显示全部楼层
第二题应该一个stack加一个result array就够了吧?遇到enter的时候,添一个新line到result里,另把这个line的index记到stack里面,遇到exit,从stack里pop出enter的那个line, 补全退出时间,另且按stack剩下的元素个数加空格,就好了。space优化没想出什么更好的办法,感觉如果log最后是记到文件里的话,可以每次stack空(也就是main退出了)的时候,把result array全写进log里面,然后清空result array。
. Waral 鍗氬鏈夋洿澶氭枃绔,
最后一题有点意思,但是感觉LZ是真的被坑了,这哪是一个小时能白板能做出来的问题嘛... 而且这个问题有解应该还需要一个条件,就是所有node都要在同一个transitive closure里。我的大概思路就是,任选一个node做为启始点,向他所有neighbor发自己的value。每个node,当第一次接收到一条message的时候,把message的来源记为自己的parent,并向自己所有除了消息来源外的neighbor broadcast自己的值。以后每次收到message的时候,都更新下自己的最大值记录,并把来源记到另一个returned set里,当returned set和neighbor set一样大的时候,说明这个node已经收集到自己和子树里的最大值了,把这个最大值发回给自己记录的parent就可以。当一开始选中的那个node得到所有neighbor的回复时,输出全网最大值。. Waral 鍗氬鏈夋洿澶氭枃绔,

  1. import threading

  2. import time

  3. import Queue





  4. class Node(threading.Thread):

  5.     def __init__(self, ID, val):
  6. . from: 1point3acres.com/bbs
  7.         self.ID = ID

  8.         self.val = val

  9.         self.max_val = val

  10.         self.neighbors = {}

  11.         self.returned = set()

  12.         self.parent = None. more info on 1point3acres.com

  13.         self.isInitiator = False

  14.         self.msgQ = Queue.Queue()

  15.         super(Node, self).__init__()






  16.     def addNeighbor(self, node):

  17.         self.neighbors[node.ID] = node. from: 1point3acres.com/bbs



  18. -google 1point3acres
  19.     def run(self):.1point3acres缃

  20.         if self.isInitiator:

  21.             if self.neighbors:
  22. . visit 1point3acres.com for more.
  23.                 for node in self.neighbors.iterkeys():. From 1point 3acres bbs

  24.                     self.send(node)
  25. . 1point 3acres 璁哄潧

  26.         while len(self.neighbors) != len(self.returned):
  27. . From 1point 3acres bbs
  28.             #handle messages

  29.             if self.msgQ:

  30. . visit 1point3acres.com for more.
  31.                 src, val = self.msgQ.get()
  32. . 1point 3acres 璁哄潧
  33.                 self.onMsg(src, val)

  34.             time.sleep(0.01)

  35. .1point3acres缃

  36.         if self.isInitiator:

  37.             self.done()
  38. . 1point 3acres 璁哄潧
  39.         else:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  40.             self.send(self.parent)

  41. .鐣欏璁哄潧-涓浜-涓夊垎鍦


  42. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  43.     def send(self, ID):


  44.         self.neighbors[ID].msgQ.put((self.ID, self.max_val))





  45.     def onMsg(self, ID, val):. From 1point 3acres bbs



  46. -google 1point3acres
  47.         if self.parent is None and not self.isInitiator:

  48.             self.parent = ID

  49.             for n in self.neighbors.iterkeys():

  50.                 if n == ID:. 1point 3acres 璁哄潧

  51.                     continue

  52.                 self.send(n)

  53.         self.returned.add(ID)

  54.         self.max_val = max(self.max_val, val)



  55.     def done(self):

  56.         print self.max_val
  57. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷



  58. if __name__ == "__main__":-google 1point3acres

  59.     node_vals = [ 4, 2, 5, 6, 3, 3, 6, 1, 12 ]

  60.     node_neighbors = [.鐣欏璁哄潧-涓浜-涓夊垎鍦

  61.         [1, 2, 3, 4],

  62.         [0, 2, 5, 6, 7],

  63.         [0, 1],

  64.         [0],

  65.         [0, 7],

  66. . From 1point 3acres bbs
  67.         [1],

  68.         [1],. visit 1point3acres.com for more.

  69.         [1, 4, 8],
  70. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  71.         [7]. Waral 鍗氬鏈夋洿澶氭枃绔,

  72.     ]
  73. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


  74.     for starter in range(len(node_vals)):

  75.         print "====== Initiator is {} ==========".format(starter)

  76.         Nodes = [ Node(idx, val) for idx, val in enumerate(node_vals) ]

  77.         for idx, nbs in enumerate(node_neighbors):

  78.             if idx == starter:

  79.                 Nodes[idx].isInitiator = True
  80. . Waral 鍗氬鏈夋洿澶氭枃绔,
  81.             for n in nbs:-google 1point3acres

  82.                 Nodes[idx].addNeighbor(Nodes[n])


  83.         for n in Nodes:

  84.             n.start()


  85.         for n in Nodes:. 1point 3acres 璁哄潧

  86.             n.join()
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 17:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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