San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 3942|回复: 18
收起左侧

April 9 2014 Google onsite

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

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

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

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

x
Google onsite.

. visit 1point3acres for more.
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, 如何无人值守给他升级内核。如何判断机器挂掉了,挂掉了怎么办。
. From 1point 3acres bbs
四轮:
Golden file 什么的。测试不太懂。完全不知道说的是什么。
给一个text file, 里面是按行分割的各种单词,让找到频率第k大的那个单词。尽可能的优化。
. visit 1point3acres for more.
本人代码全都用Python写的。Google很好,给我分配的面试官都是写Python的。

求过,攒人品。



评分

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):
  3.         self.val = val
  4.         self.left = None
  5.         self.right = None


  6. class Solution(object):

  7. . more info on 1point3acres
  8.     def __init__(self):
  9.         self._idx = 0
  10.         pass. more info on 1point3acres

  11.     def find_kth(self, root, k):
  12.         self._idx = 0
  13.         res = self._inorder(root, k). 1point 3acres 论坛
  14.         return res

  15.     def _inorder(self, node, k):
  16.         if not node:
  17.             return
  18.         left = self._inorder(node.left, k)
  19.         self._idx += 1
  20.         if self._idx == k:
  21.             return node. visit 1point3acres for more.
  22.         if left:
  23.             return left
  24.         right = self._inorder(node.right, k)
  25.         if right:
  26.             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.     def __init__(self, j, k, slist):
  3.         self._j = j
  4.         self._k = k. Waral 博客有更多文章,
  5.         self._slist = slist
  6.         self._n = len(slist)

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


  3. class Test(unittest.TestCase):

  4.     def test1(self):
  5.         slist = [1, 1]. 围观我们@1point 3 acres
  6.         f = Fibonacci(1, 2, slist). Waral 博客有更多文章,
  7.         res1 = f.next(). 牛人云集,一亩三分地
  8.         res2 = f.next()-google 1point3acres
  9.         res3 = f.next()
  10.         res4 = f.next()
  11.         # print res1, res2, res3, res4
  12.         self.assertEqual(2, res1). from: 1point3acres
  13.         self.assertEqual(3, res2)
  14.         self.assertEqual(5, res3).本文原创自1point3acres论坛
  15.         self.assertEqual(8, res4). from: 1point3acres

  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(). 1point3acres
  21.         res3 = f.next()
  22.         res4 = f.next()
  23.         # print res1, res2, res3, res4
  24.         self.assertEqual(5, res1)
    . visit 1point3acres for more.
  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 | 显示全部楼层
楼主亲自作答。


三轮。
题目一:社交网络中,如何实现好友推荐。抽象成图,然后找出共同好友最多的那个人。
  1. class Node(object):. Waral 博客有更多文章,
  2. -google 1point3acres
  3.     def __init__(self, val):
  4.         self.val = val
  5.         self.friends = []
  6. . 一亩-三分-地,独家发布

  7. def recommend(node):
  8.     exclude = node.friends + [node]
  9.     freq = {}
  10.     for item in node.friends:
  11.         for sub_item in item.friends:
  12.             if sub_item not in exclude:
  13.                 freq[sub_item] = freq.get(sub_item, 0) + 1.本文原创自1point3acres论坛
  14.     max_val = 0-google 1point3acres
  15.     res = None
  16.     for key in freq:
  17.         val = freq[key]. 围观我们@1point 3 acres
  18.         if val > max_val:
  19.             max_val = val
  20.             res = key
  21.     return res
复制代码
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-4-14 02:20:31 | 显示全部楼层
楼主亲自作答。
. 1point3acres
四轮:
给一个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].1point3acres网
  12.             if val > max_val:
  13.                 max_val = val. from: 1point3acres
  14.                 max_key = key
  15.         res = max_key
  16.         del mydict[max_key]
  17.         i += 1
  18.     return res

  19.     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):. 1point 3acres 论坛
  6.         lenA = len(self.val)
  7.         lenB = len(B.val)
  8.         carry = 0
  9.         i = 0. 1point3acres
  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]
  15.             if i < lenB:-google 1point3acres
  16.                 tmp += B.val[i]

  17.             if tmp >= BigInt.max_val:.留学论坛-一亩-三分地
  18.                 carry = 1
  19.                 tmp = tmp - BigInt.max_val. From 1point 3acres bbs
  20.             else:
  21.                 carry = 0
  22.             res.val.append(tmp). 留学申请论坛-一亩三分地
  23.             i += 1
  24.         return res
  25. . From 1point 3acres bbs
复制代码
回复 支持 反对

使用道具 举报

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

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

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


  5. def recommend(node):
  6.     exclude = node.friends + [node]. from: 1point3acres
  7.     freq = {}
  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. From 1point 3acres 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确实好写, 不过楼主都是最简单的办法啊, 看不到啥时间和空间的优化..

面试官也就问一下时间复杂度是多少。没有要求继续优化。
. 1point3acres
四轮:
给一个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主要用什么语言?
-google 1point3acres
基本上不要求语言把。我是比较熟悉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
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-26 20:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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