一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 2002|回复: 48
收起左侧

狗家10/13 onsite面经

[复制链接] |试试Instant~ |关注本帖
qbt4juik 发表于 2015-10-30 11:56:02 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 猎头 - 技术电面 Onsite |Passfresh grad应届毕业生

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

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

x
今天下午得知了HC的green light。发个面经回报大家~
面试的时候题刷的也不够,如果不是看地里的面经,肯定跪惨了。。. From 1point 3acres bbs
. visit 1point3acres.com for more.
第一轮,白人小哥,自我介绍了一下,直接出题。给字符串,
要求写一个方法,将字符串中字符重新排序,要求相邻字符不能相同。比如'aab'输出'aba'。我想的解法是用个dictionary存每个字符出现的频次,比如这个情况就是{'a' : 2, 'b' : 1},同时记录出现次数最多的字符。然后按照0,2,4,6,8,...,1,3,5,7,9,...这样的顺序摆放字符。先放出现次数最多的,剩下字符按照出现频次放就可以了。需要考虑input不合法的情况。follow up:如果相同字符必须相隔k个怎么办。如果k=1就是之前的题设。k=2的话就按照0,3,6,9,...,1,4,7,...,2,5,8,...这种顺序摆就可以了。简单问了下复杂度。
第二轮,白人哥哥(有比较重的东欧/俄国口音),直接做题。设计一个数据结构,实现get, set, delete, get_random四个方法。我先说这个很明显用hash table可以做。他叫我写一下get_random。写完了,他说你能不能证明。我以为他叫我证明复杂度,后来折腾了半天他原来意思是能不能证明这是最优的→_→。。。然后我说显然不是啊,我给他提了下用二叉搜索树的想法。他说可以,然后还是只叫我写get_random,写完了他说你这个用了几次random number generator,我说O(log(n))。他说不够好能不能只生成一次随机数。然后改了一下。之后说能不能更快,我说用array存,他问了我dynamically allocated array的amortized worst case time complexity。这一问有点卡有点忘了,还好在他提示下证明了O(1)。然后他说提示就是用array,然后我想出来了用array+dictionary可以实现四个方法都是O(1)的(用dictionary存key在array中的位置,然后去array中查找node,delete的时候,把array中最后一项搬到被删的位置)。说了想法,他说可以,不用写码了。后来聊了聊开开开心心的结束了。
-google 1point3acres
第三轮,白人大哥,在谷歌做了11年了。。。先问challenging project,然后出题:remove duplicate。比如[1,3,3]输出[1,3],[5,5,6,5,4] 输出 [5,6,4]。lc上有原题不多说了。第二题给个网页,链接用矩形表示,(x1,y1),(x2,y2)表示左上/右下顶点的坐标。给这样很多链接,写一个方法,给一个点击的位置,返回距离最近的链接。他说我们这个题主要讨论,不用写码。我说最直接的用brute force,针对每个链接算下它和点击位置的距离。他说好,距离公式怎么写。给他说了个分类讨论的方法,分9种情况,他说能不能简化,提示可以先单独算xdist和ydist。然后写了两行码。就结束了。。。xdist = max(0, x1-x, x-x2), ydist = max(0, y1-y, y-y2), dist = (x**2 + y**2) ** 0.5。然后他问如果点击量很大,怎么优化。我说可以把网页分成很小的格子,对每个格子存一个距离最近的链接。之后每次有点击的时候,直接看他在哪个格子里。他说好,如果那些rectangle都堆在一起呢,想了想我说可以对每一对矩形画一组boundary,一个horizontal boundary,一个vertical boundary。N个链接可以组成N^2 * N^2的格子。这样算出来对每个格子返回的链接是精确的。他说好像可以。然后聊了聊就走了

第四轮,白人大叔,看起来也是老资历。。。自我介绍都没有直接出题。给个有向图判断是否是树【graph valid tree】。lc带锁的题,不说了。没有follow up,做完题聊天走人。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
其实我觉得能碰到这么水的面试真的是rp爆发。。。再次感谢地里对我面试的帮助。

P.S. 现在HR叫我选SWE还是SRE。不知道地里有没有人对这个比较熟悉的求指导! 还有team match有没有什么其他建议!多谢!
.1point3acres缃

.1point3acres缃补充内容 (2015-10-30 12:15):
语言用的是python。。不造是不是因为选python的原因所以没问我什么thread之类的问题。。

评分

2

查看全部评分

 楼主| qbt4juik 发表于 2015-10-31 03:57:47 | 显示全部楼层
will_ym 发表于 2015-10-30 23:11. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
楼主 所有rectangle都堆在一起那个没看懂你的解法 能不能说的详细点啊 多谢多谢

他的意思其实就是我把页面划成小网格的方法只是近似估计,在某些特定条件下误差会比较大。所以我就说对每一对矩形画一组边界
. 1point 3acres 璁哄潧
比如rect1 = [(1,1), (3,4)], rect2 = [(2,6), (6,7)]
在这里假定rect1中心位于rect2的左/上象限,否则把下面的rect1和rect2互换就行

垂直边界:rect1右边界和rect2左边界的平均,即:x = (3+2)/2 = 2.5
水平边界:rect1下边界和rect2上边界的平均,即:y = (4+6)/2 = 5

在垂直边界以左 -> 离rect1近
在水平边界以上 -> 离rect1近

这样对每一组rect划线之后,整个页面会被分为 N^2 * N^2 的网格,每一个网格内部所有点对应的最近矩形是唯一的

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| qbt4juik 发表于 2015-10-31 03:11:38 | 显示全部楼层
djjkobe 发表于 2015-10-30 13:44
能否再详细说一下第三轮坐标那题是什么意思?

补充内容 (2015-10-30 13:48):

就是如果点击量很大,我的理解就是他觉得每次点击都要重新算一遍和所有矩阵的距离太费时间了。所以我的想法就是对平面上每个点都算一遍最近矩阵,然后存起来,这样下次有点击进来的时候就不用重新算。但这样可能太废memory,所以就把网页划成小格子,对每个格子算一个最近矩形。(不过是一种近似solution)
回复 支持 1 反对 0

使用道具 举报

 楼主| qbt4juik 发表于 2015-11-1 06:00:42 | 显示全部楼层
returning 发表于 2015-10-31 08:07
.鐣欏璁哄潧-涓浜-涓夊垎鍦(用dictionary存key在array中的位置,然后去array中查找node,delete的时候,把array中最后一项搬到被删的 ...
  1. def DataStructureYouAskedMeToDesign(object):. 1point3acres.com/bbs
  2.     def __init__(self):
  3.         self.nodes = list()
  4.         self.table = dict()
  5.         self.size = 0
  6.         
  7.     def get(self, key):
  8.         try:. From 1point 3acres bbs
  9.             return self.nodes[self.table[key]]
  10.         except KeyError:
  11.             raise
  12.         
  13.     def set(self, key, val):
  14.         # Override existing node with new val
  15.         if key in self.table:
  16.             self.nodes[self.table[key]].setval(value)
  17.         # Create a new node if key is not found
  18.         else:. visit 1point3acres.com for more.
  19.             self.size += 1
  20.             self.table[key] = size - 1
  21.             self.nodes.append(Node(key,val))

  22.     def delete(self, key):
  23.         try:
  24.             pos = self.table[key]
  25.         except KeyError:
  26.             raise
  27.         else:
  28.             # Move the last node to the deleted node
  29.             last_node = self.nodes.pop()
  30.             self.table[last_node.key] = pos-google 1point3acres
  31.             self.table[pos] = last_node
  32.             self.size -= 1. more info on 1point3acres.com

  33.     def get_random(self):
  34.         return self.nodes[int(self.size*uniform(0,1))]
复制代码

补充内容 (2015-11-1 06:05):
32行有个问题,前面应该加一个 if pos < self.size - 1:

补充内容 (2015-11-1 06:07):
还有最后要 del self.table[key]
回复 支持 1 反对 0

使用道具 举报

dukelv 发表于 2015-10-30 11:59:07 | 显示全部楼层
我觉得恩必,我们年轻人还是要学习一个
回复 支持 1 反对 0

使用道具 举报

qiuxuxing007 发表于 2015-10-30 12:09:52 | 显示全部楼层
第二题是设计一个hashmap的数据结构吧?Implement HashTable with get,set,delete,getRandom functions ?right?
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2015-10-30 12:10:30 | 显示全部楼层
第三轮能不能用hashmap来做啊?remove duplicate
回复 支持 反对

使用道具 举报

 楼主| qbt4juik 发表于 2015-10-30 12:10:35 | 显示全部楼层
qiuxuxing007 发表于 2015-10-30 12:09
第二题是设计一个hashmap的数据结构吧?Implement HashTable with get,set,delete,getRandom functions ?rig ...

对就是这意思
回复 支持 反对

使用道具 举报

 楼主| qbt4juik 发表于 2015-10-30 12:12:04 | 显示全部楼层
qiuxuxing007 发表于 2015-10-30 12:10
第三轮能不能用hashmap来做啊?remove duplicate

可以的 我用的就是two pointer一个在前面读 一个在后面写 然后用set存出现过的元素
回复 支持 反对

使用道具 举报

sxnfnj 发表于 2015-10-30 12:14:08 | 显示全部楼层
恭喜楼主!!!求问第一题“然后按照0,2,4,6,8,...,1,3,5,7,9,...这样的顺序摆放字符”是什么意思?
回复 支持 反对

使用道具 举报

 楼主| qbt4juik 发表于 2015-10-30 12:19:25 | 显示全部楼层
sxnfnj 发表于 2015-10-30 12:14
恭喜楼主!!!求问第一题“然后按照0,2,4,6,8,...,1,3,5,7,9,...这样的顺序摆放字符”是什么意思?

就是比如你有 "cbbda", 这样你就建个char array A = [''] * len(s). from: 1point3acres.com/bbs
然后b出现次数最多先放两个b,分别放在A[0], A[2]的位置,然后剩下的字符依次放在A[4], A[1], A[3](顺序无所谓)。最后就是"bcbad"
整个摆放顺序就是先放偶数位再奇数位
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷. From 1point 3acres bbs
补充内容 (2015-10-30 12:20):
顺序无所谓是指先放a,d,c之中哪个都无所谓。先解决频次最高的字符就行
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2015-10-30 12:21:24 | 显示全部楼层
其实第三题可以直接用hashmap或者hashset 然后用entry 来输出就可以了?我用的java啊?这种思路你看可以嘛?
回复 支持 反对

使用道具 举报

 楼主| qbt4juik 发表于 2015-10-30 12:22:26 | 显示全部楼层
qiuxuxing007 发表于 2015-10-30 12:21. from: 1point3acres.com/bbs
其实第三题可以直接用hashmap或者hashset 然后用entry 来输出就可以了?我用的java啊?这种思路你看可以嘛?

要保留原有array的顺序,所以不知道你这样行不行
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-10-30 12:55:16 | 显示全部楼层
恭喜lz,请问那个第三轮网页题是啥意思,网页链接和坐标是个什么样的关系?
回复 支持 反对

使用道具 举报

 楼主| qbt4juik 发表于 2015-10-30 12:58:13 | 显示全部楼层
宝贝忆彼岸 发表于 2015-10-30 12:55
恭喜lz,请问那个第三轮网页题是啥意思,网页链接和坐标是个什么样的关系?
. from: 1point3acres.com/bbs
其实就是给个坐标找最近的矩形。。跟网页没什么关系的。。。x1,y1就是矩形左上顶点的坐标,x2,y2是右下顶点的
回复 支持 反对

使用道具 举报

2ndpoet 发表于 2015-10-30 13:19:43 | 显示全部楼层
CONGRATS! 问一下第二题, get_random 是从存入数据(key, value)随机产生一个吗?请问楼主是如何在BST中随机选择一个node呢?Array+Dictionary的解法 楼主可以举一个例子吗?谢谢!
回复 支持 反对

使用道具 举报

garnett2148 发表于 2015-10-30 13:38:01 | 显示全部楼层
2ndpoet 发表于 2015-10-30 13:19
CONGRATS! 问一下第二题, get_random 是从存入数据(key, value)随机产生一个吗?请问楼主是如何在BST中 ...
. 1point 3acres 璁哄潧
最后array + dict最优解参见.1point3acres缃
http://www.geeksforgeeks.org/analysis-algorithm-set-5-amortized-analysis-introduction/
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2015-10-30 13:38:06 | 显示全部楼层
qiuxuxing007 发表于 2015-10-30 12:21
其实第三题可以直接用hashmap或者hashset 然后用entry 来输出就可以了?我用的java啊?这种思路你看可以嘛?

要用linkedhashmap
回复 支持 反对

使用道具 举报

djjkobe 发表于 2015-10-30 13:44:56 | 显示全部楼层
能否再详细说一下第三轮坐标那题是什么意思?
. From 1point 3acres bbs
补充内容 (2015-10-30 13:48):
就是点击量大的时候如何优化?
回复 支持 反对

使用道具 举报

missing 发表于 2015-10-30 14:08:28 | 显示全部楼层
楼主你该不会是那天早上和我在大厅聊天的CMU选手吧。。
回复 支持 反对

使用道具 举报

queeniejing 发表于 2015-10-30 14:11:43 | 显示全部楼层
恭喜恭喜 沾沾楼主喜气
回复 支持 反对

使用道具 举报

sxnfnj 发表于 2015-10-30 14:22:04 | 显示全部楼层
qbt4juik 发表于 2015-10-30 12:19. visit 1point3acres.com for more.
就是比如你有 "cbbda", 这样你就建个char array A = [''] * len(s)
然后b出现次数最多先放两个b,分别 ...

其实感觉可以记录所有字母出现的频次,先放最多的那个比如"abbbcd",先放一个b,然后b的次数减一,再从剩下的"acd"里面挑次数最多的一个放,以此类推地放。不过感觉这样复杂度就高了。
回复 支持 反对

使用道具 举报

gorilazz 发表于 2015-10-30 14:34:44 | 显示全部楼层
qbt4juik 发表于 2015-10-30 12:19
就是比如你有 "cbbda", 这样你就建个char array A = [''] * len(s)
然后b出现次数最多先放两个b,分别 ...

楼主能再解释下,比如“aabbcc”这种按照你的方法好像不对啊
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 20:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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