一亩三分地论坛

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

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

只有三轮的google onsite

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

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

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

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

x
一面:一个array里面找最大的这样的h:有h个数大于等于h
二面:十进制十八进制转换,十八进制加法
三面:majority element
. from: 1point3acres.com/bbs
因为room overbooked,找conference room找了二十分钟。。。第一面开始的不是很顺利,有点紧张,虽然写出来了但是过程太纠结。.鏈枃鍘熷垱鑷1point3acres璁哄潧
面试的时候有个review sheet,第三面的时候我瞄了一眼,第一面那里写的“CL”,第二面写的“AP”,也不知道是什么意思。CL肯定不是神马好词的样子,哎哎。。。



补充内容 (2014-2-22 01:41):
突然想起来,一面的面试官叫Cliffton,于是又猜测那几个字母只是initial而已。。。汗=。=

补充内容 (2014-2-23 14:42):
补充一下on campus的两道吧
一:Leetcode的Spiral Matrix,螺旋打印矩阵
二:给以下矩阵序列
level 0:
.鐣欏璁哄潧-涓浜-涓夊垎鍦0
level 1:
1,2
3,4
level 2:
5,6,7,8
9,10,11,12. 鍥磋鎴戜滑@1point 3 acres
13,14,15,16
17,18,19,20
写个转换方程. from: 1point3acres.com/bbs

. 1point3acres.com/bbs
补充内容 (2014-2-23 14:42):
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

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)的代码,好吧,就四五行,我花了 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
第一题是快排二分+快排的partitioning。 .1point3acres缃
第三题要求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;
                for(int i = 0, h=1;h<=n-i;h++){
                        if(n-i>=h)
                                max=h;
                        while(h>=a)
                                i++;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                }
                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
我不太懂你说的。那看来第一题我做错了?我是这么写的。。。
        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
看不懂你的代码。 什么h >= a, i ++

是while(h>=a),不知道为什么贴过来没有了,还变了斜体。。。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2014-2-23 13:55):
while(h >= a [ i ] )
回复 支持 反对

使用道具 举报

 楼主| muxin4ever 发表于 2014-2-23 14:45:17 | 显示全部楼层
adlxk 发表于 2014-2-23 12:28
北美农民说的“第一题是快排二分+快排的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
返回h,比如{2,3,5}答案是2,{5,6,7,8}答案是4

你的代码似乎是在枚举h, 我没看太懂。 我写了个partition的。
  1. public static int findH(int[] a) {
  2.     int start = 0;. 1point 3acres 璁哄潧
  3.     int end = a.length - 1;. 1point 3acres 璁哄潧
  4.     int pivot;.1point3acres缃
  5.     int result = -1;
  6.    
  7.     while (start <= end) {. 1point 3acres 璁哄潧
  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]) {. 1point3acres.com/bbs
  18.          result = a[p];
  19.          end = p - 1;
  20.       }
  21.       else if (p < a[p]) start = p + 1;
  22.       else end = p - 1;
  23.     }
  24.     . 1point3acres.com/bbs
  25.     return result;
  26.   }
  27.   . 1point3acres.com/bbs
  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){
                // ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
你的这段代码, 既然a已经排序了(假设升序), 为什么不直接这么写?

for (int i = a.length - 1; i >= 0; i --)
    if (a = a.length - 1 - i) return a;
.1point3acres缃
补充内容 (2014-2-23 02:38):. 1point 3acres 璁哄潧
a是a[ i ]
回复 支持 反对

使用道具 举报

 楼主| muxin4ever 发表于 2014-2-23 15:53:56 | 显示全部楼层
北美农民 发表于 2014-2-23 15:27 . From 1point 3acres bbs
你的代码似乎是在枚举h, 我没看太懂。 我写了个partition的。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我上面回复的例子你测过么。{5,6,7,8}要返回4的。我改了下你的,你可以测一下对不对,如下. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  1. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  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) {
  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++). From 1point 3acres bbs
  13.                 if (a[i] > pivot).鏈枃鍘熷垱鑷1point3acres璁哄潧
  14.                     swap(a, i, ++p);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  15.             swap(a, end, ++p);
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  16. . visit 1point3acres.com for more.
  17.             if (p + 1 <= a[p]) {
  18.                 result = p + 1;
  19.                 start = p + 1;
  20.             } else {
  21.                 end = p - 1;
  22.             }
  23.         }
  24.         return result;. 1point 3acres 璁哄潧
  25.     }
  26. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  27.     private static void swap(int[] a, int i, int j) {
  28.         int t = a[i]; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  29.         a[i] = a[j];.鏈枃鍘熷垱鑷1point3acres璁哄潧
  30.         a[j] = t;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  31.     }
复制代码

.鐣欏璁哄潧-涓浜-涓夊垎鍦
顺便附个我刚才的代码

  1.     public static int findH(int[] a) {
  2.         // sort the array first (can use bucket sort)
  3.         Arrays.sort(a);
  4.         int max = 0;.1point3acres缃
  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++;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  11.         }
  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)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 18:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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