一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2948|回复: 29
收起左侧

狗狗惨烈电面

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

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

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

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

x
自我介绍后就问了一个问题. 鍥磋鎴戜滑@1point 3 acres
给一批人, 这些人每人都花了一笔钱,
让算, 谁给谁多少钱, 能让所有人都达到平均数


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

评分

1

查看全部评分

本帖被以下淘专辑推荐:

william_gong 发表于 2016-9-8 02:43:22 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
public void calculate(int[] nums) {
                int sum = 0;
                for (int i : nums) {
                        sum += i;. 鍥磋鎴戜滑@1point 3 acres
                }
                double avg = sum * 1.0 / nums.length;
                double[] temp = new double[nums.length];
                for (int i = 0; i < nums.length; i++) {. 1point 3acres 璁哄潧
                        temp[i] = avg - nums[i];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                }
                int cur1 = 0; //pos
                int cur2 = 0; //neg
                while (cur1 < nums.length) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        while (cur1 < nums.length && temp[cur1] <= 0) {
                                cur1++;
                        }-google 1point3acres
                        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;
. from: 1point3acres.com/bbs                         }
                }
        }

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
求帮忙看看

评分

1

查看全部评分

回复 支持 3 反对 1

使用道具 举报

ivanml 发表于 2016-9-8 03:31:10 | 显示全部楼层
关注一亩三分地微博:
Warald
这题是个数学问题,最后你发现是一个公式,假设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) {. 1point3acres.com/bbs
  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
gives 2 $0
gives 3 $1
gives 4 $2

补充内容 (2016-9-8 03:32):
少写了, 公式是:
gives = (n * nums - sum) / n;. 1point 3acres 璁哄潧
其中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. 1point3acres.com/bbs
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 | 显示全部楼层
才面完就想到更好的解法了。。写出那么复杂的我也是醉了。。。
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| 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
这题是个数学问题,最后你发现是一个公式,假设ABCDE 5个人,分别花了nums = {1, 2, 3, 4, 5},假设从A的角 ...

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

使用道具 举报

ivanml 发表于 2016-9-8 04:02:19 | 显示全部楼层
Xochitl 发表于 2016-9-8 03:52
按照楼主的意思,是应该要求出来,特定的谁给谁多少钱,不是一个人拿多少或者给多少

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

使用道具 举报

Xochitl 发表于 2016-9-8 04:24:52 | 显示全部楼层
ivanml 发表于 2016-9-8 04:02. Waral 鍗氬鏈夋洿澶氭枃绔,
你看我的输出里第一项是“gives 1 $-1”,意思就是1号要给0号$1。. 鍥磋鎴戜滑@1point 3 acres
当然你说不特定以某个人的角度当然可 ...

纯讨论啊,感觉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
. From 1point 3acres bbs这题是个数学问题,最后你发现是一个公式,假设ABCDE 5个人,分别花了nums = {1, 2, 3, 4, 5},假设从A的角 ...
. From 1point 3acres bbs
很好的想法,你有当银行家的潜质
回复 支持 反对

使用道具 举报

ivanml 发表于 2016-9-8 04:36:46 | 显示全部楼层
Xochitl 发表于 2016-9-8 04:24
纯讨论啊,感觉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. 1point3acres.com/bbs
这题是个数学问题,最后你发现是一个公式,假设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
龚神厉害!写的不错!!

和fb大神还是没法比

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Xochitl 发表于 2016-9-8 06:33:20 | 显示全部楼层
ivanml 发表于 2016-9-8 04:36
这个输出的时候遇到负数改一改format不就好了么。。我觉得解答肯定不是唯一的,除非面试官要求least tran ...

二楼的也不是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, 2017-3-23 19:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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