一亩三分地论坛

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

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

Google onsite,最后挂了

[复制链接] |试试Instant~ |关注本帖
lastorderzzm 发表于 2015-8-18 16:15:26 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 本科 全职@Google - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
onsite面试两轮,然后挂了。
第一轮面试官是一个白人, 先上来一个问题是一串type为double的stream源源不断地流过来,给了window size, 问最近window size中所有数的平均。我的解法是用deque做的,空间复杂度O(n),不知道有没有O(1)空间复杂度的解法。Follow up:经过很长一段时间之后,可能数据流中的平均值不再是正确的平均值了,请解释一下为什么,该如何解决这个问题。我回答是因为double不是精确的计数,可能产生误差,解决方法是过一定时间重新将整个deque中的所有数据重新求一下平均值。
第二题给了一个matrix,每个matrix[i][j]有一个价格,给你一个budget,问如何求出最大面积的子矩阵,使得子矩阵的价格之和不超过budget。一开始我跟他简单讲述了一下O(n6)的brute force, 然后说可以建立一个sum数组优化到O(n4),然后他说能继续优化么,我说用two pointer可以把时间复杂度优化到O(n3)。然后写code写了好久。我觉得可能是我code写的太慢了吧,因为经常写着写着就要停下来想一想。
. visit 1point3acres.com for more.
第二轮面试官国人,上来的的问题是问我如果在谷歌搜索框里输入一个查询语句,请描述一下在点击回车之后会发生什么事情。因为自己做过搜索引擎,我当时以为他问搜索引擎的查询过程,然后有点答得不对题,后来才知道他问的是计算机网络的东西。我大概把这个网络部分的回答简化了,然后没有答完整。要是理解清楚题意的话,我觉得我会把应用层到物理层的过程都给他讲一遍。(居然考计算机网络,我去)
第二个问题是说谷歌服务器每个上面都有自己的log,让我做一个log viewer服务器,自己定义接口,能够实现在log viewer查询所有的服务器端整合的log,(因为去一个个服务器上查询log可能太麻烦了), 可以自己定义log viewer的功能。做完了后面试官说写的很好,然后跟我讨论了一下实现并发等,面试结束,然后就挂了。。。挂了。。。挂了。。。

评分

3

查看全部评分

hj867955629 发表于 2015-10-29 11:07:38 | 显示全部楼层
宝贝忆彼岸 发表于 2015-10-7 21:26
请问lz第一题怎么用two pointer把复杂度变成 O(N^3)?求解答啊!!!

private int findMaxLengthIn1DArray(int[] nums, int target) {
                int max = 0, i = 0, sta = 0, sum = 0;
                while (i < nums.length) {
                        sum += nums; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        if (sum > target) {-google 1point3acres
                                max = Math.max(max, i-sta);
                        }
                        while (sum > target) {
                                sum -= nums[sta++];. From 1point 3acres bbs
                        }
鏉ユ簮涓浜.涓夊垎鍦拌鍧.                         i++;
                }
                return max == 0 ? nums.length : max;
        }
       
        public int getMaxArea(int[][] nums, int target) {
                int wid = nums.length, len = nums[0].length, max = 0;
                for (int j1 = 0; j1 < wid; j1++) {
                        int[] tmp = new int[len];
                        for (int j2 = j1; j2 < wid; j2++) {
                                for (int i = 0; i < len; i++) {
                                        tmp += nums[j2];
                                }
                                int tempMax = findMaxLengthIn1DArray(tmp, target);
                                max = Math.max(max, tempMax*(j2-j1+1));. 鍥磋鎴戜滑@1point 3 acres
                        }
                } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                return max;.1point3acres缃
        }
回复 支持 2 反对 0

使用道具 举报

pushazhiniao 发表于 2016-8-25 06:03:57 | 显示全部楼层
frank11118 发表于 2016-8-23 11:46
感謝分享. Waral 鍗氬鏈夋洿澶氭枃绔,
. Waral 鍗氬鏈夋洿澶氭枃绔,
一題二問實在沒想法,有人願意用 gist 分享一下 code 嗎?

"""
```. 鍥磋鎴戜滑@1point 3 acres
def maxAreaSubmatrix(matrix, k):
        if not matrix or not matrix[0] or k <= 0:.鐣欏璁哄潧-涓浜-涓夊垎鍦
                return 0
        m, n = len(matrix), len(matrix[0])
        result = 0
        for top in range(m):
                row = [0] * n
                for bottom in range(top, m):. 1point3acres.com/bbs
                        start, curSum = 0, 0
                        for i in range(n):
                                row += matrix[bottom]
                                curSum += row
                                while curSum > k:
                                        curSum -= row[start]
                                        start += 1
                                result = max(result, (bottom - top + 1) * (i - start + 1))
        print result
        return result. more info on 1point3acres.com

matrix1 = [[2,6,4,7,3],[5,1,8,2,7],[1,4,2,8,1]]
matrix2 = [[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1]]
maxAreaSubmatrix(matrix1, 15)
maxAreaSubmatrix(matrix2, 9)
```
""". 1point 3acres 璁哄潧
跑过了没有bug 希望呈现的是对的
回复 支持 1 反对 0

使用道具 举报

hyliu0000 发表于 2015-8-20 03:25:14 | 显示全部楼层
为什么只有两轮?
回复 支持 反对

使用道具 举报

ChrisGates23 发表于 2015-8-20 03:53:08 | 显示全部楼层
请问lz是只面了两轮还是只写了两轮
回复 支持 反对

使用道具 举报

joytostuffratio 发表于 2015-8-20 04:18:48 | 显示全部楼层
同问lz只面了两轮吗?
回复 支持 反对

使用道具 举报

Williamslg 发表于 2015-8-20 13:36:23 | 显示全部楼层
请问第二轮的两个题能具体讲讲LZ的解答吗?
回复 支持 反对

使用道具 举报

jeff_xu001 发表于 2015-8-20 15:55:38 | 显示全部楼层
感觉是电话面试吧? 二轮
回复 支持 反对

使用道具 举报

ototsuyume 发表于 2015-8-20 21:03:30 | 显示全部楼层
google在国内的面试人数太多面试官太少所以帝魔两都本地学校的学生都是只面两轮,表现不差才给面后面两轮
回复 支持 反对

使用道具 举报

say543 发表于 2015-8-25 12:58:33 | 显示全部楼层
LZ log viewer 有要求要什么条件吗? 如果要用time stamp 来view 感觉跟在distributed system 中求top k 有点像? 能说说requirement吗
回复 支持 反对

使用道具 举报

alucardzhou 发表于 2015-8-26 04:54:38 | 显示全部楼层
第一个问题:
既然给了window size。
newAverage = (oldAverage * windowSize - dequeue + enqueue) / windowSize
这样就是O(1)对吧。但每次都会产生误差。
所以每过一段时间重算一次平均值很必要。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-10-7 21:26:53 | 显示全部楼层
请问lz第一题怎么用two pointer把复杂度变成 O(N^3)?求解答啊!!!
回复 支持 反对

使用道具 举报

say543 发表于 2015-10-8 13:13:22 | 显示全部楼层
alucardzhou 发表于 2015-8-26 04:54
第一个问题:
既然给了window size。. more info on 1point3acres.com
newAverage = (oldAverage * windowSize - dequeue + enqueue) / w ...

一段时间后不准是因该double average 精准度的reason吗?
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-1 09:46:28 | 显示全部楼层
hj867955629 发表于 2015-10-29 11:07.1point3acres缃
private int findMaxLengthIn1DArray(int[] nums, int target) {
                int max = 0, i = 0, sta = 0, sum = ...

嗯嗯,明白了,感谢!我觉得可以再简化一下,create一个矩阵,每个格子表示这个格子以及这个格子以上这一列的budget的和,这个可以O(n^2)来实现,然后每一行用2 point扫一遍,用O(N)来实现,所以总的复杂度就变成O(N^2)了。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-1 09:51:06 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-1 09:46
嗯嗯,明白了,感谢!我觉得可以再简化一下,create一个矩阵,每个格子表示这个格子以及这个格子以上这一 ...

说错了,每一行扫N遍,所以一共是O(n^2)
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-11-2 03:13:26 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-1 09:46
嗯嗯,明白了,感谢!我觉得可以再简化一下,create一个矩阵,每个格子表示这个格子以及这个格子以上这一 ...
.1point3acres缃
它不一定从第一行开始吧?可能从第三行到第五行,你这样做可以找这种情况吗?
回复 支持 反对

使用道具 举报

maomaoxiong 发表于 2015-11-2 13:50:07 | 显示全部楼层
上面的代码有挺多错误了。不要被误导了。
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-11-3 08:22:31 | 显示全部楼层
maomaoxiong 发表于 2015-11-2 13:50
上面的代码有挺多错误了。不要被误导了。

你是说哪错了呀?是typo还是思想?
回复 支持 反对

使用道具 举报

likeulb 发表于 2015-11-4 15:13:56 | 显示全部楼层
hj867955629 发表于 2015-10-29 11:07
private int findMaxLengthIn1DArray(int[] nums, int target) {
                int max = 0, i = 0, sta = 0, sum = ...

看懂了,想得不错!不过确实有些typo...
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-11-4 17:48:10 | 显示全部楼层
likeulb 发表于 2015-11-4 15:13
看懂了,想得不错!不过确实有些typo...

typo是论坛问题。。我运行测试过。。
回复 支持 反对

使用道具 举报

reality 发表于 2015-11-29 14:37:16 | 显示全部楼层
第一轮第二题可以用dp做吗
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 02:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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