一亩三分地论坛

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

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

Google onsite 面经

  [复制链接] |试试Instant~ |关注本帖
feihuatongxue 发表于 2016-5-6 03:28:28 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 猎头 - Onsite |Other其他

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

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

x
1. there are m piles of coins, each pile is consisted of coins with different values. you are allowed to take n coins home. However, you can only take coins from the top of each pile. What's the maximum value you can obtain.
2. output all same sub-tree pairs.
3. output the intersection between two list, O(1) space
4. Remove duplicate characters in a string
5. find longest consecutive path in tree, not necessary binary tree.鐣欏璁哄潧-涓浜-涓夊垎鍦
6. given a list, the query will be a range, return the maximum number within this range, what if there are 1000 queries per second.. 鍥磋鎴戜滑@1point 3 acres
7. detect cycle in a graph.

lots of follow up questions. They do care about space complexity.

大米,求祝福!!攒人品!!

评分

6

查看全部评分

本帖被以下淘专辑推荐:

william_gong 发表于 2016-8-2 12:49:41 | 显示全部楼层
第一题的dp, 有人能帮忙看看吗?


public int maxValue(int[][] pile, int num) {
                if (num == 0) {
                        return 0;
                }
               
                int[][] dp = new int[pile.length][num + 1];
                int temp = 0;
                for (int i = 0; i < num + 1; i++) {
                        dp[0][i] = temp;
                        if(i < pile[0].length)
                                temp += pile[0][i];
                }
                . visit 1point3acres.com for more.
                int res = 0;
                for (int i = 1; i < pile.length; i++) {
                        for (int j = 0; j < num + 1; j++) {
                                temp = 0;
                                for (int k = 0; k <= j; k++) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                        dp[i][j] = Math.max(dp[i][j], temp + dp[i - 1][j - k]);. 鍥磋鎴戜滑@1point 3 acres
                                        res  = Math.max(res, dp[i][j]);
                                        if(k < pile[i].length)
                                                temp += pile[i][k];. From 1point 3acres bbs
                                }
                        }
                }.鐣欏璁哄潧-涓浜-涓夊垎鍦
               
                return res;
        }

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

CrossTheWall 发表于 2016-5-6 15:16:47 | 显示全部楼层
edcent 发表于 2016-5-6 12:55
第二题subtree pairs楼主怎么做的?

后序遍历树, 这个过程跟踪每个结点的后序 serialized string, string相同说明子树相同
回复 支持 1 反对 1

使用道具 举报

tcomein2009 发表于 2016-5-6 14:10:28 | 显示全部楼层
feihuatongxue 发表于 2016-5-6 13:07
第一题可以用递归解,或者可以建立一个dp的matirx,这个是最好的。要注意考虑pile的金币数量不同的问题。
. From 1point 3acres bbs
谢楼主分享。
.1point3acres缃
请问第一题 两个pile里的coin是顺序已经固定了吗?. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
.鏈枃鍘熷垱鑷1point3acres璁哄潧
那样的话只有n+1种取的可能. 鍥磋鎴戜滑@1point 3 acres
从第一个pile取0,第二个取n
从第一个取1,第二个取n-1
取2,第二个n-2
。。。
取n,第二个0
回复 支持 0 反对 1

使用道具 举报

lcn 发表于 2016-7-30 14:08:17 | 显示全部楼层
sapphirew 发表于 2016-6-21 12:38
不对吧,得中序+前/后序才可以吧

如果加括号来标识子树,那么三种遍历结果的解读都是唯一的。这题应该是serialize整棵树得到string,然后serialize每个子树并在前述完整string中查找,用kmp的话是o(n),乘以子树数目结果就是o(n^2);如果不用kmp就是o(n^3)。不过o(n^3)的话,不如直接用每个sub-tree进行isSubTree查找。
回复 支持 1 反对 0

使用道具 举报

tcomein2009 发表于 2016-5-7 00:58:43 | 显示全部楼层
CrossTheWall 发表于 2016-5-6 15:16
后序遍历树, 这个过程跟踪每个结点的后序 serialized string, string相同说明子树相同

同意。前序也一样
回复 支持 0 反对 1

使用道具 举报

sapphirew 发表于 2016-6-21 12:38:23 | 显示全部楼层
tcomein2009 发表于 2016-5-7 00:58
同意。前序也一样

不对吧,得中序+前/后序才可以吧
回复 支持 1 反对 0

使用道具 举报

hidden_track 发表于 2016-5-21 05:11:45 | 显示全部楼层
feihuatongxue 发表于 2016-5-17 01:49. Waral 鍗氬鏈夋洿澶氭枃绔,
en , pass了。。。

第一题是可以recursive做,但是太慢,然后可以结合DP做

楼主可以给个DP转移方程吗?谢谢~

补充内容 (2016-5-21 05:14):
感觉像背包....
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-5-6 03:47:43 | 显示全部楼层
For #1, sort each pile of coin first ?
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-5-6 03:48:10 | 显示全部楼层
感谢楼主分享面经,请问一下5. find longest consecutive path in tree, not necessary binary tree,这一题,consecutive path一定可以是从根节点到子节点吗? 还是说也可以从子节点到根节点再到子节点(就是先上后下)。
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-5-6 04:40:33 | 显示全部楼层
题目都挺常规的,祝LZ早日拿到offer!
回复 支持 反对

使用道具 举报

Yoyo00 发表于 2016-5-6 06:42:32 | 显示全部楼层
能请问一下第一题怎么做吗
回复 支持 反对

使用道具 举报

u-r-the-one 发表于 2016-5-6 07:59:13 | 显示全部楼层
Lz能讲一下第一题怎么做的吗?
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-5-6 12:12:01 | 显示全部楼层
第一个应该是最大堆吧,priority_queue<pair<coins_val, pair<piles_index, index_inPiles>>,直到res size == n,或者queue空为止。
回复 支持 反对

使用道具 举报

CrossTheWall 发表于 2016-5-6 12:34:11 | 显示全部楼层
mingzhou1987 发表于 2016-5-6 12:12
第一个应该是最大堆吧,priority_queue

应该不是, 比如一个很大的pile, 最后有个很大的值(大于其余的和),前面的都很小, 那么按一般的最大堆很可能取不到这个值
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-5-6 12:49:15 | 显示全部楼层
CrossTheWall 发表于 2016-5-6 12:34
应该不是, 比如一个很大的pile, 最后有个很大的值(大于其余的和),前面的都很小, 那么按一般的最大 ...

同意。 我的想法是backtracking。
回复 支持 反对

使用道具 举报

edcent 发表于 2016-5-6 12:55:34 | 显示全部楼层
第二题subtree pairs楼主怎么做的?
回复 支持 反对

使用道具 举报

Altynai 发表于 2016-5-6 13:06:01 | 显示全部楼层
第一题是dp吧,只能从top往下取,dp[i][j]表示前i堆取j个的最大值,转移:for k in 0...size[i+1],  dp[i][j] = max(dp[i][j], dp[i-1][j - k] + value[i][k])
回复 支持 反对

使用道具 举报

 楼主| feihuatongxue 发表于 2016-5-6 13:07:27 来自手机 | 显示全部楼层
第一题可以用递归解,或者可以建立一个dp的matirx,这个是最好的。要注意考虑pile的金币数量不同的问题。
回复 支持 反对

使用道具 举报

Altynai 发表于 2016-5-6 13:08:38 | 显示全部楼层
第六题就是rmq的变种,存的就是区域内的最大值,但是只是list不可变的情况
如果list可变,可以用线段树做
回复 支持 反对

使用道具 举报

Altynai 发表于 2016-5-6 13:16:43 | 显示全部楼层
3. output the intersection between two list, O(1) space
这题先算一下两个指针对应list的长度,然后二分枚举一下交叉以后公共部分的长度,也是o(nlogn)吧

5. find longest consecutive path in tree, not necessary binary tree

这个dfs的时候要记录每个子节点到叶子节点的最大值,然后取当前节点中前两大的相加,同时更新全局的answer

7. detect cycle in a graph.

dfs + 用visited数据标记.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 反对

使用道具 举报

 楼主| feihuatongxue 发表于 2016-5-6 13:19:30 来自手机 | 显示全部楼层
Altynai 发表于 2016-5-6 13:06. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第一题是dp吧,只能从top往下取,dp[j]表示前i堆取j个的最大值,转移:for k in 0...size,  dp[j] = max(dp ...

转移方程不对。
回复 支持 反对

使用道具 举报

didi2 发表于 2016-5-6 13:20:25 | 显示全部楼层
祝lz早日拿到offer
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-5-6 13:26:17 | 显示全部楼层
Altynai 发表于 2016-5-6 13:16
3. output the intersection between two list, O(1) space
这题先算一下两个指针对应list的长度,然后二 ...

第三题 应该是O(n)吧, 如果求两个linked list的intersection。 计算长度diff, 让长的start point在diff 处, 然后比较。
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-5-6 13:39:29 | 显示全部楼层
多谢指正,想的不周全,backtrack确实比较直观
回复 支持 反对

使用道具 举报

CrossTheWall 发表于 2016-5-6 14:00:29 | 显示全部楼层
Yoyo00 发表于 2016-5-6 06:42. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
能请问一下第一题怎么做吗

等价于所有队列的最大前缀和的和, 约束是满足前缀下标和为n
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 08:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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