[八我司] 介绍一下Uber tech stack和各个大组的情况

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 16562|回复: 86
收起左侧

谷歌google跪经

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

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

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

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

x
MTV onsite.
. From 1point 3acres bbs
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) 没写完. 围观我们@1point 3 acres
4. 中国小哥, 提示很多。
游客,本帖隐藏的内容需要积分高于 155 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.


还是水平太差,滚回去继续刷题

大米!!!.本文原创自1point3acres论坛





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

评分

6

查看全部评分

本帖被以下淘专辑推荐:

catinclay 发表于 2016-11-21 08:30:21 | 显示全部楼层
一样维持一个最大堆 里头放的结构类似这样
class Interval{
    int numberAdded;. from: 1point3acres
    int distance;
}. from: 1point3acres

numberAdded是“已经在这个区间加入的加油站的个数” 一开始所有都预设为0
distance就是形成著个区间的两个加油站之间的距离. From 1point 3acres bbs
. 留学申请论坛-一亩三分地
最大堆依照(distance/(numberAdded+1))做比较
每次poll堆顶的Interval出来 把该Interval的numberAdded+1, 直到加入了k个加油站
此时堆顶的(Interval.distance/(numberAdded+1)) 就会是答案

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

评分

2

查看全部评分

回复 支持 8 反对 0

使用道具 举报

zzgzzm 发表于 2016-11-22 04:11:05 | 显示全部楼层
第二题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); . from: 1point3acres
  9.   }  
  10.   
  11.   // O(n^2) time
  12.   for (int i = 0; i < n; ++i)
  13.   for (int j = 0; j < n; ++j) {-google 1point3acres
  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];
  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的等概率。
回复 支持 4 反对 0

使用道具 举报

spwahaha 发表于 2016-11-22 04:42:32 | 显示全部楼层
第二题和楼主一样,不过是3种糖果,然后follow up是如何初始化使board一定有可以用一步可以消的棋子(初始化完成后不能直接死棋).... 讨论了很久,但是还是没回答出来,最后面试官说的方法挺tricky的。。
回复 支持 2 反对 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个,所以转移方程就是. 1point3acres
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]. From 1point 3acres bbs
  5.   // cur[tt]: minmaxDelta if adding tt points to delta[0,...,nn]
  6.   auto prev(vector<double>(t+1)), cur(vector<double>(t+1));. 留学申请论坛-一亩三分地
  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]
  13.         int mid = L + (R-L)/2, i = (int)delta[nn]/(tt - mid + 1);
  14.         if (i > prev[i]) R = mid; else L = mid;
  15.       }
  16.       cur[tt] = min(max(prev[L], delta[nn]/(tt-L+1)), max(prev[R], delta[nn]/(tt-R+1)));      
  17.     }
  18.     for (int tt = 0; tt <= t; ++tt) prev[tt] = cur[tt]; // update prev[]
  19.   }
  20.   return cur[t];
  21. }
复制代码
回复 支持 2 反对 0

使用道具 举报

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

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

使用道具 举报

spwahaha 发表于 2016-11-26 03:24:16 | 显示全部楼层
zzgzzm 发表于 2016-11-26 03:17
spwahaha 的意思估计是这样:在 spwahaha 的问题中只给定有3种糖果,那么在初始化设计中一旦出现以下情 ...

再分享一些东西, 我看了你的code, 在排除了两种糖果后可以用reservoir sampling 随机选剩余的糖果,这样没有额外空间,
我当时提出了一种思路,先放一种pattern后,从那个pettern的位置开始想四周BFS填糖果,这样是哪种pattern应该都可以,不过当时没有再顺着这个思路往下深究,面试官后来说这个思路也是可以的,不过不好coding(说follow up的时候也已经说不需要coding了)
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

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

第一題那樣會錯. 围观我们@1point 3 acres

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

使用道具 举报

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

第一题直接这样做是不对的,我一开始也是这么想的,小哥说不对,但是没给提示。你可以举个例子看看。
第二题我的方法不知道对不对,就是建一个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)个数尽量均匀间距。. visit 1point3acres for more.
. 1point 3acres 论坛
因为数学上很容易证明:当范围(xn-x1)和n固定时,只有等差数列的minMax:=min_j(x[j+1]-x[j])是最小的。
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-21 14:57:59 | 显示全部楼层
zzgzzm 发表于 2016-11-21 14:28
第一题:这个题应该可以DP: 假设delta[]是相邻加油站的间距,并且是sorted(这个题与顺序无关,所以若不是s ...

能否看一下我在4楼的贴子?我感觉我只需要O(lgk * n)
k = 初始的间距数量
n = 插入的加油站数

补充内容 (2016-11-21 14:59):
包含一開始的建立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)太慢了。. visit 1point3acres for more.

你的这个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的最优解如下构造:
存在指标j’(1<=j’<=N)使得d_j’/(k_j’+1) = F_c(k), 那么将{k_j}中的k_j’换为1+k_j’,其它不变,一定是对于C+1的最优解(最小化F_{c+1})。
证明:证明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)。(*).本文原创自1point3acres论坛
分两种情况:
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).. 1point3acres
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):
我是对于坐标为一般的double类型分析的,若是int类型的话应该也不影响实现。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-22 03:07:13 | 显示全部楼层
第四题:这个题貌似很喜欢考
  1. string getCountryByWeight(vector<pair<string, double>>& cw) {. Waral 博客有更多文章,
  2.   vector<double> pdf = {0.0}; double sum = 0.0;
  3.   for (auto& x:cw) { // create probability distribution function (pdf)
  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. 1point3acres
说真的,我很佩服你的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. 围观我们@1point 3 acres
说真的,我很佩服你的max heap设计!不算初始化heap,你是时间复杂度的确只有O(n*logk),而我的DP不算初 ...

这个heap的复杂度是O(k*logn)吧,虽然应该也没什么差别 来源一亩.三分地论坛.
证明的话induction可以更清晰一些,可以直接比较最后答案得到结论,不过应该都差不多
DP的话不单调优化确实比较好想,我觉得两种算法都很不错,当然从复杂度考虑确实heap更巧妙一些
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-25 23:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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