一亩三分地论坛

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

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

10.8Bloomberg 电面

[复制链接] |试试Instant~ |关注本帖
tltzhsajsdr 发表于 2015-10-9 02:20:49 | 显示全部楼层 |阅读模式

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

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

x
bloomberg,论坛里找前辈内推的,10.8电面,电面就是2-sum,但是有变形,我想简单了,本来20分钟应该做出来的问题,做到第50分钟才做出来,法克。
打电话来的是一位女性,说话很温柔,也一直提示提示,在bb工作六年了,然后先让我自己介绍我的project,接着就是题,我觉得跟她说话特别舒服,只是答题答的不太好,真是的。
题目是,2-sum,输出有效的number pair的对数,输入的数组里有重复,输出的不能有重复,假设给定sum是9,(3,6)和(6,3)是一样的,或者给定sum是12,(6,6)只算一次只要一个


例如输入(1,1,1,48,22),sum = 49,返回2
输入(3,6,1,2,3)sum = 9,返回 1. 1point3acres.com/bbs
输入(3,3,3,3,3,3,6) sum = 6,返回1

我说有两种方法,先排序然后两个指针,或者hashmap,让我用hashmap。
然后麻蛋想简单了,一直在那做做做调试调试调试,后来又用一个set存现在的unique,直到第50分钟才过全部test。哎,做过的题稍微变形一下,就傻了一样,得做很久才能做对。
不知道能不能过了。。。
-google 1point3acres


补充内容 (2015-10-9 02:26):
忽略中间我给的例子,不太对
应该是,输入(1,1,1,48,22),sum = 49,返回1
输入(3,6,1,2,3)sum = 9,返回 1
输入(3,3,3,3,3,3,6) sum = 6,返回1

补充内容 (2015-11-10 15:19):
跪。move on

本帖被以下淘专辑推荐:

smile~~~~ 发表于 2015-10-9 02:31:20 | 显示全部楼层
祝拿到onsite!请问内推了之后还需要自己在网上申请吗?你是内推多久后收到电面的?
回复 支持 反对

使用道具 举报

 楼主| tltzhsajsdr 发表于 2015-10-9 02:40:49 | 显示全部楼层
不对不对,题意比这个难,我现在自己都搞混了,是每个数都可以用一次,比如(1.1.1.48.22)这个,应该返回3,而不是1
回复 支持 反对

使用道具 举报

 楼主| tltzhsajsdr 发表于 2015-10-9 02:42:10 | 显示全部楼层
smile~~~~ 发表于 2015-10-9 02:31
祝拿到onsite!请问内推了之后还需要自己在网上申请吗?你是内推多久后收到电面的?

内推后大概两周吧,是要网申的
回复 支持 反对

使用道具 举报

MCwong 发表于 2015-10-9 02:53:09 | 显示全部楼层
所以test case是不是:
输入(1,1,1,48,22),sum = 49,返回3
输入(3,6,1,2,3)sum = 9,返回 2
输入(3,3,3,3,3,3,6) sum = 6,返回15
回复 支持 反对

使用道具 举报

 楼主| tltzhsajsdr 发表于 2015-10-9 03:06:21 | 显示全部楼层
MCwong 发表于 2015-10-9 02:53
所以test case是不是:
输入(1,1,1,48,22),sum = 49,返回3
输入(3,6,1,2,3)sum = 9,返回 2
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
嗯嗯,应该是这样的。我是越做越发现这个题比普通的 2sum难,最后就花了很久才通过test
回复 支持 反对

使用道具 举报

wildcat 发表于 2015-10-10 03:25:47 | 显示全部楼层
tltzhsajsdr 发表于 2015-10-9 02:40
不对不对,题意比这个难,我现在自己都搞混了,是每个数都可以用一次,比如(1.1.1.48.22)这个,应该返回3, ...

感觉还是不对啊,如果每个数只能用一次,那你给的这个例子里48用了3次了。
如果是每个数只能用一次,那用一个boolean array存下用过数的状态就可以
回复 支持 反对

使用道具 举报

arwintang 发表于 2015-10-10 07:58:57 | 显示全部楼层
请问lz内推后多久拿到电面的?

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

lianlu 发表于 2015-10-18 05:44:20 | 显示全部楼层
我觉得可以表述为返回元素index pair的个数。比如(3,3,3,6), sum = 6, 则答案为{{0,1},{0,2},{1,2}}.length()。
回复 支持 反对

使用道具 举报

lianlu 发表于 2015-10-18 05:44:47 | 显示全部楼层
  1. public static int getSumPair(int []A, int sum)
  2.         {. from: 1point3acres.com/bbs
  3.                 Map<Integer,Integer> map = new HashMap(); // map from number to numbers
  4.                 for (int a : A)
  5.                         map.put(a, map.get(a) == null ? 1 : map.get(a) + 1);
  6.                 int res = 0;
  7.                 for (int x : map.keySet())
  8.                 {
  9.                         if (map.get(sum - x) != null)
  10.                         {
  11.                                 if (sum - x != x)
  12.                                         res += (map.get(x) * map.get(sum - x));.鏈枃鍘熷垱鑷1point3acres璁哄潧
  13.                                 else
  14.                                         res += (map.get(x) * (map.get(sum - x) - 1));
  15.                         }
  16.                 }. from: 1point3acres.com/bbs
  17.                 return res/2;


  18.         }
复制代码

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

lyj87372517 发表于 2015-10-26 07:08:12 | 显示全部楼层
  1.         public int addtwo(int[] nums, int target){
  2.                 Arrays.sort(nums);
  3.                 int count=0;
  4.                 for(int i=0; i<nums.length-1; i++){
  5.                         for(int j=i+1; j<nums.length; j++){
  6.                                 if(nums[i]+nums[j]==target){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  7.                                         count++;
  8.                                 }
  9.                         }
  10.                 }
  11.                 return count;
  12.         }
复制代码
感觉不难啊?是我没看懂题吗?
回复 支持 反对

使用道具 举报

 楼主| tltzhsajsdr 发表于 2015-11-10 15:05:04 | 显示全部楼层

恩恩,这个做法是对的。又刷了一个月的题,现在比以前提高了许多,可以当时脑子转的不够快。
回复 支持 反对

使用道具 举报

 楼主| tltzhsajsdr 发表于 2015-11-10 15:05:24 | 显示全部楼层
lyj87372517 发表于 2015-10-26 07:08
感觉不难啊?是我没看懂题吗?

这个做法是对的,但是她要求我用O(N)的方法
回复 支持 反对

使用道具 举报

 楼主| tltzhsajsdr 发表于 2015-11-10 15:10:34 | 显示全部楼层
tltzhsajsdr 发表于 2015-11-10 15:05
这个做法是对的,但是她要求我用O(N)的方法

也不是她要求我用O(N),是我说hashmap可解,她就要求我用hashmap解,她说希望可以O(N),但是我现在已经知道这个题的最坏情况的下限是O(N^2),假设数组全是1,n个1,target是2,光形成所有组合就有n(n-1)/2的复杂度,所以任何算法都无法快过O(N^2).
我现在觉得这题最好的方法应该是,解释清楚为什么下限是O(N^2),然后就用你给的方法就可以。
回复 支持 反对

使用道具 举报

followdream 发表于 2015-11-11 11:14:56 | 显示全部楼层
tltzhsajsdr 发表于 2015-11-10 15:10. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
也不是她要求我用O(N),是我说hashmap可解,她就要求我用hashmap解,她说希望可以O(N),但是我现在已经知 ...

可是你参见10楼的答案,就是O(n)的。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 02:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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