一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 6692|回复: 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.. Waral 鍗氬鏈夋洿澶氭枃绔,
7. detect cycle in a graph.. more info on 1point3acres.com

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) {. Waral 鍗氬鏈夋洿澶氭枃绔,
                if (num == 0) {
                        return 0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                }. 1point 3acres 璁哄潧
               
                int[][] dp = new int[pile.length][num + 1];. 1point3acres.com/bbs
                int temp = 0;
                for (int i = 0; i < num + 1; i++) {
                        dp[0][i] = temp;
                        if(i < pile[0].length)
                                temp += pile[0][i];
-google 1point3acres                }
                -google 1point3acres
                int res = 0;. from: 1point3acres.com/bbs
                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]);. visit 1point3acres.com for more.
                                        res  = Math.max(res, dp[i][j]);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                        if(k < pile[i].length)
                                                temp += pile[i][k];
                                }
                        }. from: 1point3acres.com/bbs
                }
               
                return res;. more info on 1point3acres.com
        }

评分

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的金币数量不同的问题。

谢楼主分享。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
请问第一题 两个pile里的coin是顺序已经固定了吗?.1point3acres缃
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
那样的话只有n+1种取的可能
从第一个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
en , pass了。。。

第一题是可以recursive做,但是太慢,然后可以结合DP做
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
楼主可以给个DP转移方程吗?谢谢~
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (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. 1point3acres.com/bbs

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. visit 1point3acres.com for more.
这题先算一下两个指针对应list的长度,然后二 ...
.1point3acres缃
第三题 应该是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, 2017-1-20 11:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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