一亩三分地论坛

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

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

狗狗惨烈电面

[复制链接] |试试Instant~ |关注本帖
y2323k23 发表于 2016-9-8 02:05:05 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
自我介绍后就问了一个问题
给一批人, 这些人每人都花了一笔钱,
让算, 谁给谁多少钱, 能让所有人都达到平均数. visit 1point3acres.com for more.


写完了后, 面试官来了句, super complicate, 估计也是跪了。。。
能求个加面就好了。。。。. 1point3acres.com/bbs
好蛋碎,,,

评分

1

查看全部评分

本帖被以下淘专辑推荐:

william_gong 发表于 2016-9-8 02:43:22 | 显示全部楼层
public void calculate(int[] nums) {
                int sum = 0;
                for (int i : nums) {
                        sum += i;
                }
                double avg = sum * 1.0 / nums.length;
                double[] temp = new double[nums.length];
                for (int i = 0; i < nums.length; i++) {
                        temp[i] = avg - nums[i];
                }
                int cur1 = 0; //pos
                int cur2 = 0; //neg. visit 1point3acres.com for more.
                while (cur1 < nums.length) {. Waral 鍗氬鏈夋洿澶氭枃绔,
                        while (cur1 < nums.length && temp[cur1] <= 0) {. more info on 1point3acres.com
                                cur1++;
                        }
                        while (cur2 < nums.length && temp[cur2] >= 0) {
                                cur2++;
                        }
                        if (cur1 < nums.length && cur2 < nums.length) {
                                double min = Math.min(temp[cur1], -temp[cur2]);
                                System.out.println("" + cur2 + " gives " + (min) + " to " + cur1);
                                temp[cur1] -= min;
                                temp[cur2] += min;
                        }
                }
        }

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
求帮忙看看

评分

1

查看全部评分

回复 支持 3 反对 1

使用道具 举报

ivanml 发表于 2016-9-8 03:31:10 | 显示全部楼层
这题是个数学问题,最后你发现是一个公式,假设ABCDE 5个人,分别花了nums = {1, 2, 3, 4, 5},假设从A的角度出发,分别计算A要给BCDE多少钱,如果是负数就反过来给A,最后结果是,A要给第i个人:
gives = (n * nums - sum) / n;
其中n是总人数,sum是所有人花的钱总和,nums是第i个人花的钱。代码如下:
  1. void giveMoney(vector<int> &nums) {
  2.   int n = nums.size();
  3.   int sum = 0;
  4.   for (int i : nums)
  5.     sum += i;
  6.   for (int i = 1; i < n; ++ i) {
  7.     int cur = (n * nums[i] - sum) * 1.0 / n;
  8.     cout << "gives " << i << " $" << cur << endl;
  9.   }
  10. }
复制代码
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

e.g. n = 5, nums = {1,2,3,4,5}:
$ ./a.out 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
gives 1 $-1. visit 1point3acres.com for more.
gives 2 $0
gives 3 $1
gives 4 $2. 1point 3acres 璁哄潧

补充内容 (2016-9-8 03:32):
少写了, 公式是:
gives = (n * nums - sum) / n;
其中n是总人数,sum是所有人花的钱总和,nums是第i个人花的钱。

补充内容 (2016-9-8 03:33):
额方括号打不出来么...
回复 支持 3 反对 0

使用道具 举报

zyoppy008 发表于 2016-9-8 07:13:29 | 显示全部楼层
This problem can be done by general way:
go through the array starting at index 1, for each element larger than the average, give the superfluous money to the first guy
go through the array starting at index 1, for each element smaller than the average, the first guy give its money to make him to average. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
回复 支持 1 反对 0

使用道具 举报

 楼主| y2323k23 发表于 2016-9-8 02:27:45 | 显示全部楼层
才面完就想到更好的解法了。。写出那么复杂的我也是醉了。。。
回复 支持 反对

使用道具 举报

 楼主| y2323k23 发表于 2016-9-8 02:44:57 | 显示全部楼层
对的,就是这个意思
回复 支持 反对

使用道具 举报

fatalme 发表于 2016-9-8 03:06:38 | 显示全部楼层
没有要求least transactions什么的?
回复 支持 反对

使用道具 举报

 楼主| y2323k23 发表于 2016-9-8 03:15:31 | 显示全部楼层
fatalme 发表于 2016-9-8 03:06
没有要求least transactions什么的?

没有, 估计来不及问了吧, 我写完也没多少时间了, 估计是跪了
回复 支持 反对

使用道具 举报

Xochitl 发表于 2016-9-8 03:52:38 | 显示全部楼层
ivanml 发表于 2016-9-8 03:31. 1point3acres.com/bbs
这题是个数学问题,最后你发现是一个公式,假设ABCDE 5个人,分别花了nums = {1, 2, 3, 4, 5},假设从A的角 ...

按照楼主的意思,是应该要求出来,特定的谁给谁多少钱,不是一个人拿多少或者给多少
回复 支持 反对

使用道具 举报

ivanml 发表于 2016-9-8 04:02:19 | 显示全部楼层
Xochitl 发表于 2016-9-8 03:52
.鏈枃鍘熷垱鑷1point3acres璁哄潧按照楼主的意思,是应该要求出来,特定的谁给谁多少钱,不是一个人拿多少或者给多少

你看我的输出里第一项是“gives 1 $-1”,意思就是1号要给0号$1。
当然你说不特定以某个人的角度当然可以,但是我觉得会更复杂,只要能得到一个合法解,应该就可以了吧。
回复 支持 反对

使用道具 举报

Xochitl 发表于 2016-9-8 04:24:52 | 显示全部楼层
ivanml 发表于 2016-9-8 04:02
你看我的输出里第一项是“gives 1 $-1”,意思就是1号要给0号$1。
当然你说不特定以某个人的角度当然可 ...

纯讨论啊,感觉2楼的two pointer比较合适,这种输出“gives 1 $-1”==1号要给0号$1,感觉还是直接输出1 gives 0 $1比较make sense一些
回复 支持 反对

使用道具 举报

xihaokai1 发表于 2016-9-8 04:34:15 | 显示全部楼层
ivanml 发表于 2016-9-8 03:31
这题是个数学问题,最后你发现是一个公式,假设ABCDE 5个人,分别花了nums = {1, 2, 3, 4, 5},假设从A的角 ...

很好的想法,你有当银行家的潜质
回复 支持 反对

使用道具 举报

ivanml 发表于 2016-9-8 04:36:46 | 显示全部楼层
Xochitl 发表于 2016-9-8 04:24. Waral 鍗氬鏈夋洿澶氭枃绔,
纯讨论啊,感觉2楼的two pointer比较合适,这种输出“gives 1 $-1”==1号要给0号$1,感觉还是直接输出1 g ...

这个输出的时候遇到负数改一改format不就好了么。。我觉得解答肯定不是唯一的,除非面试官要求least transaction之类的
回复 支持 反对

使用道具 举报

aangel 发表于 2016-9-8 04:47:29 | 显示全部楼层
ivanml 发表于 2016-9-8 03:31
这题是个数学问题,最后你发现是一个公式,假设ABCDE 5个人,分别花了nums = {1, 2, 3, 4, 5},假设从A的角 ...

如果题目只是问谁给谁多少钱,就可以达到消费平均数,这个做法的确可以
回复 支持 反对

使用道具 举报

woshixuyoudan 发表于 2016-9-8 04:51:43 | 显示全部楼层
william_gong 发表于 2016-9-8 02:43
public void calculate(int[] nums) {
                int sum = 0;
                for (int i : nums) {

龚神厉害!写的不错!!
回复 支持 反对

使用道具 举报

woshixuyoudan 发表于 2016-9-8 04:53:38 | 显示全部楼层
y2323k23 发表于 2016-9-8 02:27
才面完就想到更好的解法了。。写出那么复杂的我也是醉了。。。

gg又出新题了= =  楼主辛苦啦!

对了,请问一下楼主  有什么更好的解法?   有说明了可以以一个人为目标么。。  就是像二楼ivanml写的
回复 支持 反对

使用道具 举报

ilovexiao77 发表于 2016-9-8 04:58:26 | 显示全部楼层
二楼的答案很给力!
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-9-8 06:27:24 | 显示全部楼层
woshixuyoudan 发表于 2016-9-8 04:51.1point3acres缃
龚神厉害!写的不错!!
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
和fb大神还是没法比

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Xochitl 发表于 2016-9-8 06:33:20 | 显示全部楼层
ivanml 发表于 2016-9-8 04:36
这个输出的时候遇到负数改一改format不就好了么。。我觉得解答肯定不是唯一的,除非面试官要求least tran ...
.1point3acres缃
二楼的也不是least transaction,我只是想说你的那个gives = (n * nums - sum) / n 和 william_gong 用的nums-sum/n 是一样的,不管后面输出是用你的分析负数方法或者用上面用的two pointer,确实要整理一下才能变成一个合理形式,
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-9-8 06:41:38 | 显示全部楼层
ivanml 发表于 2016-9-8 03:31
这题是个数学问题,最后你发现是一个公式,假设ABCDE 5个人,分别花了nums = {1, 2, 3, 4, 5},假设从A的角 ...
. 1point 3acres 璁哄潧
你这种不行吧。
你看比如 1 3 5 7 9 11 13
3 缺少4个 对吧, 1总共最开始总共只有1个,所以给不了
回复 支持 反对

使用道具 举报

fatalme 发表于 2016-9-8 06:44:02 | 显示全部楼层
Least possible transactions is n/2 (n is computed with averages excluded), can't be less, see the following; an efficient solution for the general situation is very difficult, I can't come up with one now.
1, -1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
2, -2,
3, -3
...
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 06:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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