我来说一个面试题吧，2012年参与到的Facebook Programming puzzle

Question

这题是当时自己去投Facebook的时候，programmingpuzzle那关给的题目。题目如下：你有足够数量的天秤和砝码。每个天秤有10磅。天秤的左右两边可以放砝码，也可以放天秤。题目要求是，在给定的初始组合情况下，如何添加砝码，让整体保证平衡。输入是一串数字，第一行是一个整数，代表当前初始状态一共有多少个天秤，每个天秤都有一个序号接下来往下，每两行分别代表一个天秤左右两边所包含的天秤序号和包含的砝码重量每一组的格式如下：左半的砝码重量右半的砝码重量其中,表示数组输入样例如下：4//4个天秤01//0号天秤左边放置着1号天秤02//0号天秤右边放置着2号天秤0//1号天秤左边啥都没有03//1号天秤右边放置着3号天秤3//2号天秤左边有三磅重的砝码0//2号天秤右边啥都没有0//3号天秤左边啥都没有0//3号天秤右边啥都没有输出，输出N行。第i行代表第i个天秤的左右两边需要添加多少重量的砝码输出样例如下：0:0141:1002:033:00大家可以试试看。Facebook当时给我的时间是1小时，当时做完这题就可以进入phoneinterview，可惜挂在了phoneinterview那--。我是分割线不用考虑力矩，单纯的天秤左右配平。不会出现嵌套情况。还有就是，当时我在做这题的时候，input不一定是一棵树，有可能是一个森林。测试用例我得找一找，不一定有存了。。一年前的题，我也换过了电脑。我准备周一把我的解答放上来。

Answer 1

小花了一点时间理解题意，个人解法如下：假设天平之间没有嵌套关系（即不会出现1在2左边，2在1左边这种情况）为了使一个天平平衡，首先得把放在其左边或右边的天平配平假设力矩为0，天平左右两边重量不等时在少的一边用砝码补上重量如果符合以上，题目综合性不错，涉及了简单树的遍历以及贪心算法下面是代码（脑袋不好使状态，不知道弄对了没——反正代码风格成渣渣了)importsys
defset_balance(id):
ifnotbalanced[id]:
foriinlcld[id]:
lw[id]+=set_balance(i)
foriinrcld[id]:
rw[id]+=set_balance(i)
iflw[id]ladd[id]=rw[id]-lw[id]
lw[id]+=ladd[id]
eliflw[id]>rw[id]:
radd[id]=lw[id]-rw[id]
rw[id]+=radd[id]
balanced[id]=True
returnlw[id]+rw[id]
n=int(sys.stdin.readline())
lw=[5foriinrange(n)]
rw=[5foriinrange(n)]
lcld=[[]foriinrange(n)]
rcld=[[]foriinrange(n)]
foriinrange(n):
row=[int(v)forvinsys.stdin.readline().split()]
lw[i]+=row[0]
forvinrow[1:]:
lcld[i].append(v)
row=[int(v)forvinsys.stdin.readline().split()]
rw[i]+=row[0]
forvinrow[1:]:
rcld[i].append(v)
balanced=[Falseforiinrange(n)]
ladd=[0foriinrange(n)]
radd=[0foriinrange(n)]
foriinrange(n):
get_balance(i)
foriinxrange(n):
print"%d:%d%d"%(i,ladd[i],radd[i])