一亩三分地论坛

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

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

Google onsite

[复制链接] |试试Instant~ |关注本帖
potato张 发表于 2015-11-20 02:59:51 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 校园招聘会 - Onsite |Otherfresh grad应届毕业生

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

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

x
昨天刚被Google onsite殴打完,题不是特别难,主要是自己太水了,肯定是过不了的。贴出题来赞赞人品。
第一题类似于孤岛问题,follow up是如果在来个stream,每次输入一个点是岛点,问你怎么update已经有的数组并返回新的岛的个数。第二个处理读取文件长度的,给你个每次读4096个Byte的function, 让你implement一个可以读取任意长度N的function,要用他给的4096 function。从同一个文件中读取,由于每次读取的长度不一定是4096的倍数,所以多读的要存起来,下次再读的时候要把这存起来的先读入。就是要考虑各种情况。第三个是求曼哈顿长度的,给一个2D数组,里面有1,2,-1若干,问所有1到2的manhattan distance最短的是多少。用 DP第四个3 sum

评分

4

查看全部评分

本帖被以下淘专辑推荐:

宝贝忆彼岸 发表于 2015-11-20 03:30:08 | 显示全部楼层
感谢分享,请问第三个曼哈顿距离那题,是说找出其中一个1到一个2是最短的距离就可以每个为1的点都要找到距离自己最近的2的距离?
回复 支持 反对

使用道具 举报

queeniejing 发表于 2015-11-20 03:44:49 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-20 03:30
感谢分享,请问第三个曼哈顿距离那题,是说找出其中一个1到一个2是最短的距离就可以每个为1的点都要找到距 ...

彼岸,你什么时候去GG onsite?
回复 支持 反对

使用道具 举报

 楼主| potato张 发表于 2015-11-20 03:47:57 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-20 03:30
感谢分享,请问第三个曼哈顿距离那题,是说找出其中一个1到一个2是最短的距离就可以每个为1的点都要找到距 ...

每个1到所有2的距离取最小的,然后再在这些值中取最小的
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-5 11:26:11 | 显示全部楼层
请问读4096个Byte的function就是Read N Characters Given Read4 II - Call multiple time?第三个manhattan distance这个题是对每个2进行dfs,每次更新最短距离,最后相加?
回复 支持 反对

使用道具 举报

 楼主| potato张 发表于 2015-12-7 07:56:46 | 显示全部楼层
bobzhang2004 发表于 2015-12-5 11:26
请问读4096个Byte的function就是Read N Characters Given Read4 II - Call multiple time?第三个manhattan  ...

4096那个是的。manhattan distance用dfs能做,但是用dp效率最高,我说用dfs他不满意,最后提示我用dp写出来了

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-7 21:52:21 | 显示全部楼层
楼主可以说下曼哈顿那题dp怎么做吗,那题就是Leetcode 的walls and gate吧,用bfs是O(m * n)的复杂度?
回复 支持 反对

使用道具 举报

hackenkreuz 发表于 2015-12-7 23:46:46 | 显示全部楼层
最近这个4096的题目还真是流行。。。
回复 支持 反对

使用道具 举报

 楼主| potato张 发表于 2015-12-13 04:25:24 | 显示全部楼层
bobzhang2004 发表于 2015-12-7 21:52-google 1point3acres
楼主可以说下曼哈顿那题dp怎么做吗,那题就是Leetcode 的walls and gate吧,用bfs是O(m * n)的复杂度?

建一个m*n的2D array,把原array里所有1的位置设成0,其他设成-1.写一个while loop,loop里每次遍历新array里面的所有非-1的位置比如array[j],他的上方点的值为min(array[j]+1, array[j-1]),下方左方右方同理,直到array里面没有-1.然后查看原array里所有2的位置[j],取新array里所有array[j]最小值即可。bfs复杂度是大于O(m*n)的,因为有很多个1和很多个2.
回复 支持 反对

使用道具 举报

 楼主| potato张 发表于 2015-12-13 04:26:20 | 显示全部楼层
bobzhang2004 发表于 2015-12-7 21:52
楼主可以说下曼哈顿那题dp怎么做吗,那题就是Leetcode 的walls and gate吧,用bfs是O(m * n)的复杂度?

都是i,j不知道为什么显示不出来
回复 支持 反对

使用道具 举报

crisc3 发表于 2015-12-13 11:05:24 | 显示全部楼层
potato张 发表于 2015-12-13 04:25
建一个m*n的2D array,把原array里所有1的位置设成0,其他设成-1.写一个while loop,loop里每次遍历新arr ...

没看懂你这个DP什么意思...但是 BFS 怎么可能会大于O(m*n) 我没理解错题意的话,把所有2 push到queue里面,然后出发,向外一层一层拓展,记录第i层的所有点,直到遇到1就停止BFS, return length. 即使2有n^2个 由于每个点最多被遍历一次 所以不可能超过O(m*n)
回复 支持 反对

使用道具 举报

silenceleaf 发表于 2015-12-14 15:45:40 | 显示全部楼层
potato张 发表于 2015-12-7 07:56
4096那个是的。manhattan distance用dfs能做,但是用dp效率最高,我说用dfs他不满意,最后提示我用dp写出 ...

楼主我觉得曼哈顿那题,可以用bfs啊,开始把所有的1都存到stack里面,然后对所有的1进行bfs逐层遍历,第一个遇到的2既是最短的那个,时间是O(n),这样可以吗?

补充内容 (2015-12-14 15:47):
时间空间都是O(m*n)
回复 支持 反对

使用道具 举报

 楼主| potato张 发表于 2015-12-16 13:03:21 | 显示全部楼层
crisc3 发表于 2015-12-13 11:05. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
没看懂你这个DP什么意思...但是 BFS 怎么可能会大于O(m*n) 我没理解错题意的话,把所有2 push到queue里面 ...

嗯,你的方法挺好的我觉得
回复 支持 反对

使用道具 举报

 楼主| potato张 发表于 2015-12-16 13:04:01 | 显示全部楼层
silenceleaf 发表于 2015-12-14 15:45
楼主我觉得曼哈顿那题,可以用bfs啊,开始把所有的1都存到stack里面,然后对所有的1进行bfs逐层遍历,第 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
看上去应该挺对的!
回复 支持 反对

使用道具 举报

yangyishan0901m 发表于 2015-12-21 07:36:25 | 显示全部楼层
记忆化搜索+DFS可以做, 也可以直接BFS, 引用(楼主我觉得曼哈顿那题,可以用bfs啊,开始把所有的1都存到stack里面,然后对所有的1进行bfs逐层遍历,第一个遇到的2既是最短的那个,时间是O(n),这样可以吗?)
最开始看楼主说DP以为面试官要求必须用DP呢。。。有点像POJ滑雪题, 的确是可以用DP做
int shortest(vector<vector<int>> nums){
        if(nums.size()==0||nums[0].size()==0) return 0;
        int m=nums.size();
        int n=nums[0].size();. From 1point 3acres bbs
        vector<vector<int>> dp(m,vector<int>(n,-1));
        int res=INT_MAX;
        for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                        res=max(res,dfs(i,j,dp,nums));
                }. From 1point 3acres bbs
        }
        return res;
}

int a[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int dfs(int i,int j,vector<vector<int>> &dp,vector<vector<int>> &m){
        if(dp[i][j]!=-1) return dp[i][j];
        if(m[i][j]==2) {
                dp[i][j]=0;
                return 0;
        }
        int res=INT_MAX;
        for(int k=0;k<4;k++){
                int x=a[k][0]+i;. Waral 鍗氬鏈夋洿澶氭枃绔,
                int y=a[k][1]+j;
                if(x<0||x>=dp.size()||y<0||y>=dp[0].size()) continue;
                res=min(res,dfs(x,y,dp,m)+1);
        }
        return res;
}
回复 支持 反对

使用道具 举报

 楼主| potato张 发表于 2015-12-22 12:54:38 | 显示全部楼层
yangyishan0901m 发表于 2015-12-21 07:36
记忆化搜索+DFS可以做, 也可以直接BFS, 引用(楼主我觉得曼哈顿那题,可以用bfs啊,开始把所有的1都存到s ...

厉害!请收下本小**的膝盖!
回复 支持 反对

使用道具 举报

wy193777 发表于 2016-1-28 10:50:08 | 显示全部楼层
yangyishan0901m 发表于 2015-12-21 07:36
记忆化搜索+DFS可以做, 也可以直接BFS, 引用(楼主我觉得曼哈顿那题,可以用bfs啊,开始把所有的1都存到s ...

代码有点问题啊,除了遇到2的时候把dp数组对应的元素变为0以为,没有其他赋值操作了。
回复 支持 反对

使用道具 举报

javaprogrammer 发表于 2016-2-2 04:06:41 | 显示全部楼层
yangyishan0901m 发表于 2015-12-21 07:36
记忆化搜索+DFS可以做, 也可以直接BFS, 引用(楼主我觉得曼哈顿那题,可以用bfs啊,开始把所有的1都存到s ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
滑雪的dp是不是不太适用于这个题目?因为dp matrix里存的都是每个点到最近的2的距离,而不是每个点到所有2的距离的和的叠加。。。
回复 支持 反对

使用道具 举报

javaprogrammer 发表于 2016-2-2 04:06:47 | 显示全部楼层
yangyishan0901m 发表于 2015-12-21 07:36
记忆化搜索+DFS可以做, 也可以直接BFS, 引用(楼主我觉得曼哈顿那题,可以用bfs啊,开始把所有的1都存到s ...

滑雪的dp是不是不太适用于这个题目?因为dp matrix里存的都是每个点到最近的2的距离,而不是每个点到所有2的距离的和的叠加。。。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-2 05:34:05 | 显示全部楼层
yangyishan0901m 发表于 2015-12-21 07:36
记忆化搜索+DFS可以做, 也可以直接BFS, 引用(楼主我觉得曼哈顿那题,可以用bfs啊,开始把所有的1都存到s ...

这个时间复杂度和bfs先将所有2都Push到queue的时间复杂度是一样的啊,都是O(m * n)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 16:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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