一亩三分地论坛

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

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

热乎的Google面经

[复制链接] |试试Instant~ |关注本帖
craiglin1992 发表于 2015-9-17 04:59:10 | 显示全部楼层 |阅读模式

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

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

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

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

祝大家都好运!!顺便求点大米.鐣欏璁哄潧-涓浜-涓夊垎鍦

评分

4

查看全部评分

本帖被以下淘专辑推荐:

xiaozhuxiaozhu 发表于 2015-9-17 05:16:35 | 显示全部楼层
lz面的是full-time么?
第一题的double,你指的是1.77232 那样的数么? 这道题要考虑rounding么?

补充内容 (2015-9-17 05:27):. From 1point 3acres bbs
理解错了,我看成是2个array,从一个里面找另一个的square,然后return.
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-17 05:19:09 | 显示全部楼层
第一题是把每一个数的square都计算一下?
回复 支持 反对

使用道具 举报

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

使用道具 举报

坐看云起 发表于 2015-9-17 06:03:50 | 显示全部楼层
第一题可以再解释具体一些么?
第二题用一个队列保存数字,并记录当前K个元素的sum?
回复 支持 反对

使用道具 举报

storm_hair 发表于 2015-9-17 06:18:09 | 显示全部楼层
第一题看不懂什么意思
回复 支持 反对

使用道具 举报

edna 发表于 2015-9-17 06:48:55 | 显示全部楼层
第一题应该就是double pointer,比如说给你个array,{-5,-3,1,2},最后的结果是{1, 4, 9, 25}.

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

使用道具 举报

kelvinzhong 发表于 2015-9-17 07:03:52 | 显示全部楼层
第二题难道是LRU?
回复 支持 反对

使用道具 举报

storm_hair 发表于 2015-9-17 07:21:01 | 显示全部楼层
edna 发表于 2015-9-17 06:48
第一题应该就是double pointer,比如说给你个array,{-5,-3,1,2},最后的结果是{1, 4, 9, 25}.

做法可以 ...

牛逼同学
回复 支持 反对

使用道具 举报

pyemma 发表于 2015-9-17 07:52:56 | 显示全部楼层
kelvinzhong 发表于 2015-9-16 15:03
第二题难道是LRU?

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

使用道具 举报

kelvinzhong 发表于 2015-9-17 08:04:32 | 显示全部楼层
pyemma 发表于 2015-9-17 07:52
看题目不像是LRU,可能输入是个无限流
. Waral 鍗氬鏈夋洿澶氭枃绔,
LRU不就是无限流吗?
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-9-17 08:04:39 | 显示全部楼层
pyemma 发表于 2015-9-17 07:52
看题目不像是LRU,可能输入是个无限流
. 鍥磋鎴戜滑@1point 3 acres
LRU不就是无限流吗?
回复 支持 反对

使用道具 举报

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

使用道具 举报

peach=。= 发表于 2015-9-17 12:46:14 | 显示全部楼层
edna 发表于 2015-9-17 06:48
第一题应该就是double pointer,比如说给你个array,{-5,-3,1,2},最后的结果是{1, 4, 9, 25}.

做法可以 ...

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

使用道具 举报

 楼主| craiglin1992 发表于 2015-9-17 15:05:01 | 显示全部楼层
peach=。= 发表于 2015-9-17 12:46
感觉不用找第一个大于0的,两头比较abs大的,从后往前放就可以了

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

使用道具 举报

flexwang 发表于 2015-9-17 15:57:20 | 显示全部楼层
  1. vector<double> get_sorted_square(vector<double> v) {
  2.     if (v.size() == 0) return vector<double>();. From 1point 3acres bbs
  3.     int l = 0, r = v.size();
  4.     while (l+1<r) {
  5.         int m = l+(r-l)/2;
  6.         if (v[m] > 0.0) r = m;
  7.         else l = m;
  8.     }
  9.     vector<double> square;
  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. Waral 鍗氬鏈夋洿澶氭枃绔,
  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.com
  21.     }
  22.     return square;
  23. }
    . more info on 1point3acres.com
复制代码
第一题,先二分找最接近0的负数,然后merge。
回复 支持 反对

使用道具 举报

douya 发表于 2015-9-21 02:36:03 | 显示全部楼层
craiglin1992 发表于 2015-9-17 10:46
第一题地基(不知道问什么不直接说几楼,好像是7楼)说的是对的。给{-3,-2,-1,0,1} 输出{0,1,1,4,9}-google 1point3acres
第二 ...

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

使用道具 举报

 楼主| craiglin1992 发表于 2015-9-22 00:10:59 | 显示全部楼层
douya 发表于 2015-9-21 02:36
. From 1point 3acres bbs感谢楼主分享,第二题有什么具体要求?Time complexity?

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

使用道具 举报

colfighter 发表于 2015-9-22 04:02:45 | 显示全部楼层
第二题可以用Deque做么? 类似sliding window
回复 支持 反对

使用道具 举报

走路草May 发表于 2015-9-22 12:25:41 | 显示全部楼层
craiglin1992 发表于 2015-9-22 00:10
每次average应该需要O(1)吧

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 10:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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