一亩三分地论坛

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

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

10/19google电面

[复制链接] |试试Instant~ |关注本帖
tangvictor 发表于 2015-10-20 10:11:12 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
今天下午面的,听口音是白人,谷歌干了8年了。
. Waral 鍗氬鏈夋洿澶氭枃绔,
上来先聊了下我的实习,又问了地址栏输入网址后的操作。我昨天还特意看过这问题,就DNS啊,HTTP GET答了一遍。他说ok开始代码吧。

设计一个buffer接口,给size,写出write(), read()。overwrite了就pop出最前的数。

举个例子: size = 3
b = Buffer(3). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
write(1). visit 1point3acres.com for more.
write(2)
write(3)
read()  => 1
write(4)        此时buffer里是【2,3,4】
read() => 2
read() => 3
read() => 4
write(5)     【3,4,5】
read() => 5
...

我就用个queue存数字,overwrite就pop(). 写完半天他也不吭声,我说那我带个case给你跑下怎么样,他说好。我就举了个跑了下,他说ok。时间复杂度多少。我说write()是O(1),他说pop(0)应该是O(n), 因为queue他要求是固定长度的,pop时所有元素要一个个往前移一位。我说哦。。那就O(n)。

接下来开始了长久的follow up。问:怎么改进的更快呢?

我说要不建个很长的list,把一个个数字都放进去,移动指针的头和尾控制buffer的长度,这样就是O(1)了。他说那list满了咋办,我说那就只用取最后的buffer长度放一个新表里的开头。他说ok,那现在list你是装数字可能可以很长,现在我要装其他数据结构memory不够用了怎么办,换句话就是list不能那么长怎么办。我说那就搞很多list,一个放满了就放到下一个。他又问memory放不了那么多list怎么办。我说那就搞完的就释放。他问我咋释放,我说建个hashmap,记录下list编号对应memory address,一个list搞完就把memory释放了。说完又来了个ok,也不知道对还是不对,看了下表已经45了他就让我问问题了。

我看地里电面都是面的两道题,但前段时间我同学问了一道题也过了。。我感觉他从25开始问了我20分钟的follow up问题,根本没打算问我第二题。我一直在跟他讨论解释,到头来他要不就再问我,要不就ok我也不知道回答的对不对。发上来供大家参考吧,祝我早点进入onsite!!


. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2015-10-21 18:10):
“感觉用个Array就好了啊, 当成Circular Buffer, 用两个指针一个指队首,一个指队尾” 想了下感觉@alljaz的方法可行也最优。刚接到hr电话要加面一轮,我接着准备了。。各位一起加油!

评分

1

查看全部评分

本帖被以下淘专辑推荐:

xuyuhao 发表于 2015-10-20 21:33:57 | 显示全部楼层
pengzewen37 发表于 2015-10-20 21:31
没错,linkedlist,超出内存,存disk不就好了?谁有更好的见解,或者面试官想考什么。

感觉面试官就是想让楼主说linked list吧。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
他一直表现的好像这个queue是用数组实现的一样。
回复 支持 1 反对 0

使用道具 举报

alljaz 发表于 2015-10-20 23:47:07 | 显示全部楼层
感觉用个Array就好了啊, 当成Circular Buffer, 用两个指针一个指队首,一个指队尾
回复 支持 1 反对 0

使用道具 举报

cq696925 发表于 2015-10-20 11:08:48 | 显示全部楼层
感觉问题往LRU方向去了
回复 支持 反对

使用道具 举报

snowwolf 发表于 2015-10-20 11:56:15 | 显示全部楼层
感觉他想让你说Linked List
回复 支持 反对

使用道具 举报

say543 发表于 2015-10-20 12:16:00 | 显示全部楼层
觉得就是linkedlist size 需要的是buffer size 不知道这样memory 还有没有办法improve?
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-10-20 18:07:00 | 显示全部楼层
那不是Deque么。。。。。。
回复 支持 反对

使用道具 举报

xuyuhao 发表于 2015-10-20 21:20:37 | 显示全部楼层
感觉就一个Linked List + 一个指向当前读取值的指针 + 一个记录List长度的变量就可以了吧。
回复 支持 反对

使用道具 举报

pengzewen37 发表于 2015-10-20 21:31:47 | 显示全部楼层
没错,linkedlist,超出内存,存disk不就好了?谁有更好的见解,或者面试官想考什么。
回复 支持 反对

使用道具 举报

pengzewen37 发表于 2015-10-20 21:39:26 | 显示全部楼层
xuyuhao 发表于 2015-10-20 08:33
感觉面试官就是想让楼主说linked list吧。
他一直表现的好像这个queue是用数组实现的一样。

嗯,前面肯定是想让他说linkedlist。没想到一道题能扯这么久,anyway祝他好运,至少有个二面,多给次机会。
回复 支持 反对

使用道具 举报

liyanjia92 发表于 2015-10-20 21:55:09 | 显示全部楼层
为什么read完以后数据还要留在buffer里呢?
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-10-21 00:09:57 | 显示全部楼层
应该就是LRU吧
回复 支持 反对

使用道具 举报

xuyuhao 发表于 2015-10-21 11:25:41 | 显示全部楼层
liyanjia92 发表于 2015-10-20 21:55
为什么read完以后数据还要留在buffer里呢?

因为就是这个设计。
留在buffer内反正也没损失,并没有新的数据写进来。
回复 支持 反对

使用道具 举报

zwcelesta 发表于 2015-11-9 23:31:15 | 显示全部楼层
queue 内部实现是deque或者linked list。pop本来就是O(1)的复杂度。感觉面试官在带你笼子。。。
回复 支持 反对

使用道具 举报

ohbrown 发表于 2015-11-10 10:47:11 | 显示全部楼层
感觉用个Array, 一个read指针, 一个write指针, circular操作
回复 支持 反对

使用道具 举报

eko910817 发表于 2015-11-17 13:10:54 | 显示全部楼层
overwrite了就Pop出前面的数,指的是overflow?buffer满了就是删了最旧的那个数吗
回复 支持 反对

使用道具 举报

潇洒走一回 发表于 2015-11-17 18:36:43 | 显示全部楼层
用一个循环单向列表应该就可以了吧
回复 支持 反对

使用道具 举报

oneshot 发表于 2015-11-17 23:41:55 | 显示全部楼层
建一个size那么长的Array,一个read指针一个write指针,超过size了就回到开头的地方read。
回复 支持 反对

使用道具 举报

Neil_Acton 发表于 2015-11-18 03:37:43 | 显示全部楼层
不太理解这是个什么数据结构

举个例子: size = 3
b = Buffer(3). 鍥磋鎴戜滑@1point 3 acres
write(1)
write(2)
write(3)
read()  => 1
read() => 2
read() => 3
//再读一遍什么结果?
read()  => ?
read() => ?
read() => ?
回复 支持 反对

使用道具 举报

Neil_Acton 发表于 2015-11-18 03:46:16 | 显示全部楼层
这个题楼主可能没理解题目吧 感觉follow up里的对话也不是很make sense
这种题目遇到了感觉做之前还是要花时间把实现细节问清楚的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 18:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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