一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2600|回复: 18
收起左侧

April 9 2014 Google onsite

[复制链接] |试试Instant~ |关注本帖
johnnywsd 发表于 2014-4-10 15:09:27 | 显示全部楼层 |阅读模式

2014(1-3月) 码农类 硕士 全职@Google - 网上海投 - Onsite |Other

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

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

x
Google onsite.

4 轮面试,3轮Software Engineer 一轮 Software Engineer in Test.
. from: 1point3acres.com/bbs
一轮。 给定一个binary search tree, 知道到第k大的数。

二轮。
题目一:扩展的斐波那契数列。Sn = Sn-j + Sn-k (0<j<k). 写一个generator类。有实现next()方法。
题目二:生产者消费者问题。

三轮。
题目一:社交网络中,如何实现好友推荐。抽象成图,然后找出共同好友最多的那个人。
题目二:BigInt 相加。 如何表示一个BigInt, 用一个数组。跟leetcode一样
题目三:假设google在火星上弄了个data center, 如何无人值守给他升级内核。如何判断机器挂掉了,挂掉了怎么办。

四轮:
Golden file 什么的。测试不太懂。完全不知道说的是什么。
给一个text file, 里面是按行分割的各种单词,让找到频率第k大的那个单词。尽可能的优化。

本人代码全都用Python写的。Google很好,给我分配的面试官都是写Python的。

求过,攒人品。



评分

2

查看全部评分

本帖被以下淘专辑推荐:

babyblue_jiang 发表于 2014-4-10 15:53:06 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
第三轮第一题,什么叫共同好友最多的“那个人”?意思是说共同好友最多的“两个人”吗?这题是就直接遍历所有用户,复杂度O(EV)吗?
还有第三题怎么回答?

谢谢!
回复 支持 反对

使用道具 举报

eusoff 发表于 2014-4-10 16:02:39 | 显示全部楼层
关注一亩三分地微博:
Warald
话说FLAG主要用什么语言?
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2014-4-11 00:11:17 | 显示全部楼层
Did you use yield() in round 2?
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-13 12:36:25 | 显示全部楼层
楼主亲自作答。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

一轮。 给定一个binary search tree, 知道到第k大的数。
  1. class TreeNode(object):

  2.     def __init__(self, val):
  3.         self.val = val
  4.         self.left = None
  5.         self.right = None. Waral 鍗氬鏈夋洿澶氭枃绔,


  6. class Solution(object):

  7.     def __init__(self):
  8.         self._idx = 0
  9.         pass.1point3acres缃

  10.     def find_kth(self, root, k):
  11.         self._idx = 0
  12.         res = self._inorder(root, k). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  13.         return res. Waral 鍗氬鏈夋洿澶氭枃绔,

  14.     def _inorder(self, node, k):. 1point 3acres 璁哄潧
  15.         if not node:.1point3acres缃
  16.             return
  17.         left = self._inorder(node.left, k)
  18.         self._idx += 1
  19.         if self._idx == k:
  20.             return node. From 1point 3acres bbs
  21.         if left:
  22.             return left
  23.         right = self._inorder(node.right, k)
  24.         if right:
  25.             return right
复制代码
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

readman 发表于 2014-4-13 13:19:33 | 显示全部楼层
题目三:假设google在火星上弄了个data center, 如何无人值守给他升级内核。如何判断机器挂掉了,挂掉了怎么办。

求答案...
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-13 22:30:10 | 显示全部楼层
楼主亲自作答。
. 1point 3acres 璁哄潧
二轮。
题目一:扩展的斐波那契数列。Sn = Sn-j + Sn-k (0<j<k). 写一个generator类。有实现next()方法。
  1. class Fibonacci(object):

  2.     def __init__(self, j, k, slist):
  3.         self._j = j
  4.         self._k = k. visit 1point3acres.com for more.
  5.         self._slist = slist
  6.         self._n = len(slist)
  7. . visit 1point3acres.com for more.
  8.     def next(self):
  9.         res = self._slist[self._n - self._j] +\
  10.             self._slist[self._n - self._k].1point3acres缃
  11.         self._slist.append(res)
  12.         self._n += 1
  13.         return res
复制代码
  1. from solution import Fibonacci
  2. import unittest


  3. class Test(unittest.TestCase):

  4.     def test1(self):
  5.         slist = [1, 1]
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  6.         f = Fibonacci(1, 2, slist)
  7.         res1 = f.next()
  8.         res2 = f.next()
  9.         res3 = f.next()
  10.         res4 = f.next()
  11.         # print res1, res2, res3, res4
  12.         self.assertEqual(2, res1)
  13.         self.assertEqual(3, res2)
  14.         self.assertEqual(5, res3)
  15.         self.assertEqual(8, res4)

  16.     def test2(self):
  17.         slist = [1, 2, 3, 4, 5]
  18.         f = Fibonacci(2, 5, slist)
  19.         res1 = f.next()
  20.         res2 = f.next()
  21.         res3 = f.next()
  22.         res4 = f.next()
  23.         # print res1, res2, res3, res4
  24.         self.assertEqual(5, res1)
  25.         self.assertEqual(7, res2)
  26.         self.assertEqual(8, res3)
  27.         self.assertEqual(11, res4). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  28. if __name__ == '__main__':
  29.     unittest.main(verbosity=2)
复制代码
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-13 23:42:31 | 显示全部楼层
楼主亲自作答。

. Waral 鍗氬鏈夋洿澶氭枃绔,
三轮。
题目一:社交网络中,如何实现好友推荐。抽象成图,然后找出共同好友最多的那个人。
  1. class Node(object):

  2.     def __init__(self, val):
  3.         self.val = val
  4.         self.friends = []


  5. def recommend(node):
  6.     exclude = node.friends + [node]
  7.     freq = {}
  8.     for item in node.friends:
  9.         for sub_item in item.friends:
  10.             if sub_item not in exclude:. 1point 3acres 璁哄潧
  11.                 freq[sub_item] = freq.get(sub_item, 0) + 1
  12.     max_val = 0
  13.     res = None
  14.     for key in freq:. 鍥磋鎴戜滑@1point 3 acres
  15.         val = freq[key]
  16.         if val > max_val:
  17.             max_val = val. 鍥磋鎴戜滑@1point 3 acres
  18.             res = key
  19.     return res
复制代码
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-14 02:20:31 | 显示全部楼层
楼主亲自作答。

四轮:
给一个text file, 里面是按行分割的各种单词,让找到频率第k大的那个单词。尽可能的优化。
  1. def get_kth_freq(input_file_path, k):
  2.     mydict = {}
  3.     with open(input_file_path) as input_file:
  4.         for line in input_file:
  5.             mydict[line] = mydict.get(line, 0) + 1

  6.     i = 0
  7.     while i < k:
  8.         max_key = None
  9.         max_val = 0
  10.         for key in mydict:
  11.             val = mydict[key]
  12.             if val > max_val:
  13.                 max_val = val
  14.                 max_key = key 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15.         res = max_key
  16.         del mydict[max_key]. more info on 1point3acres.com
  17.         i += 1
  18.     return res
  19. . 1point 3acres 璁哄潧
  20.     print mydict.1point3acres缃
复制代码
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-14 02:22:04 | 显示全部楼层
楼主亲自作答

三轮:. visit 1point3acres.com for more.
题目二:BigInt 相加。 如何表示一个BigInt, 用一个数组。跟leetcode一样
  1. class BigInt(object):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  2.     max_val = 10000
  3. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  4.     def __init__(self):
  5.         self.val = []. more info on 1point3acres.com
  6. .1point3acres缃
  7.     def add(self, B):
  8.         lenA = len(self.val)
  9.         lenB = len(B.val)
  10.         carry = 0
  11.         i = 0
  12.         res = BigInt()
  13.         while i < lenA or i < lenB or carry != 0:
  14.             tmp = carry
  15.             if i < lenA:. from: 1point3acres.com/bbs
  16.                 tmp += self.val[i]
  17.             if i < lenB:
  18.                 tmp += B.val[i]

  19.             if tmp >= BigInt.max_val:
  20.                 carry = 1. 1point 3acres 璁哄潧
  21.                 tmp = tmp - BigInt.max_val
  22.             else:
  23.                 carry = 0
  24.             res.val.append(tmp). Waral 鍗氬鏈夋洿澶氭枃绔,
  25.             i += 1-google 1point3acres
  26.         return res

复制代码
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-14 02:23:53 | 显示全部楼层
楼主亲自作答

三轮。-google 1point3acres
题目一:社交网络中,如何实现好友推荐。抽象成图,然后找出共同好友最多的那个人。
  1. class Node(object):

  2.     def __init__(self, val):
  3.         self.val = val. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  4.         self.friends = []


  5. def recommend(node):
  6.     exclude = node.friends + [node]. visit 1point3acres.com for more.
  7.     freq = {}. Waral 鍗氬鏈夋洿澶氭枃绔,
  8.     for item in node.friends:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  9.         for sub_item in item.friends:
  10.             if sub_item not in exclude:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  11.                 freq[sub_item] = freq.get(sub_item, 0) + 1
  12.     max_val = 0
  13.     res = None
  14.     for key in freq:
  15.         val = freq[key]
  16.         if val > max_val:
  17.             max_val = val
  18.             res = key
  19.     return res
复制代码
回复 支持 反对

使用道具 举报

jackiey99 发表于 2014-4-14 06:47:53 | 显示全部楼层
赞,楼主好人,有题有code
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-4-14 07:01:22 | 显示全部楼层
python确实好写, 不过楼主都是最简单的办法啊, 看不到啥时间和空间的优化..
回复 支持 反对

使用道具 举报

doveonthewing 发表于 2014-4-14 09:31:09 | 显示全部楼层
祝楼主好运!!!!
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-14 11:04:46 | 显示全部楼层
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-14 11:11:26 | 显示全部楼层
北美农民 发表于 2014-4-14 07:01 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
python确实好写, 不过楼主都是最简单的办法啊, 看不到啥时间和空间的优化..
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
面试官也就问一下时间复杂度是多少。没有要求继续优化。

四轮:
给一个text file, 里面是按行分割的各种单词,让找到频率第k大的那个单词。尽可能的优化。

可以优化,我写的复制度是 O(kn),面试官要求优化,我就是用了heap,但是复杂度变成了O(nlogn),不一定比原来好。

回来重新思考了一下,感觉应该可以使用quick select来选出频率第k高的。这样时间复杂度就可以到O(n)了。

又什么更好的方法,留言交流下呀。
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-14 11:19:01 | 显示全部楼层
eusoff 发表于 2014-4-10 16:02
话说FLAG主要用什么语言?

基本上不要求语言把。我是比较熟悉Python和Java。首选Python,如果它要求我用Java,那也是没有问题的。
Amazon 的online assessment 强制使用Java或者C++。其他的公司基本不限制语言把。Python简单,写的块,能够更容易的表现自己的思路,跟写伪代码似的。
回复 支持 反对

使用道具 举报

eusoff 发表于 2014-4-14 11:27:19 | 显示全部楼层
johnnywsd 发表于 2014-4-14 11:19
基本上不要求语言把。我是比较熟悉Python和Java。首选Python,如果它要求我用Java,那也是没有问题的。
...

好,谢谢回复。这样的话我还是focus在java上吧,我有c++ java的基础。。。
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-11-25 05:17:40 | 显示全部楼层
lz就是个jb
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-29 11:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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