當了一年的 Facebook Rotational Software Engineer 心得分享

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 4900|回复: 29
收起左侧

狗狗惨烈电面

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

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

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

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

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

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

评分

1

查看全部评分

本帖被以下淘专辑推荐:

william_gong 发表于 2016-9-8 02:43:22 | 显示全部楼层
public void calculate(int[] nums) {
                int sum = 0;
                for (int i : nums) {
                        sum += i;
                }.本文原创自1point3acres论坛
                double avg = sum * 1.0 / nums.length;
                double[] temp = new double[nums.length];
                for (int i = 0; i < nums.length; i++) {-google 1point3acres
                        temp[i] = avg - nums[i];. more info on 1point3acres
                }
                int cur1 = 0; //pos. 牛人云集,一亩三分地
                int cur2 = 0; //neg
. 一亩-三分-地,独家发布                while (cur1 < nums.length) {
                        while (cur1 < nums.length && temp[cur1] <= 0) {
                                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). visit 1point3acres for more.
  5.     sum += i;-google 1point3acres
  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
gives 2 $0
gives 3 $1
gives 4 $2
-google 1point3acres
补充内容 (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.. 1point3acres
回复 支持 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什么的?

没有, 估计来不及问了吧, 我写完也没多少时间了, 估计是跪了
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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。. 围观我们@1point 3 acres
当然你说不特定以某个人的角度当然可以,但是我觉得会更复杂,只要能得到一个合法解,应该就可以了吧。
回复 支持 反对

使用道具 举报

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
纯讨论啊,感觉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. from: 1point3acres
public void calculate(int[] nums) {
                int sum = 0;-google 1point3acres
                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的角 ...

你这种不行吧。
你看比如 1 3 5 7 9 11 13
. 1point 3acres 论坛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,-google 1point3acres
3, -3
...
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-21 04:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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