925 Zenefits 电面

aiuou 发表于 2015-10-15 00:29
如何efficient的比较两个集合是否相等？

我没考虑到这个点，貌似也没有特别好的方法，不知楼主是怎么做的

我想了个方法，同时从左右两边走，用两个set分别记录prefix set和surfix set。同时maintain一个diffset。如果prefix或surfix有一个新的element， 现查看是否diffset里是否有这个值，如果没有就把这个新elment加入，如果有就把这个值从diffset里剪掉。如果diffset为空，说明目前的prefix set 和 surfix set相同，把这时的prefix／surfix set的长度记录下来放在一个set里，叫pairSet。我还用了两个array分别记录 长度为i的prefixset出现的次数，比如｛1，1，1｝ prefix set就是［1］那么义工出现了3次｛1｝，｛1，1｝，｛1，1，1｝
最后过一遍pairSet，然后把相应的prefix set出现的次数 ＊ surfix set 出现的次数就可以了。
整个算法复杂度应该是O（n）

1. package zenefits;
   
2. import java.util.*;
   
3. public class PrefixSurfixArray {
   
4. 
   
5.         public static long getPrefixSurfixPair(int [] a){
   
6.                 if(a==null||a.length==0) return 0;
   
7.                 int[] leftSetCount = new int[a.length];
   
8.                 int[] rightSetCount = new int[a.length];
   
9.                 int left=0,right=0;
   
10.                 long result=0;
    
11.                 HashSet<Integer> diff = new HashSet<Integer> ();
    
12.                 HashSet<Integer> leftSet = new HashSet<Integer> ();
    
13.                 HashSet<Integer> rightSet = new HashSet<Integer> ();
    
14.                 HashSet<Integer> pairIndex = new HashSet<Integer> ();
    
15.                 while(left<a.length||right<a.length){
    
16.                         int temp=0;
    
17.                         if(leftSet.size()<=rightSet.size()&&left<a.length){
    
18.                                 temp=a[left];
    
19.                                 if(!leftSet.contains(temp)){
    
20.                                         leftSet.add(temp);
    
21.                                         leftSetCount[leftSet.size()-1]=1;
    
22.                                         if(diff.contains(temp)){
    
23.                                                 diff.remove(temp);
    
24.                                         }else{
    
25.                                                 diff.add(temp);
    
26.                                         }                       
    
27.                                 }else{
    
28.                                         leftSetCount[leftSet.size()-1]++;       
    
29.                                 }                       
    
30.                                 left++;
    
31.                         }else {
    
32.                                 temp=a[a.length-1-right];
    
33.                                 if(!rightSet.contains(temp)){
    
34.                                         rightSet.add(temp);
    
35.                                         rightSetCount[leftSet.size()-1]=1;
    
36.                                         if(diff.contains(temp)){
    
37.                                                 diff.remove(temp);
    
38.                                         }else{
    
39.                                                 diff.add(temp);
    
40.                                         }
    
41.                                 }else{
    
42.                                         rightSetCount[rightSet.size()-1]++;
    
43.                                 }                               
    
44.                                 right++;
    
45.                         }
    
46.                         if(diff.isEmpty()&&!pairIndex.contains(leftSet.size())){
    
47.                                 pairIndex.add(leftSet.size());
    
48.                         }
    
49.                 }       
    
50.                 for(Integer i: pairIndex){
    
51.                         result+=leftSetCount[i-1]*rightSetCount[i-1];
    
52.                 }
    
53.                 return result;
    
54.         }
    
55.         public static void main(String[] args) {
    
56.                 // TODO Auto-generated method stub
    
57.                 int[][] tests={
    
58.                                 {1,1,1},
    
59.                                 {1,2, 3, 1, 2},
    
60.                                 {1,2,3,4,5}
    
61.                 };
    
62.                 for(int[] test:tests){
    
63.                         System.out.println("The number of prefix-surfix pair for array " +Arrays.toString(test)+" is "+getPrefixSurfixPair(test));
    
64.                 }
    
65.         }
    
66. 
    
67. }

复制代码

darkwowgamer 发表于 2015-10-15 08:52
"左边集合为1的数量为2" 这里还是要用hashmap做记录吧?

如果用hashmap怎么做呢？是定义map<set<int>, int>吗？能用set<int>作为map的key吗？

aiuou 发表于 2015-10-15 12:03
我想了个方法，同时从左右两边走，用两个set分别记录prefix set和surfix set。同时maintain一个diffset。如 ...

感谢set的对比思路，在你基础优化改进了一下，删去了pair这个存储结构,直接在循环的过程中求得答案

1. def function(arry):
   
2.     leftSetDiff = {}
   
3.     rightSetDiff = {}
   
4.     leftSet = {}
   
5.     rightSet = {}
   
6.     l = len(arry)
   
7.     result = 0
   
8.     leftIndex, rightIndex = 0, l - 1
   
9.     while True:
   
10.         m = 0
    
11.         leftSet[arry[leftIndex]] = 1
    
12.         while leftIndex < l and arry[leftIndex] in leftSet:
    
13.             leftIndex += 1
    
14.             m += 1
    
15.         if arry[leftIndex-1] in rightSetDiff:
    
16.             del rightSetDiff[arry[leftIndex-1]]
    
17.         else:
    
18.             leftSetDiff[arry[leftIndex-1]] = 1
    
19.         n = 0
    
20.         rightSet[arry[rightIndex]] = 1
    
21.         while rightIndex >= 0 and arry[rightIndex] in rightSet:
    
22.             rightIndex -= 1
    
23.             n += 1
    
24.         if arry[rightIndex+1] in leftSetDiff:
    
25.             del leftSetDiff[arry[rightIndex+1]]
    
26.         else:
    
27.             rightSetDiff[arry[rightIndex+1]] = 1
    
28.         if len(leftSetDiff) == 0 and len(rightSetDiff) == 0:
    
29.             result += m*n
    
30.         if rightIndex < 0 or leftIndex >= l:
    
31.             break
    
32.     return result

复制代码

ymne06 发表于 2015-10-15 12:57
如果用hashmap怎么做呢？是定义map吗？能用set作为map的key吗？

在eclipse上试了一下，好像可以。那这道题简单多了

这题不是KMP的经典应用么。。。

和POJ 2752类似

题意是给你一字符串，找你找到一个子串。使得子串即是原串的前辍，又是原串的后辍。

这和我们这道题就是一模一样了。

代码如下：

1. #include <cstdio>
   
2. #include <cstdlib>
   
3. #include <cstring>
   
4. #include <string>
   
5. #include <iostream>
   
6. #include <algorithm>
   
7. #include <vector>
   
8. 
   
9. using namespace std;
   
10. 
    
11. #define print(x) cout << x << endl
    
12. #define input(x) cin >> x
    
13. 
    
14. void get_next(const string& str, vector<int>& next) {
    
15.     int n = str.size();
    
16.     next = vector<int>(n + 1, -1);
    
17. 
    
18.     for (int pre = -1, suf = 0; pre < n && suf < n; /* pass */) {
    
19.         if (pre == -1 || str[pre] == str[suf]) {
    
20.             pre++;
    
21.             suf++;
    
22.             next[suf] = pre;
    
23.         } else {
    
24.             pre = next[pre];
    
25.         }
    
26.     }
    
27. }
    
28. 
    
29. int main() {
    
30.     string name;
    
31.     vector<int> next;
    
32. 
    
33.     while (input(name)) {
    
34.         get_next(name, next);
    
35.         int n = name.size();
    
36.         int u = next[n];
    
37.         vector<int> ans;
    
38.         ans.push_back(n);
    
39.         while (u) {
    
40.             ans.push_back(u);
    
41.             u = next[u];
    
42.         }
    
43.         reverse(ans.begin(), ans.end());
    
44.         for (int i = 0; i < ans.size(); i++) {
    
45.             if (i) {
    
46.                 printf(" ");
    
47.             }
    
48.             printf("%d", ans[i]);
    
49.         }
    
50.         puts("");
    
51.     }
    
52.     return 0;
    
53. }
    

复制代码

ImGoingSSJ 发表于 2015-10-15 06:15
当时好像用的hashset，具体怎么样有点忘了，好像不是最优解，面试官说用hashmap

哦哦，好哒好哒，谢谢楼主，明白啦～

Wizmann 发表于 2015-10-16 00:39
和POJ 2752类似

题意是给你一字符串，找你找到一个子串。使得子串即是原串的前辍，又是原串的后辍。

此面试题是要前缀字符串构成的集合与后缀字符串构成的集合相等，不是前缀、后缀字符串相等。

ymne06 发表于 2015-10-16 12:24
此面试题是要前缀字符串构成的集合与后缀字符串构成的集合相等，不是前缀、后缀字符串相等。

好吧。。。

那Hash就好咯。。。

还以为Z家这么变态直接上KMP呢，哈哈