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

Question

这题是当时自己去投Facebook的时候，programming puzzle那关给的题目。

题目如下：
你有足够数量的天秤和砝码。每个天秤有10磅。天秤的左右两边可以放砝码，也可以放天秤。
题目要求是，在给定的初始组合情况下，如何添加砝码，让整体保证平衡。

输入是一串数字，第一行是一个整数，代表当前初始状态一共有多少个天秤，每个天秤都有一个序号
接下来往下，每两行分别代表一个天秤左右两边所包含的天秤序号和包含的砝码重量
每一组的格式如下：
左半的砝码重量 <天秤i,天秤j,...>
右半的砝码重量 <天秤k,天秤m,...>
其中,<>表示数组
输入样例如下：
4 //4个天秤
0 1 //0号天秤左边放置着1号天秤
0 2 //0号天秤右边放置着2号天秤
0 //1号天秤左边啥都没有
0 3 //1号天秤右边放置着3号天秤
3 //2号天秤左边有三磅重的砝码
0 //2号天秤右边啥都没有
0 //3号天秤左边啥都没有
0 //3号天秤右边啥都没有

输出，输出N行。第i行代表第i个天秤的左右两边需要添加多少重量的砝码
输出样例如下：
0: 0 14
1: 10 0
2: 0 3
3: 0 0

大家可以试试看。Facebook当时给我的时间是1小时，当时做完这题就可以进入phone interview，可惜挂在了phone interview那- -。

我是分割线

不用考虑力矩，单纯的天秤左右配平。不会出现嵌套情况。
还有就是，当时我在做这题的时候，input不一定是一棵树，有可能是一个森林。
测试用例我得找一找，不一定有存了。。一年前的题，我也换过了电脑。
我准备周一把我的解答放上来。

Answer 1

今天把答案放出。
这段代码是从去年年初的邮件里扫出来的，由于手头没数据集，没有再调试一下。不过当时都是全通过的，应该没啥问题。下面来简单的说一下思想：
针对input来看，其实就是有一棵或多棵现成的树，目的就是把每个节点的左右两个分支配平。
由于子节点的配平会影响到父节点的配平，所以很自然的就想到了用递归的方法来解这个问题。
整个递归过程就是一个树的后序遍历过程。

话说这代码缩进好像有点问题- -

分割线

调整了代码缩进，加入必要注释

package PhoneInterview;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

public class Balance {
	// 每个天秤的属性
	public boolean balanced = false;// 判断是否已经配平
	public int nodeID;// 天秤id
	public Balance[] leftChild = null;// 左子树的天秤数组
	public Balance[] rightChild = null;// 右子树的天秤数组
	public int balanceWeight = 10;// 自身重量
	public int leftWeight = 0;// 左子树总重量
	public int rightWeight = 0;// 右子树总重量
	public int adding = 0;// 为了配平，还需添加多少重量的砝码

	// 递归函数
	public static int balancing(Balance node) {
		// 判断天秤左边是否有子天秤
		if (node.leftChild != null) {
			for (int i = 0; i < node.leftChild.length; i++)
				node.leftWeight += balancing(node.leftChild[i]);
		}
		// 判断天秤右边是否有紫天秤
		if (node.rightChild != null) {
			for (int i = 0; i < node.rightChild.length; i++) {
				node.rightWeight += balancing(node.rightChild[i]);
			}
		}
		// 天秤左右子树都计算完毕，来计算当前天秤左右重量差
		node.adding = Math.abs(node.leftWeight - node.rightWeight);
		// 标记该天秤已经配平
		node.balanced = true;
		return node.balanceWeight + node.leftWeight + node.rightWeight
				+ node.adding;
	}

	// 主函数
	public static void main(String[] args) {
		int N = 0;
		Balance[] Balances;
		BufferedReader br;
		try {
			// 载入数据，初始化过程，无视这个file name吧
			br = new BufferedReader(new FileReader("input00.txt"));
			// load第一行，得到天秤总数
			String string = br.readLine();
			N = Integer.parseInt(string);
			// 初始化Balances数组
			Balances = new Balance[N];
			int i = 0;
			for (int k = 0; k < N; k++) {
				Balances[k] = new Balance();
				Balances[k].nodeID = k;
			}
			/*
			 * 开始一行一行的读入数据，每两行一个循环
			 */
			while ((string = br.readLine()) != null) {
				// 天秤左半部分初始化
				String[] strs = string.split(" ");
				Balances[i].leftWeight = Integer.parseInt(strs[0]);
				/*
				 * 这里是根据数据格式来的 如果length超过1，那就代表除了自重的值以外 还有放置的子天秤
				 * 遂初始化子树上的数组，添加对子天平的引用，方便日后调用
				 */
				if (strs.length != 1)
					Balances[i].leftChild = new Balance[strs.length - 1];
				for (int j = 1; j < strs.length; j++) {
					Balances[i].leftChild[j - 1] = Balances[Integer
							.parseInt(strs[j])];
				}
				// 天秤右半部分初始化
				string = br.readLine();
				String[] strs1 = string.split(" ");
				Balances[i].rightWeight = Integer.parseInt(strs1[0]);
				// 同理左半部分的操作
				if (strs1.length != 1)
					Balances[i].rightChild = new Balance[strs1.length - 1];
				for (int j = 1; j < strs1.length; j++) {
					Balances[i].rightChild[j - 1] = Balances[Integer
							.parseInt(strs1[j])];
				}
				i++;
			}

			// 初始化完毕，开始配平
			for (i = 0; i < Balances.length; i++) {
				if (!Balances[i].balanced)
					Balance.balancing(Balances[i]);
			}

			// 输出结果
			for (int m = 0; m < Balances.length; m++) {
				if (Balances[m].leftWeight < Balances[m].rightWeight)
					System.out.println(m + ": " + Balances[m].adding + " 0");
				else if (Balances[m].leftWeight >= Balances[m].rightWeight)
					System.out.println(m + ": 0 " + Balances[m].adding);
			}
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

	}
}

Answer 2

小花了一点时间理解题意，个人解法如下：

• 假设天平之间没有嵌套关系（即不会出现1在2左边，2在1左边这种情况）

• 为了使一个天平平衡，首先得把放在其左边或右边的天平配平

• 假设力矩为0，天平左右两边重量不等时在少的一边用砝码补上重量

如果符合以上，题目综合性不错，涉及了简单树的遍历以及贪心算法

下面是代码（脑袋不好使状态，不知道弄对了没——反正代码风格成渣渣了)

import sys

def set_balance(id):
    if not balanced[id]:
        for i in lcld[id]:
            lw[id] += set_balance(i)
        for i in rcld[id]:
            rw[id] += set_balance(i)
    if lw[id] < rw[id]:
        ladd[id] = rw[id] - lw[id]
        lw[id] += ladd[id]
    elif lw[id] > rw[id]:
        radd[id] = lw[id] - rw[id]
        rw[id] += radd[id]
    balanced[id] = True
    return lw[id] + rw[id]

n = int(sys.stdin.readline())
lw = [5 for i in range(n)]
rw = [5 for i in range(n)]
lcld = [[] for i in range(n)]
rcld = [[] for i in range(n)]
for i in range(n):
    row = [int(v) for v in sys.stdin.readline().split()]
    lw[i] += row[0]
    for v in row[1:]:
        lcld[i].append(v)
    row = [int(v) for v in sys.stdin.readline().split()]
    rw[i] += row[0]
    for v in row[1:]:
        rcld[i].append(v)

balanced = [False for i in range(n)]
ladd = [0 for i in range(n)]
radd = [0 for i in range(n)]
for i in range(n):
    get_balance(i)
    
for i in xrange(n):
    print "%d:%d %d" % (i, ladd[i], radd[i])

Answer 3

我也做过了！也挂载电话面试上了。英语不行啊