要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
系统
1分钟前
系统
3分钟前
系统
4分钟前
系统
4分钟前
系统
6分钟前
全站
6分钟前
系统
6分钟前
系统
9分钟前
系统
10分钟前
系统
10分钟前
系统
10分钟前
系统
11分钟前
全站
Warald 说: MemorialDay大礼包之二:【新功能】论坛开启用户全局威望值,每楼右上方均可投票。
37分钟前
全站
Warald 说: MemorialDay大礼包之一:【新功能】发帖后,可以邀请朋友参与讨论(自动功能)
44分钟前
查看: 5679|回复: 35
收起左侧

只有三轮的google onsite

[复制链接] |试试Instant~ |关注本帖
我的人缘0
muxin4ever 发表于 2014-2-21 13:49:28 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

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

x
一面:一个array里面找最大的这样的h:有h个数大于等于h
二面:十进制十八进制转换,十八进制加法. 围观我们@1point 3 acres
三面:majority element. visit 1point3acres for more.

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

. 围观我们@1point 3 acres

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

补充内容 (2014-2-23 14:42):. Waral 博客有更多文章,
补充一下on campus的两道吧
一:Leetcode的Spiral Matrix,螺旋打印矩阵
二:给以下矩阵序列
level 0:
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.1point3acres网
写个转换方程. from: 1point3acres


补充内容 (2014-2-23 14:42):
int get(int level, int i, int j)

评分

2

查看全部评分


上一篇:Netsuite QA postion
下一篇:FB电话面经

本帖被以下淘专辑推荐:

我的人缘0
nullas 发表于 2014-11-16 08:10:40 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
http://stackoverflow.com/questions/20139640/looking-for-algorithm-to-calculate-h-index-fast
-google 1point3acres
h-index的代码。。。非常简洁
回复 支持 1 反对 0

使用道具 举报

我的人缘0
testestest2008 发表于 2014-2-22 01:02:10 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
blessing
回复 支持 反对

使用道具 举报

我的人缘0
testestest2008 发表于 2014-2-22 01:03:13 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
楼主去哪面的?求去pitts的经验。。。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| muxin4ever 发表于 2014-2-22 01:42:11 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
abccb1 发表于 2014-2-23 06:11:03 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
bless楼主
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| muxin4ever 发表于 2014-2-23 08:51:28 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
adlxk 发表于 2014-2-23 03:51
blessing....G onsite只有三轮倒是头一次听说,第一题有朋友面G的时候碰过,给了一个scenario,求researche ...

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

使用道具 举报

我的人缘0
北美农民 发表于 2014-2-23 09:43:26 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
muxin4ever 发表于 2014-2-22 19:51
可能是因为我有过两轮on campus? 第一题我只写了sort之后走一遍找h的O(n)的代码,好吧,就四五行,我花了 ...
.留学论坛-一亩-三分地
第一题是快排二分+快排的partitioning。 . 围观我们@1point 3 acres
第三题要求majority element频率过半否?如果是就是经典题, 如果不是暂时想不到啥好方法。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| muxin4ever 发表于 2014-2-23 12:04:49 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
北美农民 发表于 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是向下取整,有奇偶数的细节要考虑,好吧,貌似也没啥。。。
回复 支持 反对

使用道具 举报

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

呃。。那这轮有点悬啊,如果是排好序之后的话,可以binary search O(logN)找到的。其实你提到bucket sort是正确的方向,h的最大也不会超过array的size
回复 支持 反对

使用道具 举报

我的人缘0
北美农民 发表于 2014-2-23 12:18:01 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
muxin4ever 发表于 2014-2-22 23:04
我不太懂你说的。那看来第一题我做错了?我是这么写的。。。
        public static int findH(int[] a){
                // ...

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

使用道具 举报

我的人缘0
adlxk 发表于 2014-2-23 12:28:54 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
muxin4ever 发表于 2014-2-23 12:04
我不太懂你说的。那看来第一题我做错了?我是这么写的。。。. Waral 博客有更多文章,
        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
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| muxin4ever 发表于 2014-2-23 13:54:48 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
北美农民 发表于 2014-2-23 12:18
看不懂你的代码。 什么h >= a, i ++

是while(h>=a),不知道为什么贴过来没有了,还变了斜体。。。

补充内容 (2014-2-23 13:55):
while(h >= a [ i ] )
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| muxin4ever 发表于 2014-2-23 14:45:17 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
adlxk 发表于 2014-2-23 12:28
北美农民说的“第一题是快排二分+快排的partitioning。”这个方法平均情况下可以达到O(n),其实就类似qui ...

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

使用道具 举报

我的人缘0
adlxk 发表于 2014-2-23 14:54:39 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
muxin4ever 发表于 2014-2-23 14:45
恩,原来partition就好了呀,我这个方法太笨了。。。

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

使用道具 举报

我的人缘0
 楼主| muxin4ever 发表于 2014-2-23 14:57:22 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
adlxk 发表于 2014-2-23 14:54
想确认一下第一题里面的要求是返回array里面的元素吗?还是H index?

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

使用道具 举报

我的人缘0
北美农民 发表于 2014-2-23 15:27:36 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
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;
  3.     int end = a.length - 1;
  4.     int pivot;
  5.     int result = -1;
  6.     . 1point 3acres 论坛
  7.     while (start <= end) {
  8.       swap(a, end, start + (end - start) / 2);
  9.       pivot = a[end];
  10.       int p = start - 1;. 围观我们@1point 3 acres
  11.       . 围观我们@1point 3 acres
  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];
  19.          end = p - 1;
  20.       }
  21.       else if (p < a[p]) start = p + 1;
  22.       else end = p - 1;. From 1point 3acres bbs
  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.   }
复制代码
回复 支持 反对

使用道具 举报

我的人缘0
北美农民 发表于 2014-2-23 15:37:48 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
muxin4ever 发表于 2014-2-22 23:04 . visit 1point3acres for more.
我不太懂你说的。那看来第一题我做错了?我是这么写的。。。
        public static int findH(int[] a){
                // ...

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

for (int i = a.length - 1; i >= 0; i --)
. 一亩-三分-地,独家发布    if (a = a.length - 1 - i) return a;

补充内容 (2014-2-23 02:38):
a是a[ i ]
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| muxin4ever 发表于 2014-2-23 15:53:56 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
北美农民 发表于 2014-2-23 15:27
你的代码似乎是在枚举h, 我没看太懂。 我写了个partition的。

我上面回复的例子你测过么。{5,6,7,8}要返回4的。我改了下你的,你可以测一下对不对,如下

  1.     public static int findH(int[] a) {
  2.         int start = 0;
  3.         int end = a.length - 1;
  4.         int pivot;. visit 1point3acres for more.
  5.         int result = -1;

  6.         while (start <= end) {
  7.             swap(a, end, start + (end - start) / 2);
  8.             pivot = a[end];
  9.             int p = start - 1;
  10. . 牛人云集,一亩三分地
  11.             // partitioning
  12.             for (int i = start; i < end; i++). from: 1point3acres
  13.                 if (a[i] > pivot)
  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.         }. visit 1point3acres for more.
  23.         return result;. 围观我们@1point 3 acres
  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;. Waral 博客有更多文章,
  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.         }
  12.         return max;
  13.     }
复制代码
来源一亩.三分地论坛.
回复 支持 反对

使用道具 举报

我的人缘0
adlxk 发表于 2014-2-23 16:42:37 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
muxin4ever 发表于 2014-2-23 14:57 . From 1point 3acres bbs
返回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)
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-27 13:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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