一亩三分地论坛

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

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

求过,攒人品。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. more info on 1point3acres.com

评分

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 | 显示全部楼层
楼主亲自作答。

一轮。 给定一个binary search tree, 知道到第k大的数。
  1. class TreeNode(object):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  2.     def __init__(self, val):.鏈枃鍘熷垱鑷1point3acres璁哄潧
  3.         self.val = val
  4.         self.left = None
  5.         self.right = None


  6. class Solution(object):
  7. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  8.     def __init__(self):
  9.         self._idx = 0. 1point 3acres 璁哄潧
  10.         pass

  11.     def find_kth(self, root, k):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  12.         self._idx = 0
  13.         res = self._inorder(root, k)
  14.         return res

  15.     def _inorder(self, node, k):
  16.         if not node:
  17.             return
  18.         left = self._inorder(node.left, k). more info on 1point3acres.com
  19.         self._idx += 1
  20.         if self._idx == k: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  21.             return node
  22.         if left:
  23.             return left
  24.         right = self._inorder(node.right, k)
  25.         if right:. From 1point 3acres bbs
  26.             return right
复制代码
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

二轮。. visit 1point3acres.com for more.
题目一:扩展的斐波那契数列。Sn = Sn-j + Sn-k (0<j<k). 写一个generator类。有实现next()方法。
  1. class Fibonacci(object):
  2. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  3.     def __init__(self, j, k, slist):.鐣欏璁哄潧-涓浜-涓夊垎鍦
  4.         self._j = j.1point3acres缃
  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] +\
  10.             self._slist[self._n - self._k]
  11.         self._slist.append(res)
  12.         self._n += 1
  13.         return res. from: 1point3acres.com/bbs
复制代码
  1. from solution import Fibonacci
  2. import unittest

  3. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  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)
  15.         self.assertEqual(5, res3). 1point3acres.com/bbs
  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()
  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. if __name__ == '__main__':. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  30.     unittest.main(verbosity=2)
复制代码
回复 支持 反对

使用道具 举报

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

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

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

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

使用道具 举报

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

四轮:
给一个text file, 里面是按行分割的各种单词,让找到频率第k大的那个单词。尽可能的优化。
  1. def get_kth_freq(input_file_path, k):
  2.     mydict = {}. Waral 鍗氬鏈夋洿澶氭枃绔,
  3.     with open(input_file_path) as input_file:
  4.         for line in input_file:. From 1point 3acres bbs
  5.             mydict[line] = mydict.get(line, 0) + 1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6. . more info on 1point3acres.com
  7.     i = 0. 1point 3acres 璁哄潧
  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]. 鍥磋鎴戜滑@1point 3 acres
  18.         i += 1
  19.     return res

  20.     print mydict
复制代码
回复 支持 反对

使用道具 举报

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

三轮:
题目二: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. from: 1point3acres.com/bbs
  10.         res = BigInt(). from: 1point3acres.com/bbs
  11.         while i < lenA or i < lenB or carry != 0:
  12.             tmp = carry
  13.             if i < lenA:
  14.                 tmp += self.val[i]
  15.             if i < lenB:
  16.                 tmp += B.val[i]

  17.             if tmp >= BigInt.max_val:
  18.                 carry = 1
  19.                 tmp = tmp - BigInt.max_val
  20.             else:
  21.                 carry = 0
  22.             res.val.append(tmp). visit 1point3acres.com for more.
  23.             i += 1.1point3acres缃
  24.         return res

复制代码
回复 支持 反对

使用道具 举报

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

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

  2.     def __init__(self, val):
  3.         self.val = val
  4.         self.friends = []
  5. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  6. def recommend(node):
  7.     exclude = node.friends + [node]. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  8.     freq = {}
  9.     for item in node.friends:
  10.         for sub_item in item.friends:
  11.             if sub_item not in exclude:
  12.                 freq[sub_item] = freq.get(sub_item, 0) + 1
  13.     max_val = 0
  14.     res = None
  15.     for key in freq:
  16.         val = freq[key]
  17.         if val > max_val:. 鍥磋鎴戜滑@1point 3 acres
  18.             max_val = val
  19.             res = key
  20.     return res. 1point3acres.com/bbs
复制代码
回复 支持 反对

使用道具 举报

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, 2016-12-9 03:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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