一亩三分地论坛

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

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

Google MTV Onsite 面经+感想

[复制链接] |试试Instant~ |关注本帖
rufa 发表于 2015-10-3 14:34:23 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
今天Youtube College Weekend刚面的~


1. 华人大叔。题目:Given a large integer array, count the number of triplets whose sum is less than or equal to an integer T..鐣欏璁哄潧-涓浜-涓夊垎鍦
大叔英文很地道, 全程态度比较认真,不冷不热。一开始猛然间以为是3-Sum的题,仔细想想不太一样,细节问题挺多。最后写了一个O(n2lgn)的算法,然后问大叔更简便的有木有,大叔迟疑了片刻说应该有数学相关的取巧办法。。. more info on 1point3acres.com


2. 华人小哥。题目:Given an array of Ad (profit, start_time, end_time) and a timespan [0, T], find the max profit of Ads that fit the timespan.
小哥进来就说了句中文:怎么样啊?顿觉好温暖,中文寒暄了几句就用英文开始了。先说了穷举法O(2^n), 然后说了贪心法(不是最优解),最后用DP解决。小哥态度灰常好,给了很有用的提示, 就像自家人啊。


3. 俄罗斯妹子。题目:M x N large board, with only white and black blocks, all black blocks are connected (vertically or horizontally), find the minimum rectangle boundary that contains all black blocks.
妹子笑的好甜,全程一直在笑,还好心地给了提示和假定。感觉交流互动非常好,可惜最后差了一点,没能想出O(n^2)以内的算法。. 1point 3acres 璁哄潧
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

4. 美国小哥。题目:Design a algorithm to initialize the board of Candy Crush Saga. With M x N board, Q types of candies. (Rules: no 3 for run after initialization, must contain at least one valid move at the beginning)
小哥说话很和气,先让我介绍了一个project,于是兴致勃勃地讲了做过的一个游戏。他于是拿出手机给我看了这个,说那就出一道游戏题吧。。游戏可以参考(. visit 1point3acres.com for more.
http://candycrushsaga.com/how-to-play),这道题很开放,没有固定模式和答案,感觉答的还不错。

大家加油~

评分

6

查看全部评分

本帖被以下淘专辑推荐:

 楼主| rufa 发表于 2015-10-5 01:28:23 | 显示全部楼层
say543 发表于 2015-10-4 14:08
同求第二题DP解法? 我的想法是要先sort by ending time 然后2维dp index 1 是第几个AD index2 是time span. ...

我当时也是这个思路~ 先按照end_time升序排列,然后列DP方程:f(i,t) = max{ (f(i-1,t), f(i-1,start) + profit) }.1point3acres缃
.1point3acres缃
其中i是当前考察的Ads数组元素下标,t是当前可用的结束时间,递归函数代码如下:
int f(int i, int t) {
    if(i < 0 || t == 0) return 0;
    int max = f(i-1, t);
    if(end <= t) {
        int tmp = f(i-1, start) + profit;
        if(tmp > max) max = tmp;
    }.鐣欏璁哄潧-涓浜-涓夊垎鍦
    return max;
}

不我觉得复杂度只是O(N * T), N是广告个数,T是时间跨度。我们需要求的最大利润是f(N-1, T)。后面优化说了用哈希表记忆已经求出来的子结果,避免重复计算。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我写了一段测试代码,试了一些比较简单的情况,暂时没发现问题。欢迎大家指正~
#include <iostream>. more info on 1point3acres.com
using namespace std;
. Waral 鍗氬鏈夋洿澶氭枃绔,
int f(int i, int t, int start[], int end[], int profit[]) {
    if(i < 0 || t == 0) return 0;
    int max = f(i-1, t, start, end, profit);
    if(end <= t) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        int tmp = f(i-1, start, start, end, profit) + profit;-google 1point3acres
        if(tmp > max) max = tmp;.鏈枃鍘熷垱鑷1point3acres璁哄潧
    }
    return max;
}

int main()
{
    int start[] = {0,0,1};
    int end[] = {1,2,3};
    int profit[] = {1,3,1};
    int T = 3;
    int len = sizeof(start) / sizeof(int);.鐣欏璁哄潧-涓浜-涓夊垎鍦
    cout << f(len-1, T, start, end, profit) << endl;
    return 0;
}
. more info on 1point3acres.com



. 1point3acres.com/bbs








回复 支持 反对

使用道具 举报

 楼主| rufa 发表于 2015-10-5 02:23:37 | 显示全部楼层
mileschen2008 发表于 2015-10-4 07:42
楼主能说说第四题怎么答的么?
.1point3acres缃
先把Candy简化成数字,类型数组就成了[0, 1, 2, ..., Q-1]。规则一共三条:随机(至少玩家看上去是);不能一开始就有3个共线的;开局至少有一步能保证有消除(不然没法玩。。)

1. 我首先关注的是前两条规则,因为觉得第三条只是小修改(尽管如果初始化完成后,再修改成符合第三条,可能导致连锁反应)。因为“随机”一直在我心头挥之不去,所以首先想到的是遍历所有格子,每次随机挑一个Q放进去,但立刻意识到这样很有可能导致死锁,尤其Q很小的时候,然后举了个死锁的例子。

2. 因为之前考虑过Q很小,所以最简单就是{0, 1}两种,立刻想到国际象棋棋盘:两色相间一定能填满而且无冲突。然后想到能不能先按照国际象棋棋盘填满,然后在这个基础上进行”随机化“。假如我有个遵循前两条规则的函数random(),对棋盘进行随机化。因为是在01棋盘改,所以第一遍下来可能还是很”假“,但既然这个函数是遵循前两条规则的,那么大可放心的多执行几遍。就像PS的滤镜叠加使用~ 然后开始讨论这个random()函数,大体思路是遍历棋盘,对每个格子有0.5 的概率进行”尝试修改“。(随机化就是一个慢慢tweak的过程,这个参数后面提到要根据实际效果调整)。尝试修改的算法就是:q = random(0, Q); 以q为中心向上下左右四个方向,一共有6条长度为3的线会造成潜在冲突,因此逐个检查一遍,假如无冲突就把当前位置替换为q。最后根据实际效果决定是否再来几次~

3. 然后就剩第三条规则:开局至少有一步能走。我上面阐述的时候就一直有个感觉,每局开始看似随机但一定有定势。然后让小哥打开手机游戏开了两局看了下,果然,每局开头一定会有{V型, _/型} 中的一种或两种排列,保证挪一步就能消除。跟小哥聊了这个想法之后,我的做法就是01棋盘生成后,随机选一个排列,比如V型,然后在棋盘上随机选一个(也可以多个)位置,把这个位置画出的V全部mark成不可修改。然后在这个基础上跑上面提到的random()算法。第三条规则也可以有很多随机性,必须类型选择,类型对应位置、个数的选择。

聊到这儿已经超时了。我问小哥这背后怎么实现的,他说他也不知道。。感觉这题很开放,不一定涉及多么高级的算法,几个随机参数的调整或许就能让开局看上去足够无规律了。

大家有什么想法欢迎交流~

评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| rufa 发表于 2015-10-5 04:52:13 | 显示全部楼层
第一题有人指出是LeetCode新题3Sum Smaller,先排序,再双指针O(n^2)就可以,参考http://www.cnblogs.com/jcliBlogger/p/4736809.html
回复 支持 反对

使用道具 举报

pengzewen37 发表于 2015-10-7 03:13:24 | 显示全部楼层
第二题 应该是类似背包问题,先把ads按照endTime排好序,然后两层for循环,i,j, i代表时间,j代表ad,dp[i][j]一开始设为dp[i][j - 1], 第j个广告取不取,取决于,是否它的endtime小与i的时间,并且加上他的profit大于现在dp[i][j - 1]的profit
for (int i = 0; i <= time; i++) {-google 1point3acres
        for (int j = 1; j <= ads.length; j++) {
                profit[i][j] = profit[i][j - 1];. From 1point 3acres bbs
                if (ads[j - 1].endTime <= i) {. Waral 鍗氬鏈夋洿澶氭枃绔,
                    profit[i][j] = Math.max(profit[i][j], profit[ads[j - 1].startTime][j - 1] + ads[j - 1].profit);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                }
            }
        }
        int max = 0;
        for (int i = time; i >= 0; i--) {
            max = Math.max(max, profit[i][ads.length]);
        }
        return max;
回复 支持 4 反对 0

使用道具 举报

flexwang 发表于 2015-10-5 10:35:30 | 显示全部楼层
第二题可以这样:
1. 先对所有的ad按照结束时间,从小到大排序;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
2. dp[i]代表排序后前i-1的广告的最大收益,那么dp[0] = 0;
3. 对于第i个广告,有选和不选两种可能,如果选的话,就要从第i-1个广告往前,找到和第i个广告不重合为止,假设找到了j,那么dp[i] = max(dp[i-1], dp[j]+profit[i])
时间复杂度的O(n^2),如果第3步用二分,就可以变成O(nlogn)
回复 支持 3 反对 0

使用道具 举报

怪兽岛 发表于 2015-10-7 02:06:24 | 显示全部楼层
宝贝忆彼岸 发表于 2015-10-7 00:34. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我觉得广告那题如果最后的结果只是max profit,DP应该是可以做到 time complexityO(T), space complexity O( ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
DP是只需要O(n), 但排序需要O(nlogn)啊
回复 支持 1 反对 0

使用道具 举报

flexwang 发表于 2015-10-4 21:06:25 | 显示全部楼层
第三题是啥意思?找到最小的矩形包含所有的黑色格子吗

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

kelvinzhong 发表于 2015-10-3 14:55:05 | 显示全部楼层
为什么第一题的解法是n^2lgn? 3sum的解法不是n^2就行了吗?
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-10-3 15:42:17 | 显示全部楼层
kelvinzhong 发表于 2015-10-3 14:55
为什么第一题的解法是n^2lgn? 3sum的解法不是n^2就行了吗?

估计LZ的做法是,穷举两点,然后二分找第三个点。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
其实我还是对那个俄罗斯妹子比较感兴趣 :)
回复 支持 反对

使用道具 举报

zxy_snow 发表于 2015-10-3 17:12:23 | 显示全部楼层
楼主,第三题意思是M*N的矩阵,里面有k个黑块?黑块是格子么还是?你说的复杂度O(N^2),是M*N么,可是怎么扫不都要扫一遍格子?还是理解有误。。
回复 支持 反对

使用道具 举报

kayv 发表于 2015-10-3 23:00:42 | 显示全部楼层
第三题貌似是遍历玩board 记录 最left,最top,最bottom,最right坐标就可以了吧。。。。 应该是O(n*m)

如果n*m很大,还有一种方法是先指定一个黑点(如果不让指定,可以随机猜),因为黑点都是connected的,所以可以用递归搜索黑点,搜索的同时记录最left,最top,最bottom,最right坐标
就像图像填充里的floor fill,如果黑点的个数是K,复杂度就是O(K)
回复 支持 反对

使用道具 举报

 楼主| rufa 发表于 2015-10-4 02:44:23 | 显示全部楼层
kelvinzhong 发表于 2015-10-3 14:55. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
为什么第一题的解法是n^2lgn? 3sum的解法不是n^2就行了吗?

这个题要求小于等于T, 3sum是恰好等于T吧,不太一样。有负数的情况比较恶心,提前退出条件就不那么容易满足了
回复 支持 反对

使用道具 举报

 楼主| rufa 发表于 2015-10-4 02:45:57 | 显示全部楼层
Wizmann 发表于 2015-10-3 15:42
估计LZ的做法是,穷举两点,然后二分找第三个点。

其实我还是对那个俄罗斯妹子比较感兴趣 :)

差不多吧~ 我也很感兴趣,那温暖的笑容直接流淌进心底啊啊啊
回复 支持 反对

使用道具 举报

 楼主| rufa 发表于 2015-10-4 02:48:34 | 显示全部楼层
zxy_snow 发表于 2015-10-3 17:12
楼主,第三题意思是M*N的矩阵,里面有k个黑块?黑块是格子么还是?你说的复杂度O(N^2),是M*N么,可是怎么 ...

恩,是这个意思。感觉是不一定都得把所有格子访问一遍,但是极端情况全黑或全白仍然要都访问
回复 支持 反对

使用道具 举报

 楼主| rufa 发表于 2015-10-4 02:52:03 | 显示全部楼层
kayv 发表于 2015-10-3 23:00. Waral 鍗氬鏈夋洿澶氭枃绔,
第三题貌似是遍历玩board 记录 最left,最top,最bottom,最right坐标就可以了吧。。。。 应该是O(n*m)

...

对,你这个方法我想到了,俄罗斯妹子直接说那就随机给你一个黑点好了~~然后我用BFS的复杂度就是O(K),但是极端情况假如全都是黑点,一样是O(M*N)了。感觉这个有点博弈,看黑的多白的多。如果黑的多就从外侧包围更快,白的多从黑的开始搜索更好吧。。总之感觉这题很有意思,妹子中间给我画了一个宽度为1的黑格子螺旋线,那叫一个美。。。
回复 支持 反对

使用道具 举报

kidzlike 发表于 2015-10-4 04:46:04 | 显示全部楼层
lz能否详细解释一下第二题呢?谢谢
回复 支持 反对

使用道具 举报

AirDreamer 发表于 2015-10-4 07:33:55 | 显示全部楼层
同求第二题dp 解法~
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-10-4 07:42:50 | 显示全部楼层
楼主能说说第四题怎么答的么?
回复 支持 反对

使用道具 举报

zxy_snow 发表于 2015-10-4 10:46:38 | 显示全部楼层
rufa 发表于 2015-10-4 02:48. 1point 3acres 璁哄潧
恩,是这个意思。感觉是不一定都得把所有格子访问一遍,但是极端情况全黑或全白仍然要都访问

如果是这个的话,是不是找黑格子的最小的x坐标最小的y坐标,最大的x坐标,最大的y坐标就可以了?
回复 支持 反对

使用道具 举报

zxy_snow 发表于 2015-10-4 10:47:32 | 显示全部楼层
rufa 发表于 2015-10-4 02:52
对,你这个方法我想到了,俄罗斯妹子直接说那就随机给你一个黑点好了~~然后我用BFS的复杂度就是O(K),但 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
刚看到这个,表示那妹子脑洞还挺大~是个好题。。
回复 支持 反对

使用道具 举报

zxy_snow 发表于 2015-10-4 10:48:53 | 显示全部楼层
我好奇你第四题怎么解的,随机生成格子,然后改么?
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-10-4 10:50:41 | 显示全部楼层
楼主, 第一题可以举个例子吗?

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

yyz999 发表于 2015-10-4 11:07:31 | 显示全部楼层
rufa 发表于 2015-10-4 02:52
对,你这个方法我想到了,俄罗斯妹子直接说那就随机给你一个黑点好了~~然后我用BFS的复杂度就是O(K),但 ...

给了初始点就直接二分查找两侧边界呗,没给初始点那就得从中间开始先二分查找初始点,稍微复杂一点。
复杂度应该能控制在O(nlog(m)) m>n
回复 支持 反对

使用道具 举报

say543 发表于 2015-10-4 14:05:52 | 显示全部楼层
hsmwz34 发表于 2015-10-4 03:03
第一题是定下一点,然后从后面用two pointer,每次都左边不动先动右边,然后他们之间的距离就是pair的个数 ...

第一题你这个作法是o(n^3) 吧? 因该没有用binary search 来的好?
回复 支持 反对

使用道具 举报

say543 发表于 2015-10-4 14:08:19 | 显示全部楼层
同求第二题DP解法? 我的想法是要先sort by ending time 然后2维dp index 1 是第几个AD index2 是time span. 每次填表要check 最多n个ads. time complexity 是o( n*m*m) m: number of ads, n: 0-n timespan 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 11:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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