我是如何肉身翻墙,从国内直接来美国工作的?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
查看: 3449|回复: 20
收起左侧

热乎的Google面经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
craiglin1992 发表于 2015-9-17 04:59:10 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

2015(7-9月) 码农类General 硕士 全职@Google - 校园招聘会 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
今天google电话面试,就刚刚,两道题。面试我的面试官是个女生声音特别好听!

1. given sorted array of doubles, return the another sorted array of doubles where all elements are the squares from the input array, 然后optimize一下到O(n)。

2. moving average. calculate the average of the most recent x number of elements. 一亩-三分-地,独家发布
. from: 1point3acres
祝大家都好运!!顺便求点大米

评分

4

查看全部评分


上一篇:Google 电面
下一篇:Google电面 08/25/2015

本帖被以下淘专辑推荐:

我的人缘0
xiaozhuxiaozhu 发表于 2015-9-17 05:16:35 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
lz面的是full-time么?
第一题的double,你指的是1.77232 那样的数么? 这道题要考虑rounding么?
.留学论坛-一亩-三分地
补充内容 (2015-9-17 05:27):
理解错了,我看成是2个array,从一个里面找另一个的square,然后return.
回复 支持 反对

使用道具 举报

我的人缘0
hbsophia 发表于 2015-9-17 05:19:09 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第一题是把每一个数的square都计算一下?
回复 支持 反对

使用道具 举报

我的人缘0
宝贝忆彼岸 发表于 2015-9-17 05:25:57 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第一题是不是可以用两个pointer,一左一右,然后用merge sort的思路,如果array的element全都是>=0的话可以直接从小到大顺序排列。
第二题给的numbers是一个stream吗?请问LZ是怎么做?要用一个数据结构把最近的 x 个数存起来吗?
回复 支持 反对

使用道具 举报

我的人缘0
坐看云起 发表于 2015-9-17 06:03:50 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第一题可以再解释具体一些么?
第二题用一个队列保存数字,并记录当前K个元素的sum?
回复 支持 反对

使用道具 举报

我的人缘0
storm_hair 发表于 2015-9-17 06:18:09 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第一题看不懂什么意思
回复 支持 反对

使用道具 举报

我的人缘0
edna 发表于 2015-9-17 06:48:55 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第一题应该就是double pointer,比如说给你个array,{-5,-3,1,2},最后的结果是{1, 4, 9, 25}.

做法可以先找到第一个大于0的元素,然后两个pointer,对上面的例子来说就是一个指向-3,一个指向1,比较abs值,然后一步一步走。
回复 支持 反对

使用道具 举报

我的人缘0
kelvinzhong 发表于 2015-9-17 07:03:52 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第二题难道是LRU?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
storm_hair 发表于 2015-9-17 07:21:01 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
edna 发表于 2015-9-17 06:48
第一题应该就是double pointer,比如说给你个array,{-5,-3,1,2},最后的结果是{1, 4, 9, 25}.. 留学申请论坛-一亩三分地

做法可以 ...

牛逼同学
回复 支持 反对

使用道具 举报

我的人缘0
pyemma 发表于 2015-9-17 07:52:56 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
kelvinzhong 发表于 2015-9-16 15:03
第二题难道是LRU?

看题目不像是LRU,可能输入是个无限流
回复 支持 反对

使用道具 举报

我的人缘0
kelvinzhong 发表于 2015-9-17 08:04:32 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
pyemma 发表于 2015-9-17 07:52
看题目不像是LRU,可能输入是个无限流

LRU不就是无限流吗?
回复 支持 反对

使用道具 举报

我的人缘0
kelvinzhong 发表于 2015-9-17 08:04:39 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
pyemma 发表于 2015-9-17 07:52
看题目不像是LRU,可能输入是个无限流

LRU不就是无限流吗?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| craiglin1992 发表于 2015-9-17 10:46:56 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第一题地基(不知道问什么不直接说几楼,好像是7楼)说的是对的。给{-3,-2,-1,0,1} 输出{0,1,1,4,9}
第二题是有一些像LRU但比LRU简单些因为不需要从中间拿出来
回复 支持 反对

使用道具 举报

我的人缘0
peach=。= 发表于 2015-9-17 12:46:14 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
edna 发表于 2015-9-17 06:48
第一题应该就是double pointer,比如说给你个array,{-5,-3,1,2},最后的结果是{1, 4, 9, 25}.

做法可以 ...

感觉不用找第一个大于0的,两头比较abs大的,从后往前放就可以了
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| craiglin1992 发表于 2015-9-17 15:05:01 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
peach=。= 发表于 2015-9-17 12:46
感觉不用找第一个大于0的,两头比较abs大的,从后往前放就可以了

正解正解,我就这么整的
回复 支持 反对

使用道具 举报

我的人缘0
flexwang 发表于 2015-9-17 15:57:20 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
  1. vector<double> get_sorted_square(vector<double> v) {
  2.     if (v.size() == 0) return vector<double>();
  3.     int l = 0, r = v.size();
  4.     while (l+1<r) {.1point3acres网
  5.         int m = l+(r-l)/2;
  6.         if (v[m] > 0.0) r = m;
  7.         else l = m;
  8.     }
  9.     vector<double> square;. visit 1point3acres for more.
  10.     while (l>=0 || r<v.size()) {
  11.         if (l>=0 && r<v.size()) {
  12.             if (v[l]*v[l] < v[r]*v[r])
  13.                 square.push_back(v[l]*v[l--]);
  14.             else
  15.                 square.push_back(v[r]*v[r++]);
  16.         }
  17.         else if (l>=0)
  18.             square.push_back(v[l]*v[l--]);
  19.         else
  20.             square.push_back(v[r]*v[r++]);. more info on 1point3acres
  21.     }. 1point3acres
  22.     return square;. visit 1point3acres for more.
  23. }
复制代码
第一题,先二分找最接近0的负数,然后merge。
回复 支持 反对

使用道具 举报

我的人缘0
douya 发表于 2015-9-21 02:36:03 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
craiglin1992 发表于 2015-9-17 10:46
第一题地基(不知道问什么不直接说几楼,好像是7楼)说的是对的。给{-3,-2,-1,0,1} 输出{0,1,1,4,9}
第二 ...

感谢楼主分享,第二题有什么具体要求?Time complexity?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| craiglin1992 发表于 2015-9-22 00:10:59 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
douya 发表于 2015-9-21 02:36-google 1point3acres
感谢楼主分享,第二题有什么具体要求?Time complexity?

每次average应该需要O(1)吧
回复 支持 反对

使用道具 举报

我的人缘0
colfighter 发表于 2015-9-22 04:02:45 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第二题可以用Deque做么? 类似sliding window
回复 支持 反对

使用道具 举报

我的人缘0
走路草May 发表于 2015-9-22 12:25:41 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
craiglin1992 发表于 2015-9-22 00:10
每次average应该需要O(1)吧

可以用Queue做嘛?每次移出queue里最早的元素, 然后keep一个currSum,每次移出元素和加入新元素都更新下currSum?不知道有没有理解对题目的意思。
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-28 13:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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