一亩三分地论坛

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

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

GOOLE NYC

[复制链接] |试试Instant~ |关注本帖
zhengshuomm 发表于 2015-12-1 05:35:53 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Other在职跳槽

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

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

x
面经大发好,第一次在地里发面经,求点积分吧。个人感觉真心的没见过的题基本上做不出来最优解,应该就是脑子笨吧。
废话不多说了:

1. 美国大叔,人很nice,就是面经里的比较两个quad tree。然后return 一个新的,这题虽然简单,但是很容易出bug。最后面试官引到了一下帮助发现bug。
2. 临时换了一个亚洲大哥。哥们出了一个画图题,给一个class {draw(boolean), move(x,y) // absolute coordinate}. draw 为true的时候是画线,draw为false的时候是抬起笔,move就是把笔移到某个位置。然后让画一个m*n 的矩形,每个格子长度为L。要求中心对称。(有俩bug,一是算float的时候两个整数相除, 2是for loop 时<= 写成<). visit 1point3acres.com for more.
    follow up: 如何一次性画完这个矩形,运行overlap某些edge。
    follow up: 如何一次性画矩形,不允许overlap。
    follow up: miniMize overlap 的edge,如果证明为啥你的方法是minimize的。(只能达brute force所有的可能性,然后算出最小的一个。 然后问brute force有何优化(答:memorization, 貌似不对。))
3. 中国大叔吧,人比较nice。题也比较简单,二维矩阵n个点,找一个最近的,带障碍。
4. 这大叔没看出来是哪的,开始看名字像日本,后来发现是老毛子。虽然题很简单,但是不知道他什么毛病,也不满意的样子。f(x) = ax2 + bx + c, 给一个input,结果也顺序输出。这人上来迟到7分钟,导致写的时候时间紧。最后匆匆忙忙写完,也没问啥别的, 最后take picture走人。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
5. abc小哥吧,小哥上来很有激情。问了问简历。出的题目说难也不难,说简单没见过也不好答。就是有一堆player,每个人beat 其他人的概率已知。然后已知初始的对阵表,问给定一个player,问他最后夺冠的概率是多少。
               ----
    ---                  ----
a--b   c---d    e---f  g---h

输入的format你自己决定。楼主当时真心也不知道啥好做法,很想用tree,但觉得用tree吧,从leaf node开始遍历到root 又很奇怪,而且很难找到一个node 的siblings。所以给了一个暴力解法,最后被证明是exponential memory usage。code也不是很好写,而且有些case也没处理。基本idea就是列出所有的对阵可能性,然后每一个可能性都有一个probability,最后结果相加。有点类似bfs。

看看人品能不能爆发一下。求各位面试官手下留情,这年头找个工作不容易

评分

8

查看全部评分

crisc3 发表于 2015-12-14 04:56:45 | 显示全部楼层
bobzhang2004 发表于 2015-12-11 11:34
请问第五题有哪位大神解答下吗?贴下二次方的code,有些复杂啊。。
. 鍥磋鎴戜滑@1point 3 acres
我来讲下第五题,如果一共有N个选手,N=2^h,那么我们就需要h次比赛才能选出冠军。-google 1point3acres
用win[j] 记录 i对j的, i赢的win rate, win[j] + win[j] = 1
如果有0,1,2,3四名选手 那么这个树里面,可能是这样的{[0]} {[0,3]} {[0,1] [2,3]} 我们把最底层成为0层,root称为h层。那么我们就是考虑root = 0, root->left = 0, root->left->left = 0, ...root->left*n = 0的可能性
我们现在要考虑的是从第K 层的结果,推出k+1层的结果。. 鍥磋鎴戜滑@1point 3 acres
所以用 DP 去做。DP大小为 H*N = logN *N,DP[j]代表的是在第 i 层(round i) 第j个选手没有被淘汰(win)的概率。由于tree的构造 你可以知道第i层中,活下来的最多为 2^(h-i)个。
特别的 i = 0 的时候, dp[0][j] = 1 for all j。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我们最终是要求dp[h][0]

好了,现在数学归纳法,假设我们已经求出了第k层,就是说我们知道了dp[k][0], dp[k][1]...dp[k][n-1]. 1point 3acres 璁哄潧
要用这些数据推出第k+1层。

OK 我们考虑dp[k+1][j] 说明j在k层肯定没被淘汰,并且与j 在k层的对局 , j赢了。那么这个概率就是
dp[k+1][j] = dp[k][j] * ( win[j][x] * dp[k][x]) for all x might fight j in round k+1, . From 1point 3acres bbs
注意这里的x不是由1~N共 N 个 哦,很简单,比如考虑dp[2][3],那么3在第一轮已经赢了,说明“2”已经被打死了,所以不可能与3再对局。同样的 dp[3][6]里面,和6对局的只可能是0,1,2,3而不可能是4,5,7(都已经死了)。所以 这个公式里求dp[k+1][j] 需要loop的所有的x一共有连续的2^k个(特别的,考虑下k+1=1和k+1=h):那么 我们如何去求出xstart呢,
大家画一画图,看下构造就不难得出,如果第k+1层j是从right child 胜出的,那么x在j的左边,xstart = j/(2^k) *2^k - 2^k, 反之如果是从left胜出的,那么xstart =  j/(2^k) *2^k
. from: 1point3acres.com/bbs
那么就可以写出我们的loop了:
input:
    int n, h;
    int win[n][n];
solution:
int dp[h][n] = {0};
for all j in 1-n:. Waral 鍗氬鏈夋洿澶氭枃绔,
    dp[0][j] = 1;
for(int k = 0; k<h ;k++){
    //calculate dp[k+1]
    for(int i = 0; i < n; i++){
        int offset = i / (2^k) * (2^k);
        int fightWithLeft = (i / (2^k)) % 2;
        int xstart = offset;
        if(fightWithLeft){
             xstart = offset - 2^k;
        }

        for(int x = xtart; x < xstart + 2^k ; x++){
             dp[k+1] += win[x]*dp[k][x];
        }. 鍥磋鎴戜滑@1point 3 acres
        dp[k+1] *= dp[k];
    } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
}
return dp[h][0];

那么这里Memory : O(h*N) = O(NlogN)
Time Complexity: 在第k+1层里,对于每个i,计算了2^k次,所以是2^k *N次
那么一共 (2^0 +2^1+...+2^(h-1) )*N = (2^h-1) * N = (N-1) * N
所以是O(N^2) time

如有错误 欢迎指正

补充内容 (2015-12-14 04:58):
好像不小心变斜体了 大家见谅
回复 支持 1 反对 0

使用道具 举报

ssross 发表于 2015-12-1 06:44:06 | 显示全部楼层
楼主会有offer的!!!

想问下楼主能把第一题说详细点嘛?在面经看过但没太搞明白,想搞明白这题到底是神马?
还有想问下楼主第四轮的解法。是用binary search找到-b/2a的x,然后以这个x为中心向两边求y放进两个不同的array里最后再merge一下吗?
. 1point3acres.com/bbs
非常感谢!
回复 支持 反对

使用道具 举报

 楼主| zhengshuomm 发表于 2015-12-1 08:12:24 | 显示全部楼层
ssross 发表于 2015-12-1 06:44
楼主会有offer的!!!

想问下楼主能把第一题说详细点嘛?在面经看过但没太搞明白,想搞明白这题到底是 ...
. 1point3acres.com/bbs
第一题就是两个quad tree 合并同类,如果两颗树相同位置的任意节点都是白的,最后的结果也是白的。如果都是黑的,最后就是黑的。
.1point3acres缃
我没有用binary search,因为总体的时间复杂度就是O(n)。 两个pointer同时往外移动,所以binary search对总体时间并没有帮助。linear 扫一下就好了。
回复 支持 反对

使用道具 举报

byrlhb 发表于 2015-12-1 09:53:48 | 显示全部楼层
lz可能实力很好,但是向第二题这种不知道答案根本做不出来的题,也不知道小哥考得有什么意义,祝lzoffer
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-12-1 14:37:38 | 显示全部楼层
lz, 第二题是画m*n的矩阵嘛?根据欧拉原理,矩阵有大于2的奇数点,如何一笔画?
如果是画矩形,那一个长方形一笔画就完事了,为何还有overlap?谢谢lz不吝赐教
回复 支持 反对

使用道具 举报

 楼主| zhengshuomm 发表于 2015-12-1 23:49:45 | 显示全部楼层
yjfox 发表于 2015-12-1 14:37
lz, 第二题是画m*n的矩阵嘛?根据欧拉原理,矩阵有大于2的奇数点,如何一笔画?. from: 1point3acres.com/bbs
如果是画矩形,那一个长方 ...

是画一个矩阵。应该是只有m,n 都为1的情况下能一笔画(就是个矩形)。他的第三个follow up就是在不能一笔画完的情况下,提供一种方法minimize overlap的edge。
回复 支持 反对

使用道具 举报

will_ym 发表于 2015-12-2 00:11:14 | 显示全部楼层
感谢楼主分享。还是没看懂第二题啊。m*n的矩形,这里m和n是cell的个数么?每个cell的边长是L?
还有第四题,输入是x然后求f(x),还是输入是f(x)的值然后求x?. Waral 鍗氬鏈夋洿澶氭枃绔,
多谢楼主
回复 支持 反对

使用道具 举报

cancerlk 发表于 2015-12-2 01:30:29 | 显示全部楼层
楼主会有offer的。。。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-2 02:49:17 来自手机 | 显示全部楼层
比赛那题暴力解是数学的计算?
回复 支持 反对

使用道具 举报

 楼主| zhengshuomm 发表于 2015-12-2 07:10:51 | 显示全部楼层
will_ym 发表于 2015-12-2 00:11
感谢楼主分享。还是没看懂第二题啊。m*n的矩形,这里m和n是cell的个数么?每个cell的边长是L?. 1point3acres.com/bbs
还有第四题 ...

是的。
输入排序x,求排序f(x)
回复 支持 反对

使用道具 举报

 楼主| zhengshuomm 发表于 2015-12-2 07:11:43 | 显示全部楼层
cancerlk 发表于 2015-12-2 01:30
楼主会有offer的。。。

楼主今天突然发现第搞了一个大bug
回复 支持 反对

使用道具 举报

 楼主| zhengshuomm 发表于 2015-12-2 07:12:25 | 显示全部楼层
bobzhang2004 发表于 2015-12-2 02:49
比赛那题暴力解是数学的计算?

我是暴力解法,相当与列出所有可能性了
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-12-2 08:48:37 | 显示全部楼层
lz你的题多和数学有关,背景原因?
回复 支持 反对

使用道具 举报

 楼主| zhengshuomm 发表于 2015-12-2 09:07:38 | 显示全部楼层
yjfox 发表于 2015-12-2 08:48
lz你的题多和数学有关,背景原因?

大一上过高数吧。。。
回复 支持 反对

使用道具 举报

cancerlk 发表于 2015-12-2 09:18:59 | 显示全部楼层
zhengshuomm 发表于 2015-12-2 09:07
大一上过高数吧。。。

上过高数亮了 你越来越冷幽默!
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-11 11:34:34 | 显示全部楼层
请问第五题有哪位大神解答下吗?贴下二次方的code,有些复杂啊。。
  1. public class SortSortedArray {

  2.         public static void main(String[] args) {
  3.                 int[] arr = {-5, -3, -1, 0, 4, 9, 11, 13};
  4.                 int[] res = sortSortedArray(arr, -1, 2, 0);
  5.                 for (int i : res) {
  6.                         System.out.print(i + " ");
  7.                 }
  8.         }
  9.         public static int[] sortSortedArray(int[] arr, int a, int b, int c) {
  10.                 int pivot = -b / (2 * a);
  11.                 int[] res = new int[arr.length];
  12.                 int index = findPivot(arr, pivot);
  13.                 int left = index;-google 1point3acres
  14.                 int right = index + 1;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  15.                 boolean faceUp = true;
  16.                 if (a < 0) {
  17.                         faceUp = false;
  18.                 }
  19.                 int pos = 0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  20.                 if (faceUp) {
  21.                         while (left >= 0 && right < arr.length) {
  22.                                 if (getResult(arr[left], a, b, c) > getResult(arr[right], a, b, c)) {
  23.                                         res[pos++] = getResult(arr[right], a, b, c);
  24.                                         right++;
  25.                                 } else {
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  26.                                         res[pos++] = getResult(arr[left], a, b, c);
  27.                                         left--;
  28.                                 }. From 1point 3acres bbs
  29.                         }
  30.                         while (left >= 0) {
  31.                                 res[pos++] = getResult(arr[left], a, b, c);
  32.                                 left--;
  33.                         }
  34.                         while (right < arr.length) {
  35.                                 res[pos++] = getResult(arr[right], a, b, c);
  36.                                 right++;
  37.                         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  38.                 } else {
  39.                         pos = res.length - 1;
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  40.                         while (left >= 0 && right < arr.length) {
  41.                                 if (getResult(arr[left], a, b, c) > getResult(arr[right], a, b, c)) {
  42.                                         res[pos--] = getResult(arr[left], a, b, c);
  43.                                         left--;
  44.                                 } else {
  45.                                         res[pos--] = getResult(arr[right], a, b, c);
  46.                                         right++;
  47.                                 }
  48.                         }
  49.                         while (left >= 0) {. from: 1point3acres.com/bbs
  50.                                 res[pos--] = getResult(arr[left], a, b, c);-google 1point3acres
  51.                                 left--;
  52.                         }
  53.                         while (right < arr.length) {
  54.                                 res[pos--] = getResult(arr[right], a, b, c);
  55.                                 right++;
  56.                         }
  57.                 }
  58.                 return res;
  59.         }

  60.         private static int getResult(int i, int a, int b, int c) {
  61.                 return a * i * i + b * i + c;
  62.         }

  63.         private static int findPivot(int[] arr, int pivot) {
  64.                 int start = 0;
  65.                 int end = arr.length - 1;
  66.                 while (start + 1 < end) {. from: 1point3acres.com/bbs
  67.                         int mid = (end - start) / 2 + start;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  68.                         if (arr[mid] == pivot) {
  69.                                 return mid;
  70.                         } else if (arr[mid] > pivot) {. 1point 3acres 璁哄潧
  71.                                 end = mid;. Waral 鍗氬鏈夋洿澶氭枃绔,
  72.                         } else {
  73.                                 start = mid;
  74.                         }
  75.                 }
  76.                 if (arr[end] <= pivot) {. more info on 1point3acres.com
  77.                         return end;
  78.                 } else {
  79.                         return start;. 1point3acres.com/bbs
  80.                 }
  81.         }
  82. }
复制代码
回复 支持 反对

使用道具 举报

sooorrr 发表于 2015-12-14 06:01:30 | 显示全部楼层
crisc3 发表于 2015-12-14 04:56
我来讲下第五题,如果一共有N个选手,N=2^h,那么我们就需要h次比赛才能选出冠军。
用win[j] 记录 i对j ...

感觉没什么必要用DP,不就是一颗满二叉树由叶子节点往根节点层序遍历吗?每个节点存有所有的以它为根的子节点队伍,以及它们在本子树中胜出的概率。能优化的就是,目标队伍的所有祖先节点只要保留这支队伍的获胜概率。
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-12-21 05:48:26 | 显示全部楼层
crisc3 发表于 2015-12-14 04:56 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我来讲下第五题,如果一共有N个选手,N=2^h,那么我们就需要h次比赛才能选出冠军。
用win[j] 记录 i对j ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
赞一下思路,但是xstart的位置计算可能有问题,如果fightWithLeft == 0 那应该fightWithRight
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 20:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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