一亩三分地论坛

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

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

Google电面

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

2015(4-6月) 码农类 本科 全职@Google - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚刚电面的,新鲜出炉的面经。. Waral 鍗氬鏈夋洿澶氭枃绔,

Two IntStreams are given. Then, found union integers between two streams.
  1. class IntStream {
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  2. public:
  3.    
复制代码
Implement (e.g., give the other methods, member variables, as well as implementation of the methods)

class UnionOp {
public:
    UnionOp(IntStream*, IntStream*);
    int Next(); // Returns next int in the stream;
};

Example
IntStream a = [1, 2, 3];
IntStream b = [2, 4];
UnionOp op(&a, &b);
Next() -> [1, 2, 3, 4];

Result return的比一定是要sorted.



.1point3acres缃
补充内容 (2015-6-11 08:22): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第一次发帖。加代码好像不成功,不知道怎么编辑。把东西重新贴在下一楼

评分

3

查看全部评分

 楼主| coolzai 发表于 2015-6-11 08:23:57 | 显示全部楼层
class IntStream {
public:
    bool more() const; // Are there any more integers in the stream?
    int Next(); // Returns next item in IntStream if there are more().
要求Implement:

class UnionOp {
public:
   UnionOp(IntStream*, IntStream*);
   int Next(); // Returns next int in the stream
};
回复 支持 反对

使用道具 举报

milanelllo13 发表于 2015-6-11 11:56:50 | 显示全部楼层
楼主能分享一下思路吗~谢谢~!!
回复 支持 反对

使用道具 举报

 楼主| coolzai 发表于 2015-6-11 20:51:56 | 显示全部楼层
我的想法比较笨,就是把两个IntStream都放在同一个HashMap里面,重复的自己就去掉了。
最后要的结果也没有说一定要是sorted。

之后google的时候可能还有follow up问怎么找intersect,不过union我只勉强写完并且还有bug。。。还得多练习。。
回复 支持 反对

使用道具 举报

dapangmao 发表于 2015-6-11 22:28:46 | 显示全部楼层
merge sorted linked list
回复 支持 反对

使用道具 举报

jill_8668 发表于 2015-6-11 23:06:41 | 显示全部楼层
如果用HashMap, 就需要把两个IntStream里面,不同的int, 全部存下来, 如果IntStream很大, HashMap会效率低, 并且会爆内存。

楼主也没说IntStream都是 sorted的, 所以用merge sorted linked list也不对吧?
回复 支持 反对

使用道具 举报

love1point 发表于 2015-6-11 23:09:09 | 显示全部楼层
又一次证明google非常爱考hashmap
回复 支持 反对

使用道具 举报

 楼主| coolzai 发表于 2015-6-11 23:24:01 | 显示全部楼层
jill_8668 发表于 2015-6-11 23:06
如果用HashMap, 就需要把两个IntStream里面,不同的int, 全部存下来, 如果IntStream很大, HashMap会效率 ...

面试官说input和output不一定要是sorted的
回复 支持 反对

使用道具 举报

jill_8668 发表于 2015-6-11 23:58:08 | 显示全部楼层
coolzai 发表于 2015-6-11 23:24
面试官说input和output不一定要是sorted的

那面试官有没有说,全部IntStream可以放入内存? 如果IntStream很大, 可能需要分组处理重复,比如, 1-10000的int存入一个文件,file1, 10001-20000的int,存入另一个文件,file2,。。。然后分别去掉重复,最后合并文件。
回复 支持 反对

使用道具 举报

say543 发表于 2015-6-12 07:00:11 | 显示全部楼层
題目很vague... 請問有說Intstreaming data 會一直出現新的嗎..
回复 支持 反对

使用道具 举报

 楼主| coolzai 发表于 2015-6-12 21:51:04 | 显示全部楼层
jill_8668 发表于 2015-6-11 23:58
那面试官有没有说,全部IntStream可以放入内存? 如果IntStream很大, 可能需要分组处理重复,比如, 1-1 ...
. 鍥磋鎴戜滑@1point 3 acres
这点我没考虑到。。。所以没问。。面试官没说
回复 支持 反对

使用道具 举报

 楼主| coolzai 发表于 2015-6-12 21:52:27 | 显示全部楼层
say543 发表于 2015-6-12 07:00
題目很vague... 請問有說Intstreaming data 會一直出現新的嗎..

对呀,题目很模糊。本来想问是不是一直出新的。 可是他让我Implement一个UnionOp class的constructor。。又觉得好像不能是一直出新的吧。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 14:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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