传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 5304|回复: 35
收起左侧

只有三轮的google onsite

[复制链接] |试试Instant~ |关注本帖
muxin4ever 发表于 2014-2-21 13:49:28 | 显示全部楼层 |阅读模式

2014(1-3月) 码农类 本科 全职@Google - 校园招聘会 - Onsite |Other

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
一面:一个array里面找最大的这样的h:有h个数大于等于h
二面:十进制十八进制转换,十八进制加法
三面:majority element. 1point3acres.com/bbs

因为room overbooked,找conference room找了二十分钟。。。第一面开始的不是很顺利,有点紧张,虽然写出来了但是过程太纠结。
面试的时候有个review sheet,第三面的时候我瞄了一眼,第一面那里写的“CL”,第二面写的“AP”,也不知道是什么意思。CL肯定不是神马好词的样子,哎哎。。。



补充内容 (2014-2-22 01:41):
突然想起来,一面的面试官叫Cliffton,于是又猜测那几个字母只是initial而已。。。汗=。=
. 1point3acres.com/bbs
补充内容 (2014-2-23 14:42):
补充一下on campus的两道吧
一:Leetcode的Spiral Matrix,螺旋打印矩阵
二:给以下矩阵序列
level 0:. 鍥磋鎴戜滑@1point 3 acres
0
level 1:
1,2
3,4
level 2:
5,6,7,8
9,10,11,12
13,14,15,16
17,18,19,20
写个转换方程
. Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (2014-2-23 14:42):. visit 1point3acres.com for more.
int get(int level, int i, int j)

评分

2

查看全部评分

本帖被以下淘专辑推荐:

nullas 发表于 2014-11-16 08:10:40 | 显示全部楼层
http://stackoverflow.com/questions/20139640/looking-for-algorithm-to-calculate-h-index-fast. Waral 鍗氬鏈夋洿澶氭枃绔,

h-index的代码。。。非常简洁
回复 支持 1 反对 0

使用道具 举报

testestest2008 发表于 2014-2-22 01:02:10 | 显示全部楼层
blessing
回复 支持 反对

使用道具 举报

testestest2008 发表于 2014-2-22 01:03:13 | 显示全部楼层
楼主去哪面的?求去pitts的经验。。。
回复 支持 反对

使用道具 举报

 楼主| muxin4ever 发表于 2014-2-22 01:42:11 | 显示全部楼层
回复 支持 反对

使用道具 举报

adlxk 发表于 2014-2-23 03:51:54 | 显示全部楼层
blessing....G onsite只有三轮倒是头一次听说,第一题有朋友面G的时候碰过,给了一个scenario,求researcher的H index,要求O(n)的时间复杂度,后面的follow up还扯到了map reduce
回复 支持 反对

使用道具 举报

abccb1 发表于 2014-2-23 06:11:03 | 显示全部楼层
bless楼主
回复 支持 反对

使用道具 举报

 楼主| muxin4ever 发表于 2014-2-23 08:51:28 | 显示全部楼层
adlxk 发表于 2014-2-23 03:51
blessing....G onsite只有三轮倒是头一次听说,第一题有朋友面G的时候碰过,给了一个scenario,求researche ...

可能是因为我有过两轮on campus? 第一题我只写了sort之后走一遍找h的O(n)的代码,好吧,就四五行,我花了半小时。。。我提到sort可以bucket sort,但没时间写了。。。
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-2-23 09:43:26 | 显示全部楼层
muxin4ever 发表于 2014-2-22 19:51
可能是因为我有过两轮on campus? 第一题我只写了sort之后走一遍找h的O(n)的代码,好吧,就四五行,我花了 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一题是快排二分+快排的partitioning。
第三题要求majority element频率过半否?如果是就是经典题, 如果不是暂时想不到啥好方法。
回复 支持 反对

使用道具 举报

 楼主| muxin4ever 发表于 2014-2-23 12:04:49 | 显示全部楼层
北美农民 发表于 2014-2-23 09:43
第一题是快排二分+快排的partitioning。
第三题要求majority element频率过半否?如果是就是经典题, 如 ...

我不太懂你说的。那看来第一题我做错了?我是这么写的。。。
        public static int findH(int[] a){
                // sort the array first
                int max = 0;
                int n = a.length;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                for(int i = 0, h=1;h<=n-i;h++){
                        if(n-i>=h)
                                max=h;
                        while(h>=a)
                                i++;
                }. 1point3acres.com/bbs
                return max;
        }

第三题就是找超过n/2的,n/2是向下取整,有奇偶数的细节要考虑,好吧,貌似也没啥。。。
回复 支持 反对

使用道具 举报

adlxk 发表于 2014-2-23 12:15:41 | 显示全部楼层
muxin4ever 发表于 2014-2-23 08:51
可能是因为我有过两轮on campus? 第一题我只写了sort之后走一遍找h的O(n)的代码,好吧,就四五行,我花了 ...

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷呃。。那这轮有点悬啊,如果是排好序之后的话,可以binary search O(logN)找到的。其实你提到bucket sort是正确的方向,h的最大也不会超过array的size
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-2-23 12:18:01 | 显示全部楼层
muxin4ever 发表于 2014-2-22 23:04 .鏈枃鍘熷垱鑷1point3acres璁哄潧
我不太懂你说的。那看来第一题我做错了?我是这么写的。。。
        public static int findH(int[] a){
                // ...

看不懂你的代码。 什么h >= a, i ++
回复 支持 反对

使用道具 举报

adlxk 发表于 2014-2-23 12:28:54 | 显示全部楼层
muxin4ever 发表于 2014-2-23 12:04
我不太懂你说的。那看来第一题我做错了?我是这么写的。。。
        public static int findH(int[] a){
                // ...

北美农民说的“第一题是快排二分+快排的partitioning。”这个方法平均情况下可以达到O(n),其实就类似quick select (O(n)时间下在unsorted array中找第k大的elem),思路就是如果array排好序后可以binary找到目标,那么在未排序的情况下用quick sort的一次parition确定的pivot位置是最终排好序的位置,然后apply同样的binary过程,这样可以避免sort整个array
回复 支持 反对

使用道具 举报

 楼主| muxin4ever 发表于 2014-2-23 13:54:48 | 显示全部楼层
北美农民 发表于 2014-2-23 12:18 . 1point3acres.com/bbs
看不懂你的代码。 什么h >= a, i ++

是while(h>=a),不知道为什么贴过来没有了,还变了斜体。。。
.1point3acres缃
补充内容 (2014-2-23 13:55):
while(h >= a [ i ] )
回复 支持 反对

使用道具 举报

 楼主| muxin4ever 发表于 2014-2-23 14:45:17 | 显示全部楼层
adlxk 发表于 2014-2-23 12:28 . 鍥磋鎴戜滑@1point 3 acres
北美农民说的“第一题是快排二分+快排的partitioning。”这个方法平均情况下可以达到O(n),其实就类似qui ...

恩,原来partition就好了呀,我这个方法太笨了。。。
回复 支持 反对

使用道具 举报

adlxk 发表于 2014-2-23 14:54:39 | 显示全部楼层
muxin4ever 发表于 2014-2-23 14:45
恩,原来partition就好了呀,我这个方法太笨了。。。

想确认一下第一题里面的要求是返回array里面的元素吗?还是H index?
回复 支持 反对

使用道具 举报

 楼主| muxin4ever 发表于 2014-2-23 14:57:22 | 显示全部楼层
adlxk 发表于 2014-2-23 14:54
想确认一下第一题里面的要求是返回array里面的元素吗?还是H index?

返回h,比如{2,3,5}答案是2,{5,6,7,8}答案是4
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-2-23 15:27:36 | 显示全部楼层
muxin4ever 发表于 2014-2-23 01:57 . 鍥磋鎴戜滑@1point 3 acres
返回h,比如{2,3,5}答案是2,{5,6,7,8}答案是4

你的代码似乎是在枚举h, 我没看太懂。 我写了个partition的。
  1. public static int findH(int[] a) {
  2.     int start = 0;
  3.     int end = a.length - 1;
  4.     int pivot;
  5.     int result = -1;. From 1point 3acres bbs
  6.    
  7.     while (start <= end) {
  8.       swap(a, end, start + (end - start) / 2); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  9.       pivot = a[end];
  10.       int p = start - 1;
  11.       
  12.       //partitioning
  13.       for (int i = start; i < end; i ++)
  14.         if (a[i] > pivot) swap(a, i, ++p);
  15.       swap(a, end, ++p);
  16.       
  17.       if (p == a[p]) {
  18.          result = a[p];-google 1point3acres
  19.          end = p - 1;
  20.       }
  21.       else if (p < a[p]) start = p + 1;
  22.       else end = p - 1;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  23.     }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  24.    
  25.     return result;
  26.   }
  27.   
  28.   private static void swap(int[] a, int i, int j) {
  29.     int t = a[i];. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  30.     a[i] = a[j];
  31.     a[j] = t;
  32.   }
复制代码
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-2-23 15:37:48 | 显示全部楼层
muxin4ever 发表于 2014-2-22 23:04
我不太懂你说的。那看来第一题我做错了?我是这么写的。。。
        public static int findH(int[] a){
                // ...

你的这段代码, 既然a已经排序了(假设升序), 为什么不直接这么写?

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷for (int i = a.length - 1; i >= 0; i --). from: 1point3acres.com/bbs
    if (a = a.length - 1 - i) return a;.鐣欏璁哄潧-涓浜-涓夊垎鍦
. 1point 3acres 璁哄潧
补充内容 (2014-2-23 02:38):
a是a[ i ]
回复 支持 反对

使用道具 举报

 楼主| muxin4ever 发表于 2014-2-23 15:53:56 | 显示全部楼层
北美农民 发表于 2014-2-23 15:27 . 1point3acres.com/bbs
你的代码似乎是在枚举h, 我没看太懂。 我写了个partition的。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我上面回复的例子你测过么。{5,6,7,8}要返回4的。我改了下你的,你可以测一下对不对,如下
  1. . Waral 鍗氬鏈夋洿澶氭枃绔,
  2.     public static int findH(int[] a) {
  3.         int start = 0;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  4.         int end = a.length - 1;
  5.         int pivot;
  6.         int result = -1;

  7.         while (start <= end) {
    . from: 1point3acres.com/bbs
  8.             swap(a, end, start + (end - start) / 2);
  9.             pivot = a[end];.鏈枃鍘熷垱鑷1point3acres璁哄潧
  10.             int p = start - 1;

  11.             // partitioning
  12.             for (int i = start; i < end; i++)
  13.                 if (a[i] > pivot). 鍥磋鎴戜滑@1point 3 acres
  14.                     swap(a, i, ++p);
  15.             swap(a, end, ++p);

  16.             if (p + 1 <= a[p]) {
  17.                 result = p + 1;
  18.                 start = p + 1;
  19.             } else {
  20.                 end = p - 1;
  21.             }
  22.         }
  23.         return result;
  24.     }

  25.     private static void swap(int[] a, int i, int j) {
  26.         int t = a[i];
  27.         a[i] = a[j];
  28.         a[j] = t;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  29.     }
复制代码


顺便附个我刚才的代码

  1.     public static int findH(int[] a) {
  2.         // sort the array first (can use bucket sort)
  3.         Arrays.sort(a);
  4.         int max = 0;
  5.         int n = a.length;
  6.         for (int i = 0, h = 1; h <= n - i; h++) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  7.             if (n - i >= h)
  8.                 max = h;
  9.             while (h >= a[i])
  10.                 i++;
  11.         }. more info on 1point3acres.com
  12.         return max;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  13.     }
复制代码

回复 支持 反对

使用道具 举报

adlxk 发表于 2014-2-23 16:42:37 | 显示全部楼层
muxin4ever 发表于 2014-2-23 14:57
返回h,比如{2,3,5}答案是2,{5,6,7,8}答案是4

ok, 那就是完全一样的题了。其实你们在写的partition方法不是最好的O(n),因为它worst case还是可能会到O(n^2),完全依赖于parition的效果。还是开一个size为n的数组来counting sort比较好,可以保证worst case O(n)
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-24 09:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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