电面面经一枚 顺带求人品

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

没有针对简历提问， 只有一道算法题 ---- 已知一个Lis

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

不是最优 。 抛砖引玉。我用了一个linkedlist 和 hashmap。

能不能不在set上操作， 用hashMap记录visited, fast指向的元素 !visited && in set 就继续走，如果slow fast间距离达到set的size就说明找到了； 否则，看是因为什么fail的：如果是因为visited,就移动slow, 等slow经过重复的元素就停，继续移动fast; 如果是因为遇到了set里没有的元素，就slow和fast都指向后面的元素

写了下代码，时间和空间复杂度都是O(n)，其实这个题就是sliding window

1. public class SublistEqualsSet {
   
2. 
   
3.         public static boolean isSublistEqualsSet(List<Integer> list,
   
4.                         Set<Integer> set) {
   
5.                 if (set == null || list == null) {
   
6.                         return false;
   
7.                 }
   
8.                 if (set.size() == 0) {
   
9.                         return true;
   
10.                 }
    
11.                 if (list.size() == 0) {
    
12.                         return false;
    
13.                 }
    
14.                 int start = 0;
    
15.                 int pos = 0;
    
16.                 System.out.println(set.size());
    
17.                 Set<Integer> tmp = new HashSet<Integer>();
    
18.                 while (pos < list.size()) {
    
19.                         int cur = list.get(pos);
    
20.                         if (set.contains(cur)) {
    
21.                                 while (start < pos && tmp.contains(cur)) {
    
22.                                         tmp.remove(list.get(start));
    
23.                                         start++;
    
24.                                 }
    
25.                                 tmp.add(cur);
    
26.                                 if (tmp.size() == set.size()) {
    
27.                                         return true;
    
28.                                 }
    
29.                         } else {
    
30.                                 start = pos + 1;
    
31.                                 tmp.clear();
    
32.                         }
    
33.                         pos++;
    
34.                 }
    
35. 
    
36.                 return false;
    
37.         }
    
38. 
    
39.         public static void main(String[] args) {
    
40.                 List<Integer> list = new ArrayList<Integer>(
    
41.                                 Arrays.asList(1, 2, 3, 2, 4, 1));
    
42.                 Set<Integer> set = new HashSet<Integer>();
    
43.                 set.add(1);
    
44.                 set.add(2);
    
45.                 set.add(3);
    
46.                 set.add(4);
    
47.                 System.out.println(isSublistEqualsSet(list, set));
    
48.         }
    
49. }

复制代码

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;

        }

一一对应的具体要求是什么？ sublist 里没有 set 中没有的元素？sublist 中不允许有重复元素？

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

时间复杂度 O(n)，空间复杂度 O(1)

P.S. Google 不是一般都两轮电面么？

fsd123 发表于 2015-12-18 21:46
一一对应的具体要求是什么？ sublist 里没有 set 中没有的元素？sublist 中不允许有重复元素？

如果两个 ...

List里可以有重复的， 找出的sublist是必须没有重复元素的的（因为SET里也没有重复的）， sublist里不能有SET里没有的元素（两个要互相一一对应）

记得以前上学的时候是两轮电面，我是在职逃难的....突然失眠中

xiaomiaoaoao 发表于 2015-12-18 21:57
List里可以有重复的， 找出的sublist是必须没有重复元素的的（因为SET里也没有重复的）， sublist里不能 ...

那我理解对了。

twitter 么。。逃难。。

fsd123 发表于 2015-12-18 22:11
那我理解对了。

twitter 么。。逃难。。

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

Good idea， 学习了， 使用伸缩方式做

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的

set 既然无序是不是就是set的任一permutation 是list的substring

cbmbbz 发表于 2015-12-19 11:31
我没理解错的话...你说的方法不适合这个test case：list是abcbda，set是abcd，扫list的时候扫到第二个b， ...

啊，是的。确实过不了这个 case ，那就修改下移动策略

初始化 slow 和 fast 为 head，进入循环，判定 fast 所指是否在 set 中，在就从 set 移除，并移动 fast ，否则判定 slow 和 fast 是否指向同一个，是则同时移动，否则将 slow 所指加入 set ，并只移动 slow。

这样就能覆盖掉你说的这个 case 了，复杂度还是没变

而且实现后发现比原来的代码还简单了。囧

cbmbbz 发表于 2015-12-19 11:31
我没理解错的话...你说的方法不适合这个test case：list是abcbda，set是abcd，扫list的时候扫到第二个b， ...

不过我没明白为什么要用 hashmap ？