问两道facebook面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问两道facebook面试题

问两道facebook面试题# JobHunting - 待字闺中

N*g2012-01-18 08:01

1 楼

☆─────────────────────────────────────☆
tingtingliu (芙蓉一出，谁与争峰，千秋万代，一统江湖) 于 (Wed Jun 17 14:32:53 2009, 美东) 提到:
买了个 1k的东西
就不让我用cc
非要用 check
☆─────────────────────────────────────☆
suny82 (SUNY_阳光下) 于 (Wed Jun 17 14:37:49 2009, 美东) 提到:
co-bs

l*12012-01-18 08:01

2 楼

向大牛们求教：
1）N*N期盼，从(x,Y)到（0，0）的所有路径，只能向左或下走。貌似career-cup上只
有求一条路的。那位牛人给个所有路径的code？
2）一个二叉树，每个节点都是正或负整数，如何找到一个subtree whose sum is the
max.
谢谢！

d*o2012-01-18 08:01

3 楼

第一题：
总的路径数是C(X+Y,X)
比如
X=3 Y=4
用0表示向左，1表示向下。下面就表示了一个路径
1110000
下面我们做的就是找出所有的combination
比如
输出 0 1 2就是表示1110000
输出 0 2 3表示 1011000
//XY中选X个
void combinationXY(int out[],int XYLen, int XLen,int lev,int start)
{
if(lev==XLen)
{
for(int i=0;icout<cout<return;
}
for(int i=start;i{
out[lev]=i;
combinationXY(out,XYLen,XLen,lev+1,i+1);
}
}

the

【在 l**********1 的大作中提到】

: 向大牛们求教：
: 1）N*N期盼，从(x,Y)到（0，0）的所有路径，只能向左或下走。貌似career-cup上只
: 有求一条路的。那位牛人给个所有路径的code？
: 2）一个二叉树，每个节点都是正或负整数，如何找到一个subtree whose sum is the
: max.
: 谢谢！

d*o2012-01-18 08:01

4 楼

第2题：
不知道对不对？
int maxSubTree(node* root,node** maxRoot, int& maxNum)
{
if(root==NULL) return 0;
else
{
int sum = root->data+maxSubTree(root->left)+maxSubTree(root->right);
if(sum>maxNum)
{
maxNum=sum;
(*maxRoot) = root;
}
return sum;
}
}
node* maxSub(node* root)
{
assert(root);
node* p = NULL;
int maxNum = root->data;
maxSubTree(root,&p,maxNum);
return p;
}

the

【在 l**********1 的大作中提到】

r*12012-01-18 08:01

5 楼

第二题：
http://puddleofriddles.blogspot.com/2012/01/write-program-to-fi
包子啊。

q*x2012-01-18 08:01

6 楼

相当于在(x+y)个位置里选x个左。经典组合题。
the
递归。

【在 l**********1 的大作中提到】

p*22012-01-18 08:01

7 楼

第二题
int maxSum=int.MinValue;
Node maxTree=null;
int Find(Node* node)
{
if(node==null)
return 0;
int l=Find(node.left);
int r=Find(node.right);
int sum=l+r+node.value;
if(sum>maxSum)
{
maxTree=node;
maxSum=sum;
}
return sum;
}

q*x2012-01-18 08:01

8 楼

good

【在 p*****2 的大作中提到】

: 第二题
: int maxSum=int.MinValue;
: Node maxTree=null;
: int Find(Node* node)
: {
: if(node==null)
: return 0;
: int l=Find(node.left);
: int r=Find(node.right);
: int sum=l+r+node.value;

p*22012-01-18 08:01

9 楼

是不是罗嗦点？

【在 r**********1 的大作中提到】

: 第二题：
: http://puddleofriddles.blogspot.com/2012/01/write-program-to-fi
: 包子啊。

r*12012-01-18 08:01

10 楼

int maxSum(struct node* root, int* max)
{
if(root == NULL)
return 0;
if((root->left == NULL) && (root->right == NULL))
{
if(root->data > *max)
*max = root->data;
return root->data;
}
int sum = maxSum(root->left, max) + maxSum(root->right, max) + root->data;
if(sum > *max)
*max = sum;
return sum;
}
你是觉得哪里罗嗦了？我感觉和前面一个写的差不多啊。

【在 p*****2 的大作中提到】

:
: 是不是罗嗦点？

p*22012-01-18 08:01

11 楼

第一题这样可以吗？
public class Game
{
private void FindPath(int total, int x, int level, List path)
{
if (path.Count == x)
{
foreach (int i in path)
Console.Write("{0} ", i);
Console.WriteLine();
return;
}
for (int i = level; i < total; i++)
{
path.Add(i);
FindPath(total, x,i + 1, path);
path.RemoveAt(path.Count - 1);
}
}
public void AllPaths(int x, int y)
{
List path = new List();
FindPath(x+y, x, 0, path);
}
}

p*22012-01-18 08:01

12 楼

这段有必要吗？
if((root->left == NULL) && (root->right == NULL))
{
if(root->data > *max)
*max = root->data;
return root->data;
}

【在 r**********1 的大作中提到】

: int maxSum(struct node* root, int* max)
: {
: if(root == NULL)
: return 0;
: if((root->left == NULL) && (root->right == NULL))
: {
: if(root->data > *max)
: *max = root->data;
: return root->data;
: }

r*12012-01-18 08:01

13 楼

yeah, 你是对的。

【在 p*****2 的大作中提到】

: 这段有必要吗？
: if((root->left == NULL) && (root->right == NULL))
: {
: if(root->data > *max)
: *max = root->data;
: return root->data;
: }

b*y2012-01-18 08:01

14 楼

That answer is wrong,
it should be
int left = maxSum(root->left, max);
int right = maxSum(root->right, max);
int sum = left + right + root->data;
int localMax = max(sum, max(left,right));
if(sum > *max)
*max = sum;
return max;

【在 r**********1 的大作中提到】

: 第二题：
: http://puddleofriddles.blogspot.com/2012/01/write-program-to-fi
: 包子啊。

j*j2012-01-18 08:01

15 楼

第一题，如果假设矩阵中有若干不能通过的点，怎么列出所有路径？

【在 d****o 的大作中提到】

: 第一题：
: 总的路径数是C(X+Y,X)
: 比如
: X=3 Y=4
: 用0表示向左，1表示向下。下面就表示了一个路径
: 1110000
: 下面我们做的就是找出所有的combination
: 比如
: 输出 0 1 2就是表示1110000
: 输出 0 2 3表示 1011000

e*r2012-01-18 08:01

16 楼

search with backtracking, remember what you have been through

【在 j*****j 的大作中提到】

: 第一题，如果假设矩阵中有若干不能通过的点，怎么列出所有路径？

l*a2012-01-18 08:01

17 楼

what language are you using now?
the combination of C and C#?

【在 p*****2 的大作中提到】

: 第二题
: int maxSum=int.MinValue;
: Node maxTree=null;
: int Find(Node* node)
: {
: if(node==null)
: return 0;
: int l=Find(node.left);
: int r=Find(node.right);
: int sum=l+r+node.value;

m*l2012-01-18 08:01

18 楼

还好,你没有说smalltalk

【在 l*****a 的大作中提到】

: what language are you using now?
: the combination of C and C#?

l*a2012-01-18 08:01

19 楼

what will happen if there is only one node and the value is negative number?

【在 p*****2 的大作中提到】

: 第二题
: int maxSum=int.MinValue;
: Node maxTree=null;
: int Find(Node* node)
: {
: if(node==null)
: return 0;
: int l=Find(node.left);
: int r=Find(node.right);
: int sum=l+r+node.value;

p*22012-01-18 08:01

20 楼

for interview, use C# now。feel much better than C， but it took me 2 months
to transition.

【在 l*****a 的大作中提到】

: what language are you using now?
: the combination of C and C#?

p*22012-01-18 08:01

21 楼

number?
好像没问题吧？

【在 l*****a 的大作中提到】

: what will happen if there is only one node and the value is negative number?

l*a2012-01-18 08:01

22 楼

不work
why 包子

【在 r**********1 的大作中提到】

: 第二题：
: http://puddleofriddles.blogspot.com/2012/01/write-program-to-fi
: 包子啊。

l*a2012-01-18 08:01

23 楼

i mean "node *" in your code

months

【在 p*****2 的大作中提到】

:
: number?
: 好像没问题吧？

p*22012-01-18 08:01

24 楼

typo. 现在有的时候还是有C的习惯。sigh。面试时候有时也会这样。

【在 l*****a 的大作中提到】

: i mean "node *" in your code
:
: months

l*a2012-01-18 08:01

25 楼

u tried that?
真的没问题？
what is maxnode and maxnum with your code?

【在 p*****2 的大作中提到】

:
: typo. 现在有的时候还是有C的习惯。sigh。面试时候有时也会这样。

p*22012-01-18 08:01

26 楼

没问题呀。输出都是-5.
using System;
using System.Text;
using System.Collections.Generic;
public class Node
{
public int value;
public Node left;
public Node right;
public Node(int v, Node l, Node r)
{
value = v;
left = l;
right = r;
}
}
public class MaxSum
{
public int maxSum = int.MinValue;
public Node maxTree = null;
public int Find(Node node)
{
if(node==null)
return 0;
int l=Find(node.left);
int r=Find(node.right);
int sum=l+r+node.value;
if(sum>maxSum)
{
maxTree=node;
maxSum=sum;
}
return sum;
}
}
public class Test
{
static void Main(string[] args)
{
MaxSum test = new MaxSum();
Node node = new Node(-5, null, null);
test.Find(node);
Console.WriteLine(test.maxSum);
Console.WriteLine(test.maxTree.value);
Console.In.ReadLine();
}
}

【在 l*****a 的大作中提到】

: u tried that?
: 真的没问题？
: what is maxnode and maxnum with your code?

l*a2012-01-18 08:01

27 楼

-5 works
how about one node with int.MinValue

【在 p*****2 的大作中提到】

:
: 没问题呀。输出都是-5.
: using System;
: using System.Text;
: using System.Collections.Generic;
: public class Node
: {
: public int value;
: public Node left;
: public Node right;

m*e2012-01-18 08:01

28 楼

Q1: left = 0, down = 1
#include
#include
using namespace std;
void pathes(int x, int y, string s){
if( x == 0 && y == 0){
cout<return;
}
if(x > 0){
pathes(x-1, y, s+"0");
}
if(y > 0){
pathes(x, y-1, s+"1");
}
};
int main(int argc, char **argv){
pathes(3, 2, "");
}
If some points are not allowed, check it before move left or down.

p*22012-01-18 08:01

29 楼

good catch. overflow的问题也没有考虑。

【在 l*****a 的大作中提到】

: -5 works
: how about one node with int.MinValue

p*22012-01-18 08:01

30 楼

这样的话。上边那个答案也有问题吧？上来把root.value给了maxvalue。

【在 l*****a 的大作中提到】

: -5 works
: how about one node with int.MinValue

d*o2012-01-18 08:01

31 楼

赞，这个recursion

【在 m*********e 的大作中提到】

: Q1: left = 0, down = 1
: #include
: #include
: using namespace std;
: void pathes(int x, int y, string s){
: if( x == 0 && y == 0){
: cout<: return;
: }
: if(x > 0){

H*e2012-01-18 08:01

32 楼

第一题，
只需要加入一个path参数，每次保持处理一个新的点，push进去path,然后处理完再pop
出来就可以了。
java code如下:
import java.util.Stack;
public class PrintAllPathInMatrix {
private int[][] data;
public PrintAllPathInMatrix(int[][] data) {
this.data = data;
}
public void emumeratePath(int i, int j, Stack path) {
if (i > data.length - 1) {
return;
}
if (j > data[0].length - 1) {
return;
}
path.add(data[i][j]);
//found a path
if (i == data.length - 1 && j == data[0].length - 1) {
for (int p = 0; p < path.size(); p++) {
System.out.print(path.get(p) + "");
}
System.out.print("\n");
}

emumeratePath(i + 1, j, path);
emumeratePath(i, j + 1, path);
path.pop();
}
public void emumeratePath() {
if(data==null || data.length==0){
return;
}
Stack path = new Stack();
emumeratePath(0, 0, path);
}
public static void main(String[] args) {
int[][] data = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
PrintAllPathInMatrix printAllPathInMatrix = new PrintAllPathInMatrix(
data);
printAllPathInMatrix.emumeratePath();
}
}

the

【在 l**********1 的大作中提到】

H*e2012-01-18 08:01

33 楼

第二题，
用往上面反值的方法，左右子树传值给parent node. 总复杂度为O(n).
inside a class:
BSTNode maxsumNode = null;
int maxValue = Integer.MIN_VALUE;
public void findMaxSumSubtree(BSTNode node, MutableInt sum) {
// base cases:
if (node == null) {
sum.setValue(0);
return;
}
// normal cases:
MutableInt leftSum = new MutableInt();
MutableInt rightSum = new MutableInt();
findMaxSumSubtree(node.left, leftSum);
findMaxSumSubtree(node.right, rightSum);
sum.setValue(leftSum.getValue() + rightSum.getValue() + node.key);
if (sum.getValue() > maxValue) {
maxValue = sum.getValue();
maxsumNode = node;
}
}
public BSTNode findMaxSumSubtree() {
MutableInt sum = new MutableInt();
findMaxSumSubtree(root, sum);
return maxsumNode;
}

the

【在 l**********1 的大作中提到】

g*y2012-01-18 08:01

34 楼

ur codes do not work for a tree like this:
1
/ \
-50 -30
/ \
100 20

【在 p*****2 的大作中提到】

: 第二题
: int maxSum=int.MinValue;
: Node maxTree=null;
: int Find(Node* node)
: {
: if(node==null)
: return 0;
: int l=Find(node.left);
: int r=Find(node.right);
: int sum=l+r+node.value;

p*22012-01-18 08:01

35 楼

我试了一下，返回100呀。这个值不对吗？

【在 g***y 的大作中提到】

: ur codes do not work for a tree like this:
: 1
: / \
: -50 -30
: / \
: 100 20

a*n2012-01-18 08:01

36 楼

#include
using namespace std;
// 0 means right, 1 means down
void AllPath(int N, int row, int col, int path[], int idx) {
if(row==N-1 && col==N-1) {
for(int i=0; i<2*N-2; i++) {
cout << path[i] << " ";
}
cout << endl;
}
// go down
if(row != N-1) {
path[idx] = 1;
AllPath(N, row+1, col, path, idx+1);
}
// go right
if(col != N-1) {
path[idx] = 0;
AllPath(N, row, col+1, path, idx+1);
}
}
int main() {
int path[4];
AllPath(3, 0, 0, path, 0);
}

H*e2012-01-18 08:01

37 楼

对的

【在 p*****2 的大作中提到】

: 我试了一下，返回100呀。这个值不对吗？

g*y2012-01-18 08:01

38 楼

你对了我看错了我以为你的结果是find的return value。
my codes (C#):
public static int getMaxSum(Node root)
{
if (root == null)
return 0;
int max = 0;
getMaxSumHelper(root, ref max);
return max;
}
private static int getMaxSumHelper(Node root, ref int currMax
)
{
int leftSum = 0;
int rightSum = 0;
if (root.left != null)
{
leftSum = getMaxSumHelper(root.left, ref currMax);
}
if (root.right != null)
{
rightSum = getMaxSumHelper(root.right, ref currMax);
}
if (rightSum + leftSum + root.payLoad > currMax)
{
currMax = rightSum + leftSum + root.payLoad;
}
return rightSum + leftSum + root.payLoad;

}

【在 p*****2 的大作中提到】

: 我试了一下，返回100呀。这个值不对吗？

p*22012-01-18 08:01

39 楼

嗯。我没有好好写。用了两个全局变量。

【在 g***y 的大作中提到】

: 你对了我看错了我以为你的结果是find的return value。
: my codes (C#):
: public static int getMaxSum(Node root)
: {
: if (root == null)
: return 0;
: int max = 0;
: getMaxSumHelper(root, ref max);
: return max;
: }

H*e2012-01-18 08:01

40 楼

喝喝，如果我需要全局变量来比较clean得话，我一般把他们wrap到一个 class里面。。

【在 p*****2 的大作中提到】

: 嗯。我没有好好写。用了两个全局变量。

p*22012-01-18 08:01

41 楼

。。
我在VS上是这么搞的。我当时就是在纸上写了一下就发上来了。只是表达一个算法。

【在 H***e 的大作中提到】

: 喝喝，如果我需要全局变量来比较clean得话，我一般把他们wrap到一个 class里面。。

r*12012-01-18 08:01

42 楼

没有错。
你的这个比较，在原函数的recursive calls里面就比较过了。

【在 b****y 的大作中提到】

: That answer is wrong,
: it should be
: int left = maxSum(root->left, max);
: int right = maxSum(root->right, max);
: int sum = left + right + root->data;
: int localMax = max(sum, max(left,right));
: if(sum > *max)
: *max = sum;
: return max;

r*12012-01-18 08:01

43 楼

如果你说这个函数没返回subtree的"root",是有这个问题。但是，对于sum值，是没问
题的。和peking2一样的啊。而且算法关键是recursive就行了啊。
对于包子，我也不在乎。但是我是前几个发帖子的，而且实现给了关键点了啊，怎么着
，我要个包子，我是理直气壮的吧。

【在 l*****a 的大作中提到】

: 不work
: why 包子

r*12012-01-18 08:01

44 楼

我又看了一遍，这段就是对叶子节点的直接处理，避免了进一步的call。我不觉的这
样有啥不妥的。

【在 p*****2 的大作中提到】

: 这段有必要吗？
: if((root->left == NULL) && (root->right == NULL))
: {
: if(root->data > *max)
: *max = root->data;
: return root->data;
: }

p*22012-01-18 08:01

45 楼

如果树大的话，每一个node都要进行判断，会影响performance.当然这不是关键，关键
就是代码看起来不简洁。

【在 r**********1 的大作中提到】

: 我又看了一遍，这段就是对叶子节点的直接处理，避免了进一步的call。我不觉的这
: 样有啥不妥的。