一亩三分地论坛

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

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

10月23日onsite面试

[复制链接] |试试Instant~ |关注本帖
hhllryslh 发表于 2015-11-18 09:27:52 | 显示全部楼层 |阅读模式

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

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

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

x
报一个google onsite的面经, 攒攒攒攒攒人品,回报地里!
面的时间比较久远了,其中经历也有点小波折。
10月23号面的,一共四轮(虽然我也很好奇为什么我只有四轮,具体原因我也不太清楚)
第一轮. from: 1point3acres.com/bbs
上来就是OOD的题目。让我设计一个手机的打字输入法,然后我蒙了一下就开始巴拉巴拉扯,说了下Trie树,然后写了一点interface,面试官问怎么样improve搜索的efficiency,然后我说就把可能的word都存起来,放在trie的node里边,然后他提了几个这样做的不足,然后我就说另外弄一个map存一下每个word的出现频率之类的提高效率。最后再用pointer来节省空间。

第二轮
中国人,国语面试。问的题目还算简单,大概medium难度的,问了两道题。第一道题是x^y,recursive和非recursive的方法都要写,这个要注意一下corner case。第二个题是走迷宫的题,一个矩阵,给矩阵里一个入口和一个出口,让你从入口走到出口,每次可以走1步或者2步。我当时第一反应是bfs,但是因为之前的那题非recursive用的是有点DP的思想做的,然后突然忘记bfs怎么做了。。扯了下dfs和dp如何做,然后国人小哥这里稍微提示了一下。(呜呜呜,不应该犯这个错误的,面完这一轮后我懊悔了好久)

第三轮
扫描线问题,就是问多少个interval 是overlap的然后找出他们overlap的时间段。用priority queue秒杀, bug free,这个要注意一下终点和起点的顺序。

第四轮.鐣欏璁哄潧-涓浜-涓夊垎鍦
问了两道题,都没见过。。。.1point3acres缃
第一道题是 Ax^2 + Bx + C 然后给一个x的sorted的input array 让输出的y也是 sorted的。找到对称轴 然后两根指针做了。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第二道题是 leetcode带锁题目,稍微有点改动的strobogrammatic numberII。

总结一下,总体来说不难,但是每个题目我觉得都容易错,得把好多corner case想清楚,关键还是得刷题刷熟练了。另外还有就是遇到不会的不要紧张,说着说着自己就会有思路的。
面完后其实自己心还是吊着的,中间过程说我申请的 提姆不太match让我转去general那里,磕磕碰碰的。由于自己没实习,简历上好多公司连简历关都没有过,现在想想觉得要是大家觉得自己简历不够strong还是找人推比较合适。
下午recruiter打了电话 告诉我hiring committe通过了,接下来还有一大堆流程。然后组match,请问地里的各位,这一阶段是不是还有风险啊,比如说组没有match上还是有可能挂掉?
保佑正式 offer快快来,攒攒攒人品,希望大家也一帆风顺!
.1point3acres缃

本帖被以下淘专辑推荐:

queeniejing 发表于 2015-11-18 09:33:01 | 显示全部楼层
谢谢LZ分享, 走迷宫那题能具体说下做法吗?
回复 支持 反对

使用道具 举报

 楼主| hhllryslh 发表于 2015-11-18 09:52:57 | 显示全部楼层
queeniejing 发表于 2015-11-18 09:33
谢谢LZ分享, 走迷宫那题能具体说下做法吗?

就是
得定义一个 Point struct. From 1point 3acres bbs
struct Point{. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  int x;
int y;. more info on 1point3acres.com
Point(int row, int col): x(row), y(col){}.鐣欏璁哄潧-涓浜-涓夊垎鍦
}
然后你知道了入口之后就把入口的坐标初始化成为一个point 放到你的queue上,然后
每次往下一个level走的时候就把下一个level的点放到你的queue里边,直到找到出口,不过我有点忘了当时他有没有让我返回那条路径了,如果让返回的话 可以变成queue of stack,stack里边存路径。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-18 10:31:19 | 显示全部楼层
请问第三轮的哪个扫描线是只能两两overlap吗还是说会出现[1,10],[2,7],[3,11]这种?
回复 支持 反对

使用道具 举报

 楼主| hhllryslh 发表于 2015-11-18 12:01:22 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-18 10:31
请问第三轮的哪个扫描线是只能两两overlap吗还是说会出现[1,10],[2,7],[3,11]这种?

是都可以overlap哦,会出现[1,10],[2,7],[3,11]这样的情况
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-18 12:06:46 | 显示全部楼层
hhllryslh 发表于 2015-11-18 12:01
是都可以overlap哦,会出现[1,10],[2,7],[3,11]这样的情况

哦哦,感觉有点难,我只想到brute force。。。请问lz是怎么答的?
回复 支持 反对

使用道具 举报

 楼主| hhllryslh 发表于 2015-11-18 14:11:30 | 显示全部楼层
就是得自己建一个struct 里边有它端点数值 和bool表示它是否是start,然后放在priority queue里边一个一个pop出来 发现一个start就加一 发现一个end就减一 然后得维持一个pair里边存放的就是overlap的段
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-18 14:19:40 | 显示全部楼层
hhllryslh 发表于 2015-11-18 14:11
就是得自己建一个struct 里边有它端点数值 和bool表示它是否是start,然后放在priority queue里边一个一个p ...

感谢lz回复,比如说[1,10],[2,7],[3,11]这个
放到queue里就是 1S,2S,3S,7E,10E,11E (S表示start,E表示end)
加一减一我能理解是说当前overlap的数量,哪个pair是什么怎么维护呢?
回复 支持 反对

使用道具 举报

queeniejing 发表于 2015-11-18 15:13:11 | 显示全部楼层
hhllryslh 发表于 2015-11-18 09:52
就是
得定义一个 Point struct
struct Point{
. 1point 3acres 璁哄潧
谢谢LZ 只要走到出口就行了吗? 还是要求最短路径或者其他的什么?
回复 支持 反对

使用道具 举报

 楼主| hhllryslh 发表于 2015-11-18 15:32:55 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-18 14:19
感谢lz回复,比如说[1,10],[2,7],[3,11]这个
放到queue里就是 1S,2S,3S,7E,10E,11E (S表示start,E表示 ...

就是 你遇到一个start 就把pair的 first变成这个start 遇到end就把这个pair的second变成end。维持两个pair 一个是prev的overlap的,另外一个是curr的overlap的。 然后看那个overlap的segment多就要哪个
回复 支持 反对

使用道具 举报

 楼主| hhllryslh 发表于 2015-11-18 15:33:44 | 显示全部楼层
queeniejing 发表于 2015-11-18 15:13
谢谢LZ 只要走到出口就行了吗? 还是要求最短路径或者其他的什么?

我不大记得了 应该是要求出最短路径的 要把路径返回的
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-11-18 15:33:58 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-18 12:06
哦哦,感觉有点难,我只想到brute force。。。请问lz是怎么答的?

这种题也可以把所有start看成正数,所有end看成负数,然后绝对值排序,这里就是 1 2 3 -7 -10 -11, 顺序扫一遍,遇到正的次数加1,负得次数减1,次数大于1就是overlap了,次数是多少就是overlap多少次。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-18 15:48:43 | 显示全部楼层
queeniejing 发表于 2015-11-18 15:13.鐣欏璁哄潧-涓浜-涓夊垎鍦
谢谢LZ 只要走到出口就行了吗? 还是要求最短路径或者其他的什么?
. Waral 鍗氬鏈夋洿澶氭枃绔,
哦哦,明白了,题目是要输出最多overlap的时间段是吧?我以为要输出所有overlap的时间段。。。。那上面的例子就应该输出[3,7]?
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-18 15:48:54 | 显示全部楼层
hj867955629 发表于 2015-11-18 15:33
这种题也可以把所有start看成正数,所有end看成负数,然后绝对值排序,这里就是 1 2 3 -7 -10 -11, 顺 ...

嗯嗯,知道啦!
回复 支持 反对

使用道具 举报

shuishuimiao 发表于 2015-11-19 04:46:29 | 显示全部楼层
请问楼主 那题迷宫是求最小的步数走到出口么 还是只是找到一个路径走到出口?
回复 支持 反对

使用道具 举报

queeniejing 发表于 2015-11-19 05:14:01 | 显示全部楼层
hj867955629 发表于 2015-11-18 15:33
这种题也可以把所有start看成正数,所有end看成负数,然后绝对值排序,这里就是 1 2 3 -7 -10 -11, 顺 ...

我有个问题不太理解: “就是 1 2 3 -7 -10 -11, 顺序扫一遍,遇到正的次数加1,负得次数减1,次数大于1就是overlap了”  比如这里 顺序扫一遍 遇到正数加1, 那么现在是3, 然后遇到负数减1  最后不又变成0 了吗?  怎么会有overlap 次数大于1呢?  能再说说吗? 谢谢啦
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-11-19 09:12:01 | 显示全部楼层
queeniejing 发表于 2015-11-19 05:14
我有个问题不太理解: “就是 1 2 3 -7 -10 -11, 顺序扫一遍,遇到正的次数加1,负得次数减1,次数大 ...

中间会大于1呀。。比如扫到2,遇到两个正数1和2,所以次数为2,说明从2开始的部分是重叠两次
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-5 23:23:49 | 显示全部楼层
请问楼主第三轮是求最多overlap的个数吗?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-5 23:50:35 | 显示全部楼层
写了下sort array a*x^2 + bx + c的代码,这题代码量也不少啊。。。
  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;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  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--;
    . more info on 1point3acres.com
  28.                                 }
    . visit 1point3acres.com for more.
  29.                         }. 1point 3acres 璁哄潧
  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.                         }
  38.                 } else {. 1point 3acres 璁哄潧
  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.                                 }. From 1point 3acres bbs
  48.                         }
  49.                         while (left >= 0) {
  50.                                 res[pos--] = getResult(arr[left], a, b, c);
  51.                                 left--;
  52.                         }
  53.                         while (right < arr.length) {. more info on 1point3acres.com
  54.                                 res[pos--] = getResult(arr[right], a, b, c);
  55.                                 right++;
  56.                         }
  57.                 }
  58.                 return res;. 1point3acres.com/bbs
  59.         }

  60.         private static int getResult(int i, int a, int b, int c) {
  61.                 return a * i * i + b * i + c;
  62.         }
  63. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  64.         private static int findPivot(int[] arr, int pivot) {.1point3acres缃
  65.                 int start = 0;
  66.                 int end = arr.length - 1;
  67.                 while (start + 1 < end) {
  68.                         int mid = (end - start) / 2 + start;
  69.                         if (arr[mid] == pivot) {.1point3acres缃
  70.                                 return mid;
  71.                         } else if (arr[mid] > pivot) {
  72.                                 end = mid;
  73.                         } else {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  74.                                 start = mid;
  75.                         }
  76.                 }
  77.                 if (arr[end] <= pivot) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  78.                         return end;
  79.                 } else {
  80.                         return start;
  81.                 }
  82.         }
  83. }. 鍥磋鎴戜滑@1point 3 acres
复制代码
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-5 23:53:17 | 显示全部楼层
hhllryslh 发表于 2015-11-18 09:52
就是
得定义一个 Point struct
struct Point{

请问这么做和一次走1步2步没什么关系啊,2步不就是走两次吗?是要求最小的走得次数吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 01:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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