一亩三分地论坛

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

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

[算法题] 真心求教iterator of iterator

[复制链接] |试试Instant~ |关注本帖
mymax2009 发表于 2016-4-1 05:24:18 | 显示全部楼层 |阅读模式

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

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

x
最近刷G面经的时候经常看到一个高频题是iterator of iterator,
原题大概就是说有一个list的迭代器,写一个wrapper iterator可以遍历那个list中的所有迭代器?

想请问下各位大大能不能给一下思路?比如需要具体实现一些什么功能? 就是相当于一堆指针的指针吗?
另外想问问地里有没有人总结了G家onsite高频题的帖子,十分急需一个link  谢谢大家了

本帖被以下淘专辑推荐:

stellari 发表于 2016-4-1 21:54:40 | 显示全部楼层
这种题一般都是先给定一个接口,通常是类似于Java中的Iterator<E>接口。所以你就算主语言是C++,做这题最好也先切换到Java思维。

interface Iterator<E> {
  public E next();
  public boolean hasNext();
}

然后这个题里给的输入很可能是这个样子的
Iterator<Iterator<Integer> > iterOfIter;
也就是说,我现在有N个容器,比如List,然后对应地有N个List.Iterator。再把这N个Iterator放在一个大容器里,iterOfIter就是这个大容器的总的Iterator。

那么你要写的是这样一个类:
1. 实现Iterator<E>接口,
2. 包装iterOfIter,
3. 功能是将iterOfIter中所有iterator的内容顺次取出(展平),也就是:

class FlatteneddIterator<E> implements Iterator<E> {
   // 包装一个Iterator<Iterator<Integer> > iterOfIter;
   // 实现构造函数FlattenedIterator()
   // 实现hasNext();
   // 实现next();
}

特别要注意的坑是:
1. iterOfIter可以是null
2. iterOfIter中的iter可以是空(尤其是这一条,此题区分度应该主要在这一点上)。

写完可以和面试官提一下,这本质上是用到了设计模式中的Decorator Pattern。

你先实际写写看。完整代码不会很长,但是思维要严密些。


评分

2

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| mymax2009 发表于 2016-4-2 01:48:30 | 显示全部楼层
stellari 发表于 2016-4-1 21:54
这种题一般都是先给定一个接口,通常是类似于Java中的Iterator接口。所以你就算主语言是C++,做这题最好也 ...

太感谢你了, 说的特别详细。

看了一下你的描述大概能了解意思了, 是不是有点类似于leetcode里的一个zigzag iterator的题目?
总的来说就是design一个iterator结构, 它能通过内部多个容器的iterator然后依某种顺序访问每个元素,然后总的iterator可以为null, 每一个容器中的iterator也可以是null。是这个意思不?

然后有个小问题就是你说的第二个坑是不是意思是比如一个list遍历完了那么这个list的iter就只会返回null了?

回复 支持 反对

使用道具 举报

stellari 发表于 2016-4-2 02:41:46 来自手机 | 显示全部楼层
mymax2009 发表于 2016-4-2 01:48
太感谢你了, 说的特别详细。

看了一下你的描述大概能了解意思了, 是不是有点类似于leetcode里的一个 ...

是的,就是类似于ZigzagIterator。我面G的时候就是挂在Zigzag这道题上,所以特别怨念。

我列的坑1和2合起来的意思是说,每个'iterator对应的容器都可能处于三种状态:null,空(0个元素),非空(1个以上元素)。你的代码必须能够合理地处理这三种情况才行。

回复 支持 反对

使用道具 举报

 楼主| mymax2009 发表于 2016-4-2 04:02:39 | 显示全部楼层
stellari 发表于 2016-4-2 02:41
是的,就是类似于ZigzagIterator。我面G的时候就是挂在Zigzag这道题上,所以特别怨念。

我列的坑1和2 ...

明白意思了,清晰又详细,十分感谢!
回复 支持 反对

使用道具 举报

stellari 发表于 2016-4-2 06:46:51 | 显示全部楼层
mymax2009 发表于 2016-4-2 04:02
明白意思了,清晰又详细,十分感谢!

不客气。代码写出来的话,交流一下?我很想看看别人是怎么写的。
回复 支持 反对

使用道具 举报

 楼主| mymax2009 发表于 2016-4-2 13:19:57 | 显示全部楼层
stellari 发表于 2016-4-2 06:46
不客气。代码写出来的话,交流一下?我很想看看别人是怎么写的。

你是说zigzag iter的代码吗?
我用c++写的
目前试了两种,但其实都还没真正用到iterator,正准备试试的
第一种是用一个queue保存所有list, 构造函数里初始化queue
next函数返回queue的第一个list的第一个元素,然后把元素从list里删掉,再把list移到queue尾部。
hasNext直接返回queue是否不为空就行了。
这种就是代码比较少,几行就搞定了

然后第二种我直接贴上来吧,
  1. class zzIter{
  2. public:
  3.         int x, y;
  4.         bool getfirst;
  5.         unordered_set<int> row;
  6.         vector<vector<int>> nums;

  7.         zzIter(vector<vector<int>>& n){
  8.                 nums = n;
  9.                 int len = nums.size();
  10.                 for (int i = 0; i < len; i++)row.insert(i);
  11.                 x =y= 0;
  12.                 getfirst=false;
  13.         }
  14.         bool hasNext(){
  15.                 return !row.empty();
  16.         }
  17.         int next(){
  18.                 if (!getfirst){
  19.                         getfirst = true;
  20.                         return nums[x][y];
  21.                 }
  22.                 x++;
  23.                 modify();
  24.                 if (y == nums[x].size()-1)row.erase(x);
  25.                 return nums[x][y];
  26.         }
  27.         void modify(){
  28.                 while (row.find(x)==row.end()&&x<nums.size()){
  29.                         x++;                       
  30.                 }
  31.                 if (x == nums.size()){
  32.                         x = 0;
  33.                         y++;
  34.                         modify();
  35.                 }
  36.         }
  37. };
复制代码
这个就是要调整当前元素的position,多了一个modify的函数。

另外正准备写个用iterator实现的,按理应该效率会比上面两种高。
回复 支持 反对

使用道具 举报

 楼主| mymax2009 发表于 2016-4-2 13:21:44 | 显示全部楼层
stellari 发表于 2016-4-2 06:46
不客气。代码写出来的话,交流一下?我很想看看别人是怎么写的。

忘了说,第一个用queue的next方法里稍做个判断,如果list已经空了就不添加到queue尾了
回复 支持 反对

使用道具 举报

stellari 发表于 2016-4-2 23:38:13 | 显示全部楼层
mymax2009 发表于 2016-4-2 13:19
你是说zigzag iter的代码吗?
我用c++写的
目前试了两种,但其实都还没真正用到iterator,正准备试试的 ...

我其实指的是iterator of iterators的代码……不过两道题意思其实差不多。

面试的话,还是上来就给iterator实现的好。现在的这种写法是和vector类型绑定死的,而且出现了vector复制,效率不乐观。这两点很容易被面试官抓住攻击。
回复 支持 反对

使用道具 举报

junw24 发表于 2016-4-3 06:59:03 | 显示全部楼层
期待C++写法。
回复 支持 反对

使用道具 举报

 楼主| mymax2009 发表于 2016-4-4 04:44:56 | 显示全部楼层
stellari 发表于 2016-4-2 23:38
我其实指的是iterator of iterators的代码……不过两道题意思其实差不多。

面试的话,还是上来就给ite ...

嗯嗯有道理,多谢提醒啊!
回复 支持 反对

使用道具 举报

Sendoh2015 发表于 2016-4-4 11:22:00 | 显示全部楼层
谁能贴个Java的解法?多谢啊
回复 支持 反对

使用道具 举报

 楼主| mymax2009 发表于 2016-4-4 13:33:34 | 显示全部楼层
本帖最后由 mymax2009 于 2016-4-4 13:42 编辑
stellari 发表于 2016-4-2 23:38
我其实指的是iterator of iterators的代码……不过两道题意思其实差不多。

面试的话,还是上来就给ite ...

我写了个zigzag用iterator的解法,感觉除了需要一个STL存iterator,还是需要把input的container都存一下的,
比如我用的是
  1. queue<vector<int>::iterator> zigIt
复制代码
  1. queue<vector<int>> numbers
复制代码

剩下的思路跟我之前说的那个queue的差不多,
判定hasNext需要把queue里等于当前container end()的都pop掉,return是否不为空,
next函数就取zigIt里front指向的数据,然后在numbers里把这个数删掉,再把这个vector移到numbers的队尾,最后再处理下zigIt。这个的话我感觉跟LRU cache思路有点接近

  1.         queue<vector<int>::iterator> zit;
  2.         queue<vector<int>> number;
  3.         zigzagIter(vector<vector<int>>& nums) {
  4.                
  5.                 for (vector<int> n : nums){
  6.                         number.push(n);
  7.                         zit.push(number.back().begin());
  8.                 }
  9.         }
  10.         bool hasNext(){
  11.                 if (zit.empty())return false;
  12.                 while (!zit.empty() && zit.front() == number.front().end()){
  13.                         zit.pop();
  14.                         number.pop();
  15.                 }
  16.                 if (zit.empty())return false;
  17.                 else return true;
  18.         }
  19.         int next(){
  20.                 int res = *zit.front();
  21.                 number.front().erase(zit.front());
  22.                 zit.pop();
  23.                 number.push(number.front());
  24.                 number.pop();
  25.                 zit.push(number.back().begin());
  26.                
  27.                 return res;
  28.         }
复制代码
所以我感觉复制vector也是难以避免吧(当然C++里一般是用vector,所以类型确实是绑定的,JAVA会有更general点的container可以包含各种object)
因为一方面iterator需要指向实际存在的成员,不然都会变成null吧
然后每个iterator要判定他是不是到当前container的end()的指针时候要是不知道container的ref貌似没办法判定。不过这里应该还是会有更好的办法,我这块知识有限,要是有知道的大神也麻烦给点思路。






回复 支持 反对

使用道具 举报

stellari 发表于 2016-4-4 17:12:07 | 显示全部楼层
mymax2009 发表于 2016-4-4 13:33
我写了个zigzag用iterator的解法,感觉除了需要一个STL存iterator,还是需要把input的container都存一下 ...

嗯,这个用到了iterator,算法是正确的,但是还是不能完全满足我当初面试G时现场被问到的要求:

1. 输入是Iterator<Iterator<Type>>,这点面试官在现场特别强调过,也就是要求底层容器可以是任意类型。不过可以假设我们手头已经有可用的Iterator<Type>的具体类,不需自行实现。

2. ZigzagIterator内部不能使用超过O(K)的内存,其中K是外层容器的尺寸。也就是说内部存放二维容器的数据是不允许的。

3. ZigzagIterator必须实现Iterator<Type>接口。


换言之,ZigzagIterator必须是这个样子的:

template<typename Type>
class ZigzagIterator : public Iterator<Type> {
   ...
public:
    ZigzagIterator(Iterator<Iterator<Type>>& );
    Type next() {...}
    bool hasNext() {...}
};

这种限制条件下,你怎么做呢?
回复 支持 反对

使用道具 举报

bingo1995 发表于 2016-4-4 17:19:13 | 显示全部楼层
我被这道题坑过  主要是没太用过java里面的iterator   然后我用C++ 当时一脸懵逼不知道要干啥
四轮面试里面唯一一轮低分
回复 支持 反对

使用道具 举报

stellari 发表于 2016-4-4 19:01:35 | 显示全部楼层
bingo1995 发表于 2016-4-4 17:19
我被这道题坑过  主要是没太用过java里面的iterator   然后我用C++ 当时一脸懵逼不知道要干啥
四轮面试里 ...

我也是同样遭遇,面试官自己明显是Java背景。Java下的迭代器通常都是实现自通用的Iterator<E>接口,常见容器中都实现了Iterable<E>接口(该接口其中提供了一个Iterator<E>)。但问题是C++的 STL容器都是各自为战,压根就没有这么个“通用迭代器”接口,而algorithm中接受iterator的算法都是通过template来实现的。在现有C++框架下想实现个通用的iterator接口并不trivial,而且关键是各路大牛们都认为这么做是个很糟糕的主意。

所以对用C++的同学来说,遇到这题只能是假设已经有个实现好的Iterator<E>。

另外问一下,你怎么知道你每一轮的成绩的?
回复 支持 反对

使用道具 举报

bingo1995 发表于 2016-4-4 19:02:58 | 显示全部楼层
stellari 发表于 2016-4-4 19:01
我也是同样遭遇,面试官自己明显是Java背景。Java下的迭代器通常都是实现自通用的Iterator接口,常见容器 ...

感觉啊。最后HR说有一个面试官说我coding不行  但我最后还是拿到offer了 说明其他三轮是不错的。
虽然最后没接 233
回复 支持 反对

使用道具 举报

 楼主| mymax2009 发表于 2016-4-5 01:27:57 | 显示全部楼层
bingo1995 发表于 2016-4-4 19:02
感觉啊。最后HR说有一个面试官说我coding不行  但我最后还是拿到offer了 说明其他三轮是不错的。
虽然最 ...

厉害啊!
回复 支持 反对

使用道具 举报

 楼主| mymax2009 发表于 2016-4-5 01:37:20 | 显示全部楼层
stellari 发表于 2016-4-4 17:12
嗯,这个用到了iterator,算法是正确的,但是还是不能完全满足我当初面试G时现场被问到的要求:

1. 输 ...

如果Iterator<Type>已经有了的话那其实也还好,就跟JAVA和C#类似的不过需要多做一个box和unbox类似的操作吧。
但是只能用O(N)内存的话,
还是那两点疑问啊,一个是得有一个方法能判断当前iterator是否到达它自己的end()才行的吧。不过这个应该还是能有办法。
另一点如果类的内部不存储整个数据那指针操作不就没意义了吗?
回复 支持 反对

使用道具 举报

stellari 发表于 2016-4-5 05:16:09 | 显示全部楼层
mymax2009 发表于 2016-4-5 01:37
如果Iterator已经有了的话那其实也还好,就跟JAVA和C#类似的不过需要多做一个box和unbox类似的操作吧。
...

你说的这两个问题,恰好是Iterator<Type>接口要解决的问题:

1. 判断被包装的Iterator是否已经到达容器尾,直接调用它提供的hasNext()接口函数即可。
2. 你获得下一个元素的唯一途径,就是通过被包装的Iterator的next()函数。你自己写的代码中不应该出现任何指向容器内元素的指针。

这是纯粹的Java思路,所以我才建议你做这题时最好转用Java来做。用C++强行实现这种思路太痛苦了。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 16:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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