近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

电面面经一枚 顺带求人品

[复制链接] |试试Instant~ |关注本帖
xiaomiaoaoao 发表于 2015-12-18 15:23:56 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Other在职跳槽

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
第一次发面经~为进入G家攒人品 求bless

没有针对简历提问, 只有一道算法题 ---- 已知一个List里全是interger, 还有一个set里也全是integer,求是否存在一个sublist, set里所有元素和sublist中所有元素一一对应。[sublist 这里要求必须为原List的连续项, 注意set里元素无序]

楼主似乎见闻比较少, 没有刷过这道题, 虽然找到了一个面试官同意的解法写了出来, 但是实在不知道是不是最优 。 抛砖引玉。我用了一个linkedlist 和 hashmap。

评分

1

查看全部评分

zealot5209 发表于 2015-12-19 20:42:43 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
能不能不在set上操作, 用hashMap记录visited, fast指向的元素 !visited && in set 就继续走,如果slow fast间距离达到set的size就说明找到了; 否则,看是因为什么fail的:如果是因为visited,就移动slow, 等slow经过重复的元素就停,继续移动fast; 如果是因为遇到了set里没有的元素,就slow和fast都指向后面的元素
回复 支持 1 反对 0

使用道具 举报

fsd123 发表于 2015-12-18 21:46:31 | 显示全部楼层
关注一亩三分地微博:
Warald
一一对应的具体要求是什么? sublist 里没有 set 中没有的元素?sublist 中不允许有重复元素?

如果两个的答案都是“是”,觉得似乎可以用两个指针指向 list ,初始化的时候将两个指针放在第一个在 set 中存在元素的所在位置,然后快的指针向后移动,如果指向的元素在 set 存在就继续移动,并且从 set 中删除该元素。如果循环过程中 set 为空,则找到 sublist ,否则快的指针指向的元素在 set 中不存在,这样移动慢指针恢复 set ,之后再同时移动两个指针到之后出现的在 set 包含的元素的位置。

时间复杂度 O(n),空间复杂度 O(1). From 1point 3acres bbs

P.S. Google 不是一般都两轮电面么?
回复 支持 反对

使用道具 举报

 楼主| xiaomiaoaoao 发表于 2015-12-18 21:57:28 | 显示全部楼层
fsd123 发表于 2015-12-18 21:46
一一对应的具体要求是什么? sublist 里没有 set 中没有的元素?sublist 中不允许有重复元素?

如果两个 ...
. From 1point 3acres bbs
List里可以有重复的, 找出的sublist是必须没有重复元素的的(因为SET里也没有重复的), sublist里不能有SET里没有的元素(两个要互相一一对应). From 1point 3acres bbs

记得以前上学的时候是两轮电面,我是在职逃难的....突然失眠中
回复 支持 反对

使用道具 举报

fsd123 发表于 2015-12-18 22:11:17 | 显示全部楼层
xiaomiaoaoao 发表于 2015-12-18 21:57
List里可以有重复的, 找出的sublist是必须没有重复元素的的(因为SET里也没有重复的), sublist里不能 ...

那我理解对了。

twitter 么。。逃难。。
回复 支持 反对

使用道具 举报

 楼主| xiaomiaoaoao 发表于 2015-12-18 22:45:01 | 显示全部楼层
fsd123 发表于 2015-12-18 22:11
那我理解对了。

twitter 么。。逃难。。

你说的是list里指针吧 我忘了可以从set里删除 复杂度比你的高了 也写得麻烦了 sigh... 似乎只能求放水了...
回复 支持 反对

使用道具 举报

JohnsonMS 发表于 2015-12-19 04:09:23 | 显示全部楼层
Good idea, 学习了, 使用伸缩方式做
回复 支持 反对

使用道具 举报

cbmbbz 发表于 2015-12-19 11:31:56 | 显示全部楼层
fsd123 发表于 2015-12-18 21:46
一一对应的具体要求是什么? sublist 里没有 set 中没有的元素?sublist 中不允许有重复元素?

如果两个 ...

我没理解错的话...你说的方法不适合这个test case:list是abcbda,set是abcd,扫list的时候扫到第二个b,就会从d开始,而错过了cbda这个答案
我觉得这题是leetcode Longest Substring Without Repeating Characters的变体,需要用到hashmap的
回复 支持 反对

使用道具 举报

fhq843 发表于 2015-12-19 11:37:53 | 显示全部楼层
set 既然无序是不是就是set的任一permutation 是list的substring
回复 支持 反对

使用道具 举报

fsd123 发表于 2015-12-19 14:11:05 | 显示全部楼层
cbmbbz 发表于 2015-12-19 11:31
. 1point3acres.com/bbs我没理解错的话...你说的方法不适合这个test case:list是abcbda,set是abcd,扫list的时候扫到第二个b, ...
. From 1point 3acres bbs
啊,是的。确实过不了这个 case ,那就修改下移动策略

初始化 slow 和 fast 为 head,进入循环,判定 fast 所指是否在 set 中,在就从 set 移除,并移动 fast ,否则判定 slow 和 fast 是否指向同一个,是则同时移动,否则将 slow 所指加入 set ,并只移动 slow。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这样就能覆盖掉你说的这个 case 了,复杂度还是没变

而且实现后发现比原来的代码还简单了。囧
回复 支持 反对

使用道具 举报

fsd123 发表于 2015-12-19 14:11:52 | 显示全部楼层
cbmbbz 发表于 2015-12-19 11:31
我没理解错的话...你说的方法不适合这个test case:list是abcbda,set是abcd,扫list的时候扫到第二个b, ...

.鏈枃鍘熷垱鑷1point3acres璁哄潧不过我没明白为什么要用 hashmap ?
回复 支持 反对

使用道具 举报

 楼主| xiaomiaoaoao 发表于 2015-12-19 16:32:46 | 显示全部楼层
fsd123 发表于 2015-12-19 14:11. Waral 鍗氬鏈夋洿澶氭枃绔,
啊,是的。确实过不了这个 case ,那就修改下移动策略

初始化 slow 和 fast 为 head,进入循环,判定  ...
. visit 1point3acres.com for more.
不过你这个方法要每次拷贝set, 当指针移动的时候, 时间应该还是o(mn)
回复 支持 反对

使用道具 举报

fsd123 发表于 2015-12-19 16:43:15 | 显示全部楼层
xiaomiaoaoao 发表于 2015-12-19 16:32
不过你这个方法要每次拷贝set, 当指针移动的时候, 时间应该还是o(mn)

为什么要拷贝 set ?就算最后要维护 set 不变,返回前再将元素加进 set 就好。

而且时间是 O(n) 啊,slow 和 fast 都只遍历 list 一次
回复 支持 反对

使用道具 举报

ninacc 发表于 2015-12-20 17:39:43 | 显示全部楼层
O(n^2) 和 O(n) 不知道有没问题。祝楼主顺利拿到Onsite~!! 求大家指导代码,谢谢!
        public static boolean subList(HashSet<Integer> set,int[] nums){
                if(set==null || nums ==null) return false;
                int left = 0,right=0;
                HashSet<Integer> visited = new HashSet<Integer>();
                for(;right<nums.length;right++){
                        if(!set.contains(nums[right])){
                                visited.clear();
                                continue;
                        }else{
                                if(visited.contains(nums[right])){
                                        while(left<right && nums[left]!=nums[right]){
                                                visited.remove(nums[left]);
                                                left++;
                                        }
                                        left++;
                                }else{
                                        visited.add(nums[right]);
                                        if(visited.size()==set.size()) return true;
                                }
                        }
                }
                return false;
        }
. 1point3acres.com/bbs



回复 支持 反对

使用道具 举报

ninacc 发表于 2015-12-20 17:40:17 | 显示全部楼层
O(n^2) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  1.         public static boolean subListExist(HashSet<Integer> set, int[] nums){
  2.                 if(set==null || nums ==null) return false;
  3.                 for(int i=0;i<nums.length;i++){
  4.                         HashSet<Integer> found = new HashSet<Integer>();
  5.                         for(int j=i;j<i+set.size();j++){
  6.                                 if(!set.contains(nums[j])){-google 1point3acres
  7.                                         break;. 1point 3acres 璁哄潧
  8.                                 }else{
  9.                                         if(found.contains(nums[j])){
  10.                                                 break;
  11.                                         }else{
  12.                                                 found.add(nums[j]);
  13.                                         }
  14.                                 }
  15.                         }. 1point 3acres 璁哄潧
  16.                         if(found.size()==set.size()) return true;
  17.                 }
  18.                 return false;
  19.         }
复制代码
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-2 06:46:53 | 显示全部楼层
写了下代码,时间和空间复杂度都是O(n),其实这个题就是sliding window
  1. public class SublistEqualsSet {

  2.         public static boolean isSublistEqualsSet(List<Integer> list,
  3.                         Set<Integer> set) {
  4.                 if (set == null || list == null) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  5.                         return false;
  6.                 }
  7.                 if (set.size() == 0) {-google 1point3acres
  8.                         return true;
  9.                 }
  10.                 if (list.size() == 0) {
  11.                         return false;. 1point3acres.com/bbs
  12.                 }
  13.                 int start = 0;
  14.                 int pos = 0;
  15.                 System.out.println(set.size());
  16.                 Set<Integer> tmp = new HashSet<Integer>();
  17.                 while (pos < list.size()) {
  18.                         int cur = list.get(pos);
  19.                         if (set.contains(cur)) {
  20.                                 while (start < pos && tmp.contains(cur)) {
  21.                                         tmp.remove(list.get(start));
  22.                                         start++;
  23.                                 }
  24.                                 tmp.add(cur);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  25.                                 if (tmp.size() == set.size()) {
  26.                                         return true;
  27.                                 }
  28.                         } else {
  29.                                 start = pos + 1;
  30.                                 tmp.clear();
  31.                         }
  32.                         pos++;
  33.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,

  34.                 return false;
  35.         }. from: 1point3acres.com/bbs
  36. -google 1point3acres
  37.         public static void main(String[] args) {
  38.                 List<Integer> list = new ArrayList<Integer>(
  39.                                 Arrays.asList(1, 2, 3, 2, 4, 1));
  40.                 Set<Integer> set = new HashSet<Integer>();
  41.                 set.add(1);
  42.                 set.add(2);
  43.                 set.add(3);
  44.                 set.add(4);
  45.                 System.out.println(isSublistEqualsSet(list, set));
  46.         }
  47. }
复制代码
回复 支持 反对

使用道具 举报

csgtc 发表于 2016-2-3 13:33:59 | 显示全部楼层
Sliding Window. 正解是O(n)时间和O(n)空间 hashset
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-29 02:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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