一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2679|回复: 22
收起左侧

发个Google Onsite

[复制链接] |试试Instant~ |关注本帖
aloncgo 发表于 2016-3-9 07:14:10 | 显示全部楼层 |阅读模式

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

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

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

x
第一轮,tree版的 clone graph,状态不太好,被提醒了几次,有些无用的变量和步骤, 然后问了一下进程间通信怎么实现, 我答了通过文件或者socket

第二轮,就一道题   完完全全不会做, 面了这轮就知道悲剧了。。。
给一个un sorted array  长度为n
可以用 O(n)的时间和空间做 precomputation
然后 input是两个 int 表示区间, 输出那个区间的最大值
要求每次求最大值的时间为 O(log n)  反正我完全不会

第三轮,
https://leetcode.com/problems/se ... ialize-binary-tree/
https://leetcode.com/problems/largest-rectangle-in-histogram/


第四轮,
脑残DFS + 聊天

然后之后HR给我打电话,居然说再给我两轮电面,有点神奇,好好准备吧


补充内容 (2016-3-9 10:41):
当时第二轮的做法是,  把array分段,求每段的max,  设每段大小为K,   这样的话每次找max的时间复杂度是O(n / k) + 2k . more info on 1point3acres.com

补充内容 (2016-3-9 10:42):. from: 1point3acres.com/bbs
中间部分被完整包含于某段的直接查预先计算好的max就行了,遍历取最大就行了o(n / k), 需要单独处理两头o(2k)

补充内容 (2016-3-9 10:47):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
然后需要确定K的值,  总的比较次数就是 n /k + 2k , 求最小值, 对k求导后得到 2 - n * k ^ -2,  对应最小值的k 就是 sqrt(2n) / 4  

补充内容 (2016-3-9 10:47):
将k 值带入 时间复杂度和空间复杂度都能得到 O(logn)

评分

6

查看全部评分

csgtc 发表于 2016-3-9 07:37:33 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
第二题不就是裸的线段树么。。挺容易的呀 segment tree
回复 支持 1 反对 0

使用道具 举报

ryancooper 发表于 2016-3-10 00:28:52 | 显示全部楼层
关注一亩三分地微博:
Warald
aloncgo 发表于 2016-3-9 11:11
三哥提醒出来的。。。。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
准确来说你这个解法还不是时间和空间都是logn的做法啊,而是sqrt(n)吧。这里的思想是macro/micro decomposition。
回复 支持 1 反对 0

使用道具 举报

guschen802 发表于 2016-3-9 07:42:03 | 显示全部楼层
第二題我也不太懂唉,自己想了一個。。不知道算不算log(n);

  1. public class UnsortedArray {
  2.     public static void main(String[] args) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  3.         UnsortedArray us = new UnsortedArray(new int[]{1,1,1,1,1,6,1,1,1,1});
  4.         System.out.println(us.getIntervalMax(2,3));.鐣欏璁哄潧-涓浜-涓夊垎鍦
  5.         System.out.println(us.getIntervalMax(0,5));
  6.         System.out.println(us.getIntervalMax(4,6));
  7.         System.out.println(us.getIntervalMax(5,6));
  8. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  9.     }
  10.     private int[] array;
  11.     private int[] maxArray;
  12.     public UnsortedArray(int[] array) {
  13.         this.array = array;

  14.         if (array == null && array.length == 0) {
  15.             throw new IllegalArgumentException();
  16.         }
  17. . more info on 1point3acres.com
  18.         //maxArray[i] == max value from 0 ~ i
  19.         maxArray = new int[array.length]; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  20.         maxArray[0] = array[0];
  21.         for (int i = 1; i < array.length; i++) {
  22.             maxArray[i] = Math.max(maxArray[i-1], array[i]);
  23.         }
  24.     }

  25.     public int getIntervalMax (int i, int j) {. From 1point 3acres bbs
  26.         if (i < 0 || j < 0 || i >= array.length || j>= array.length ||i >j) {
    -google 1point3acres
  27.             throw new IllegalArgumentException();
  28.         }

  29.         //if maxArray[j]'s value is not equal to maxArray[i-1], which means maxArray[j]'s value
  30.         // must come from i~j, then just return
  31.         //O(1)
  32.         if (i == 0 || maxArray[j] != maxArray[i-1]) {
  33.             return maxArray[j];
  34.         }

  35.         //find max during i~j. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  36.         //O(j-i)
  37.         int max = array[i];
  38.         for (int x = i +1; x <= j; x++) {
  39.             max = Math.max(array[x], max);
  40.         }
  41.         return max;
  42.     }
  43. }
复制代码

补充内容 (2016-3-9 07:42):
無視test case...後來隨手改了一個= =

补充内容 (2016-3-9 09:01):
樓下發了個segment tree版的,現學的。。
回复 支持 反对

使用道具 举报

guschen802 发表于 2016-3-9 07:44:06 | 显示全部楼层
csgtc 发表于 2016-3-9 07:37
.鏈枃鍘熷垱鑷1point3acres璁哄潧第二题不就是裸的线段树么。。挺容易的呀 segment tree

最近才聽說的segment tree呢。。表示自己好無知啊。。求問還有什麼類似的高級一點的數據結構?想去了解下
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

guschen802 发表于 2016-3-9 09:01:19 | 显示全部楼层
根據2樓提示,現學了一把segment tree, 求大神們檢查和指教,謝謝!. 鍥磋鎴戜滑@1point 3 acres

  1. public class UnsortedArray {-google 1point3acres
  2.     public static void main(String[] args) {
  3.         UnsortedArray us = new UnsortedArray(new int[]{5,4,2,1,9,8,7});
  4.         System.out.println(us.getIntervalMax(2,3) == 2);
  5.         System.out.println(us.getIntervalMax(0,5) == 9);
  6.         System.out.println(us.getIntervalMax(4,6) == 9);
  7.         System.out.println(us.getIntervalMax(5,6) == 8);.1point3acres缃
  8.         System.out.println(us.getIntervalMax(3,3) == 1);
  9.     }
  10.     private int[] array;
  11.     private SegmentNode root;
  12.     public UnsortedArray(int[] array) {
  13.         this.array = array;
  14. . 1point 3acres 璁哄潧
  15.         if (array == null && array.length == 0) {
  16.             throw new IllegalArgumentException();
  17.         }.1point3acres缃

  18.         Queue<SegmentNode> queue = new LinkedList<>();. 1point 3acres 璁哄潧

  19.         for (int i = 0; i < array.length; i++) {
  20.             queue.offer(new SegmentNode(i,i,array[i]));
  21.         }

  22.         while (queue.size() >1) {
  23.             int size = queue.size();
  24.             for (int i = 0; i < size;) {
  25.                 if (i == size-1) {
  26.                     queue.offer(queue.poll());
  27.                     break;
  28.                 }
  29.                 SegmentNode left = queue.poll();
  30.                 SegmentNode right = queue.poll();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  31.                 SegmentNode newNode = new SegmentNode(left.start, right.end, Math.max(left.max, right.max));. visit 1point3acres.com for more.
  32.                 newNode.left = left;
  33.                 newNode.right = right;. Waral 鍗氬鏈夋洿澶氭枃绔,
  34.                 queue.offer(newNode);
  35.                 i += 2;
  36.             }
  37.         }
  38.         root = queue.poll();
  39.     }

  40.     public int getIntervalMax (int i, int j) {
  41.         if (i < 0 || j < 0 || i >= array.length || j>= array.length ||i >j) {
  42.             throw new IllegalArgumentException();
  43.         }

  44.         return helper(root,i,j);. more info on 1point3acres.com
  45.     }

  46.     private int helper(SegmentNode node,int i, int j) {
  47.         if (node.start == i && node.end == j) {
  48.             return node.max;. From 1point 3acres bbs
  49.         }
  50.         if (i > node.mid) {
  51.             return helper(node.right, i, j);
  52.         }
  53.         if (j <= node.mid) {
  54.             return helper(node.left, i, j);
  55.         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  56. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  57.         return Math.max(helper(node.left, i, node.mid), helper(node.right, node.mid+1, j));

  58.     }

  59.     class SegmentNode {
  60.         int start;
  61.         int end;
  62.         int mid;
  63.         int max;
  64.         SegmentNode left;
  65.         SegmentNode right;

  66.         public SegmentNode(int start, int end, int max) {
  67.             this.start = start;
  68.             this.end = end;
  69.             mid = start + (end - start)/2;
  70.             this.max = max;
  71.         }

  72.         @Override
  73.         //for debug. Waral 鍗氬鏈夋洿澶氭枃绔,
  74.         public String toString() {
  75.             return "SegmentNode{" +
  76.                     "start=" + start +-google 1point3acres
  77.                     ", end=" + end +
  78.                     ", max=" + max +
  79.                     '}';
  80.         }. more info on 1point3acres.com
  81.     }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  82. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| aloncgo 发表于 2016-3-9 09:20:02 | 显示全部楼层
csgtc 发表于 2016-3-9 07:37. Waral 鍗氬鏈夋洿澶氭枃绔,
第二题不就是裸的线段树么。。挺容易的呀 segment tree
.鐣欏璁哄潧-涓浜-涓夊垎鍦
我给他说了一下线段树了。不过我当时说的空间o(n),   他说得log n      我发错了。pre computation 是要小于o n 空间
回复 支持 反对

使用道具 举报

guschen802 发表于 2016-3-9 09:31:29 | 显示全部楼层
aloncgo 发表于 2016-3-9 09:20
我给他说了一下线段树了。不过我当时说的空间o(n),   他说得log n      我发错了。pre computation 是要 ...

唉。。要log(n)的話。。。-0-投降,求來個大神指教
回复 支持 反对

使用道具 举报

 楼主| aloncgo 发表于 2016-3-9 10:48:49 | 显示全部楼层
guschen802 发表于 2016-3-9 09:31
唉。。要log(n)的話。。。-0-投降,求來個大神指教

我把当时的做法更新上去了
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-3-9 11:11:43 | 显示全部楼层
第二轮能想出这个做法也是够厉害的。。。
回复 支持 反对

使用道具 举报

 楼主| aloncgo 发表于 2016-3-9 11:11:59 | 显示全部楼层
william_gong 发表于 2016-3-9 11:11
第二轮能想出这个做法也是够厉害的。。。

三哥提醒出来的。。。。
回复 支持 反对

使用道具 举报

hercule24 发表于 2016-3-10 00:34:22 | 显示全部楼层
请问楼主面的是tools and infrastructure吗
回复 支持 反对

使用道具 举报

 楼主| aloncgo 发表于 2016-3-10 00:35:06 | 显示全部楼层
hercule24 发表于 2016-3-10 00:34
请问楼主面的是tools and infrastructure吗

不是的,就一般的SDE
回复 支持 反对

使用道具 举报

hercule24 发表于 2016-3-10 00:37:08 | 显示全部楼层
aloncgo 发表于 2016-3-10 00:35
不是的,就一般的SDE

我面的是tools and infrastructure 本质上好像是测试组 我有同学之前也面了SWE/SDE 但是没有面好 加面就让调低难度面tools and infrastructure了
回复 支持 反对

使用道具 举报

 楼主| aloncgo 发表于 2016-3-10 00:43:29 | 显示全部楼层
hercule24 发表于 2016-3-10 00:37
.鐣欏璁哄潧-涓浜-涓夊垎鍦我面的是tools and infrastructure 本质上好像是测试组 我有同学之前也面了SWE/SDE 但是没有面好 加面就 ...

挺有可能啊。。 我觉得我前两轮实在太糟糕了
回复 支持 反对

使用道具 举报

 楼主| aloncgo 发表于 2016-3-10 00:45:36 | 显示全部楼层
ryancooper 发表于 2016-3-10 00:28
准确来说你这个解法还不是时间和空间都是logn的做法啊,而是sqrt(n)吧。这里的思想是macro/micro decompo ...

是啊。。 我当时都还不知道 logn 和 sqrt n 不一样。。。 太蠢了.鐣欏璁哄潧-涓浜-涓夊垎鍦

补充内容 (2016-3-10 00:45):
log n 实在不会
回复 支持 反对

使用道具 举报

hercule24 发表于 2016-3-10 00:46:24 | 显示全部楼层
aloncgo 发表于 2016-3-10 00:43
挺有可能啊。。 我觉得我前两轮实在太糟糕了
.鏈枃鍘熷垱鑷1point3acres璁哄潧
加油 我上周三面的 正在想要不要去催一下结果。。。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-10 01:54:10 | 显示全部楼层
ryancooper 发表于 2016-3-10 00:28. visit 1point3acres.com for more.
准确来说你这个解法还不是时间和空间都是logn的做法啊,而是sqrt(n)吧。这里的思想是macro/micro decompo ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
大神可以详细说说解法吗?我想到的就是用segment tree啊,O(n)时间和空间的复杂度做预处理
回复 支持 反对

使用道具 举报

tmacytr 发表于 2016-3-10 02:26:48 | 显示全部楼层
第二轮长见识了。。。
回复 支持 反对

使用道具 举报

yijingzeng 发表于 2016-3-11 05:18:21 | 显示全部楼层
楼主能说说第四轮的题目吗?谢谢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-2-20 07:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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