一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 2260|回复: 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.

一轮。 给定一个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的。

求过,攒人品。


.鏈枃鍘熷垱鑷1point3acres璁哄潧

评分

2

查看全部评分

本帖被以下淘专辑推荐:

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

谢谢!
回复 支持 反对

使用道具 举报

eusoff 发表于 2014-4-10 16:02:39 | 显示全部楼层
话说FLAG主要用什么语言?
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-13 12:36:25 | 显示全部楼层
楼主亲自作答。
. more info on 1point3acres.com
一轮。 给定一个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

  6. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  7. class Solution(object):

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

  11.     def find_kth(self, root, k):.鏈枃鍘熷垱鑷1point3acres璁哄潧
  12.         self._idx = 0
  13.         res = self._inorder(root, k)
  14.         return res
  15. -google 1point3acres
  16.     def _inorder(self, node, k):
  17.         if not node:
  18.             return
  19.         left = self._inorder(node.left, k)
  20.         self._idx += 1
  21.         if self._idx == k:
  22.             return node
  23.         if left:
  24.             return left
  25.         right = self._inorder(node.right, k)
  26.         if right:
  27.             return right
复制代码
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-13 22:30:10 | 显示全部楼层
楼主亲自作答。

二轮。
题目一:扩展的斐波那契数列。Sn = Sn-j + Sn-k (0<j<k). 写一个generator类。有实现next()方法。
  1. class Fibonacci(object):
  2. . 1point 3acres 璁哄潧
  3.     def __init__(self, j, k, slist):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  4.         self._j = j
  5.         self._k = k
  6.         self._slist = slist
  7.         self._n = len(slist)

  8.     def next(self):
  9.         res = self._slist[self._n - self._j] +\
    . from: 1point3acres.com/bbs
  10.             self._slist[self._n - self._k]
  11.         self._slist.append(res)
  12.         self._n += 1
  13.         return res
复制代码
  1. from solution import Fibonacci.1point3acres缃
  2. import unittest


  3. . 鍥磋鎴戜滑@1point 3 acres
  4. class Test(unittest.TestCase):

  5.     def test1(self):
  6.         slist = [1, 1].鐣欏璁哄潧-涓浜-涓夊垎鍦
  7.         f = Fibonacci(1, 2, slist)
  8.         res1 = f.next()
  9.         res2 = f.next()
  10.         res3 = f.next()
  11.         res4 = f.next()
  12.         # print res1, res2, res3, res4
  13.         self.assertEqual(2, res1)
  14.         self.assertEqual(3, res2). more info on 1point3acres.com
  15.         self.assertEqual(5, res3)
  16.         self.assertEqual(8, res4)

  17.     def test2(self):
  18.         slist = [1, 2, 3, 4, 5]
  19.         f = Fibonacci(2, 5, slist) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  20.         res1 = f.next()
  21.         res2 = f.next()
  22.         res3 = f.next(). 1point3acres.com/bbs
  23.         res4 = f.next()
  24.         # print res1, res2, res3, res4
  25.         self.assertEqual(5, res1)
  26.         self.assertEqual(7, res2)
  27.         self.assertEqual(8, res3)
  28.         self.assertEqual(11, res4)

  29. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  30. if __name__ == '__main__':. 1point3acres.com/bbs
  31.     unittest.main(verbosity=2). visit 1point3acres.com for more.
复制代码
回复 支持 反对

使用道具 举报

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


三轮。
题目一:社交网络中,如何实现好友推荐。抽象成图,然后找出共同好友最多的那个人。
  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:. 1point3acres.com/bbs
  9.         for sub_item in item.friends:
  10.             if sub_item not in exclude:
  11.                 freq[sub_item] = freq.get(sub_item, 0) + 1-google 1point3acres
  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. 1point 3acres 璁哄潧
  19.     return res. 鍥磋鎴戜滑@1point 3 acres
复制代码
回复 支持 反对

使用道具 举报

 楼主| 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:
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  5.             mydict[line] = mydict.get(line, 0) + 1-google 1point3acres
  6. . Waral 鍗氬鏈夋洿澶氭枃绔,
  7.     i = 0
  8.     while i < k:
  9.         max_key = None
  10.         max_val = 0
  11.         for key in mydict:
  12.             val = mydict[key]
  13.             if val > max_val:
  14.                 max_val = val
  15.                 max_key = key
  16.         res = max_key
  17.         del mydict[max_key]
  18.         i += 1
  19.     return res

  20.     print mydict. From 1point 3acres bbs
复制代码
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-14 02:22:04 | 显示全部楼层
楼主亲自作答
. from: 1point3acres.com/bbs
三轮:
题目二:BigInt 相加。 如何表示一个BigInt, 用一个数组。跟leetcode一样
  1. class BigInt(object):
  2.     max_val = 10000

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

  5.     def add(self, B):
  6.         lenA = len(self.val)
  7.         lenB = len(B.val)
  8.         carry = 0
  9.         i = 0
  10.         res = BigInt()
  11.         while i < lenA or i < lenB or carry != 0:
  12.             tmp = carry
  13.             if i < lenA:
  14.                 tmp += self.val[i]. 1point3acres.com/bbs
  15.             if i < lenB:
  16.                 tmp += B.val[i]
  17. -google 1point3acres
  18.             if tmp >= BigInt.max_val:
  19.                 carry = 1
  20.                 tmp = tmp - BigInt.max_val
  21.             else:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  22.                 carry = 0
  23.             res.val.append(tmp)
  24.             i += 1
  25.         return res
  26. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
复制代码
回复 支持 反对

使用道具 举报

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

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷三轮。
题目一:社交网络中,如何实现好友推荐。抽象成图,然后找出共同好友最多的那个人。
  1. class Node(object):

  2.     def __init__(self, val):. from: 1point3acres.com/bbs
  3.         self.val = val
  4.         self.friends = []


  5. def recommend(node):
  6.     exclude = node.friends + [node]. from: 1point3acres.com/bbs
  7.     freq = {}
  8.     for item in node.friends:. From 1point 3acres bbs
  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:
    . from: 1point3acres.com/bbs
  17.             max_val = val. 1point3acres.com/bbs
  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-1-17 03:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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