一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 3118|回复: 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。。。
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的时候边写代码边说话真的反应不过来啊 = =. visit 1point3acres.com for more.
还有就是最近kirkland在新建一个楼,所以要招不少人。还有就是G家真好啊,给报销好多钱,然后一直所有的联系人都特别nice,所以心情一直都还好。.1point3acres缃
祝大家面试顺利~楼主已经放弃治疗玩耍去了~

评分

3

查看全部评分

 楼主| airywu 发表于 2016-1-10 00:16:02 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
哗啦啦 发表于 2016-1-9 14:46-google 1point3acres
同求rain drop 面经,谢谢!

好吧,楼主特地去翻了一遍地里的帖子。。。下面第一题
http://www.1point3acres.com/bbs/ ... %3Dradio&page=1
这里面第二题:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
http://www.1point3acres.com/bbs/ ... adio%26sortid%3D311

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

aiwojiujiu 发表于 2016-1-9 03:55:14 | 显示全部楼层
关注一亩三分地微博:
Warald
第二轮 第二题 可以这么考虑:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
一元二次方程画出来是一个U形曲线,这样你可以先求出顶点坐标的横坐标,并将其作为起始点。. From 1point 3acres bbs
从起始点开始,在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) 啊 不知道为什么讨论那么久复杂度
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| airywu 发表于 2016-1-9 11:06:58 | 显示全部楼层
aiwojiujiu 发表于 2016-1-9 04:22
第三轮 bottom-up 的写法就是 O(n) 啊 不知道为什么讨论那么久复杂度
. more info on 1point3acres.com
说了不少问题不光是复杂度
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

bobzhang2004 发表于 2016-2-11 10:30:45 | 显示全部楼层
第四轮第二题
  1. public class SortStringBaseGivenString {
  2. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  3.         public static void main(String[] args) {
  4.                 System.out.println(sortStringBaseGivenString("bananaxxbb", "can"));
  5.         }. 1point 3acres 璁哄潧
  6. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  7.         public static String sortStringBaseGivenString(String s1, String s2) {
  8.                 HashMap<Character, Integer> map = new HashMap<Character, Integer>();
  9.                 for (int i = 0; i < s2.length(); i++) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  10.                         if (!map.containsKey(s2.charAt(i))) {
  11.                                 map.put(s2.charAt(i), i);
  12.                         }
  13.                 }
  14.                 Character[] chars = new Character[s1.length()];.鏈枃鍘熷垱鑷1point3acres璁哄潧
  15.                 for (int i = 0; i < s1.length(); i++) {
  16.                         chars[i] = (Character) s1.charAt(i);
  17.                 }
  18.                 Arrays.sort(chars, new Comparator<Character>() {
  19.                         public int compare(Character c1, Character c2) {
  20.                                 if (!map.containsKey(c1) || !map.containsKey(c2)) {
  21.                                         return map.containsKey(c1) ? -1 : 1;. From 1point 3acres bbs
  22.                                 } else {
  23.                                         return map.get(c1) - map.get(c2);
  24.                                 }
  25.                         }. From 1point 3acres bbs
  26.                 });
  27.                 StringBuilder sb = new StringBuilder();
  28.                 for (Character c : chars) {
  29.                         sb.append(c);
  30.                 }
  31.                 return sb.toString();
  32.         }
  33. }
复制代码
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-11 11:32:03 | 显示全部楼层
round two
  1. public class SortSortedArrayII {
  2. . 鍥磋鎴戜滑@1point 3 acres
  3.         public static void main(String[] args) {
  4.                 int[] arr = { -5, -3, -1, 0, 4, 9, 11, 13 };
  5.                 int[] res = sortSortedArray(arr, -1, 2, 0);
  6.                 for (int i : res) {. more info on 1point3acres.com
  7.                         System.out.print(i + "  ");
  8.                 }
  9.         }.1point3acres缃

  10.         public static int[] sortSortedArray(int[] arr, int a, int b, int c) {
  11.                 int pivot = -b / (2 * a);
  12.                 int[] res = new int[arr.length];
  13.                 int index = findPivot(arr, pivot);
  14.                 int left = index;
  15.                 int right = index + 1;
  16.                 int pos = 0;
  17.                 while (left >= 0 && right < arr.length) {
  18.                         if (pivot - arr[left]  > arr[right] - pivot) {
  19.                                 res[pos++] = arr[right];.鐣欏璁哄潧-涓浜-涓夊垎鍦
  20.                                 right++;
  21.                         } else {. 1point3acres.com/bbs
  22.                                 res[pos++] = arr[left];
  23.                                 left--;
  24.                         }
  25.                 }
  26.                 while (left >= 0) {. 鍥磋鎴戜滑@1point 3 acres
  27.                         res[pos++] = arr[left];
  28.                         left--;
  29.                 }
  30.                 while (right < arr.length) {
  31.                         res[pos++] = arr[right];
  32.                         right++;
  33.                 }
  34.                 for (int i = 0; i < res.length; i++) {
  35.                         res[i] = getResult(res[i], a, b, c);
  36.                 }
  37.                 if (a < 0) {
  38.                         reverse(res);
  39.                 }
  40.                 return res;
  41.         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  42. . visit 1point3acres.com for more.
  43.         private static void reverse(int[] res) {
  44.                 int left = 0;
  45.                 int right = res.length - 1;
  46.                 while (left < right) {
  47.                         int tmp = res[right];. Waral 鍗氬鏈夋洿澶氭枃绔,
  48.                         res[right] = res[left];
  49.                         res[left] = tmp;
  50.                         left++;
  51.                         right--;
    .1point3acres缃
  52.                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  53.         }

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

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

使用道具 举报

 楼主| 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, 2017-2-25 23:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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