925 Zenefits 电面【一亩三分地论坛面经版】 - Powered by Discuz!

925 Zenefits 电面【一亩三分地论坛面经版】 - Powered by Discuz!
arr = [1,2, 3, 1, 2]. From 1point 3acres bbs
Prefixes of the array: [1], [1, 2], [1,2, 3], [1,2,3,1], [1,2,3,1,2]
Suffixes of the array: [2], [1, 2], [3,1,2], [2,3,1,2], [1,2,3,1,2]

prefix [1,2, 3, 1] == {1, 2, 3}.
suffix [1, 2, 3, 1, 2] == {1,2,3}

[1, 2, 3, 1] == [1, 2, 3, 1, 2]. 

Q.How many prefix-suffix pairs (P, S) are there such that set(P) == set(S)?. 

def function(arry):
    leftSetDiff = {}
    rightSetDiff = {}
    leftSet = {}.
    rightSet = {}.
    l = len(arry)
    result = 0
    leftIndex, rightIndex = 0, l - 1
    while True:
        m = 0
        leftSet[arry[leftIndex]] = 1
        while leftIndex < l and arry[leftIndex] in leftSet:
            leftIndex += 1
            m += 1.
        if arry[leftIndex-1] in rightSetDiff:
            del rightSetDiff[arry[leftIndex-1]]
        else:
            leftSetDiff[arry[leftIndex-1]] = 1.
        n = 0
        rightSet[arry[rightIndex]] = 1
        while rightIndex >= 0 and arry[rightIndex] in rightSet:
            rightIndex -= 1
            n += 1-google 1point3acres
        if arry[rightIndex+1] in leftSetDiff:
            del leftSetDiff[arry[rightIndex+1]]
        else:
            rightSetDiff[arry[rightIndex+1]] = 1
        if len(leftSetDiff) == 0 and len(rightSetDiff) == 0:
            result += m*n
        if rightIndex < 0 or leftIndex >= l:
            break.

    return result

我想了个方法，同时从左右两边走，用两个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）

        public static long getPrefixSurfixPair(int [] a){
                if(a==null||a.length==0) return 0;
                int[] leftSetCount = new int[a.length];
                int[] rightSetCount = new int[a.length];
                int left=0,right=0;
                long result=0;
                HashSet<Integer> diff = new HashSet<Integer> ();
                HashSet<Integer> leftSet = new HashSet<Integer> ();
                HashSet<Integer> rightSet = new HashSet<Integer> ();
                HashSet<Integer> pairIndex = new HashSet<Integer> ();-google 1point3acres
                while(left<a.length||right<a.length){
                        int temp=0;
                        if(leftSet.size()<=rightSet.size()&&left<a.length){
                                temp=a[left];
                                if(!leftSet.contains(temp)){
                                        leftSet.add(temp);
                                        leftSetCount[leftSet.size()-1]=1;-google 1point3acres
                                        if(diff.contains(temp)){
                                                diff.remove(temp);
                                        }else{
                                                diff.add(temp);
                                        }                      
                                }else{
                                        leftSetCount[leftSet.size()-1]++;      
                                }  
                                left++;
                        }else {
                                temp=a[a.length-1-right];
                                if(!rightSet.contains(temp)){
                                        rightSet.add(temp);
                                        rightSetCount[leftSet.size()-1]=1;
                                        if(diff.contains(temp)){
                                                diff.remove(temp);
                                        }else{
                                                diff.add(temp);
                                        }
                                }else{
                                        rightSetCount[rightSet.size()-1]++;
                                }
                                right++;
                        }
                        if(diff.isEmpty()&&!pairIndex.contains(leftSet.size())){
                                pairIndex.add(leftSet.size());
                        }
                }      
                for(Integer i: pairIndex){
                        result+=leftSetCount[i-1]*rightSetCount[i-1];
                }
                return result;
        }
        public static void main(String[] args) {
                // TODO Auto-generated method
                int[][] tests={
                                {1,1,1},
                                {1,2, 3, 1, 2},
                                {1,2,3,4,5}
                };
                for(int[] test:tests){
                        System.out.println("The number of prefix-surfix pair for array " +Arrays.toString(test)+" is "+getPrefixSurfixPair(test));
                }
        }
Read full article from 925 Zenefits 电面【一亩三分地论坛面经版】 - Powered by Discuz!