一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2409|回复: 20
收起左侧

Google 电面第2面 9/11

[复制链接] |试试Instant~ |关注本帖
complete_46 发表于 2015-9-11 07:35:40 | 显示全部楼层 |阅读模式

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

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

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

x
第一题
Longest Consecutive Sequence

第二题
InterleavingIterator Flatten 2D Vector 变种 ,输入不再是List<List<>>而是List<Iterator>,遍历顺序也变成了先遍历每一个list的第n个元素
比如 说 <1,2,3><4, 5, 6><7, 8>
要返回的是<1, 4, 7, 2, 5, 8, 3, 6>

第二题答的不怎么样,code也没写的完整,发面经求RP吧
顺便 求点米呀

评分

1

查看全部评分

本帖被以下淘专辑推荐:

KevinFromJail 发表于 2015-9-11 10:53:33 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
第二个问题是每次从头取, 再放到队列尾巴。空指针不放入。空队列停止。
回复 支持 反对

使用道具 举报

say543 发表于 2015-9-11 12:31:24 | 显示全部楼层
关注一亩三分地微博:
Warald
KevinFromJail 发表于 2015-9-11 10:53
第二个问题是每次从头取, 再放到队列尾巴。空指针不放入。空队列停止。

same solution. 感谢楼主分享
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-9-11 21:53:42 | 显示全部楼层
KevinFromJail 发表于 2015-9-11 10:53.鐣欏璁哄潧-涓浜-涓夊垎鍦
第二个问题是每次从头取, 再放到队列尾巴。空指针不放入。空队列停止。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
你好,方不方便贴个代码呢?因为不知道hasNext()和next()这两个方法里怎么让外部的iterator循环的遍历,是每次都遍历2变吗?
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-12 00:00:02 | 显示全部楼层
第二题为什么是先遍历每一个list的第n个元素?
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

storm_hair 发表于 2015-9-14 09:08:42 | 显示全部楼层
第一题LEETCODE已经有了
回复 支持 反对

使用道具 举报

阿海 发表于 2015-9-15 01:03:55 | 显示全部楼层
我写了这么长的代码,被几行代码击败。哭了
# class Solution(object):
#     def longestConsecutive(self, nums):
#         """. 鍥磋鎴戜滑@1point 3 acres
#         :type nums: List[int]
#         :rtype: int
#         """
#         if not nums:
#             return 0. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
#         max_length = 1. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
#         length = 1. more info on 1point3acres.com
#         smallest_num = nums[0]
.1point3acres缃#         hash_table = dict()
#         hash_table[smallest_num] = 0
#         for i in range(len(nums)):
#             if nums[i] not in hash_table:
#                 hash_table[nums[i]] = i
#             if nums[i] < smallest_num:. 鍥磋鎴戜滑@1point 3 acres
#                 smallest_num = nums[i]

#         while hash_table:
#             smallest_num += 1. more info on 1point3acres.com
#             if smallest_num in hash_table:
#                 length += 1-google 1point3acres
#                 hash_table.pop(smallest_num)

#             else:
#                 smallest_num = hash_table.keys()[0]. more info on 1point3acres.com
#                 length = 1
#                 for k, v in hash_table.iteritems():.1point3acres缃
#                     if k < smallest_num:
#                         smallest_num = k
#                 hash_table.pop(smallest_num)
#             max_length = max(max_length, length) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
#         return max_length
. From 1point 3acres bbs

class Solution:
    def longestConsecutive(self, nums):
        nums = set(nums)
        best = 0. Waral 鍗氬鏈夋洿澶氭枃绔,
        for n in nums:. visit 1point3acres.com for more.
            if n - 1 not in nums:
                m = n + 1
                while m in nums:
                    m += 1
                best = max(best, m - n)-google 1point3acres
        return best
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-9-15 15:18:28 | 显示全部楼层
阿海 发表于 2015-9-15 01:03
我写了这么长的代码,被几行代码击败。哭了
# class Solution(object):
#     def longestConsecutive(se ...

你给出的短代码的答案,我觉得不是O(n)的呀,至少worst case应该不是O(n), 因为set操作
回复 支持 反对

使用道具 举报

tbu 发表于 2015-9-15 15:50:03 | 显示全部楼层
请教LZ, Google全职电面一共有几轮呢?
回复 支持 反对

使用道具 举报

storm_hair 发表于 2015-9-15 19:14:32 | 显示全部楼层
tbu 发表于 2015-9-15 15:50
请教LZ, Google全职电面一共有几轮呢?

一轮电面 然后onsite
回复 支持 反对

使用道具 举报

peach=。= 发表于 2015-9-18 14:57:20 | 显示全部楼层
say543 发表于 2015-9-11 12:31
same solution. 感谢楼主分享
. 1point 3acres 璁哄潧
请问可以说详细一点吗?这题是要implement一个iterator还是返回arraylist呢?另外,从头取再放到队列尾巴是什么意思呢?求指教!
回复 支持 反对

使用道具 举报

douya 发表于 2015-9-20 10:52:35 | 显示全部楼层
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;
回复 支持 反对

使用道具 举报

stellari 发表于 2015-9-20 20:03:24 | 显示全部楼层
douya 发表于 2015-9-20 10:52
这里这个iterator的意思是,next() 下一个list?
所以我大概写了下,这样对不对?

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

使用道具 举报

douya 发表于 2015-9-21 04:58:34 | 显示全部楼层
stellari 发表于 2015-9-20 20:03
你大概是没理解这个题意。题目的意思并不是希望得到result这个完整序列,而是让你实现AlternateIterator: ...

哦,多谢高人指点。我大概明白了。我试着写了下。. 鍥磋鎴戜滑@1point 3 acres
您看这样写对不对:
Class MyIterator{

    List<Iterator> input;
    int index=0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    public MyIterator(List<Iterator> input){. visit 1point3acres.com for more.
        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;
    }
-google 1point3acres
    public boolean hasNext(){
        return !input.isEmpty();
    }
}
回复 支持 反对

使用道具 举报

stellari 发表于 2015-9-21 13:04:02 | 显示全部楼层
douya 发表于 2015-9-21 04:58
哦,多谢高人指点。我大概明白了。我试着写了下。
您看这样写对不对:
Class MyIterator{

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

回复 支持 反对

使用道具 举报

douya 发表于 2015-9-22 07:05:17 | 显示全部楼层
stellari 发表于 2015-9-21 13:04. from: 1point3acres.com/bbs
这个是通不过的。如果List中所有的Iterator都为空,那么第一次调用hasNext()会返回什么?应该返回什么?
...

有道理!我去改改,多谢!多谢!
回复 支持 反对

使用道具 举报

uuuouou 发表于 2015-9-22 10:36:38 | 显示全部楼层
谢lz面经,分享个第二题C++的solution
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4. #include <list>
  5. using namespace std;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6. . Waral 鍗氬鏈夋洿澶氭枃绔,
  7. class InterleavingIterator{
  8. private:
  9.         typedef vector<int>::const_iterator CI;
  10.         typedef pair<CI, CI> Cursor;
  11.         typedef list<Cursor>::iterator Iter;. 鍥磋鎴戜滑@1point 3 acres
  12. private:. From 1point 3acres bbs
  13.         list<Cursor> cursorList;
  14.         Iter         iter;. Waral 鍗氬鏈夋洿澶氭枃绔,
  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()));. 1point3acres.com/bbs
  20.                         }
  21.                 }.1point3acres缃
  22.                 iter = cursorList.begin();
  23.         }. from: 1point3acres.com/bbs
  24.         bool hasNext()const{
  25.                 return !cursorList.empty();
  26.         }
  27.         int next(){
  28.                 int x = *(*iter).first++;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  29.                 if((*iter).first == (*iter).second){
  30.                         iter = cursorList.erase(iter);
  31.                 }
  32.                 else{
  33.                         ++iter;. visit 1point3acres.com for more.
  34.                 }
  35.                 if(iter == cursorList.end()) iter = cursorList.begin();
  36.                 return x;
  37.         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  38. };

  39. int main()
  40. {. 1point 3acres 璁哄潧
  41.         int a[] = {1, 2, 3};
  42.         int b[] = {4, 5, 6};-google 1point3acres
  43.         int c[] = {7, 8};

  44.         vector<vector<int> > arrays;
  45.         arrays.push_back(vector<int>(a, a + sizeof(a)/sizeof(int)));
  46.         arrays.push_back(vector<int>(b, b + sizeof(b)/sizeof(int)));
  47.         arrays.push_back(vector<int>(c, c + sizeof(c)/sizeof(int)));
  48. . visit 1point3acres.com for more.
  49.         InterleavingIterator iter(arrays);
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  50.         while(iter.hasNext()){
  51.                 cout << iter.next() << " ";
  52.         }. visit 1point3acres.com for more.

  53.         return 0;
  54. }
复制代码
回复 支持 反对

使用道具 举报

uuuouou 发表于 2015-9-22 10:57:52 | 显示全部楼层
额,修改一下,可能看起来更舒服些
  1. #include <iostream>. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  2. #include <vector>
  3. #include <utility> 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  4. #include <list>
  5. using namespace std;

  6. class Cursor{. more info on 1point3acres.com
  7.         typedef vector<int>::const_iterator CI;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  8. private:
  9.         CI cur, end;
  10. public:
  11.         Cursor(const vector<int>& arr){
  12.                 cur = arr.begin();
  13.                 end = arr.end();
  14.         }
  15.         bool hasNext()const{
  16.                 return cur != end;
  17.         }
  18.         int next(){
  19.                 return *cur++;. from: 1point3acres.com/bbs
  20.         }. visit 1point3acres.com for more.
  21. };

  22. class InterleavingIterator{. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  23.         typedef list<Cursor>::iterator Iter;
  24. private: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  25.         list<Cursor> cursorList;. Waral 鍗氬鏈夋洿澶氭枃绔,
  26.         Iter         iter;
  27. public:
  28.         InterleavingIterator(const vector<vector<int> >& arrays){. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  29.                 for(int i = 0; i < arrays.size(); ++i){
  30.                         if(!arrays[i].empty()){
  31.                                 cursorList.push_back(Cursor(arrays[i]));
  32.                         }
  33.                 }
  34.                 iter = cursorList.begin();
  35.         }
  36.         bool hasNext()const{
  37.                 return !cursorList.empty();
  38.         }
  39.         int next(){
  40.                 int x = (*iter).next();
  41.                 if((*iter).hasNext()){
  42.                         ++iter;
  43.                 }
    . from: 1point3acres.com/bbs
  44.                 else{.1point3acres缃
  45.                         iter = cursorList.erase(iter);
  46.                 }
  47.                 if(iter == cursorList.end()) iter = cursorList.begin();
  48.                 return x;
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  49.         }
  50. };

  51. int main()
  52. {
  53.         int a[] = {1, 2, 3};
  54.         int b[] = {4, 5, 6};
  55.         int c[] = {7, 8};. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  56.         vector<vector<int> > arrays;. 鍥磋鎴戜滑@1point 3 acres
  57.         arrays.push_back(vector<int>(a, a + sizeof(a)/sizeof(int)));
  58.         arrays.push_back(vector<int>(b, b + sizeof(b)/sizeof(int)));
  59.         arrays.push_back(vector<int>(c, c + sizeof(c)/sizeof(int)));
  60. . Waral 鍗氬鏈夋洿澶氭枃绔,
  61.         InterleavingIterator iter(arrays);
  62.         while(iter.hasNext()){
  63.                 cout << iter.next() << " ";
  64.         }
  65. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  66.         return 0;
  67. }
复制代码
回复 支持 反对

使用道具 举报

stellari 发表于 2015-9-22 13:10:39 | 显示全部楼层
uuuouou 发表于 2015-9-22 10:57. Waral 鍗氬鏈夋洿澶氭枃绔,
额,修改一下,可能看起来更舒服些

感谢分享!不过我觉得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设计了。
回复 支持 反对

使用道具 举报

uuuouou 发表于 2015-9-22 16:45:51 | 显示全部楼层
stellari 发表于 2015-9-22 13:10
感谢分享!不过我觉得InterleavingIterator最好是能继承自一个Iterator接口(在C++中是纯虚类)。cursorL ...

很有道理的会说,感谢指点~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-1 01:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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