Google 电面第2面 9/11

say543 发表于 2015-9-11 12:31
same solution. 感谢楼主分享

请问可以说详细一点吗？这题是要implement一个iterator还是返回arraylist呢？另外，从头取再放到队列尾巴是什么意思呢？求指教！

KevinFromJail 发表于 2015-9-11 10:53
第二个问题是每次从头取， 再放到队列尾巴。空指针不放入。空队列停止。

这里这个iterator的意思是，next() 下一个list？
所以我大概写了下，这样对不对？

result
while(hasNext()){
    list = next();
    if(list.isEmpty()) break;
    result.add(list.get(0));
    list.remove(0);
}

return result;

douya 发表于 2015-9-20 10:52
这里这个iterator的意思是，next() 下一个list？
所以我大概写了下，这样对不对？

你大概是没理解这个题意。题目的意思并不是希望得到result这个完整序列，而是让你实现AlternateIterator::hasNext()和AternateIterator::next()这两个函数。题目中本来可以给List<List<Type> >， 但是实际上却用Iterator替换掉了内层的List，稍微增加了一些难度，但是算法本质是一样的。这道题的输入甚至还可以可给成Iterator<Iterator<Type> >，做法都是一样的。

stellari 发表于 2015-9-20 20:03
你大概是没理解这个题意。题目的意思并不是希望得到result这个完整序列，而是让你实现AlternateIterator: ...

哦，多谢高人指点。我大概明白了。我试着写了下。
您看这样写对不对：
Class MyIterator{

    List<Iterator> input;
    int index=0;
    public MyIterator(List<Iterator> input){
        this. input = input;      
    }
    public int next(){
        Iterator iter=input.get(index);
        int result;
        if(iter.hasNext()){
            result=iter.next();
        }
        if(!iter.hasNext()) {
            input.remove(iter);
        } else {
            index=(index+1)%input.size();
        }
        return result;
    }

    public boolean hasNext(){
        return !input.isEmpty();
    }
}

douya 发表于 2015-9-21 04:58
哦，多谢高人指点。我大概明白了。我试着写了下。
您看这样写对不对：
Class MyIterator{

这个是通不过的。如果List中所有的Iterator都为空，那么第一次调用hasNext()会返回什么？应该返回什么？

stellari 发表于 2015-9-21 13:04
这个是通不过的。如果List中所有的Iterator都为空，那么第一次调用hasNext()会返回什么？应该返回什么？
...

有道理！我去改改，多谢！多谢！

谢lz面经，分享个第二题C++的solution

1. #include <iostream>
   
2. #include <vector>
   
3. #include <utility>
   
4. #include <list>
   
5. using namespace std;
   
6. 
   
7. class InterleavingIterator{
   
8. private:
   
9.         typedef vector<int>::const_iterator CI;
   
10.         typedef pair<CI, CI> Cursor;
    
11.         typedef list<Cursor>::iterator Iter;
    
12. private:
    
13.         list<Cursor> cursorList;
    
14.         Iter         iter;
    
15. public:
    
16.         InterleavingIterator(const vector<vector<int> >& arrays){
    
17.                 for(int i = 0; i < arrays.size(); ++i){
    
18.                         if(!arrays[i].empty()){
    
19.                                 cursorList.push_back(Cursor(arrays[i].begin(), arrays[i].end()));
    
20.                         }
    
21.                 }
    
22.                 iter = cursorList.begin();
    
23.         }
    
24.         bool hasNext()const{
    
25.                 return !cursorList.empty();
    
26.         }
    
27.         int next(){
    
28.                 int x = *(*iter).first++;
    
29.                 if((*iter).first == (*iter).second){
    
30.                         iter = cursorList.erase(iter);
    
31.                 }
    
32.                 else{
    
33.                         ++iter;
    
34.                 }
    
35.                 if(iter == cursorList.end()) iter = cursorList.begin();
    
36.                 return x;
    
37.         }
    
38. };
    
39. 
    
40. int main()
    
41. {
    
42.         int a[] = {1, 2, 3};
    
43.         int b[] = {4, 5, 6};
    
44.         int c[] = {7, 8};
    
45. 
    
46.         vector<vector<int> > arrays;
    
47.         arrays.push_back(vector<int>(a, a + sizeof(a)/sizeof(int)));
    
48.         arrays.push_back(vector<int>(b, b + sizeof(b)/sizeof(int)));
    
49.         arrays.push_back(vector<int>(c, c + sizeof(c)/sizeof(int)));
    
50. 
    
51.         InterleavingIterator iter(arrays);
    
52.         while(iter.hasNext()){
    
53.                 cout << iter.next() << " ";
    
54.         }
    
55. 
    
56.         return 0;
    
57. }
    

复制代码

额，修改一下，可能看起来更舒服些

1. #include <iostream>
   
2. #include <vector>
   
3. #include <utility>
   
4. #include <list>
   
5. using namespace std;
   
6. 
   
7. class Cursor{
   
8.         typedef vector<int>::const_iterator CI;
   
9. private:
   
10.         CI cur, end;
    
11. public:
    
12.         Cursor(const vector<int>& arr){
    
13.                 cur = arr.begin();
    
14.                 end = arr.end();
    
15.         }
    
16.         bool hasNext()const{
    
17.                 return cur != end;
    
18.         }
    
19.         int next(){
    
20.                 return *cur++;
    
21.         }
    
22. };
    
23. 
    
24. class InterleavingIterator{
    
25.         typedef list<Cursor>::iterator Iter;
    
26. private:
    
27.         list<Cursor> cursorList;
    
28.         Iter         iter;
    
29. public:
    
30.         InterleavingIterator(const vector<vector<int> >& arrays){
    
31.                 for(int i = 0; i < arrays.size(); ++i){
    
32.                         if(!arrays[i].empty()){
    
33.                                 cursorList.push_back(Cursor(arrays[i]));
    
34.                         }
    
35.                 }
    
36.                 iter = cursorList.begin();
    
37.         }
    
38.         bool hasNext()const{
    
39.                 return !cursorList.empty();
    
40.         }
    
41.         int next(){
    
42.                 int x = (*iter).next();
    
43.                 if((*iter).hasNext()){
    
44.                         ++iter;
    
45.                 }
    
46.                 else{
    
47.                         iter = cursorList.erase(iter);
    
48.                 }
    
49.                 if(iter == cursorList.end()) iter = cursorList.begin();
    
50.                 return x;
    
51.         }
    
52. };
    
53. 
    
54. int main()
    
55. {
    
56.         int a[] = {1, 2, 3};
    
57.         int b[] = {4, 5, 6};
    
58.         int c[] = {7, 8};
    
59. 
    
60.         vector<vector<int> > arrays;
    
61.         arrays.push_back(vector<int>(a, a + sizeof(a)/sizeof(int)));
    
62.         arrays.push_back(vector<int>(b, b + sizeof(b)/sizeof(int)));
    
63.         arrays.push_back(vector<int>(c, c + sizeof(c)/sizeof(int)));
    
64. 
    
65.         InterleavingIterator iter(arrays);
    
66.         while(iter.hasNext()){
    
67.                 cout << iter.next() << " ";
    
68.         }
    
69. 
    
70.         return 0;
    
71. }
    

复制代码

uuuouou 发表于 2015-9-22 10:57
额，修改一下，可能看起来更舒服些

感谢分享！不过我觉得InterleavingIterator最好是能继承自一个Iterator接口（在C++中是纯虚类）。cursorList不是list<Cursor>类型，而是list<Iterator*>（因为传进来的参数就是list<Iterator*>），这样的好处是：具有Iterator接口的InterleavingIterator本身又可以被其他Iterator包装，因此可以轻松实现各种Iterator方式的组合。比如InterleavingIterator被EvenIterator（只返回偶数的Iterator）包装的话，就能够实现“以Interleaving方式取数字，但是要隔一行取一个这种方式”。然后你再跟面试官说一句，“Essentially I just implemented the Decorator Pattern”，他可能就会觉得你很懂OO设计了。

stellari 发表于 2015-9-22 13:10
感谢分享！不过我觉得InterleavingIterator最好是能继承自一个Iterator接口（在C++中是纯虚类）。cursorL ...

很有道理的会说，感谢指点~