Google 电面面经 10-13-2015

Google 面经：

昨天中午接到的电面，面试官是工作了四年的印度小哥， 口语不错，除了极个别单词听不懂外，其他都ok

[size=10.5000pt]1）给一段代码，修改其中的错误。注意数组长度不溢出，还有for loop 边界问题

2）给一个input integer array： [1,2,4,4,8,12], 得到所有由+可能得到的数组

outPut：[1,2,4,8,12,3,5,9,13,6,10,14,16,7,11......,31] 不能重复

和leetcode里面subset很

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

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

rrayList<Integer>(path));

    for(int i=pos; i<nums.length; i++){

      path.add(nums[i]);

      helper(res, path, i+1, nums);

      path.remove(path.size()-1);

    }

   

  }

想问下大家有没有优化方法的，貌似我的空间复杂度有点高，顺便求米，谢谢！

楼组 被坑了啊。。


补充内容 (2015-10-15 04:08):
如果没有负数 应该是dp。。

不知道楼上为什么觉得这是一道dp题目。可以用subsets的方法解出来。

public class SubSum {

        public static void main(String[] args) {
                // TODO Auto-generated method stub
                int[] num = {1,2,4,4,8,12};
                Set<Integer> result = new HashSet<Integer>();
                List<Integer> list = new ArrayList<Integer>();
                Arrays.sort(num);
               
                subSumHelper(0, result, list, num);
               
                for (int n : result) {
                        System.out.print(n + "\t");
                }
        }
       
        private static void subSumHelper(int pos,
                                                                        Set<Integer> result,
                                                                        List<Integer> list,
                                                                        int[] num) {
                if (!list.isEmpty()) {
                        int sum = listSumHelper(new ArrayList(list));
                        result.add(sum);
                        System.out.println(sum + "\t" + list);
                }
               
                for (int i = pos; i < num.length; i++) {
                        list.add(num[i]);
                        subSumHelper(i + 1, result, list, num);
                        list.remove(list.size() - 1);
                }
        }
       
        private static int listSumHelper(List<Integer> list) {
                if (list == null) {
                        throw new NullPointerException();
                }
                int sum = 0;
                for (Integer ele : list) {
                        sum += ele;
                }
               
                return sum;
        }

}

1. def findSums(list):
   
2.     record = {x:[i] for i,x in enumerate(list)}
   
3.     for i in xrange(1,len(list)):
   
4.         newRecord = {}
   
5.         for key in record.keys():
   
6.             for index,num in enumerate(list):
   
7.                 newNum = key + num
   
8.                 if newNum not in record and newNum not in newRecord and index not in record[key]:
   
9.                     newRecord[newNum] = record[key]+[index]
   
10.                     record[newNum] = newRecord[newNum]
    
11.     sumList = [key for key in record]
    
12.     return sumList

复制代码

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

1. def subsum(L):
   
2.     def dfs(L):
   
3.         if len(L)==0: return set([0])
   
4.         h,rest = L[0],L[1:]
   
5.         return set([x+y for x in dfs(rest) for y in [0,h]])
   
6.     return list(dfs(L))
   
7. print subsum([1,2,4,4,8,12])

复制代码

贴个python的，如果有错误请告诉，多谢！

1. def subsetsSum(A):
   
2.         # corner case
   
3.         if A == None or len(A) == 0:
   
4.                 return []
   
5.        
   
6.         A.sort()
   
7.         res = set()
   
8.         helper(A, [], res)
   
9.         return list(res)
   
10. 
    
11. def helper(A, line, res):
    
12.         if len(line) > 0:
    
13.                 res.add(sum(line))
    
14. 
    
15.         for i in range(len(A)):
    
16.                 helper(A[i+1:], line + [A[i]], res)

复制代码

yuanb10 发表于 2015-10-15 23:11
不知道楼上为什么觉得这是一道dp题目。可以用subsets的方法解出来。

public class SubSum {

没有负数的情况 就是dp    背包变种
public class DPsolution {

    /**
     * @param args the command line arguments
     */
    public ArrayList<Integer> getallnum(int []nums)
    {
        int sum=0;
        for(int aa:nums)
        {
            sum+=aa;
        }
        int []dp=new int[sum+1];
        dp[0]=1;
         for(int i=0;i<nums.length;i++)
         {
             for(int j=sum;j>=nums[i];j--)
             {
                 if(dp[j]==1) continue;
                 if(dp[j-nums[i]]==1)dp[j]=1;
             }
         }
         ArrayList<Integer> result=new ArrayList<Integer>();
         for(int i=1;i<=sum;i++)
         {
             if(dp[i]==1)
             {
                 result.add(i);
             }
         }
         return result;
     }
    public static void main(String[] args) {
        // TODO code application logic here
        DPsolution xx=new DPsolution();
        int nums[]={2,2,2};
        ArrayList<Integer> bb=xx.getallnum(nums);
        for(Integer ss:bb)
        {
            System.out.println(ss);
        }
    }
   
}