一亩三分地论坛

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

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

Google onsite + 后续

[复制链接] |试试Instant~ |关注本帖
liuwz 发表于 2015-11-29 02:26:32 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - Other - Onsite |Failfresh grad应届毕业生

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

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

x
很久之前(9月初)就面完了onsite,然后一直被拖,一个月之后告诉我被on hold了,正在project fit,最后估计也没fit成功,问要不要面test,我说行又要了两轮test,结果也挂了,最后还问我要不要再面另一个program,实在是不想再纠结了就回复他们说最近忙过段时间再决定要不要面。。
整个timeline是6月HR给我发邮件问我有没有兴趣面Google,当时真的是很激动啊,然后敲定了一个月之后电面,电面的题目很简单,实现一个类,类里包含一个矩阵,让我写函数怎么set值,然后再写一个函数,给一个坐标,返回坐标左上角所有值的和。followup是如何优化,问了些C++的细节,const之类的。
一周后收到onsite。定的是九月初。onsite一共4轮,第一轮问了perfect square,就是给一个数,比如12,返回3因为12 = 4+4+4, leetcode原题; 第二轮给一个string,有重复,让重新排列,首先判断是否能得到一个字符串相邻的char不重复,如果可以返回重新排列后的字符串; 第三轮decode ways; 第四轮先问了hash和tree的各种方法的复杂度和不同,然后给个数组,返回一个数组,返回数组的每个元素是原数组中右边的第一个大于该位置元素的index。本来题都不难,但是奈何准备不好,所以就on hold了。
后来面test,跟之前的面试都差不多,但是会问到用什么testcase.

最后从HR联系我到现在大半年时间,最后还是悲剧了。。。

评分

2

查看全部评分

tomato347 发表于 2015-11-29 02:43:48 | 显示全部楼层
请问test问了什么?有问system design吗? test case是需要写出来还是说说就好? 知道是什么组的人问的吗?谢谢!
回复 支持 反对

使用道具 举报

 楼主| liuwz 发表于 2015-11-29 03:22:01 | 显示全部楼层
tomato347 发表于 2015-11-29 02:43
请问test问了什么?有问system design吗? test case是需要写出来还是说说就好? 知道是什么组的人问的吗?谢 ...

test是两轮,第一个人就问了问怎么找到tree里面最深得那个node,但是感觉写的code他并不怎么care,主要问了有什么case需要注意的,我就答了非法的输入啊,extreme input啊,后来还问了道题但是我不记得了,很简单就记得。主要挂在了第二个人的问题上,给一个数组比如【2,3,49】,给一个N,比如100, 让随机产生一个数字,但这个数字不能在数组里。我开始给了个算法,就是rand随便产生一个数,如果在数组里扔掉再选。但是他嫌这个算法时间慢,然后就各种优化。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

无聊的ttt 发表于 2015-11-29 06:35:22 | 显示全部楼层
lz别灰心 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
请问第四轮找右边第一个大于该元素的index,是用一个object包含index来排序,然后用一个min array,记录从右到左的index min value来做的嘛?
回复 支持 反对

使用道具 举报

 楼主| liuwz 发表于 2015-11-29 06:56:00 | 显示全部楼层
无聊的ttt 发表于 2015-11-29 06:35. visit 1point3acres.com for more.
lz别灰心
请问第四轮找右边第一个大于该元素的index,是用一个object包含index来排序,然后用一个min arra ...

具体的我不太记得,只记得是用了一个数组(就是output的那个数组),然后是从后往前处理了一遍,记录了一些东西,反正最后的复杂度是比N大但是比N方小,然后bestcase复杂度是N。当时一开始我只写了N方的,是面试官给了提示,就说从后往前遍历才做出来的
回复 支持 反对

使用道具 举报

wilber5945 发表于 2015-11-29 07:25:16 | 显示全部楼层
LZ 别灰心,好offer都再后边!
LZ on hold 是什么意思呀, 是HR直接和你说被on hold了吗?
回复 支持 反对

使用道具 举报

 楼主| liuwz 发表于 2015-11-29 09:06:52 | 显示全部楼层
wilber5945 发表于 2015-11-29 07:25
LZ 别灰心,好offer都再后边!. visit 1point3acres.com for more.
LZ on hold 是什么意思呀, 是HR直接和你说被on hold了吗?

对呀,on hold就是刚过线,不拒也不录,要一些其他的资料,然后再决定,会有一个project fit, 就是看有没有组感兴趣有的话直接和manager聊,没有估计就被推到test了
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-12 08:56:37 | 显示全部楼层
返回数组的每个元素是原数组中右边的第一个大于该位置元素的index
请问使用什么记录呢?使用bst,每次都是lgn,然后总得时间复杂度是O(nlgn)?
回复 支持 反对

使用道具 举报

tltzhsajsdr 发表于 2016-1-27 10:43:48 | 显示全部楼层
请问楼主,onsite是刚好面了4题吗
回复 支持 反对

使用道具 举报

haifengc 发表于 2016-1-27 10:57:04 | 显示全部楼层
liuwz 发表于 2015-11-29 03:22
test是两轮,第一个人就问了问怎么找到tree里面最深得那个node,但是感觉写的code他并不怎么care,主要问 ...

产生一个数不在数组里,N在这里有什么用吗?谢谢。
回复 支持 反对

使用道具 举报

 楼主| liuwz 发表于 2016-1-27 21:56:04 | 显示全部楼层
tltzhsajsdr 发表于 2016-1-27 10:43
请问楼主,onsite是刚好面了4题吗

对呀。。。。。
回复 支持 反对

使用道具 举报

 楼主| liuwz 发表于 2016-1-27 21:56:56 | 显示全部楼层
haifengc 发表于 2016-1-27 10:57. visit 1point3acres.com for more.
产生一个数不在数组里,N在这里有什么用吗?谢谢。
.1point3acres缃
就是让随机产生一个数,范围在【0,N)
回复 支持 反对

使用道具 举报

lingmingyang 发表于 2016-1-28 00:13:41 | 显示全部楼层
不知道第四轮怎么做,有遇到过第四轮那个题目的吗
回复 支持 反对

使用道具 举报

 楼主| liuwz 发表于 2016-1-28 00:28:12 | 显示全部楼层
lingmingyang 发表于 2016-1-28 00:13
不知道第四轮怎么做,有遇到过第四轮那个题目的吗

已经不太记得了。。。。
回复 支持 反对

使用道具 举报

javaprogrammer 发表于 2016-2-2 07:25:35 | 显示全部楼层
第四轮有O(N)的解法

http://www.geeksforgeeks.org/next-greater-element/

稍微改一下,stack里存index应该就可以了
回复 支持 反对

使用道具 举报

javaprogrammer 发表于 2016-2-2 07:36:38 | 显示全部楼层
第四轮
  1. public static int[] nextGreaterElement(int[] nums) {
  2.         if (nums == null || nums.length <= 1) return new int[]{};
  3.         int n = nums.length;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  4.         int[] indexes = new int[n];
  5.         Stack<Integer> stack = new Stack<Integer>();
  6.         stack.push(0);
  7.         for (int i = 1; i < n; i++) {
  8.             if (nums[i] <= nums[stack.peek()]) {. 1point 3acres 璁哄潧
  9.                 stack.push(i);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  10.             }
  11.             else {.1point3acres缃
  12.                 while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
  13.                     indexes[stack.pop()] = i;
  14.                 }
  15.                 stack.push(i);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  16.             }
  17.         }
  18.         while (!stack.isEmpty()) {
  19.             indexes[stack.pop()] = -1;-google 1point3acres
  20.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  21.         return indexes;
  22.     }
  23.    
  24.     public static void main(String[] args) {
  25.        // int[] nums = {3,2,5,1,6,4};
  26.         int[] nums = {13, 7, 6, 12};
  27.         int[] indexes = nextGreaterElement(nums);
  28.         for (int d : indexes) {
  29.             System.out.print(d + " ");
  30.         }            
  31.     }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 22:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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