一亩三分地论坛

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

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

Google 1月 Onsite 面经

[复制链接] |试试Instant~ |关注本帖
chasingthesun 发表于 2016-2-2 09:44:40 | 显示全部楼层 |阅读模式

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

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

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

x

round 1:
  • 黑白棋。给一个棋盘和一个棋子的坐标,判断这个棋子是不是活的。Leetcode也有类似的比这个难得题目。DFS/BFS看能不能走到棋盘的边缘就好。分析复杂度。
  • 给一堆点,问怎么画凸包,说思路就好。这个面经上没见过,lz当时是完全不知道凸包的概念。
round 2:
  • 写有weight的随机数生成器,请参见以前的面经。写完之后问了如何测试。
  • 给一个int array,和一个这个array里面存在的数字,把这个数移到array的最后面。two pointers就好。. more info on 1point3acres.com
round 3:
  • 给一个int array,找任意一个popular number, popular number就是出现次数大于等于array length 的 1/4 的数。其实就是 Leetcode 169, 229 Mojority Element. 第一问unsorted array 用的hashmap。 第二问sorted array用的binary search。lz没有说moore's voting algorithm的做法感觉有点假。第二问复杂度,worst case问的很细。
round 4:
  • 类似Leetcode 26, 80, remove adjacent duplicate elements from a list of characters。
  • 类似Lint code data stream median, 写个API,有两个方法,addURL(String url) 和 getURL(),getURL()返回的是目前为止所有URL长度的中位数。lz使用两个heap做的。follow-up: what if we know the range of the input,比如我们知道URL的大小不会超过2k,那有没有别的implement的方法。这个没想出来请大家指教。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

 楼主| chasingthesun 发表于 2016-2-2 12:50:29 | 显示全部楼层
chasingthesun 发表于 2016-2-2 12:47
凸包我回来还没仔细查,有weight随机数题目和代码如下:

import java.util.Arrays;

import java.util.Arrays;
import java.util.Random;

/**
大概就是一个数组
1,4,2,6....
每次调用一个函数,按照数组里面的数字的大小,返回相应的Index。
比如, 上面的例子就是
1/13 的概率返回0,. from: 1point3acres.com/bbs
4/13的概率返回1.
说了两个办法,一个累加起来, 然后用一个随即数,看看在哪个范围里面。另一个先加好,然后Binary search,让写了第二个。
大概写了5分钟,然后改成了一个class,. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
因为题目有什么城市阿,人口阿乱七八糟的。 又华了5分钟,然后没时间了。-google 1point3acres
*/
public class Q099_Random_Number_Generator_With_Probality {. more info on 1point3acres.com
        public static void main(String[] args) {
                int[] nums = {1, 4, 2, 6};
                MyRNG r0 = new MyRNG(nums); //
                MyRNG2 r = new MyRNG2(nums);
                System.out.println(r.nextInt());
               
        }
}

// O(nums.length) space, O(logn) time
class MyRNG2 extends Random{
        int[] probs;
        Random r = new Random();
        . From 1point 3acres bbs
        public MyRNG2(int[] nums) {
                probs = new int[nums.length];
                probs[0] = nums[0];.鏈枃鍘熷垱鑷1point3acres璁哄潧
                for (int i = 1; i < nums.length; i++) {
                        probs = probs[i - 1] + nums;
                }
                System.out.println(Arrays.toString(probs));. From 1point 3acres bbs
        }
. visit 1point3acres.com for more.       
        @Override
        public int nextInt() {
                int target = r.nextInt(probs[probs.length - 1] + 1);
                return search(probs, target);
        }
       
        private int search(int[] nums, int target) {
                int start = 0, end = nums.length - 1;
                while (start <= end) {
                        int mid = start + (end - start) / 2;. Waral 鍗氬鏈夋洿澶氭枃绔,
                        if (nums[mid] >= target) {
                                end = mid - 1;
                        } else {
                                start = mid + 1;
                        }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                }
               
                return end + 1;
        }
}

// O(cum) space, O(1) time
class MyRNG extends Random{
        int[] probs;
        Random r = new Random();
        public MyRNG(int[] nums) {
                int sum = 0;
                for (int i = 0; i < nums.length; i++) {. 鍥磋鎴戜滑@1point 3 acres
                        sum += nums;
                }.鐣欏璁哄潧-涓浜-涓夊垎鍦
                probs = new int[sum];
                int index = -1;
                for (int i = 0; i < nums.length; i++) {
                        int count = 0;
                        while (count++ < nums) {
                                probs[++index] = i;
. Waral 鍗氬鏈夋洿澶氭枃绔,                        }
                }
                System.out.println(Arrays.toString(probs));
        }
        鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        @Override
        public int nextInt() {
                int index = r.nextInt(probs.length);
                return probs[index];
        }
}
回复 支持 2 反对 0

使用道具 举报

lancelot981 发表于 2016-2-2 12:08:47 | 显示全部楼层
最后一题可以用Binary Index Tree,add和get操作都是log(n)
回复 支持 1 反对 0

使用道具 举报

haifengc 发表于 2016-2-2 10:55:47 | 显示全部楼层
类似Lint code data stream median, 写个API,有两个方法,addURL(String url) 和 getURL(),getURL()返回的是目前为止所有URL长度的中位数。lz使用两个heap做的。follow-up: what if we know the range of the input,比如我们知道URL的大小不会超过2k,那有没有别的implement的方法。这个没想出来请大家指教。

感觉可以用一个2k的数组,比如a[i]记录长度小于等于i的URL的个数,然后用二分来找中位数,这样行不?
回复 支持 反对

使用道具 举报

Hotzenplotz 发表于 2016-2-2 11:23:10 | 显示全部楼层
请问LZ是在哪里面的?
回复 支持 反对

使用道具 举报

 楼主| chasingthesun 发表于 2016-2-2 11:24:31 | 显示全部楼层
Hotzenplotz 发表于 2016-2-2 11:23
请问LZ是在哪里面的?

在匹兹堡
回复 支持 反对

使用道具 举报

Hotzenplotz 发表于 2016-2-2 11:27:31 | 显示全部楼层
. from: 1point3acres.com/bbs
请问是多久以前啊?
回复 支持 反对

使用道具 举报

lancelot981 发表于 2016-2-2 12:04:15 | 显示全部楼层
同意楼主,我也觉得moore's voting algorithm有点假,不做题根本不会知道
回复 支持 反对

使用道具 举报

cocaptainco 发表于 2016-2-2 12:15:54 | 显示全部楼层
感觉楼主面的可以啊,feedback咋说
回复 支持 反对

使用道具 举报

 楼主| chasingthesun 发表于 2016-2-2 12:35:51 | 显示全部楼层
Hotzenplotz 发表于 2016-2-2 11:27
请问是多久以前啊?

1月20号面的
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-2 12:40:42 | 显示全部楼层
最后面第二个题就是bucket sort, 另外求问凸包和weight随机数的详情和解法...
回复 支持 反对

使用道具 举报

 楼主| chasingthesun 发表于 2016-2-2 12:47:08 | 显示全部楼层
johnjavabean 发表于 2016-2-2 12:40
最后面第二个题就是bucket sort, 另外求问凸包和weight随机数的详情和解法...

凸包我回来还没仔细查,有weight随机数题目和代码如下:

import java.util.Arrays;. from: 1point3acres.com/bbs
import java.util.Random;
  1. <div>/**</div><div></div><div>大概就是一个数组</div><div>1,4,2,6....</div><div>每次调用一个函数,按照数组里面的数字的大小,返回相应的Index。</div><div>比如, 上面的例子就是</div><div>1/13 的概率返回0,</div><div>4/13的概率返回1.</div><div>说了两个办法,一个累加起来, 然后用一个随即数,看看在哪个范围里面。另一个先加好,然后Binary search,让写了第二个。</div><div>大概写了5分钟,然后改成了一个class,</div><div>因为题目有什么城市阿,人口阿乱七八糟的。 又华了5分钟,然后没时间了。</div><div> */</div><div>public class Q099_Random_Number_Generator_With_Probality {</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>public static void main(String[] args) {</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>int[] nums = {1, 4, 2, 6};</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>MyRNG r0 = new MyRNG(nums); // </div><div><span class="Apple-tab-span" style="white-space:pre">                </span>MyRNG2 r = new MyRNG2(nums);</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>System.out.println(r.nextInt());</div><div><span class="Apple-tab-span" style="white-space:pre">                </span></div><div><span class="Apple-tab-span" style="white-space:pre">        </span>}</div><div>}</div><div>
  2. </div><div>// O(nums.length) space, O(logn) time</div><div>class MyRNG2 extends Random{</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>int[] probs;</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>Random r = new Random();</div><div><span class="Apple-tab-span" style="white-space:pre">        </span></div><div><span class="Apple-tab-span" style="white-space:pre">        </span>public MyRNG2(int[] nums) {</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>probs = new int[nums.length];</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>probs[0] = nums[0];</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>for (int i = 1; i < nums.length; i++) {</div><div><span class="Apple-tab-span" style="white-space:pre">                        </span>probs[i] = probs[i - 1] + nums[i];</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>}</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>System.out.println(Arrays.toString(probs));</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>}</div><div><span class="Apple-tab-span" style="white-space:pre">        </span></div><div><span class="Apple-tab-span" style="white-space:pre">        </span>@Override </div><div><span class="Apple-tab-span" style="white-space:pre">        </span>public int nextInt() {</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>int target = r.nextInt(probs[probs.length - 1] + 1);</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>return search(probs, target);</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>}</div><div><span class="Apple-tab-span" style="white-space:pre">        </span></div><div><span class="Apple-tab-span" style="white-space:pre">        </span>private int search(int[] nums, int target) {</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>int start = 0, end = nums.length - 1;</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>while (start <= end) {</div><div><span class="Apple-tab-span" style="white-space:pre">                        </span>int mid = start + (end - start) / 2;</div><div><span class="Apple-tab-span" style="white-space:pre">                        </span>if (nums[mid] >= target) {</div><div><span class="Apple-tab-span" style="white-space:pre">                                </span>end = mid - 1;</div><div><span class="Apple-tab-span" style="white-space:pre">                        </span>} else {</div><div><span class="Apple-tab-span" style="white-space:pre">                                </span>start = mid + 1;</div><div><span class="Apple-tab-span" style="white-space:pre">                        </span>}</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>}</div><div><span class="Apple-tab-span" style="white-space:pre">                </span></div><div><span class="Apple-tab-span" style="white-space:pre">                </span>return end + 1;</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>}</div><div>}</div><div>
  3. </div><div>// O(cum) space, O(1) time</div><div>class MyRNG extends Random{</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>int[] probs;</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>Random r = new Random();</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>public MyRNG(int[] nums) {</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>int sum = 0;</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>for (int i = 0; i < nums.length; i++) {</div><div><span class="Apple-tab-span" style="white-space:pre">                        </span>sum += nums[i];</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>}</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>probs = new int[sum];</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>int index = -1;</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>for (int i = 0; i < nums.length; i++) {</div><div><span class="Apple-tab-span" style="white-space:pre">                        </span>int count = 0;</div><div><span class="Apple-tab-span" style="white-space:pre">                        </span>while (count++ < nums[i]) {</div><div><span class="Apple-tab-span" style="white-space:pre">                                </span>probs[++index] = i;</div><div><span class="Apple-tab-span" style="white-space:pre">                        </span>}</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>}</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>System.out.println(Arrays.toString(probs));</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>}</div><div><span class="Apple-tab-span" style="white-space:pre">        </span></div><div><span class="Apple-tab-span" style="white-space:pre">        </span>@Override </div><div><span class="Apple-tab-span" style="white-space:pre">        </span>public int nextInt() {</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>int index = r.nextInt(probs.length);</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>return probs[index];</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>}</div><div>}</div>
复制代码

补充内容 (2016-2-2 12:49):
啊抱歉格式怎么变成了这样。。。可以删一下吗。。。
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-2-2 13:41:12 | 显示全部楼层
楼主跪在哪里?你不是都做出来了吗?
回复 支持 反对

使用道具 举报

Fiery 发表于 2016-2-2 13:55:33 | 显示全部楼层
能麻烦LZ讲一下round 3的sorted array是怎么用binary search的呀?没想出lgN的解法。。
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-2-2 14:20:40 | 显示全部楼层
Fiery 发表于 2016-2-2 13:55
能麻烦LZ讲一下round 3的sorted array是怎么用binary search的呀?没想出lgN的解法。。
. more info on 1point3acres.com
一个思路:分成8段,看那些段的首尾相同。对于首尾相同的,再用binary search依次找到该数出现的频率,取频率大于1/4那个
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-2 14:45:47 | 显示全部楼层
chasingthesun 发表于 2016-2-2 12:50
import java.util.Arrays;
import java.util.Random;

好的,谢谢啦
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-2 14:47:14 | 显示全部楼层
Fiery 发表于 2016-2-2 13:55
. 1point 3acres 璁哄潧能麻烦LZ讲一下round 3的sorted array是怎么用binary search的呀?没想出lgN的解法。。

n/4的话只需要看0, n/4, n/2, n*3/4, n这几个点相邻的是否相等,相等那个数就是popular number

补充内容 (2016-2-2 14:48):
好像不对,请忽略我
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-2-2 15:09:51 | 显示全部楼层
johnjavabean 发表于 2016-2-2 14:47
n/4的话只需要看0, n/4, n/2, n*3/4, n这几个点相邻的是否相等,相等那个数就是popular number. 1point3acres.com/bbs

补充内容 ...

如果是 sorted, 这样搞?. Waral 鍗氬鏈夋洿澶氭枃绔,

(1)看 arr[0]和 arr[n/4]是否相等,相等则返回arr[0]; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
(2)如果不等, binary search arr[n/4]第一次出现的位置,假设为j,比较 arr[j] 和 arr[j+n/4],相等则返回 arr[j]
(3) 如果上一步还好是不返回,接着binary search [n/2]...
(4) 类似的接着binary search [n/4]

补充内容 (2016-2-2 15:55):
第三步是 搜索 arr[n/2]
第四部是搜索 arr[3n/4]

最坏的情况是3次 binary search, 4次comparison.
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-2 15:17:18 | 显示全部楼层
guixi107 发表于 2016-2-2 15:09
如果是 sorted, 这样搞?. 1point 3acres 璁哄潧

(1)看 arr[0]和 arr[n/4]是否相等,相等则返回arr[0];

楼上有个说法对了,分成八段找相同的,n/4必定会cover一个n/8的区域,然后再对那个数search range,两次binary search 搞定
回复 支持 反对

使用道具 举报

Fiery 发表于 2016-2-2 15:24:15 | 显示全部楼层
googlerr 发表于 2016-2-2 14:20
一个思路:分成8段,看那些段的首尾相同。对于首尾相同的,再用binary search依次找到该数出现的频率,取 ...

有一定道理!我也觉得先确定几个数,再分别用binary search去找精确区间是合理的。. visit 1point3acres.com for more.
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2016-2-2 15:40):
细想了一下,貌似check 0, 1/4, 1/2, 3/4, 1这五个点对应的range就可以了,必有一个是落在1/4 majority里面的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 21:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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