一亩三分地论坛

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

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

Google 6.14电面

[复制链接] |试试Instant~ |关注本帖
genericname 发表于 2016-6-17 06:27:31 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
来跟大家分享phone interview的两道题1. write a matrix class
set(int i, int j, int value)
sum(int i, int j) 可求(0,0)到(i,j)整个square matrix elements的和

2. 2sum BST
第一题楼主用HashMap做的,思考了好久,sum只能想到O(N*N)的解,我是不是蠢得没谁了?
导致第二题没写完,只写了个outline。好在面试官表示知道我的想法了....... visit 1point3acres.com for more.



. more info on 1point3acres.com



补充内容 (2016-6-17 08:03):
刚才HR电话给我说schedule第二次电面...本来已经自我安慰MOVE ON了

评分

3

查看全部评分

本帖被以下淘专辑推荐:

nevets 发表于 2016-6-18 01:27:12 | 显示全部楼层
楼主不要慌,你要相信电面的candidate只有50%能从容的把基础做法讲完,其余的人要嘛是直接在思考优化做法反倒支支吾吾让面试官觉得蛋疼,要嘛是理解错题目然后不知道想啥的。如果你能很好的把基础算法说完并且写出来你已经站在50%的线上了。之后能优化一点是一点,想到合理的算法就讲出来,和面试官好好讨论。最后就算你没有拿出最优解,你可以比较你所有的算法然后说 当N很小的时候这些算法也是有竞争力的 虽然这有狡辩取巧之嫌,但是比一句话不讲灰溜溜挂电话高不知道哪里去了。

楼主碰上的题目是我在地里电面中碰到的比较难的题目了,要bug free的写完两题很不简单。. more info on 1point3acres.com

1. 回答(0, 0)到(i, j)的和是2D segment tree或者2D binary index tree的经典应用,但是如果怕短时间写不出可以先退而求其次。这题可以有3个解法:
1.1 正常模拟,O(1) set,O(NM) 扫描全局求和;. more info on 1point3acres.com
1.2 用两个矩阵,一个矩阵v[ i ][ j ]记录当前的值,一个矩阵m[ i ][ j ]记录的是m[ 0 ][ j ]到m[ i ][ j ]的和。set时,比较v[ i ][ j ],得到一个差值delta = now - v[ i ][ j ],然后用差值维护m矩阵:m[i .. N][j] += delta,O(N);sum时,由于m记录了列的和,所以只需求m[0..j]的和,O(M)。
1.3 2D BIT,其实就是1.2的换汤不换药。药理一模一样,只是求和的工具变了。这个时候set和sum的复杂度都变为O(logNlogM)。.鐣欏璁哄潧-涓浜-涓夊垎鍦

这时候问题来了。O(logNlogM)并不见得什么时候都比O(N)或者O(M)来的小,况且1.2的做法并不是每次都会达到理论最大值N或者M,但是1.3的做法每次必然是理论最大值。另外,由于1.3每次更新都需要行列更新,而1.2更新只关心列,求和只关心行,这提供了一个很好的并行化可能。综上,我们有了很好的trade off策略,可以考虑的tradeoff factor有dimension大小,set和sum的操作频率,在操作频率之上的cache加速,并行加速等等,不一一列举。

第二题其实应该马上把BST inorder traverse成一个sorted array然后直接做2sum,这样至少证明你普通的2sum是没问题的然后就是考察编程基本功了,用栈模拟递归做inorder traversal(左根右)和reverse inorder traversal(右根左),然后正常2sum。
. 1point3acres.com/bbs
总而言之,不要一言不发!不要硬着头皮追求完美!计算复杂度的时候一定要考虑常数,overhead,已经并行化可能性,这样才能把trade off大法发挥到极致
.1point3acres缃
补充内容 (2016-6-18 01:29):.鏈枃鍘熷垱鑷1point3acres璁哄潧
关于2D BIT的资料可以看这里:https://www.topcoder.com/communi ... y-indexed-trees/#2d

评分

1

查看全部评分

回复 支持 8 反对 0

使用道具 举报

blackrose 发表于 2016-6-17 07:40:55 | 显示全部楼层
2sum BST code 确实要很久,楼主没事。
回复 支持 反对

使用道具 举报

Altynai 发表于 2016-6-17 07:53:23 | 显示全部楼层
第一题可以用二维的binary indexed tree或者四分树
回复 支持 反对

使用道具 举报

phantom 发表于 2016-6-17 08:17:46 | 显示全部楼层
第一题是leetcode的这个题吧:
https://leetcode.com/problems/range-sum-query-2d-mutable/
回复 支持 反对

使用道具 举报

Jazzouple.Lee 发表于 2016-6-20 13:49:22 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!. 1point3acres.com/bbs

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。. more info on 1point3acres.com
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

Jazzouple.Lee 发表于 2016-6-20 14:04:05 | 显示全部楼层
我觉得第一题并用不到Binary Indexed Tree. 问题给的是要算出(0,0) 到(i,j)的总和 并不是(k,t) 到 (i, j)的总和。dp可以解了;dp(i, j) = sum(dp(0,0) to dp(i,j)) = dp(i - 1, j) +  valueInMatrix(i, j) 那么对于set的那个method我们就可以当做更新 (i, j)的sum: dp(i, j) =  dp(i - 1, j) + new value for i, j
回复 支持 反对

使用道具 举报

nevets 发表于 2016-6-20 14:44:04 | 显示全部楼层
Jazzouple.Lee 发表于 2016-6-20 14:04
我觉得第一题并用不到Binary Indexed Tree. 问题给的是要算出(0,0) 到(i,j)的总和 并不是(k,t) 到 (i, j ...

这个思路有问题,因为每次更新的时候会影响所有包含这个cell的sub-matrix,所以如果在set的时候更新,必须把包含这个cell的所有矩阵都更新了,但是明显这样做的复杂度非常高。
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-20 21:33:41 | 显示全部楼层
nevets 发表于 2016-6-20 14:44
这个思路有问题,因为每次更新的时候会影响所有包含这个cell的sub-matrix,所以如果在set的时候更新,必 ...

只需要进行col dp,每次更新复杂度O(col),求sum O(row)
回复 支持 反对

使用道具 举报

zjuzqh 发表于 2016-6-20 21:37:31 | 显示全部楼层
nevets 发表于 2016-6-18 01:27.鐣欏璁哄潧-涓浜-涓夊垎鍦
楼主不要慌,你要相信电面的candidate只有50%能从容的把基础做法讲完,其余的人要嘛是直接在思考优化做法反 ...

仰慕大神解法
回复 支持 反对

使用道具 举报

readman 发表于 2016-6-20 21:47:21 | 显示全部楼层
楼上说的很好了..我来贴code.1point3acres缃

public class FenwickTree2D {

        public static void add(int[][] t, int r, int c, int value) {
                for (int i = r; i < t.length; i |= i + 1)
                        for (int j = c; j < t[0].length; j |= j + 1)
                                t[j] += value;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        }

        public static int sum(int[][] t, int r, int c) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                int res = 0;
                for (int i = r; i >= 0; i = (i & (i + 1)) - 1). from: 1point3acres.com/bbs
                        for (int j = c; j >= 0; j = (j & (j + 1)) - 1)
                                res += t[j];
                return res;
        }

        public static int sum(int[][] t, int r1, int c1, int r2, int c2) {
                return sum(t, r2, c2) - sum(t, r1 - 1, c2) - sum(t, r2, c1 - 1) + sum(t, r1 - 1, c1 - 1);
        }

        public static int get(int[][] t, int r, int c) {. more info on 1point3acres.com
                return sum(t, r, c, r, c);
        }

        public static void set(int[][] t, int r, int c, int value) {
                add(t, r, c, -get(t, r, c) + value);. 1point3acres.com/bbs
        }.鏈枃鍘熷垱鑷1point3acres璁哄潧

        public static void main(String[] args) {
                int[][] t = new int[4][4];
                add(t, 0, 0, 1);
                add(t, 0, 1, 1); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                add(t, 1, 0, 1);. from: 1point3acres.com/bbs
                add(t, 1, 1, 1);-google 1point3acres

                System.out.println(4 == sum(t, 3, 3));
        }
}

补充内容 (2016-6-20 21:48):
非原创,某acm大神模板..背下来就好了...
回复 支持 反对

使用道具 举报

nevets 发表于 2016-6-20 22:05:02 | 显示全部楼层
blackrose 发表于 2016-6-20 21:33. more info on 1point3acres.com
只需要进行col dp,每次更新复杂度O(col),求sum O(row)

这就是我说的解法1.2啊
回复 支持 反对

使用道具 举报

pengpengche 发表于 2016-6-26 01:06:32 | 显示全部楼层
求问楼主,什么是2 sum bst, bst中找两个数和是target?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 08:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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