一亩三分地论坛

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

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

wepay 第一轮电面

[复制链接] |试试Instant~ |关注本帖
何打发123 发表于 2015-12-5 02:01:13 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@wepay - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
1. 给数组 求平均数
2. 给数组 求  和是 3的倍数的所有可能的子列(连续) 总数
. from: 1point3acres.com/bbs

大家有什么好的想法嘛? 真心求教。。 还要好好努力吖~ 一面试脑子就卡壳。。。。
nemoleoliu 发表于 2015-12-6 12:44:15 | 显示全部楼层
本帖最后由 nemoleoliu 于 2015-12-6 12:46 编辑

第二道题 .1point3acres缃
如果一个自数组和是三的倍数 sum[i...j] = sum[0...j]-sum[0...i-1]  那么 sum[0...i-1] 和 sum[0...j]应该是对于3同余的 所以可以用三个count0 count1 count2 分别代表除以3余0 1 2 的个数,然后 遍历一遍 当计算从0到当前的和 假如余2 那么 它可以和他前面所有的余2的sum分别组成一个unique的子数组 所以result+=count2 最后得出结果 O(n)
回复 支持 1 反对 0

使用道具 举报

348210207 发表于 2015-12-5 02:44:07 | 显示全部楼层
第一个不说了,第二个我抛砖引玉,应该是二维数组做动规吧?先把i,j区间是不是3的倍数存储到p[j],然后i,j+1只要保证(p[j]&&A[j]%3)即可。
不过这种题一般都会有个o(n)吧。。。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2015-12-5 02:44):. 1point 3acres 璁哄潧
!A[j]%3.......笔误。。。。
回复 支持 反对

使用道具 举报

 楼主| 何打发123 发表于 2015-12-5 02:53:03 | 显示全部楼层
348210207 发表于 2015-12-5 02:44
第一个不说了,第二个我抛砖引玉,应该是二维数组做动规吧?先把i,j区间是不是3的倍数存储到p[j],然后i, ...

第一题不用考虑overflow吗。。。。。。。
第二题新建一个数组 把到这个数之前的和存一下 应该是要用n^2的。。
回复 支持 反对

使用道具 举报

 楼主| 何打发123 发表于 2015-12-5 02:59:25 | 显示全部楼层
真心求教>.< 我是这么做的 但是感觉面试官不满意  估计是要跪了@@。。
求rp~~~
回复 支持 反对

使用道具 举报

yifeichan 发表于 2015-12-6 02:32:37 | 显示全部楼层
何打发123 发表于 2015-12-5 02:59. from: 1point3acres.com/bbs
真心求教>.< 我是这么做的 但是感觉面试官不满意  估计是要跪了@@。。
求rp~~~

dp应该也是O(n2)时间,面试官是觉得时间复杂度高了么?
回复 支持 反对

使用道具 举报

 楼主| 何打发123 发表于 2015-12-6 02:36:29 | 显示全部楼层
yifeichan 发表于 2015-12-6 02:32
dp应该也是O(n2)时间,面试官是觉得时间复杂度高了么?

不知道>.< 感觉面试官冷淡淡的~ 估计要悲剧啦T T 哎~ 你加油~
回复 支持 反对

使用道具 举报

willscan 发表于 2015-12-6 09:14:54 | 显示全部楼层
什么是 “所有可能的子列(连续) 总数 ”, 比如 [1,2,3,5] 那么是[1,2],[1,2,3] 符合题意?所以是两个? [1,5]这个不连续就不是么?

补充内容 (2015-12-6 10:56):. from: 1point3acres.com/bbs
还有[3],所以是[1,2][1,2,3][3],三个么
回复 支持 反对

使用道具 举报

 楼主| 何打发123 发表于 2015-12-6 10:39:52 | 显示全部楼层
willscan 发表于 2015-12-6 09:14
什么是 “所有可能的子列(连续) 总数 ”, 比如 [1,2,3,5] 那么是[1,2],[1,2,3] 符合题意?所以是两个?  ...

[1,2] [3]   就是subarray 不是subsequence
回复 支持 反对

使用道具 举报

willscan 发表于 2015-12-6 11:05:13 | 显示全部楼层
面你的人叫啥名字呢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 06:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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