楼主: knight0clk
跳转到指定楼层
上一主题 下一主题
收起左侧

Google Internship电面

🔗
 楼主| knight0clk 2016-11-6 22:17:02 | 只看该作者
全局:
foolish 发表于 2016-11-6 22:15
构造辅助数组的时间复杂度应该是 O(n)? 构造的时候时间复杂度是 O(logk), 但是得到结果的时候应该是O(n),  ...

构造辅助数组时间是nlogk
回复

使用道具 举报

🔗
foolish 2016-11-6 22:20:24 | 只看该作者
全局:
knight0clk 发表于 2016-11-6 22:17
构造辅助数组时间是nlogk

是的,我傻逼了。。。
话说面试官对于这种做法有啥表态不?
回复

使用道具 举报

🔗
 楼主| knight0clk 2016-11-7 00:04:40 | 只看该作者
全局:
foolish 发表于 2016-11-6 22:20
是的,我傻逼了。。。
话说面试官对于这种做法有啥表态不?

没啥表态,就说那你写吧
回复

使用道具 举报

🔗
坨坨 2016-11-7 02:24:52 | 只看该作者
全局:
第二题楼主的space complexity应该也是nlogk?
回复

使用道具 举报

🔗
youngxie 2016-11-14 04:49:06 | 只看该作者
全局:
我觉得这也可以用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 估计会更快。
回复

使用道具 举报

🔗
kiru 2016-11-15 00:08:40 | 只看该作者
全局:
请问lz, 电面之前有oa么
回复

使用道具 举报

🔗
 楼主| knight0clk 2016-11-15 00:31:39 | 只看该作者
全局:
kiru 发表于 2016-11-15 00:08
请问lz, 电面之前有oa么

没有,直接点面
回复

使用道具 举报

🔗
鼓頔娜夫 2016-11-15 06:39:46 | 只看该作者
全局:
LZ 有信儿了吗?
回复

使用道具 举报

🔗
wangdi561 2016-12-15 11:26:04 | 只看该作者
全局:
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?!
回复

使用道具 举报

🔗
pwwpche 2016-12-15 11:48:57 | 只看该作者
全局:
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)内算出来
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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