一亩三分地论坛

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

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

GOOGLE三面求过,已经没心情写逗比版的了。。。

[复制链接] |试试Instant~ |关注本帖
372284362 发表于 2015-11-3 11:55:35 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Other其他

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

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

x
        之前面过两次on-campus,表现还不是完全符合google的预期,所以补了这次电面。面试官是个女的,听口音应该是个中国人,反正一听口音我就放松下来了。
        第一题是求一个数组的逆序对数目。我很诚实地跟她说这题我见过,因为以前是搞竞赛的,所以这个题目应该是很熟了。告诉她可以用归并排序或者树状数组做,然后问她要不要换题。她表示先不换了,让我讲讲树状数组的做法。我先说树状数组这个数据结构有两个功能,一是对区间中某个元素做加法修改,二是求区间中前n个元素的和,于是也显然可以求任意区间内所有元素的和。
int *cnt = new int [n];
int tot = 0;
for (int i = 0; i < n;i++) {
         add(a);
         tot += sum(n) - sum(a);
}
        然后结合了一个例子,[4 2 2 1]。先访问第一个数字4,之后可以求得5-7之间有0个数。再访问第二个数字2,可求得3-7之间有1个数。以此类推。
[4 2 2 1]
num
1 2 3 4 5 6 7
0 1 0 1 0 0 0
        期间问她这里面有没有可能有非正数或者小数,她说有可能。我就说那可以先排序一下,然后用一个哈希来做映射。可能说得不太清楚,我就举了个例子给她。比如原数据是[52 4 1],那么就先将其变为[42 3 1],原数据是[5 2 2 1],那么就变为[3 2 2 1]。总之我们能把a变为1到n之间的某个数,又可以用树状数组解了。
[5, 2, 4, 1] [4,2,3,1] 1<=a<= n
[5, 2, 2,1] [3,2,2,1]
        第二题她先说题,“有一个矩阵,行和列都是递增的,这题你见过没?”“额。。。你还没说问题呢。。。”“嗯,判断在这个矩阵里有没有一个给定的数。”“嗯,我应该是见过。。。我想想怎么做来着。。。”
2, 20,  35,  41,  70,
11,24,  44,  60,  78,
21,30,  50,  75,  90,
31,38,  99, 100,  102
        然后和她说了下O(m+n)的算法,她问有没有什么优化。我觉得这个应该是时间上最优的了,空间复杂度也是O(1),就问她什么方面的优化,她说任何方面。我先说的是我拿到这道题的时候,最先想到的是四分法,但是时间复杂度和直接搜索相比没啥提升,她顺势就问我那时间复杂度是多少。
        我先说了下四分法的想法。先和左上角矩形的右下角比,如果比它大就搜三个*的矩阵,否则搜那个-的矩阵。她让我想下是这样么。我想了几秒钟,发现不是,就改过来了。算时间复杂度用主定理。
-----******       **** ****
**********       **** -----
T(N)= 3T(N/4) +  O(1)
(nm)^(log_{4}^{3})
        她接着问有啥别的优化。我问她有没有可能多次询问,有可能的话用一个hash来存下以前的所有解,方便重复询问时直接判断。但是这样空间复杂度有提升。
mem:O(1) -> O(t)
unordered_map<int,bool> isAsked;
if(isAsked(x) != isAsked.end())
         return isAsked[x];
//Run the algorithm
isAsked[x]= true / false
        她还是问这题又啥优化,我想想之后硬说可以两种方向搜。这样如果矩阵很大,但是目标离某个角很近的话可以少走几步,如果能并行计算的话更好,最坏情况是走2(m + n)步。她又提醒我再想一下,发现最坏情况是两条路径撞在了一起,所以还是(m + n)步。
find75:
31-> 38 -> 99 -> 50 -> 75 O(m+n)
70-> 78 -> 60 -> 75
find 46
31 -> 38 -> 99 -> 50 -> 75 O(m + n)
70-> 78 -> 60 -> 75         O(m + n)  O(m + n)
        她问我还想接着优化还是做新题。我说能不能提示下还有什么优化。她提升了一下说要不试试对最后一行做二分搜索。发现这样确实可以一下删掉一些列,不过没发现还可以删最后一行,这里她也提醒了一下。。。
        所以,她想要的优化是对于一个矩阵的最后一行做二分搜索后,删掉前几列和最后一行,得到一个子矩阵。重复这样的操作,时间复杂度是O(min(m,n)log(max(m,n)))。之后跟她提了一下这个方法在m和n相差比较大的时候可能比较有用。
2,  20,  35,  41,  70,
11, 24,  44,  60,  78,
21, 30,  50,  75,  90,
31, 38,  99, 100,  102
75
38 <= 75 < 99 start from 99
n columns O(log(n))
m rows O(m)
O(mlog(n))
diff(m, n) is too large
        她看还有五分钟就又出了一道题,说不用写代码,讲方法就好了。也是leetcode原题,perfect squares。简单说了下BFS的算法,她最开始问我是不是brute force,我说不是呀,然后写了个列子,把每层的情况列了一下。
1, 4, 9, 16….
12 = 4 + 4 + 4 = 9 + 1 + 1 + 1
1 4 9
2 5 10 8
3 6 11 12
O(n)
12 -> X 4^2 + ...
n -> sqrt(n)
t candidates: 1, 4, 9, … sqrt(n)^2
BFS
q can be reached in the graph / can be representedas d perfrect numbers
queue<int> q, sol;
q.push(0);
sol.push(0);
while (q.) {
         int x =q.front();
         int d =sol.front();
         q.pop();
         sol.pop();
         for (inti = 0; i < t; i++)
                   if(x + cand < n) {
                            q.push(i)
sol.push
                   }
                   elseif (x + can)
                   else
                            break;
}
        感觉还凑活吧!发上来求点儿人品
.鐣欏璁哄潧-涓浜-涓夊垎鍦


补充内容 (2015-11-11 21:44):
等着跟team match,求带走。。。!

补充内容 (2015-12-22 03:59):
match 到了 payment 组,开开心心地从了,可以准备找全职了~

评分

3

查看全部评分

本帖被以下淘专辑推荐:

 楼主| 372284362 发表于 2015-11-3 15:18:03 | 显示全部楼层
全程没写代码。。。比较虚。。。
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-11-4 02:16:28 | 显示全部楼层
372284362 发表于 2015-11-3 15:18
全程没写代码。。。比较虚。。。

LZ好厉害,思维敏捷,羡慕!. 鍥磋鎴戜滑@1point 3 acres

. From 1point 3acres bbs第二题leetcode上有, quad partition: T(n) = 3T(n/2) + c, binary partition: T(n) = 2T(n/2) + cn -> O(min(m,n)log(max(m,n))), 但是leetcode大神还有一个improved binary partition复杂度更低,虽然没有证明.

http://articles.leetcode.com/201 ... matrix-part-ii.html
回复 支持 反对

使用道具 举报

abcd1992719g 发表于 2015-11-4 02:35:52 | 显示全部楼层
Arthur 好厉害!
回复 支持 反对

使用道具 举报

peter13140 发表于 2015-11-9 00:39:27 | 显示全部楼层
问题看上去好难呀,面试官给hint了吗?
回复 支持 反对

使用道具 举报

bjwmz 发表于 2015-11-9 00:47:24 | 显示全部楼层
恭喜,看的我人都斜了
回复 支持 反对

使用道具 举报

kiru 发表于 2016-1-14 07:20:11 | 显示全部楼层
请问lz是总共进行了3次电面后直接拿offer么,没有onsite? 可以再问下lz是几月投的G家么,谢谢
回复 支持 反对

使用道具 举报

 楼主| 372284362 发表于 2016-1-14 07:24:51 | 显示全部楼层
kiru 发表于 2016-1-14 07:20. from: 1point3acres.com/bbs
请问lz是总共进行了3次电面后直接拿offer么,没有onsite? 可以再问下lz是几月投的G家么,谢谢

对,只进行了三次店面,没有onsite,剩下就是等team match了。. 鍥磋鎴戜滑@1point 3 acres

我是9月投的,10月收到的面试。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-25 10:27:43 | 显示全部楼层
楼主最后一题的是要输出最短的square的数量还是所有的最短的呢?
回复 支持 反对

使用道具 举报

 楼主| 372284362 发表于 2016-1-25 19:24:45 | 显示全部楼层
bobzhang2004 发表于 2016-1-25 10:27
楼主最后一题的是要输出最短的square的数量还是所有的最短的呢?

是让求的最短的
回复 支持 反对

使用道具 举报

alen231x 发表于 2016-1-26 06:53:20 | 显示全部楼层
从右上角开始找,大就往下走,小就往左走O(m+n)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 02:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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