一亩三分地论坛

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

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

Square的店面

[复制链接] |试试Instant~ |关注本帖
nothingtrouble 发表于 2016-2-24 11:45:07 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 博士 全职@Square - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
店面就一轮,顺便问问有没有更好的思路,算是设计题目,第一问就是一堆人出去玩,吃饭或者什么的,有人先付钱,其他人欠着,最后求每个人的balance.. 1point3acres.com/bbs
比如 person A,B,C
Transaction 1 is 12$, A pays for A,B,C
Transaction 2 is 10$, B pays for A,B
. 鍥磋鎴戜滑@1point 3 acres
那么最后balance就是
A: -3
B: -1
C: 4 (C需要给A,B各1元和3元)

设计数据结构和打印出每个人的balance.

第二问是打印出谁应该给谁多少钱,比如上例中,应该是

C gives 1 to B
C gives 3 to A

第一问没什么好说的,第二问的时间复杂度是可以做到o(n)的,我想的是维持两个queue,一个是欠钱的,一个是收钱的,队首print,然后balance清零出队。不知道有没有更好的思路。
kinggarden2001 发表于 2016-2-24 13:05:59 | 显示全部楼层
这应该是一个有向图的遍历. visit 1point3acres.com for more.
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-2-24 15:12:00 | 显示全部楼层
楼主你第一问的思路是什么?
回复 支持 反对

使用道具 举报

daniel_hl 发表于 2016-2-24 15:35:09 | 显示全部楼层
第二问要求求出最简单的清算方法吗?还是只要能给清就行?
回复 支持 反对

使用道具 举报

 楼主| nothingtrouble 发表于 2016-2-25 03:06:16 | 显示全部楼层
kinggarden2001 发表于 2016-2-24 13:05
这应该是一个有向图的遍历

你想复杂了吧,这题不要求谁一定给谁钱,只要最后大家少付钱的多付,多付钱的拿进钱就可以了
回复 支持 反对

使用道具 举报

 楼主| nothingtrouble 发表于 2016-2-25 03:07:06 | 显示全部楼层
daniel_hl 发表于 2016-2-24 15:35
第二问要求求出最简单的清算方法吗?还是只要能给清就行?

没有具体要求,应该是給清就好
回复 支持 反对

使用道具 举报

 楼主| nothingtrouble 发表于 2016-2-25 03:08:59 | 显示全部楼层
wtcupup 发表于 2016-2-24 15:12
楼主你第一问的思路是什么?

第一问,就是每个人付钱以后,更新balance,然后其他没有付钱的参与这次消费的,也更新balance。第二问接着就是根据所有人的balance,找出一个方案然后所有人把帐结清
回复 支持 反对

使用道具 举报

echo33 发表于 2016-2-25 04:54:12 | 显示全部楼层
第一题可以用一个n*n matrix吗,类似图了 这样第二问也解决了 就是矩阵可能很稀疏 浪费空间

如果是稀疏矩阵就用个hashmap也可以
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 12:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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