传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 3159|回复: 20
收起左侧

热乎的Google面经

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

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

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

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

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么?.鏈枃鍘熷垱鑷1point3acres璁哄潧
第一题的double,你指的是1.77232 那样的数么? 这道题要考虑rounding么?

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

使用道具 举报

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

使用道具 举报

宝贝忆彼岸 发表于 2015-9-17 05:25:57 | 显示全部楼层
第一题是不是可以用两个pointer,一左一右,然后用merge sort的思路,如果array的element全都是>=0的话可以直接从小到大顺序排列。. from: 1point3acres.com/bbs
第二题给的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}.
. more info on 1point3acres.com
做法可以先找到第一个大于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,可能输入是个无限流

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

使用道具 举报

kelvinzhong 发表于 2015-9-17 08:04:39 | 显示全部楼层
pyemma 发表于 2015-9-17 07:52
看题目不像是LRU,可能输入是个无限流

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大的,从后往前放就可以了
. From 1point 3acres bbs
正解正解,我就这么整的
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-17 15:57:20 | 显示全部楼层
  1. vector<double> get_sorted_square(vector<double> v) {
  2.     if (v.size() == 0) return vector<double>();
  3.     int l = 0, r = v.size();.1point3acres缃
  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()) {. from: 1point3acres.com/bbs
  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++]);
  21.     }
  22.     return square;
    . 1point3acres.com/bbs
  23. }
复制代码
第一题,先二分找最接近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}. 鍥磋鎴戜滑@1point 3 acres
第二 ...

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

使用道具 举报

 楼主| craiglin1992 发表于 2015-9-22 00:10:59 | 显示全部楼层
douya 发表于 2015-9-21 02:36
感谢楼主分享,第二题有什么具体要求?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?不知道有没有理解对题目的意思。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-21 13:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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