一亩三分地论坛

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

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

Google 电面

[复制链接] |试试Instant~ |关注本帖
sigridsylvia 发表于 2015-9-4 01:39:14 | 显示全部楼层 |阅读模式

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

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

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

x
五月初约的google电面,当时leetcode还没刷到100题,立跪~

题目是找出一个整数的最短平方和,比如11=9+1+1,输出3,1,1; 12=4+4+4=9+1+1+1,输出2,2,2而不是3,1,1,1。
notturno 发表于 2015-9-4 08:53:54 | 显示全部楼层
public int sqrt(int n) {
    return (int)(Math.sqrt(n));
  }
  . more info on 1point3acres.com
  public List<Integer> MinSum(int n) {.1point3acres缃
    List<List<Integer>> res=new ArrayList<List<Integer>> ();
    List<Integer> list=new ArrayList<Integer> ();.1point3acres缃
    res.add(list); //this is for '0'
    for(int i=1;i<=n;i++) {. From 1point 3acres bbs
      int r=sqrt(i);
      for(int j=1;j<=r;j++) {
        List<Integer> pre=new ArrayList<Integer> (res.get(i-j*j));
        pre.add(j);
        if(res.size()<=i) res.add(pre);
        else if(pre.size()<res.get(i).size()) {
          res.set(i,pre);
        }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
      }
    }
    System.out.println(res);
    return res.get(n);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  }
回复 支持 1 反对 0

使用道具 举报

jiebour 发表于 2015-9-4 01:49:31 | 显示全部楼层
楼主请问一下Google是说你可以协商面试时间?由你自己来定?谢谢
回复 支持 反对

使用道具 举报

 楼主| sigridsylvia 发表于 2015-9-4 01:55:41 | 显示全部楼层
jiebour 发表于 2015-9-4 01:49
楼主请问一下Google是说你可以协商面试时间?由你自己来定?谢谢

对,当时recruiter让我在之后三周内自己定几个可以面试时间段给他安排,但基本上都是你选的时间段的第一天
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-4 03:25:43 | 显示全部楼层
sigridsylvia 发表于 2015-9-4 01:55
对,当时recruiter让我在之后三周内自己定几个可以面试时间段给他安排,但基本上都是你选的时间段的第一 ...

非常感谢!
回复 支持 反对

使用道具 举报

notturno 发表于 2015-9-4 07:48:18 | 显示全部楼层
谢谢分享

dp问题,不太容易
回复 支持 反对

使用道具 举报

say543 发表于 2015-9-7 12:39:33 | 显示全部楼层
这题不容易bug free LZ pat pat...
回复 支持 反对

使用道具 举报

blactangeri 发表于 2015-9-7 22:09:57 | 显示全部楼层
notturno 发表于 2015-9-4 08:53
public int sqrt(int n) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
    return (int)(Math.sqrt(n));
  }

Thanks for the solution but could you explain your idea a little bit?
回复 支持 反对

使用道具 举报

snklee 发表于 2015-9-8 00:56:57 | 显示全部楼层
dp solution, I think this could be optimized tho.
  1. def minSqrSum(num):
  2.     opt = [[] for i in range(0, num+1)]
  3.     sq = 1
  4.     while sq**2<num:
  5.         sq += 1
  6.     sqrs = [i**2 for i in range(1,sq)]. more info on 1point3acres.com
  7.     for i in sqrs:
  8.         opt[i] = [i]
  9.     for i in range(1, num+1):
  10.         for sq in sqrs:.鐣欏璁哄潧-涓浜-涓夊垎鍦
  11.             if i+sq>num:
  12.                 break
  13.             tmp = opt[i] + [sq]
  14.             if not opt[i+sq] or len(tmp)<len(opt[i+sq]):
  15.                 opt[i+sq] = tmp
  16.     return opt[num]
复制代码
回复 支持 反对

使用道具 举报

snklee 发表于 2015-9-8 00:57:47 | 显示全部楼层
DP solution. I think this could be optimized tho
  1. def minSqrSum(num):
  2.     opt = [[] for i in range(0, num+1)]
  3.     sq = 1
  4.     while sq**2<num:
  5.         sq += 1
  6.     sqrs = [i**2 for i in range(1,sq)]
  7.     for i in sqrs:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  8.         opt[i] = [i]
  9.     for i in range(1, num+1):
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  10.         for sq in sqrs:
  11.             if i+sq>num:
  12.                 break
  13.             tmp = opt[i] + [sq]
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  14.             if not opt[i+sq] or len(tmp)<len(opt[i+sq]):
  15.                 opt[i+sq] = tmp
  16.     return opt[num]
复制代码
回复 支持 反对

使用道具 举报

snklee 发表于 2015-9-8 00:58:07 | 显示全部楼层
  1. def minSqrSum(num):
  2.     opt = [[] for i in range(0, num+1)]
  3.     sq = 1
  4.     while sq**2<num:
  5.         sq += 1. 鍥磋鎴戜滑@1point 3 acres
  6.     sqrs = [i**2 for i in range(1,sq)].鐣欏璁哄潧-涓浜-涓夊垎鍦
  7.     for i in sqrs:. visit 1point3acres.com for more.
  8.         opt[i] = [i]
  9.     for i in range(1, num+1):.鐣欏璁哄潧-涓浜-涓夊垎鍦
  10.         for sq in sqrs:
  11.             if i+sq>num:
  12.                 break
  13.             tmp = opt[i] + [sq]
  14.             if not opt[i+sq] or len(tmp)<len(opt[i+sq]):
  15.                 opt[i+sq] = tmp
  16.     return opt[num]
复制代码
回复 支持 反对

使用道具 举报

snklee 发表于 2015-9-8 00:58:21 | 显示全部楼层
  1. def minSqrSum(num):     opt = [[] for i in range(0, num+1)]     sq = 1     while sq**2<num:         sq += 1     sqrs = [i**2 for i in range(1,sq)]     for i in sqrs:         opt[i] = [i]     for i in range(1, num+1):         for sq in sqrs:             if i+sq>num:                 break             tmp = opt[i] + [sq]             if not opt[i+sq] or len(tmp)<len(opt[i+sq]):                 opt[i+sq] = tmp     return opt[num]
复制代码
回复 支持 反对

使用道具 举报

snklee 发表于 2015-9-8 00:59:00 | 显示全部楼层
  1. def minSqrSum(num):. visit 1point3acres.com for more.
  2.     opt = [[] for i in range(0, num+1)]
  3.     sq = 1
  4.     while sq**2<num:. 1point 3acres 璁哄潧
  5.         sq += 1
  6.     sqrs = [i**2 for i in range(1,sq)]. from: 1point3acres.com/bbs
  7.     for i in sqrs:
  8.         opt[i] = [i]
  9.     for i in range(1, num+1):
  10.         for sq in sqrs:
  11.             if i+sq>num:
    . from: 1point3acres.com/bbs
  12.                 break
  13.             tmp = opt[i] + [sq]
  14.             if not opt[i+sq] or len(tmp)<len(opt[i+sq]):. more info on 1point3acres.com
  15.                 opt[i+sq] = tmp
  16.     return opt[num]
复制代码
回复 支持 反对

使用道具 举报

rb131108 发表于 2015-9-10 08:29:56 | 显示全部楼层
感觉可以转换成dp找钱的题

dp[n]=min(dp[n-1^2], dp[n-2^2]...dp[n-k^2])+1     k<=sqrt(n)

回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-9-23 08:22:56 | 显示全部楼层
可以从1到n计算最少组合数,复杂度是n的3/2次方;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
利用四平方和定理,可以提升到O(n);
不过貌似都是伪多项式时间的
回复 支持 反对

使用道具 举报

xnature 发表于 2015-9-23 08:59:57 | 显示全部楼层
用四平方和定理明显overkill,只要能正确写出dp解法即可
回复 支持 反对

使用道具 举报

xnature 发表于 2015-9-23 09:00:13 | 显示全部楼层
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 03:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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