一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2391|回复: 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.总共四轮...上午三轮...然后吃饭..然后下午再一轮..
. From 1point 3acres bbs
第一轮:
Leetcode Sentence Screen Fitting. input是个string...不是String[]...其他的没区别..没截过这道..给美国姐姐说了第一个解法..姐姐说ok...然后就写...写完了问complexity多少..回答:L*W....问能不能improve..然后就说了个更好的...姐姐说..不错..写吧...又擦掉...再写...问Big-O...回答..L*S...姐姐说..ok...然后回答问题..
. visit 1point3acres.com for more.
第二轮面试官进来. 貌似是中国人? 但是英文好到跟老外没区别.
问简历..
第二轮题目: 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可以由下面的来代表.. From 1point 3acres bbs
class LogItem {
        String name;
        long t;
        bool is_enter;
. Waral 鍗氬鏈夋洿澶氭枃绔,}

output:. 鍥磋鎴戜滑@1point 3 acres
main t6-t1
   foo t3-t2 (注意要有spaces before foo, 如果foo calls foo2, 那foo2有4个spaces, so on so forth). 1point3acres.com/bbs
   bar t5-t4

说了我的算法..国人哥哥ok...能写code么..写了之后.. 问我你觉得对了吗? 你觉得对的话. 我们可以move on了. 检查了下. 有bug. 他就说exactly. 幸好我说检查. 不然就傻逼了. 就口述了下如何改.
然后就讨论如何优化Space...没多少时间讨论如何优化...国人哥哥说没事..做得挺好的. 你基本上都写出来了. 只是优化而已...你基本的data structures都掌握的不错..
. 鍥磋鎴戜滑@1point 3 acres
第三轮. 带个帽子的. 貌似是个犹太人? 非常的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的问题.. 其实没太懂..不知道为啥没什么时间了...还出这种需要解释的题目...给他大概解释了我的解法...她应该没懂..然后他主动放我吃饭...我心里默念:大哥。我想留着给你讲解啊...
-google 1point3acres
吃饭轮:
一个为了女朋友。从加拿大来ny工作的小哥。真爱啊....感觉ny食堂还行吧. 比fb的总部小好多....但是感觉比fb的好吃....view蛮不错的..
吃完就坐在房间外面跟小哥聊天. 面试开始前几分钟. 小哥就放我回去了.

第四轮面试官已经早早的坐在房间等我了. 貌似俄罗斯人.
第四轮:
这轮算是我面试人生中..最难最难最难的一轮. 面完这轮. 感觉4年cs白学了.
一听他说话. 就知道完蛋了. 这人肯定很难聊. 冷面虎. 口音很重.
说..我给你出道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;

        void start() {...}. 1point 3acres 璁哄潧
        send(ID, ...);
        onMsg(ID, ...) {...}
        void done(int max) -> call this method when network max is known.
        ...
}

... 代表的是我要写的. 你可以给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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
Patpat 群主,我最后一轮也被一个口音很重的厄瓜多尔人给坑了。。。
回复 支持 反对

使用道具 举报

 楼主| leixiang5 发表于 2016-11-11 15:14:58 | 显示全部楼层
关注一亩三分地微博:
Warald
samuelling 发表于 2016-11-11 15:07. Waral 鍗氬鏈夋洿澶氭枃绔,
Patpat 群主,我最后一轮也被一个口音很重的厄瓜多尔人给坑了。。。

-.- 也不能说被他坑了吧...感觉就算他写个no hire...其他人写hire...怎么样也会过的...说明其他人的feedback写的也不咋的..
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (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吗?

自己试着写一下吧~。stack 并不能给你output
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| leixiang5 发表于 2016-11-18 12:05:13 | 显示全部楼层
EmilyMMMM 发表于 2016-11-17 16:11
群主666,NYC office是狗家最难面的一个了…………
. more info on 1point3acres.com
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]. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
stack 里面可以记录in及其打印顺序和in的时间, .1point3acres缃
顺序一开始从低到高是 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}>
遇到main_out <1, {main, start, end, stack_size=0}>. visit 1point3acres.com for more.

然后按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自己的数值。
. visit 1point3acres.com for more.
这样的话 每个节点最多只会给邻居发送一次不同的值, 发送总量应该是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.1point3acres缃
最后那题,因为每个节点只有固定的邻居,对于每个节点,要知道全网最大值,必须通过邻居节点收集其他所有节 ...

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做啊

bully 只是选leader - -..跟这个无关...
回复 支持 反对

使用道具 举报

头像被屏蔽
lll_2013 发表于 2016-11-21 15:15:00 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

 楼主| leixiang5 发表于 2016-11-21 15:16:53 | 显示全部楼层
lll_2013 发表于 2016-11-21 15:15
最后一题选择任意一个node,用bfs,然后访问过的记录一下,最后返回的是bfs过的node & 对应的val
.1point3acres缃
- -这是distributed algo...
原理上来说...直接bfs or dfs找最大值就对了...但是因为在不同的machine上...implement会困难许多..。
回复 支持 反对

使用道具 举报

头像被屏蔽
lll_2013 发表于 2016-11-21 19:36:55 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

 楼主| 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。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

最后一题有点意思,但是感觉LZ是真的被坑了,这哪是一个小时能白板能做出来的问题嘛... 而且这个问题有解应该还需要一个条件,就是所有node都要在同一个transitive closure里。我的大概思路就是,任选一个node做为启始点,向他所有neighbor发自己的value。每个node,当第一次接收到一条message的时候,把message的来源记为自己的parent,并向自己所有除了消息来源外的neighbor broadcast自己的值。以后每次收到message的时候,都更新下自己的最大值记录,并把来源记到另一个returned set里,当returned set和neighbor set一样大的时候,说明这个node已经收集到自己和子树里的最大值了,把这个最大值发回给自己记录的parent就可以。当一开始选中的那个node得到所有neighbor的回复时,输出全网最大值。

  1. import threading. more info on 1point3acres.com

  2. import time

  3. import Queue


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


  5. class Node(threading.Thread):

  6.     def __init__(self, ID, val):. more info on 1point3acres.com

  7.         self.ID = ID

  8.         self.val = val. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  9.         self.max_val = val

  10.         self.neighbors = {}

  11.         self.returned = set().鐣欏璁哄潧-涓浜-涓夊垎鍦
  12. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  13.         self.parent = None-google 1point3acres

  14.         self.isInitiator = False

  15.         self.msgQ = Queue.Queue(). from: 1point3acres.com/bbs

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


  17. .1point3acres缃
  18. . 1point3acres.com/bbs
  19. . more info on 1point3acres.com

  20.     def addNeighbor(self, node):

  21.         self.neighbors[node.ID] = node

  22. . 1point3acres.com/bbs


  23.     def run(self):

  24.         if self.isInitiator:

  25.             if self.neighbors:

  26.                 for node in self.neighbors.iterkeys():
  27. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  28.                     self.send(node). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴


  29.         while len(self.neighbors) != len(self.returned):.鐣欏璁哄潧-涓浜-涓夊垎鍦

  30.             #handle messages

  31.             if self.msgQ:

  32.                 src, val = self.msgQ.get()

  33.                 self.onMsg(src, val)

  34.             time.sleep(0.01)



  35.         if self.isInitiator:

  36.             self.done().鐣欏璁哄潧-涓浜-涓夊垎鍦

  37.         else:

  38.             self.send(self.parent) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.




  39.     def send(self, ID):


  40.         self.neighbors[ID].msgQ.put((self.ID, self.max_val))
  41. . from: 1point3acres.com/bbs




  42.     def onMsg(self, ID, val):
    . 1point3acres.com/bbs


  43. . 鍥磋鎴戜滑@1point 3 acres
  44.         if self.parent is None and not self.isInitiator:

  45.             self.parent = ID

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

  47.                 if n == ID:
  48. . from: 1point3acres.com/bbs
  49.                     continue
  50. . From 1point 3acres bbs
  51.                 self.send(n).鏈枃鍘熷垱鑷1point3acres璁哄潧
  52. . From 1point 3acres bbs
  53.         self.returned.add(ID)

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

  55. . more info on 1point3acres.com

  56.     def done(self):

  57.         print self.max_val
  58. .鐣欏璁哄潧-涓浜-涓夊垎鍦



  59. if __name__ == "__main__":

  60.     node_vals = [ 4, 2, 5, 6, 3, 3, 6, 1, 12 ]
  61. . From 1point 3acres bbs
  62.     node_neighbors = [

  63.         [1, 2, 3, 4],. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  64. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  65.         [0, 2, 5, 6, 7],

  66.         [0, 1],

  67.         [0],

  68.         [0, 7],
  69. . From 1point 3acres bbs
  70.         [1],

  71.         [1],

  72.         [1, 4, 8],

  73.         [7]

  74.     ]


  75. -google 1point3acres
  76.     for starter in range(len(node_vals)):

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

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

  79.         for idx, nbs in enumerate(node_neighbors):. from: 1point3acres.com/bbs
  80. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  81.             if idx == starter:

  82.                 Nodes[idx].isInitiator = True
  83. . more info on 1point3acres.com
  84.             for n in nbs:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  85. . 1point3acres.com/bbs
  86.                 Nodes[idx].addNeighbor(Nodes[n]). Waral 鍗氬鏈夋洿澶氭枃绔,


  87.         for n in Nodes:

  88.             n.start().鏈枃鍘熷垱鑷1point3acres璁哄潧
  89. . visit 1point3acres.com for more.

  90.         for n in Nodes:

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-2-25 23:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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