google phone interview SETI

面了google SEIT
phone interview

没有闲聊
Pascal Triangle
给定坐标i j 输出value
1,
1,1
1,2,1
1,3,3,1
1,4,6,4,1

given i=4

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

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

容 (2017-7-1 09:10):
又想了一下 recursion的复杂度也是O(N^2) 所以还是不知道interviewer想要的答案是什么

楼主，用二项式计算表达第 i row，
C(i,0), C(i,1), .., C(i,j),.. C(i,i)
所以C(i,j) = C(i,j-1) * (i-j+1)/j
是不是就递归求出i行j列的元素了，time 是O（n），求教

static long max = 1000;
private static Map<Long, Long> map = new HashMap<>();
public static void main(String[] args) {
    System.out.println(f(50, 8));
}

static long f(long x, long y) {
    if (y > x) {
        return -1;
    }
    if (y == 0 || x == y) {
        return 1;
    }
    if (map.containsKey(x * max + y)) {
        return map.get(x * max + y);
    }
    long value = f(x - 1, y - 1) + f(x - 1, y);
    map.put(x * max + y, value);
    return value;
}

1.用二项式是最快 O(N) O(1)
2.DP 进一步优化（每row只算必须的，红色部分） O(N^2) O(N)
3.DP 只存一维数组 O(N^2) O(N) 或者 trade off 用 recursion+memory O(N^2) 这个只算红色部分 但是space O(N^2)
4.DP 存在2维数组 O(N^2) O(N^2)
5.recursion 无memory O(2^N）O(N)

一开始的方法是#3 DP。interviewer应该是要recursion的trade off的方法。

补充内容 (2017-7-7 13:20):
#3 recursion+memory space 应该是O(N)
所以比DP要好 不是trade off

二项式定理 可以O1解决

weitongg 发表于 2017-7-1 09:12
二项式定理 可以O1解决

确实 value = i！/j！（i-j）！ 不过感觉可能interviewer是在找一个介于这个和O(N^2)之间的方法吧。这个数学确实早忘了

请问楼主谷歌又开始招人了？

优化是用滚动数组

forteller 发表于 2017-7-2 13:17
优化是用滚动数组

什么意思？楼主已经说了space O(n)，不是已经用了滚动数组吗？

求问楼主，Recursion复杂度O(n^2)是如何计算出来的？想不太懂

knight0clk 发表于 2017-7-2 21:58
什么意思？楼主已经说了space O(n)，不是已经用了滚动数组吗？

lz的N=i*j  我的N = j。另外时间N^2就是两个for套起来。

补充内容 (2017-7-4 07:26):
我说错了。忽略我。没看到