Google Internship电面

foolish 发表于 2016-11-6 22:15
构造辅助数组的时间复杂度应该是 O(n)? 构造的时候时间复杂度是 O(logk), 但是得到结果的时候应该是O(n),  ...

构造辅助数组时间是nlogk

knight0clk 发表于 2016-11-6 22:17
构造辅助数组时间是nlogk

是的，我傻逼了。。。
话说面试官对于这种做法有啥表态不？

foolish 发表于 2016-11-6 22:20
是的，我傻逼了。。。
话说面试官对于这种做法有啥表态不？

没啥表态，就说那你写吧

第二题楼主的space complexity应该也是nlogk?

我觉得这也可以用TOP-DOWN 的backtracking + memoization
bottom-up 的dp （如下），感觉计算了很多多余的值
dp[i][k] = a[i]*…*a[i+k-1]
dp[i][k] = dp[i][k/2] * dp[i+k/2][k-k/2]
top-down 估计会更快。

请问lz, 电面之前有oa么

kiru 发表于 2016-11-15 00:08
请问lz, 电面之前有oa么

没有，直接点面

LZ 有信儿了吗？

knight0clk 发表于 2016-11-6 21:12
好吧，我在统一说一下，最初，我们有A1=[A,B,C,D,E,F,G,H,I,J], 根据A1，可以有A2=[AB, BC, CD, DE, EF,  ...

类似 segment tree?!

1  -> 1 2 3 4
2  ->   2 3 4 | 5
3  ->      3 4 | 5 6
4  ->         4 | 5 6 7

这样看还是用第一题product of array except self 的思路，对于每一组k个数都能在O(k) 时间内算出来，那么所有n个数也能在O(n)内算出来