一亩三分地论坛

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

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

[编程题] 几个最近常见的iterator题

[复制链接] |试试Instant~ |关注本帖
cjlm007 发表于 2015-2-28 04:15:35 | 显示全部楼层 |阅读模式

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

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

x
这个是G家经常考的peek iterator.
http://www.fgdsb.com/2015/01/25/peek-iterator/

这个是Zigzag。
http://www.fgdsb.com/2015/01/30/zigzag-iterator/
这个是nested,最近很高频。
http://www.fgdsb.com/2015/01/19/nested-iterator/

这个是归并排序的iterator,G家考过几次。
http://www.fgdsb.com/2015/01/15/merge-sorted-stream/

因为不想帖子太长,就不把内容都粘过来了,请看链接吧。
都是C++实现,除了nested和merge用到一些C++11特性外,另外两题应该很轻松翻译成java。

评分

3

查看全部评分

本帖被以下淘专辑推荐:

stellari 发表于 2015-2-28 13:09:36 | 显示全部楼层
很实用的资料。我在Google的面试就被要求实现Zigzag Iterator。只是条件比楼主给出的略为苛刻,面试官是这么问的:

Given an iterator A of iterators B's , alternately output the contents in all the B's

也就是说我现在有一群iterator B1, B2, ... Bk,分别是Collection C1, C2, ... , Ck的iterator. 但是不把这些iterator的引用直接给你,而是把这些iterator再放到一个Collection (比如记为B)中,然后给你的只是B的一个iterator BI。输出方式就是按楼主所说的zigzag形。

我当时说可以用BI先把B遍历一遍,把所有的iterator B1, B2, ... , Bk先拷贝到一个能够随机访问的Collection中,然后用楼主上面给出的方法。但是面试官似乎不太认可这个答案,但是也没有明说到底哪里应该改进。我觉得他可能是想让我找一个不用预先遍历的方法,或者是甚至不需要用到额外O(k)内存的方法。但是我到最后也没想出来。

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

samantha_kr 发表于 2015-2-28 13:40:49 | 显示全部楼层
stellari 发表于 2015-2-28 13:09
很实用的资料。我在Google的面试就被要求实现Zigzag Iterator。只是条件比楼主给出的略为苛刻,面试官是这 ...

请问是sorted的么?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-2-28 14:10:28 | 显示全部楼层
samantha_kr 发表于 2015-2-28 13:40
请问是sorted的么?

不是。而且这个题只是要求按照指定顺序输出,即使每个Collection C1, C2, ... Ck是排好序的,也无法利用这点来提高效率吧。
回复 支持 反对

使用道具 举报

samantha_kr 发表于 2015-2-28 16:27:49 | 显示全部楼层
stellari 发表于 2015-2-28 14:10
不是。而且这个题只是要求按照指定顺序输出,即使每个Collection C1, C2, ... Ck是排好序的,也无法利用 ...

哦哦!我看错题了。。我以为是输出B中的common elements....应该是LZ题目的general版本~
回复 支持 反对

使用道具 举报

samantha_kr 发表于 2015-2-28 16:32:12 | 显示全部楼层
本帖最后由 samantha_kr 于 2015-2-28 16:34 编辑
stellari 发表于 2015-2-28 14:10
不是。而且这个题只是要求按照指定顺序输出,即使每个Collection C1, C2, ... Ck是排好序的,也无法利用 ...

那如果不用extra memory的话。。感觉时间复杂度会很高很暴力。。。
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-4-4 21:29:01 | 显示全部楼层
哎 真的是很怕包装iterator的题....
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 16:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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