推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

Square的店面

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

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

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

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

x
店面就一轮,顺便问问有没有更好的思路,算是设计题目,第一问就是一堆人出去玩,吃饭或者什么的,有人先付钱,其他人欠着,最后求每个人的balance.
比如 person A,B,C
Transaction 1 is 12$, A pays for A,B,C
Transaction 2 is 10$, B pays for A,B

那么最后balance就是
A: -3
B: -1
C: 4 (C需要给A,B各1元和3元). visit 1point3acres.com for more.

设计数据结构和打印出每个人的balance.
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第二问是打印出谁应该给谁多少钱,比如上例中,应该是
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
C gives 1 to B
C gives 3 to A

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

使用道具 举报

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. from: 1point3acres.com/bbs
楼主你第一问的思路是什么?

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

使用道具 举报

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

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

使用道具 举报

wangxinbo1123 发表于 2017-1-8 11:05:42 | 显示全部楼层
回复 支持 反对

使用道具 举报

wangxinbo1123 发表于 2017-1-8 11:51:49 | 显示全部楼层
                ○ First sub-problem: print all debts after transactions
                        § use a hash map
                ○ Second sub-problem: print the balancing process
                        § use two priority queue
                ○ Third sub-problem: return the minimum transactions to balance debt
                        § DFS, O(n!)
回复 支持 反对

使用道具 举报

biubiugo 发表于 2017-1-8 15:58:57 | 显示全部楼层
求问楼主是哪个岗位呀
回复 支持 反对

使用道具 举报

johnnywsd 发表于 2017-1-24 15:50:56 | 显示全部楼层
  1. from collections import defaultdict
  2. . 1point 3acres 璁哄潧

  3. class Solution:
  4.     def get_balance(self, transations):
  5.         balance_dct = defaultdict(int)
  6.         for amount, payer, payees in transations:
  7.             balance_dct[payer] -= amount
  8.             amount_payee = float(amount) / len(payees)
  9.             for payee in payees:
  10.                 balance_dct[payee] += amount_payee
  11.         return balance_dct

  12.     def get_due(self, balance_dct):
  13.         if sum(balance_dct.values()) != 0:
  14.             raise Exception('Not balance')
  15.         debets = sorted([it for it in balance_dct.items() if it[1] > 0], key=lambda x: x[1])
  16.         credit = sorted([it for it in balance_dct.items() if it[1] < 0], key=lambda x: -x[1])
  17.         give_dct = defaultdict(list)
  18.         while debets and credit:
  19.             debet_user, debet_val = debets.pop()
  20.             credit_user, credit_val = credit.pop()
  21.             bal = debet_val + credit_val
  22.             if bal > 0:
  23.                 debets.append((debet_user, bal)). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  24.             elif bal < 0:
  25.                 credit.append((credit_user, bal))
  26. . more info on 1point3acres.com
  27.             give_dct[debet_user].append((credit_user, min(debet_val, -credit_val)))
  28.         return give_dct
复制代码


. 1point 3acres 璁哄潧
  1. import unittest. visit 1point3acres.com for more.
  2. from solution import Solution

  3. class Tests(unittest.TestCase):-google 1point3acres
  4.     def test_1(self):
  5.         sol = Solution()
  6.         transations = [(12, 'A', ('A', 'B', 'C')), (10, 'B', ('A', 'B'))]
  7.         res = sol.get_balance(transations)
  8.         print res

  9.     def test_2(self):
  10.         sol = Solution()
  11.         transations = [(12, 'A', ('A', 'B', 'C')), (10, 'B', ('A', 'B'))]
  12.         balance_dct = sol.get_balance(transations)
  13.         res = sol.get_due(balance_dct). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  14.         print res

  15. if __name__ == '__main__':
  16.     unittest.main(verbosity=2).鏈枃鍘熷垱鑷1point3acres璁哄潧
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-18 17:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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