推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 13522|回复: 80
收起左侧

谷歌google跪经

  [复制链接] |试试Instant~ |关注本帖
gougou9903 发表于 2016-11-21 06:59:57 | 显示全部楼层 |阅读模式

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
MTV onsite.

1. 印度小哥,全程没有提示。这道题完全不知道怎么写,最后瞎写了一下。。。 题目:有一条公路,长度是m, 中间有k个加油站,由此我们可以得到一个加油站之间的最大距离,然后给你一个数t,这个数代表增加的加油站的数量(往里面插入),求使得加油站之间最大距离变得最小的值,返回这个最小的最大距离。感觉应该是个动态规划的问题。
2. 印度小哥,上来先问了问一个数组全是0,1,应该怎么sort. (bucket sort/ counting sort). 然后问题: Candy Crush. 假设要设计一个这样的游戏,我们有4种Candy, 然后有一个board(n * n), 规定在任何一行和一列上不能出现连续的3个相同的Candy, 如何设计这个游戏版。 这个游戏版是用于游戏的初始化,所以每次要尽可能的使版面随机,并且满足限制条件。
中午是个国人大哥,带吃饭非常爽
3. 白人小哥, leetcode 425 Wrod Squares 稍微修改了一下, 有重复,并且每个字的长度不一定相同, follow up : test cases 应该怎么写 (DFS + Trie) 没写完. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
4. 中国小哥, 提示很多。有一个数组,类似于:{{'Canada', 3}, {'USA', 5}, {'UK', 2}, {'Brasil', 3}}, 数组的类型是Country, 有两个变量, Country.name, Country.weight. 每个国家都有一个权重,然后给一个output()函数,每次调用这个函数的时候就输出一个国家的名字,要使每个国家被输出的概率相等。我用的方法是平摊weight: {Canada, Canada, USA, USA, USA, USA, UK, UK, Brasil, Brasil, Brasil}, 然后用Random 函数输出。Follow up : 如果这个权重的值很大很大,比如billio级别,应该怎么办。我的方法是类似于线段树,然后再用sum * Random(), 看这个区间坐落在哪里。

还是水平太差,滚回去继续刷题
. visit 1point3acres.com for more.
大米!!!





补充内容 (2016-11-21 09:52):. from: 1point3acres.com/bbs
第四题说错了,应该是输出的概率和权重匹配,就是canada应该是3/13, USA: 5/13

评分

5

查看全部评分

本帖被以下淘专辑推荐:

zzgzzm 发表于 2016-11-22 04:11:05 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
第二题candy crash: 这个好像就是随机的一行一行从左向右生在board上成均匀随机数{1, 2, 3, 4}。在位置(i,j)时,同时检查若纵向(i-1,j)与(i-2,j)的candy相同,那么(i,j)不能放这种candy;同理对横向(i,j-1), (i,j-2)同样处理。将不允许放的candy从{1, 2, 3, 4}去除然后再均匀分布生成。
  1. // candy at cell[i][j] could be 1, 2, 3 or 4
  2. vector<vector<int>> getRandCandyBoard(int n) {
  3.   vector<vector<int>> board(n, vector<int>(n));
  4.   // options[i][i]: candy options if candy i and j not allowed: O(1) time/space
  5.   vector<vector<vector<int>>> options(n, vector<vector<int>>(n));
  6.   for (int i = 0; i <= 4; ++i)
  7.   for (int j = 0; j <= 4; ++j) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  8.     for (int k = 1; k <= 4; ++k) if (k != i && k != j) options[i][j].push_back(k);
  9.   }  
  10.   -google 1point3acres
  11.   // O(n^2) time
  12.   for (int i = 0; i < n; ++i)
  13.   for (int j = 0; j < n; ++j) {. 1point3acres.com/bbs
  14.     int vert = 0, hor = 0; // not allowed candy
  15.     if (i > 1 && board[i-1][j] == board[i-2][j]) vert = board[i-1][j]; . 1point3acres.com/bbs
  16.     if (j > 1 && board[i][j-1] == board[i][j-2]) hor  = board[i][j-1];
  17.     board[i][j] = options[vert][hor][rand()%options[vert][hor].size()];
  18.   }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  19.   return board;
  20. }
复制代码

补充内容 (2016-11-24 07:12):
我的方法也未必是等概率的。用3X1的棋盘验证即可,若4种candy的话共有60种棋盘,但我的方法给出12种以概率1/48出现,48种以概率1/64出现。不是每个1/60的等概率。
回复 支持 3 反对 0

使用道具 举报

catinclay 发表于 2016-11-21 08:30:21 | 显示全部楼层
关注一亩三分地微博:
Warald
一样维持一个最大堆 里头放的结构类似这样. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
class Interval{
    int numberAdded;
    int distance;
}

numberAdded是“已经在这个区间加入的加油站的个数” 一开始所有都预设为0. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
distance就是形成著个区间的两个加油站之间的距离
. From 1point 3acres bbs
最大堆依照(distance/(numberAdded+1))做比较
每次poll堆顶的Interval出来 把该Interval的numberAdded+1, 直到加入了k个加油站.鐣欏璁哄潧-涓浜-涓夊垎鍦
此时堆顶的(Interval.distance/(numberAdded+1)) 就会是答案
. 1point3acres.com/bbs

补充内容 (2016-11-21 15:02):
堆顶poll出来, numberAdded+1之后还要放回堆里..

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

spwahaha 发表于 2016-11-22 04:42:32 | 显示全部楼层
第二题和楼主一样,不过是3种糖果,然后follow up是如何初始化使board一定有可以用一步可以消的棋子(初始化完成后不能直接死棋).... 讨论了很久,但是还是没回答出来,最后面试官说的方法挺tricky的。。
回复 支持 1 反对 0

使用道具 举报

zzgzzm 发表于 2016-11-21 14:28:18 | 显示全部楼层
第一题:这个题应该可以DP: 假设delta[]是相邻加油站的间距,并且是sorted(这个题与顺序无关,所以若不是sorted那么排序即可,i.e.,sorted假设不失一般性)。设dp[n-1][t]:=对delta[0,...,n-1]增加t个加油站所得到的最小最大间距,那么对delta[0,...,n]时,在delta[n]中必然至少放一个加油站才能让minMax最小,若在delta[n]中放i个(0<i<=t),那么自然在delta[0,...,n-1]中放了t-i个,所以转移方程就是
dp[n][t] = min(dp[n-1][t-i], delta[n]/(i+1)) 对 0<i<=t求最小。注意到dp[][t-i]对i是一定单调递增,而 delta[n]/(i+1)对i是一定单调递减,所以在[0, i)范围对i binary search求最小(即dp[n-1][t-i]与delta[n]/(i+1)最接近时最小)。时间复杂度O(n*t*log(t)). 不知道还有没有更快的。
  1. // assume delta is sorted and delta[] > 0.0
  2. double minmaxDelta(vector<double>& delta, int t) {
  3.   int n = delta.size();
  4.   // prev[tt]: minmaxDelta if adding tt points to delta[0,...,nn-1]
  5.   // cur[tt]: minmaxDelta if adding tt points to delta[0,...,nn]. Waral 鍗氬鏈夋洿澶氭枃绔,
  6.   auto prev(vector<double>(t+1)), cur(vector<double>(t+1));.1point3acres缃
  7.   for (int tt = 0; tt <= t; ++tt) prev[tt] = delta[0]/(tt+1); // initialize prev
  8.   for (int nn = 1; nn < n; ++nn) {
  9.     cur[0] = delta[nn];  
  10.     for (int tt = 1; tt <= t; ++tt) {
  11.       int L = 0, R = tt-1;
  12.       while (R - L > 1) { // binary search to solve delta[nn]/(tt - i + 1) == prev[i]. Waral 鍗氬鏈夋洿澶氭枃绔,
  13.         int mid = L + (R-L)/2, i = (int)delta[nn]/(tt - mid + 1);
  14.         if (i > prev[i]) R = mid; else L = mid;. 1point 3acres 璁哄潧
  15.       }
  16.       cur[tt] = min(max(prev[L], delta[nn]/(tt-L+1)), max(prev[R], delta[nn]/(tt-R+1)));      . from: 1point3acres.com/bbs
  17.     }
  18.     for (int tt = 0; tt <= t; ++tt) prev[tt] = cur[tt]; // update prev[]
  19.   }
  20.   return cur[t];
  21. }
复制代码
回复 支持 1 反对 0

使用道具 举报

LockOn 发表于 2016-11-21 07:26:57 | 显示全部楼层
第一题怎么感觉是维护一个最大堆,保存各个加油站之间的距离。。。每次加入一个堆,就把取出堆顶maxD,然后再把maxD/2或maxD/2+1放进堆里。。。
第二题楼主怎么做的呀,求点思路。
还有第四题,要求使每个国家被输出的概率相等?如果这样的话,和权重有关系吗。。。不是只和国家数量有关了么。。。
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-21 07:50:07 | 显示全部楼层
LockOn 发表于 2016-11-21 07:26.鏈枃鍘熷垱鑷1point3acres璁哄潧
第一题怎么感觉是维护一个最大堆,保存各个加油站之间的距离。。。每次加入一个堆,就把取出堆顶maxD,然后 ...

第一題那樣會錯

补充内容 (2016-11-21 08:21):
想了一下 好像可以根據這個為基礎得到正確的解法 等等貼我的想法
回复 支持 反对

使用道具 举报

 楼主| gougou9903 发表于 2016-11-21 09:52:09 | 显示全部楼层
LockOn 发表于 2016-11-21 07:26
第一题怎么感觉是维护一个最大堆,保存各个加油站之间的距离。。。每次加入一个堆,就把取出堆顶maxD,然后 ...

第一题直接这样做是不对的,我一开始也是这么想的,小哥说不对,但是没给提示。你可以举个例子看看。.鏈枃鍘熷垱鑷1point3acres璁哄潧
第二题我的方法不知道对不对,就是建一个VISITED数组,然后用random()函数随机取出一个candy, 然后以它为基准上下左右看符不符合标准,不符合就重新在剩余的set中随机取出一个。他没有说不对,但是我感觉概率上还是不够随机?
第四题我好像说错了,应该是输出的概率和权重匹配,就是canada应该是3/13, USA: 5/13
回复 支持 反对

使用道具 举报

zj45499 发表于 2016-11-21 10:58:45 | 显示全部楼层
第一题是啥意思..
楼主能不能举个栗子?
回复 支持 反对

使用道具 举报

 楼主| gougou9903 发表于 2016-11-21 12:41:25 | 显示全部楼层
zj45499 发表于 2016-11-21 10:58
第一题是啥意思..
楼主能不能举个栗子?

假设有条公路长度为500m,在0,100,200,300,500处有加油站,我们可以得到最大距离是200(300 - 500)。然后我们往里面插入3个加油站,任意位置都可以,求加油站间距最大值的最小可能值。比如我们先插入到350,那么最大距离就变成了150。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-21 14:36:53 | 显示全部楼层
zj45499 发表于 2016-11-21 10:58
第一题是啥意思..
楼主能不能举个栗子?

这个题可以这么直观的看成一个数学问题:给定一些实数x1 < x2 < ... < xn,现在然你随意在(x1, xn)区间内再插入t个实数,使得插入之后的(n+t)个数尽量均匀间距。

因为数学上很容易证明:当范围(xn-x1)和n固定时,只有等差数列的minMax:=min_j(x[j+1]-x[j])是最小的。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-21 14:56:55 | 显示全部楼层
LockOn 发表于 2016-11-21 07:26
第一题怎么感觉是维护一个最大堆,保存各个加油站之间的距离。。。每次加入一个堆,就把取出堆顶maxD,然后 ...

第一题贪心算法是不行的,比如两个间距1,9。要求再加2个点。最优结果应该是3,但贪心算法结果为4。因为贪心算法每次只考虑一个点,无法预见二等分以上的情况。
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-21 14:57:59 | 显示全部楼层
zzgzzm 发表于 2016-11-21 14:28.鏈枃鍘熷垱鑷1point3acres璁哄潧
第一题:这个题应该可以DP: 假设delta[]是相邻加油站的间距,并且是sorted(这个题与顺序无关,所以若不是s ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
能否看一下我在4楼的贴子?我感觉我只需要O(lgk * n)
k = 初始的间距数量
n = 插入的加油站数

补充内容 (2016-11-21 14:59):-google 1point3acres
包含一開始的建立heap應該是O(k + lgk * n)
回复 支持 反对

使用道具 举报

LockOn 发表于 2016-11-21 15:16:14 | 显示全部楼层
zzgzzm 发表于 2016-11-21 14:56
第一题贪心算法是不行的,比如两个间距1,9。要求再加2个点。最优结果应该是3,但贪心算法结果为4。因为 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
谢谢反例~想太简单了
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-22 01:23:11 | 显示全部楼层
catinclay 发表于 2016-11-21 14:57
能否看一下我在4楼的贴子?我感觉我只需要O(lgk * n)
k = 初始的间距数量
n = 插入的加油站数

说真的,我很佩服你的max heap设计!不算初始化heap,你是时间复杂度的确只有O(n*logk),而我的DP不算初始化排序时间O(n*k*logn)太慢了。
.1point3acres缃
你的这个max heap真的很巧妙,我把你的描述用数学严格证明一下:(纯娱乐了。。。)因为我刚看到这个题的时候就感觉是个数学问题。

给定正数列{d_j} (1<=j<=N)和整数C>=0,求非负整数列k = {k_j}最优解使得目标函数F_c(k)最小化:
F_c(k) := Max_j(d_j/(k_j+1)), 其中k = {k_j}的元素总和为C.
对于C=0, 显然每个k_j = 0 (1<=j<=N)为最优解。
若对于C的最优解为{k_j}, 那么对于C+1的最优解如下构造:. 1point 3acres 璁哄潧
存在指标j’(1<=j’<=N)使得d_j’/(k_j’+1) = F_c(k), 那么将{k_j}中的k_j’换为1+k_j’,其它不变,一定是对于C+1的最优解(最小化F_{c+1})。.鏈枃鍘熷垱鑷1point3acres璁哄潧
证明:证明k_1, k_2, …, 1+k_j’,…,k_N是F_{c+1}的最优解,就是等价于对任意解{g_j}(总和为C+1),证明:
对任意j!=j’有d_j/(k_j+1) <= F_{c+1}(g) 以及d_j’/(k_j’+2) <= F_{c+1}(g)。(*). From 1point 3acres bbs
分两种情况:
1. 若g_j’ = 0,那么d_j/(k_j+1) <= d_j’/(k_j’+1)<=d_j’<=F_{c+1}(g),并且d_j’/(k_j’+2)<= d_j’<=F_{c+1}(g).
2. 若g_j’>0,那么g_1, g_2, …, g_j’-1,…,g_N是F_c的一个解,但我们已假设F_c的最优解为{k_j},所以d_j’/(k_j’+1) = F_c(k)<= max(d_j*/(g_j*+1), d_j’/g_j’)对于某个j* != j’。
若 d_j*/(g_j*+1)>= d_j’/g_j’,那么d_j/(k_j+1)<= d_j’/(k_j’+1)<=d_j*/(g_j*+1)<=F_{c+1}(g),并且d_j’/(k_j’+2)< d_j’/(k_j’+1)<= d_j*/(g_j*+1)<=F_{c+1}(g),所以结论(*)得证。
否则d_j*/(g_j*+1) < d_j’/g_j’,那么d_j’/(k_j’+1)< d_j’/g_j’,所以k_j’+1>g_j’,即k_j’>=g_j’。  那么d_j’/(k_j’+2)< d_j’/(g_j’+1)<=F_{c+1}(g),并且d_j/(k_j+1)<= d_j’/(k_j’+1)<= d_j’/(g_j’+1)<=F_{c+1}(g),所以结论(*)得证。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2016-11-22 02:46):. From 1point 3acres bbs
我是对于坐标为一般的double类型分析的,若是int类型的话应该也不影响实现。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-22 03:07:13 | 显示全部楼层
第四题:这个题貌似很喜欢考
  1. string getCountryByWeight(vector<pair<string, double>>& cw) {
  2.   vector<double> pdf = {0.0}; double sum = 0.0;
  3.   for (auto& x:cw) { // create probability distribution function (pdf). visit 1point3acres.com for more.
  4.     pdf.push_back(pdf.back()+x.second);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  5.     sum += x.second;
  6.   }
  7.   for (auto& p:pdf) p /= sum;
  8.   int i = lower_bound(pdf.begin(), pdf.end(), rand()/RAND_MAX) - pdf.begin();
  9.   return cw[i-1].first;
  10. }
复制代码
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-22 03:10:32 | 显示全部楼层
zzgzzm 发表于 2016-11-22 01:23. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
说真的,我很佩服你的max heap设计!不算初始化heap,你是时间复杂度的确只有O(n*logk),而我的DP不算初 ...

我比较佩服你能用dp解...我是刚好灵光乍现想到的..
回复 支持 反对

使用道具 举报

flashpacker 发表于 2016-11-22 03:22:01 | 显示全部楼层
...竟然当场写Word squares II,有点狠啊
回复 支持 反对

使用道具 举报

flashpacker 发表于 2016-11-22 03:22:31 | 显示全部楼层
感觉第一题有点像lc410?
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-22 04:19:47 | 显示全部楼层
catinclay 发表于 2016-11-22 03:10
我比较佩服你能用dp解...我是刚好灵光乍现想到的..

DP基本相当于暴力解了,correctness比较显然但效率低。
Max Heap在每次加入点后及时优化自动调出当前的max subinterval(max heap), 高效率。就是correctness要证明还真不容易。
回复 支持 反对

使用道具 举报

doorkeeper 发表于 2016-11-22 04:30:04 | 显示全部楼层
zzgzzm 发表于 2016-11-22 01:23
说真的,我很佩服你的max heap设计!不算初始化heap,你是时间复杂度的确只有O(n*logk),而我的DP不算初 ...
. 鍥磋鎴戜滑@1point 3 acres
这个heap的复杂度是O(k*logn)吧,虽然应该也没什么差别. 1point 3acres 璁哄潧
证明的话induction可以更清晰一些,可以直接比较最后答案得到结论,不过应该都差不多
DP的话不单调优化确实比较好想,我觉得两种算法都很不错,当然从复杂度考虑确实heap更巧妙一些
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-28 10:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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