Square的店面

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

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

的是维持两个queue,一个是欠钱的，一个是收钱的，队首print，然后balance清零出队。不知道有没有更好的思路。

1. from collections import defaultdict
   
2. 
   
3. 
   
4. class Solution:
   
5.     def get_balance(self, transations):
   
6.         balance_dct = defaultdict(int)
   
7.         for amount, payer, payees in transations:
   
8.             balance_dct[payer] -= amount
   
9.             amount_payee = float(amount) / len(payees)
   
10.             for payee in payees:
    
11.                 balance_dct[payee] += amount_payee
    
12.         return balance_dct
    
13. 
    
14.     def get_due(self, balance_dct):
    
15.         if sum(balance_dct.values()) != 0:
    
16.             raise Exception('Not balance')
    
17.         debets = sorted([it for it in balance_dct.items() if it[1] > 0], key=lambda x: x[1])
    
18.         credit = sorted([it for it in balance_dct.items() if it[1] < 0], key=lambda x: -x[1])
    
19.         give_dct = defaultdict(list)
    
20.         while debets and credit:
    
21.             debet_user, debet_val = debets.pop()
    
22.             credit_user, credit_val = credit.pop()
    
23.             bal = debet_val + credit_val
    
24.             if bal > 0:
    
25.                 debets.append((debet_user, bal))
    
26.             elif bal < 0:
    
27.                 credit.append((credit_user, bal))
    
28. 
    
29.             give_dct[debet_user].append((credit_user, min(debet_val, -credit_val)))
    
30.         return give_dct
    

复制代码

1. import unittest
   
2. from solution import Solution
   
3. 
   
4. class Tests(unittest.TestCase):
   
5.     def test_1(self):
   
6.         sol = Solution()
   
7.         transations = [(12, 'A', ('A', 'B', 'C')), (10, 'B', ('A', 'B'))]
   
8.         res = sol.get_balance(transations)
   
9.         print res
   
10. 
    
11.     def test_2(self):
    
12.         sol = Solution()
    
13.         transations = [(12, 'A', ('A', 'B', 'C')), (10, 'B', ('A', 'B'))]
    
14.         balance_dct = sol.get_balance(transations)
    
15.         res = sol.get_due(balance_dct)
    
16.         print res
    
17. 
    
18. if __name__ == '__main__':
    
19.     unittest.main(verbosity=2)
    

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

wtcupup 发表于 2016-2-24 15:12
楼主你第一问的思路是什么？

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

这应该是一个有向图的遍历

楼主你第一问的思路是什么？

第二问要求求出最简单的清算方法吗？还是只要能给清就行？

kinggarden2001 发表于 2016-2-24 13:05
这应该是一个有向图的遍历

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

daniel_hl 发表于 2016-2-24 15:35
第二问要求求出最简单的清算方法吗？还是只要能给清就行？

没有具体要求，应该是給清就好

第一题可以用一个n*n matrix吗，类似图了 这样第二问也解决了 就是矩阵可能很稀疏 浪费空间

如果是稀疏矩阵就用个hashmap也可以

https://leetcode.com/problems/optimal-account-balancing/