《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 2042|回复: 11
收起左侧

wepay 第一轮电面

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

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

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

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

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


大家有什么好的想法嘛? 真心求教。。 还要好好努力吖~ 一面试脑子就卡壳。。。。

评分

1

查看全部评分

nemoleoliu 发表于 2015-12-6 12:44:15 | 显示全部楼层
本帖最后由 nemoleoliu 于 2015-12-6 12:46 编辑

第二道题
如果一个自数组和是三的倍数 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)
回复 支持 3 反对 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):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
!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
真心求教>.< 我是这么做的 但是感觉面试官不满意  估计是要跪了@@。。
求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]这个不连续就不是么?
.1point3acres缃
补充内容 (2015-12-6 10:56):
还有[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 | 显示全部楼层
面你的人叫啥名字呢
回复 支持 反对

使用道具 举报

1451427216 发表于 2017-9-5 10:36:52 | 显示全部楼层
第二题O(n)的解法还是很不错的。我拓展了下,通过了geeksforgeeks 的测试。代码如下
  1. public int subCount(int[]nums,int k){
  2.         int n = nums.length;
  3.         int []cnt=new int[k];
  4.         int cntNum=0,sum=0;
  5.         for(int i=0;i<n;++i){
  6.             sum+=nums[i];
  7.             int rem = sum%k;
  8.             if(rem==0){
  9.                 cntNum+=++cnt[0];
  10.             }else{
  11.                 cntNum+=cnt[rem];
  12.                 cnt[rem]++;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  13.             }
  14.         }
  15.         return cntNum;
  16.     }
复制代码

补充内容 (2017-9-5 10:40):
解释下第九行,它代表index从0开始的subarray
回复 支持 反对

使用道具 举报

wantyoulee 发表于 2017-9-19 12:14:25 | 显示全部楼层
1451427216 发表于 2017-9-5 10:36
第二题O(n)的解法还是很不错的。我拓展了下,通过了geeksforgeeks 的测试。代码如下

补充内容 (2017-9-5 1 ...

-google 1point3acres机智机智
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-25 17:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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