一亩三分地论坛

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

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

Google 面经

[复制链接] |试试Instant~ |关注本帖
hufm92 发表于 2015-1-22 09:06:08 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Fail

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

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

x
唔,昨天下午连续面了三轮,自己感觉还比较好,然后刚刚收到邮件说杯具了。真是分分钟被打脸。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

三轮面试应该是两个美国人,一个印度人吧

第一个面试:
上来第一个问题是说说你遇到的最大的挑战是什么,怎么解决的。
然后开始码代码。。
第一个是x^y,比较简单了,注意负数、零这种情况,然后先写了一个naive的O(n)的,然后写了一个O(logn)的。
然后是n个数里面找最大的k个。。==
然后是一个design题,design一个cache,然后需要设计哪些操作,需要考虑哪些参数,用什么hardware储存。。

第二个面试:. visit 1point3acres.com for more.
先自我介绍一下,然后就简历里面到project问了几个问题。
然后开始码代码。
第一个是给你一个board,有黑色和白色的cell,判断是否所有的白色cell都相连。
第二个问题是找最长的回文字串。。
leetcode都有差不多的题目……
这次面试中,每道题都被问了该如何设计test 数据。. Waral 鍗氬鏈夋洿澶氭枃绔,
. more info on 1point3acres.com
第三个面试:
一个印度哥们,虽然很友好,但是确实有点听的不习惯。
然后上来直接码代码
第一个问题就是存在这样一个结构的array,先上升再下降。然后找最大值。。直接二分找吧。
然后问最小值。。==……
然后第二题是这样一个场景:
一群人在排队,然后每个人知道自己前面有多少人比自己高,然后给你每个人的高度,要求reconstruct 这个序列。

好吧。感觉题目都不拿。答起来也感觉很愉快。。
不知道为什么就这么跪了,不开森……>.<
写个面经造福大家吧,希望暑假能找到人要我……. from: 1point3acres.com/bbs

评分

2

查看全部评分

 楼主| hufm92 发表于 2015-1-23 01:40:22 | 显示全部楼层
圆梦梦剧场 发表于 2015-1-23 01:28
请问插入是怎么做到O(logN)的?

而且其实我很好奇python中这样操作的复杂度是多少。
stack = stack[:i] +  [new] +stack[i:]……
回复 支持 1 反对 0

使用道具 举报

mzhang 发表于 2015-1-22 09:18:29 | 显示全部楼层
pat LZ, 我上周一面的,还在等结果。这种情况的确比较不爽。
回复 支持 反对

使用道具 举报

kiviljc 发表于 2015-1-22 22:51:07 | 显示全部楼层
lz 第一题能否具体说一下。谢谢了
回复 支持 反对

使用道具 举报

 楼主| hufm92 发表于 2015-1-22 22:53:52 | 显示全部楼层
kiviljc 发表于 2015-1-22 22:51
lz 第一题能否具体说一下。谢谢了

第一个面试的第一题?x^y?
if y > 2:
    if y%2 == 0:
        return power(x*x, y/2)
    else:. From 1point 3acres bbs
        return power(x*x, y/2)*x
回复 支持 反对

使用道具 举报

kiviljc 发表于 2015-1-22 22:59:03 | 显示全部楼层
hufm92 发表于 2015-1-22 22:53
第一个面试的第一题?x^y?
if y > 2:
    if y%2 == 0:

谢谢楼主.鐣欏璁哄潧-涓浜-涓夊垎鍦

补充内容 (2015-1-22 23:06):
我以为是实现亦或操作符呢,,lol
回复 支持 反对

使用道具 举报

OracleDesire 发表于 2015-1-22 23:58:57 | 显示全部楼层
话说排队那个题咋做?
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2015-1-23 00:04:47 | 显示全部楼层
OracleDesire 发表于 2015-1-22 23:58
话说排队那个题咋做?

感觉可以这样子

假设队伍高度是:
数组A: 2 3 1 5 4

那么对应的在A之前比他高的人数是:
数组B: 0 0 2 0 1

那么首先把高度排序:
数组C: 5 4 3 2 1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后对数组B从后往前扫,. visit 1point3acres.com for more.
B[4] = 1, 说明 A[4] = C[1] = 4,同时从数组C删除4,此时数组C为:5 3 2 1
接下来:
B[3] = 0, 说明A[3] = C[0] = 5,同时从数组C删除元素5

以此类推

时间复杂度是O(n^2)。. more info on 1point3acres.com
. from: 1point3acres.com/bbs
不知道楼主怎么做的。有没有O(n)或者O(NlogN)的算法?. 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

 楼主| hufm92 发表于 2015-1-23 01:03:19 | 显示全部楼层
圆梦梦剧场 发表于 2015-1-23 00:04
感觉可以这样子

假设队伍高度是:

哦,我是这样做的。
先排序,然后从高到低重建队列。因此每个人在重建的时候,所有比他高的人都已经在队伍中了,所以直接将他插入到对应位置就行了,因为每个人都知道有多少比自己高的人在自己前面。. From 1point 3acres bbs
插入的复杂度可以降到logN。这样就是O(NlogN)了。
回复 支持 反对

使用道具 举报

 楼主| hufm92 发表于 2015-1-23 01:06:36 | 显示全部楼层
圆梦梦剧场 发表于 2015-1-23 00:04
感觉可以这样子-google 1point3acres

假设队伍高度是:

感觉你的算法用到了B的顺序,其实这个是没有给的。。输入只有每个人的高度和他们前面有多少人。
可以认为是[(b0, c0), (b1,c1), ...]这样的structure。
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2015-1-23 01:28:29 | 显示全部楼层
hufm92 发表于 2015-1-23 01:03
哦,我是这样做的。.鏈枃鍘熷垱鑷1point3acres璁哄潧
先排序,然后从高到低重建队列。因此每个人在重建的时候,所有比他高的人都已经在队 ...

请问插入是怎么做到O(logN)的?
回复 支持 反对

使用道具 举报

 楼主| hufm92 发表于 2015-1-23 01:37:24 | 显示全部楼层
圆梦梦剧场 发表于 2015-1-23 01:28
请问插入是怎么做到O(logN)的?

额,我当时没有仔细想,觉得可能是要O(n),然后觉得应该可以logn。

比如用链表存队列,再用一个平衡树来维护链表节点的位置。这样每次新插入一个点,在树中找到对应的链表节点,然后再在链表里插入,然后再更新树。。。
. visit 1point3acres.com for more.
反正挺麻烦,但是感觉肯定有logn的方法。
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2015-1-23 01:39:19 | 显示全部楼层
hufm92 发表于 2015-1-23 01:37
额,我当时没有仔细想,觉得可能是要O(n),然后觉得应该可以logn。
. 鍥磋鎴戜滑@1point 3 acres
比如用链表存队列,再用一个平衡树 ...

好像这样确实logN了。。多谢楼主~   good luck
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2015-1-23 01:44:49 | 显示全部楼层
hufm92 发表于 2015-1-23 01:40
而且其实我很好奇python中这样操作的复杂度是多少。
stack = stack[:i] +  [new] +stack……

楼主是用python面的?不懂python诶
C++和Java里面都得O(n)在array里插入一个新值
回复 支持 反对

使用道具 举报

 楼主| hufm92 发表于 2015-1-23 02:20:11 | 显示全部楼层
圆梦梦剧场 发表于 2015-1-23 01:44
楼主是用python面的?不懂python诶
C++和Java里面都得O(n)在array里插入一个新值

嗯嗯。。谢谢……我觉得其实O(N^2)的算法比较简洁,NlogN感觉数据结构上弄的有些过于复杂了。。==
回复 支持 反对

使用道具 举报

yourway 发表于 2015-1-23 04:51:00 | 显示全部楼层
hufm92 发表于 2015-1-22 12:40
而且其实我很好奇python中这样操作的复杂度是多少。
stack = stack[:i] +  [new] +stack……

在 python 中 slice 操作的复杂度就是取出元素的个数[1]。所以这样仍然是 O(N^2)
. 1point3acres.com/bbs
类似的题在 mitbbs 中曾经讨论过[2]。  . visit 1point3acres.com for more.

1: https://wiki.python.org/moin/TimeComplexity
2: http://www.mitbbs.com/article_t/JobHunting/32856675.html
回复 支持 反对

使用道具 举报

heavensyu 发表于 2015-1-24 15:14:26 | 显示全部楼层
弱弱问一句,楼主面的hosts吗?怎么有这么多轮?
回复 支持 反对

使用道具 举报

 楼主| hufm92 发表于 2015-1-24 15:42:26 | 显示全部楼层
heavensyu 发表于 2015-1-24 15:14
弱弱问一句,楼主面的hosts吗?怎么有这么多轮?

hosts是熟么?我面的就是普通的software engineer intern。。今年google好像都要三轮电面。。==
回复 支持 反对

使用道具 举报

heavensyu 发表于 2015-1-24 15:45:17 | 显示全部楼层
好多额……host就是你过了电面想选你进组的人。总之多谢分享!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 03:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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