一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1027|回复: 8
收起左侧

Google 电面面经 10-13-2015

[复制链接] |试试Instant~ |关注本帖
ab380765597 发表于 2015-10-15 00:40:04 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
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很像,不同的地方在于求sum,而不是单个放入
private static int[] subset(int[] nums){
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if(nums==null||nums.length==0){
      return null;
    }
    List<Integer> path = new ArrayList<Integer>();
    helper(res, path, 0, nums);
    Set<Integer> sumList = new HashSet<Integer>();
    for(int i=0; i<res.size(); i++){
      int sum =0;
      for(int j=0; j<res.get(i).size();j++){
        sum = sum+res.get(i).get(j);
        
      }
      if(!sumList.contains(sum)){
        sumList.add(sum);
      }
      
    }
    int counter = 0;
    int size = sumList.size();
    int[] result = new int[size];
    for(int input: sumList){
      result[counter] = input;
      counter++;
    }
    return result;
  }
  private static void helper(List<List<Integer>> res, List<Integer> path, int pos, int[] nums){
      res.add(new ArrayList<Integer>(path));
    for(int i=pos; i<nums.length; i++){
      path.add(nums);
      helper(res, path, i+1, nums);
      path.remove(path.size()-1);
    }
   
  }
. 鍥磋鎴戜滑@1point 3 acres
想问下大家有没有优化方法的,貌似我的空间复杂度有点高,顺便求米,谢谢!

评分

2

查看全部评分

本帖被以下淘专辑推荐:

jml901031 发表于 2015-10-15 03:16:02 | 显示全部楼层
楼组 被坑了啊。。

鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2015-10-15 04:08):
如果没有负数 应该是dp。。
回复 支持 反对

使用道具 举报

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

public class SubSum {. visit 1point3acres.com for more.
. from: 1point3acres.com/bbs
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                int[] num = {1,2,4,4,8,12};. visit 1point3acres.com for more.
                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");
                }
        }. more info on 1point3acres.com
       
        private static void subSumHelper(int pos,
                                                                        Set<Integer> result,
                                                                        List<Integer> list,
                                                                        int[] num) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                if (!list.isEmpty()) {. from: 1point3acres.com/bbs
                        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);. 1point 3acres 璁哄潧
                }
        }
       
        private static int listSumHelper(List<Integer> list) {. From 1point 3acres bbs
                if (list == null) {. 1point 3acres 璁哄潧
                        throw new NullPointerException();. Waral 鍗氬鏈夋洿澶氭枃绔,
                }
                int sum = 0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                for (Integer ele : list) {
                        sum += ele;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                }
               
                return sum;
        }

}
回复 支持 反对

使用道具 举报

cffls 发表于 2015-10-16 00:40:38 | 显示全部楼层
  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].鏈枃鍘熷垱鑷1point3acres璁哄潧
  11.     sumList = [key for key in record]
  12.     return sumList
复制代码
回复 支持 反对

使用道具 举报

cc11328 发表于 2015-10-16 03:37:16 | 显示全部楼层
是用回溯做么
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_set>
  4. using namespace std;
  5. int countSum(int start, int end, const vector<int> &nums) {
  6.     int sum = 0;
  7.     for(int i = start ; i <= end; i++) {. 1point 3acres 璁哄潧
  8.         sum += nums[i];.鏈枃鍘熷垱鑷1point3acres璁哄潧
  9.     }
  10.     return sum;
  11. }
  12. void backTracking(int start, int end, vector<int> &res, unordered_set<int> &record, const vector<int> &nums){
  13.     if(start == nums.size()) return;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  14.     int sum = countSum(start, end, nums);. 1point 3acres 璁哄潧
  15.     if(record.find(sum) == record.end()){
  16.         record.insert(sum);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  17.         res.push_back(sum);
  18.     }. more info on 1point3acres.com
  19.     if(end == nums.size() - 1) backTracking(start + 1, start + 1, res, record, nums);
  20.     else backTracking(start, end + 1, res, record, nums);. 鍥磋鎴戜滑@1point 3 acres
  21. }
  22. vector<int> outPut(const vector<int> &nums) {
  23.     vector<int> res;. From 1point 3acres bbs
  24.     if(nums.size() == 0) return res;
  25.     unordered_set<int> record;
  26.     backTracking(0,0,res,record,nums);
  27.     return res;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  28. }
  29. int main() {
  30.         vector<int> nums = {1,2,4,4,8,12};
  31.         vector<int> res = outPut(nums);
  32.         for(int i : res). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  33.         cout<<i<<" ";
  34.         return 0;
  35. }
复制代码
output:1 3 7 11 19 31 2 6 10 18 30 4 8 16 28 12 24 20

补充内容 (2015-10-16 03:46):
不对 我这个做的事subarray的了 跟楼主的意思还不一样
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-10-16 03:50:51 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
  1. def subsum(L):.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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])
复制代码
回复 支持 反对

使用道具 举报

cc11328 发表于 2015-10-16 04:13:31 | 显示全部楼层
这把应该没问题了
  1. #include <iostream>
  2. #include <vector>. 1point 3acres 璁哄潧
  3. #include <unordered_set>
  4. using namespace std;
  5. int getSum(const vector<int> &nums){
  6.     int sum = 0;
  7.     for(int i : nums) sum += i;
  8.     return sum; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  9. }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  10. void backTracking(int index,vector<int> &temp,vector<int> &res,vector<int> &nums,unordered_set<int> &record){
  11.         if(!temp.empty()) {
  12.             int sum = getSum(temp);
  13.             if(record.find(sum) == record.end()) {
  14.                 record.insert(sum);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  15.                 res.push_back(sum);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  16.             }
  17.         }
  18.         for(int i = index;i < nums.size();i++){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  19.             temp.push_back(nums[i]);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  20.             backTracking(i+1,temp,res,nums,record);
  21.             temp.pop_back();
  22.         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  23.     }
  24. vector<int> all_Sum(vector<int>& nums) {
  25.         vector<int> res;
  26.         vector<int> temp;
  27.         unordered_set<int> record;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  28.         backTracking(0,temp,res,nums,record);
  29.         return res;
  30.     }
  31.    
  32. int main() {
  33.         vector<int> nums = {1,2,4,4,8,12};. visit 1point3acres.com for more.
  34.     vector<int> res = all_Sum(nums);
  35.     for(int i : res)
  36.     cout<<i<<" ";
  37.     return 0;
  38. }
复制代码
回复 支持 反对

使用道具 举报

tangvictor 发表于 2015-10-16 08:25:13 | 显示全部楼层
贴个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. def helper(A, line, res):
  11.         if len(line) > 0:
  12.                 res.add(sum(line)).鐣欏璁哄潧-涓浜-涓夊垎鍦
  13. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  14.         for i in range(len(A)):
  15.                 helper(A[i+1:], line + [A[i]], res)
复制代码
回复 支持 反对

使用道具 举报

jml901031 发表于 2015-10-16 09:00:45 | 显示全部楼层
yuanb10 发表于 2015-10-15 23:11
不知道楼上为什么觉得这是一道dp题目。可以用subsets的方法解出来。

public class SubSum {
-google 1point3acres

没有负数的情况 就是dp    背包变种 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
public class DPsolution {

    /**
     * @param args the command line arguments
     */. from: 1point3acres.com/bbs
    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++)
         {. From 1point 3acres bbs
             for(int j=sum;j>=nums;j--)-google 1point3acres
             {
                 if(dp[j]==1) continue;
                 if(dp[j-nums]==1)dp[j]=1;
             }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
         }
         ArrayList<Integer> result=new ArrayList<Integer>();
         for(int i=1;i<=sum;i++)
         {
             if(dp==1)
             {
                 result.add(i);
             }
         }
         return result; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
     }
    public static void main(String[] args) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
        // TODO code application logic here
        DPsolution xx=new DPsolution();
        int nums[]={2,2,2};
        ArrayList<Integer> bb=xx.getallnum(nums);
. From 1point 3acres bbs        for(Integer ss:bb).1point3acres缃
        {
            System.out.println(ss);-google 1point3acres
        }
    }
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
}
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 04:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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