一亩三分地论坛

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

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

G家 kirkland onsite

[复制链接] |试试Instant~ |关注本帖
airywu 发表于 2016-1-7 09:30:10 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 校园招聘会 - 校园招聘会 |Otherfresh grad应届毕业生

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

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

x
来个面经~还是感觉答得不怎么样所以也不用攒人品了。。。面的T&I,校园招聘联系的。
round one:白人小哥,T&I~妥妥的迟到了也没怎么问问题,一半时间在闲扯,不给任何提示只能自己想= =一开始先从闲扯开始,扯了一会开代码。写一个next(node), 在postorder的遍历下返回下一个值。跟树不一样的是node有一个指向parent的指针,所以输入任意一个node,都要返回postorder遍历的下一个值。然后对这个写test cases。然后又开始闲扯。。。
round two:国人developer,出了两个面经里见过的,第一个就是那个rain drop,每次1cm,问啥时候打湿1m的strick。第二个就是y=a*x^2+b*x+c,给一个sorted list of x, return sorted y。大家有兴趣可以好好想想怎么写。反正小哥一直在各种提示我,嗯,估计挂了。。。两题都见过,可惜没时间仔细研究过。。。

round three:看上去像ABC的小哥,做chrome干嘛的忘了,带个shadow,又迟到了。。。remove a subtree if sum of itself and all nodes below It is zero。然后就这这个题目一直问问问,一点点扣big O之类的,然后又是写各种test cases。。。.鏈枃鍘熷垱鑷1point3acres璁哄潧
round four:国人developer,中文面的我也是醉了,人很nice啊。问了挺简单的一题,  然后就一直再让我写各种test cases,然后我就满屏幕给他写。别问了写了啥,全是扯我自己也没记住反正要求写了三种test cases。第一个是有个function,输入两个string,还有一个运算符号,比如3+2,然后自己去写test case吧,于是我就写了二十分钟的。。。中间问了个简单的问题,“bananaxxbb”,“can” ,参照“can”的顺序返回"aaannabxxbb",不在“can”里面的保持不变。编完写test cases。。。一看还有时间又问如果是使用command line打开文件的话可以写啥test case。。。. more info on 1point3acres.com


总的来说面试官都挺好的,真是运气挺好的。不过自己水平有限,还是继续努力吧~我想吐槽一句为毛前三个人问的全是tree。。。还有就是code的时候边写代码边说话真的反应不过来啊 = =
还有就是最近kirkland在新建一个楼,所以要招不少人。还有就是G家真好啊,给报销好多钱,然后一直所有的联系人都特别nice,所以心情一直都还好。
祝大家面试顺利~楼主已经放弃治疗玩耍去了~
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

评分

3

查看全部评分

 楼主| airywu 发表于 2016-1-10 00:16:02 | 显示全部楼层
哗啦啦 发表于 2016-1-9 14:46. from: 1point3acres.com/bbs
同求rain drop 面经,谢谢!

好吧,楼主特地去翻了一遍地里的帖子。。。下面第一题
http://www.1point3acres.com/bbs/ ... %3Dradio&page=1-google 1point3acres
这里面第二题:
http://www.1point3acres.com/bbs/ ... adio%26sortid%3D311

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

aiwojiujiu 发表于 2016-1-9 03:55:14 | 显示全部楼层
第二轮 第二题 可以这么考虑:
一元二次方程画出来是一个U形曲线,这样你可以先求出顶点坐标的横坐标,并将其作为起始点。
从起始点开始,在sorted array中找到第一个离这个点最近的点作为第一个点加入result(logn)
这时,从加入result的这个位置开始分别向两边找,将下一个距离顶点最近的点加入result,知道将array中所有的点都加入result
整个过程时间复杂度是O(n)
如果a<0, 最后需要将result reverse一下。
回复 支持 1 反对 0

使用道具 举报

say543 发表于 2016-1-7 15:34:02 | 显示全部楼层
rain drop 的面经LZ还记得在哪吗? 能分享一下吗感谢
回复 支持 反对

使用道具 举报

aiwojiujiu 发表于 2016-1-9 04:22:57 | 显示全部楼层
第三轮 bottom-up 的写法就是 O(n) 啊 不知道为什么讨论那么久复杂度
回复 支持 反对

使用道具 举报

 楼主| airywu 发表于 2016-1-9 11:06:58 | 显示全部楼层
aiwojiujiu 发表于 2016-1-9 04:22
第三轮 bottom-up 的写法就是 O(n) 啊 不知道为什么讨论那么久复杂度

说了不少问题不光是复杂度
回复 支持 反对

使用道具 举报

哗啦啦 发表于 2016-1-9 14:46:15 | 显示全部楼层
同求rain drop 面经,谢谢!
回复 支持 反对

使用道具 举报

哗啦啦 发表于 2016-1-10 00:26:06 | 显示全部楼层
airywu 发表于 2016-1-10 00:16
好吧,楼主特地去翻了一遍地里的帖子。。。下面第一题
http://www.1point3acres.com/bbs/forum.php?mod= ...

谢谢!(字数补充器)
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-1-11 02:50:42 | 显示全部楼层
第二题有意思
回复 支持 反对

使用道具 举报

echo33 发表于 2016-1-13 02:33:48 | 显示全部楼层
raindrop那个最近出现频率好高啊。。。。。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-11 08:42:16 | 显示全部楼层
有大神可以具体说说这个raindrop怎么做吧?是开两个array进行记录?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-11 09:03:55 | 显示全部楼层
写了下第三题,
  1. public class RemoveSubtree {
  2. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  3.         static class Node {
  4.                 int val;. From 1point 3acres bbs
  5.                 Node left, right;
  6.                 public Node(int v) {
  7.                         val = v;
  8.                 }
  9.         }
  10.        
  11.         static class Result {
  12.                 Node node;
  13.                 int sum;
  14.                 public Result(Node n, int s) {
  15.                         node = n;
  16.                         sum = s;
  17.                 }
  18.         }
  19.        
  20.         public static Result removeSubtree(Node root) {
  21.                 if (root == null) {
  22.                         return new Result(null, 0);
  23.                 }
  24.                 Result left = removeSubtree(root.left);
  25.                 Result right = removeSubtree(root.right);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  26.                 root.left = left.node;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  27.                 root.right = right.node;
  28.                 int tmpSum = root.val + left.sum + right.sum;. from: 1point3acres.com/bbs
  29.                 if (tmpSum == 0) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  30.                         return new Result(null, tmpSum);
  31.                 } else {
  32.                         return new Result(root, tmpSum);
  33.                 }
  34.         }
  35.        
  36.         public static void printTree(Node root) {
  37.                 if (root == null) {
  38.                         return;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  39.                 }
  40.                 printTree(root.left);
  41.                 System.out.print(root.val + " ");. visit 1point3acres.com for more.
  42.                 printTree(root.right);
  43.         }. 1point3acres.com/bbs
  44.         . from: 1point3acres.com/bbs
  45.         public static void main(String[] args) {
  46.                 Node root = new Node(5);
  47.                 root.left = new Node(1);
  48.                 root.right = new Node(6);
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  49.                 root.left.left = new Node(5);
  50.                 root.left.right = new Node(2);
  51.                 root.right.left = new Node(5);
  52.                 root.right.left.left = new Node(4);
  53.                 root.right.right = new Node(7);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  54.                 root.right.right.left = new Node(1);
  55.                 root.right.right.right = new Node(-8);
  56.                 printTree(root);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  57.                 System.out.println();
  58.                 removeSubtree(root);
  59.                 printTree(root);
  60.         }
  61. }
复制代码
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-11 09:12:11 | 显示全部楼层
请问"第一个是有个function,输入两个string,还有一个运算符号,比如3+2"是要输出什么呢?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-11 10:30:45 | 显示全部楼层
第四轮第二题
  1. public class SortStringBaseGivenString {
  2. . more info on 1point3acres.com
  3.         public static void main(String[] args) {
  4.                 System.out.println(sortStringBaseGivenString("bananaxxbb", "can"));.1point3acres缃
  5.         }.鏈枃鍘熷垱鑷1point3acres璁哄潧

  6.         public static String sortStringBaseGivenString(String s1, String s2) {
  7.                 HashMap<Character, Integer> map = new HashMap<Character, Integer>();
  8.                 for (int i = 0; i < s2.length(); i++) {
  9.                         if (!map.containsKey(s2.charAt(i))) {
  10.                                 map.put(s2.charAt(i), i);. visit 1point3acres.com for more.
  11.                         }
  12.                 }
  13.                 Character[] chars = new Character[s1.length()];
  14.                 for (int i = 0; i < s1.length(); i++) {. visit 1point3acres.com for more.
  15.                         chars[i] = (Character) s1.charAt(i);
  16.                 }
  17.                 Arrays.sort(chars, new Comparator<Character>() {
  18.                         public int compare(Character c1, Character c2) {
  19.                                 if (!map.containsKey(c1) || !map.containsKey(c2)) {
  20.                                         return map.containsKey(c1) ? -1 : 1;
  21.                                 } else {
  22.                                         return map.get(c1) - map.get(c2);
  23.                                 }
  24.                         }-google 1point3acres
  25.                 });
  26.                 StringBuilder sb = new StringBuilder();
  27.                 for (Character c : chars) {
  28.                         sb.append(c);
  29.                 }. visit 1point3acres.com for more.
  30.                 return sb.toString();
  31.         }
  32. }
复制代码
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-11 11:32:03 | 显示全部楼层
round two . visit 1point3acres.com for more.
  1. public class SortSortedArrayII {

  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;. Waral 鍗氬鏈夋洿澶氭枃绔,
  14.                 int right = index + 1;
  15.                 int pos = 0;
  16.                 while (left >= 0 && right < arr.length) {
  17.                         if (pivot - arr[left]  > arr[right] - pivot) {
  18.                                 res[pos++] = arr[right];
  19.                                 right++;
  20.                         } else {-google 1point3acres
  21.                                 res[pos++] = arr[left];
  22.                                 left--;
  23.                         }
  24.                 }
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  25.                 while (left >= 0) {
  26.                         res[pos++] = arr[left];.鐣欏璁哄潧-涓浜-涓夊垎鍦
  27.                         left--;
  28.                 }
  29.                 while (right < arr.length) {
  30.                         res[pos++] = arr[right]; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  31.                         right++;
  32.                 }
  33.                 for (int i = 0; i < res.length; i++) {
  34.                         res[i] = getResult(res[i], a, b, c);
  35.                 }
  36.                 if (a < 0) {
  37.                         reverse(res);
  38.                 }. 1point3acres.com/bbs
  39.                 return res;
  40.         }
  41. . more info on 1point3acres.com
  42.         private static void reverse(int[] res) {
  43.                 int left = 0;
  44.                 int right = res.length - 1;
  45.                 while (left < right) {
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  46.                         int tmp = res[right];
  47.                         res[right] = res[left];
  48.                         res[left] = tmp;
    . 1point 3acres 璁哄潧
  49.                         left++;
  50.                         right--;
  51.                 }
  52.         }

  53.         private static int getResult(int i, int a, int b, int c) {
  54.                 return a * i * i + b * i + c;
  55.         }

  56.         private static int findPivot(int[] arr, int pivot) {-google 1point3acres
  57.                 int start = 0;. visit 1point3acres.com for more.
  58.                 int end = arr.length - 1;
  59.                 while (start + 1 < end) {
  60.                         int mid = (end - start) / 2 + start;
  61.                         if (arr[mid] == pivot) {
  62.                                 return mid;
  63.                         } else if (arr[mid] > pivot) {
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  64.                                 end = mid;
  65.                         } else {
  66.                                 start = mid;
  67.                         }
  68.                 }
  69.                 if (arr[end] <= pivot) {
  70.                         return end;
  71.                 } else {
  72.                         return start;
  73.                 }
  74.         }
  75. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| airywu 发表于 2016-2-12 13:50:25 | 显示全部楼层
bobzhang2004 发表于 2016-2-11 09:12
请问"第一个是有个function,输入两个string,还有一个运算符号,比如3+2"是要输出什么呢?

输出string 5
回复 支持 反对

使用道具 举报

yyyusa 发表于 2016-2-16 12:05:01 | 显示全部楼层
楼主在kirkland面的??
回复 支持 反对

使用道具 举报

maggiejiao 发表于 2016-3-5 00:01:09 | 显示全部楼层
LZ, 这道题我不是很懂诶 “bananaxxbb”,“can” ,参照“can”的顺序返回"aaannabxxbb", 这里不应该返回"aaannbxxbb"吗,为什么你多了一个'a'
回复 支持 反对

使用道具 举报

tigercode 发表于 2016-9-26 03:16:40 | 显示全部楼层
1.2 只需要分a>0和a<0两种情况,然后two pointers;  3  应该是想push你给O(n)的算法
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-5 00:34:36 | 显示全部楼层
aiwojiujiu 发表于 2016-1-9 04:22
第三轮 bottom-up 的写法就是 O(n) 啊 不知道为什么讨论那么久复杂度

第三题是DFS递归么?叶子遇到本身是0的,就直接删掉,不然的话把自身的值返回给父亲,父亲拿到叶子的值计算SUM,如果是0,从父亲开始以下全部删掉,不然把这个SUM值再返回上去?

第一题就用往上爬的方法找PREORDER的节点吧,如果自己是父亲的左孩子或者自己是父亲的右孩子,但父亲没有左孩子,就是父亲?如果自己是父亲的右孩子,而父亲还有左孩子,就找到父亲左孩子最右边的那个节点?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 12:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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