k*******n
发帖数: 190 | 1 public class BinaryTree {
TreeNode root;
Vector path;
public void FindPath() {
if (root!=null) FindPath(root);
};
public void FindPath(TreeNode curNode) {
boolean isLeaf=(curNode.leftNode==null && curNode.rightNode==null);
if (!isLeaf) {
path.add(curNode);
if (curNode.leftNode!=null) FindPath(curNode.leftNode);
if (curNode.rightNode!=null) FindPath(curNode.rightNode);
path.removeElement(curNode);
} else {
path.add(curNode);
... 阅读全帖 |
|
k*******n
发帖数: 190 | 2 public class BinaryTree {
TreeNode root;
Vector path;
public void FindPath() {
if (root!=null) FindPath(root);
};
public void FindPath(TreeNode curNode) {
boolean isLeaf=(curNode.leftNode==null && curNode.rightNode==null);
if (!isLeaf) {
path.add(curNode);
if (curNode.leftNode!=null) FindPath(curNode.leftNode);
if (curNode.rightNode!=null) FindPath(curNode.rightNode);
path.removeElement(curNode);
} else {
path.add(curNode);
... 阅读全帖 |
|
O******i
发帖数: 269 | 3 最近面了一家IT大公司被拒，一共经历了N轮技术面试。自己感觉还不算太坏，但也有
三轮发挥不太完美，所以心里很没底。
结果还是被拒了。
下面是这三轮的详细经历，请大家探讨一下大公司招人的标准。
第i轮是找二叉树从根开始的所有路径，使得该路径上所有节点的值之和等于一个给定
的数。我犯了一个战略错误，因为我在准备过程中看过CarrerCup的更通用的解法，不
要求从根开始，也不要求到叶子结束，于是我直接用了那个思路，在白板上写下了类似
下面的代码
void FindPath(Node* root, int sum, int path[], int level)
{
if (root == NULL)
return;
int s = 0;
for (int i = 0; i < level; i++)
s += path[i];
int value = root->data;
if (s + value == sum)
PrintPath(path, level, value);
path[leve... 阅读全帖 |
|
d*****d
发帖数: 180 | 4 If only two directions are allowed :
findPath(5,0,0,"");
void findPath(int n, int x, int y, String path)
{
if (x==n-1 && y==n-1)
{
System.out.println(path);
return;
}
else if (x>=n || y>=n)
{
return;
}
path+=" ("+x','+y+')';
findPath(n, x, y+1, path);
findPath(n, x+1,y, path);
} |
|
p*****2
发帖数: 21240 | 5 第一题这样可以吗？
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,... 阅读全帖 |
|
c***g
发帖数: 472 | 6 给一定一个binary tree， 给定一个值，然后求出从root开始的和为target value的
path
我这段程序为什么不对呢？
void
Tree::findPath(Node* head, int sum, int path[], int level){
if(head == NULL) return;
if(sum == 0) {
for(int i = 0 ; i < level; i++)
std::cout<
} else {
path[level] = head->value;
findPath(head->left, sum - head->value, path, level+1);
findPath(head->right, sum - head->value, path, level+1);
}
} |
|
c***g
发帖数: 472 | 7 改了一下，这下似乎对了
void
Tree::findPath(Node* head, int sum, int path[], int level){
if(head == NULL || sum < head->value ) return;
sum = sum - head->value;
path[level] = head->value;
level++;
if(sum == 0) {
for(int i = 0 ; i < level; i++)
std::cout<
std::cout<
}
findPath(head->left, sum, path, level);
findPath(head->right, sum, path, level);
} |
|
k*******2
发帖数: 84 | 8 Not sure whether it is right;
I think the space cost is O(log(n));
The time cost seems to be hard to analyze; But I think it ll not be O(n^3);
#define tr(c, i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i+
+ )
unordered_map > findPath(TreeNode *root, int sum)
{
unordered_map > sumAtRoot;
if(root == NULL)
return sumAtRoot;
unordered_map > sumAtLeft = findPath(root->left, sum);
unordered_map阅读全帖 |
|
j*****y
发帖数: 1071 | 9 写了一个 code ,不过需要 O((log n)) 的 extra space
first get k = log n;
int * findPath(int A[], int start, int end, int & size)
{
if(start == end)
{
int *result = new int[k];
result[0] = A[start];
size = 1;
return result;
}
int mid = (start + end) / 2;
int size1 = 0, size2 = 0;
int *left = findPath(A, start, mid, size1);
int *right = findPath(A, mid + 1, end, size2);
if(left[0] > right[0])
... 阅读全帖 |
|
m*******t
发帖数: 1060 | 10 A simple solution as shown below.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class PathFinder {
private static void printPath(List path) {
for (int i = 0; i < path.size(); i++) {
System.out.format("%2d", path.get(i));
if (i != path.size() - 1)
System.out.print("->");
else
System.out.println();
}
}
private boolean shouldSkip(List阅读全帖 |
|
z******w
发帖数: 36 | 11 用dfs的方法实现了一下，dfs有些改动，需要记录当前栈内已经访问的节点，发现当前点和路
径不符立即返回false，否则递归处理相邻的元素。一旦发现路径走完立即返回true
-----------------------------
import java.util.HashSet;
import java.util.Set;
public class FindPath {
public boolean findPath(String[] m, String path) {
if (path.length() == 0) return true;
for (int i = 0; i < m.length; i ++) {
for (int j = 0; j < m[0].length(); j ++) {
Set set = new HashSet();
if (dfs(m, i, j, path, 0, set))
return true;
}
}
return false;
}
private boolean dfs(String[] m, int ... 阅读全帖 |
|
w****x
发帖数: 2483 | 12 面试官第二题的考点是什么???
如果是RPC: bool GetIndex(int x, int y),
这个RPC是由比如master机器映射到不同机器上读取数据, 主要问题是Map太大了不能放
到一台机器上??
如果考分布式计算那么每台计算机计算一个block, 给每个block的端口编号, 每个编号
不同从 1...n, 然后计算所有两两之间的通路, 然后再把block连起来??
如果是这样的话既然不同block的端口不一样, 那么知道端口号也知道了block号, 也知
道这两点间怎么走.
把所有的端口到端口的pair混在一起来做一个3元组PORT_PATH:
1. 根据start point 和 end point 找到最近的端口ptBeg & ptEnd, 问题就是在<
port1, port2, path>这一堆3元组中找到通路让ptBeg ..... --> ptEnd
2. bool FindPath(int ptBeg, int ptEnd, map> mp, bRec[
n])
... 阅读全帖 |
|
h*******0
发帖数: 68 | 13 I have a solution which takes about 50 seconds for the 8x7 matrix. The brute
force recursive DFS takes more than 200 minutes on the same machine. The C+
+ code is given below.
[root@cli-linux ~]# ./findPaths
Searching...
Total 301716 paths found in 53 seconds. |
|
h***o
发帖数: 30 | 14 先检查sum是否为0就对了
给一定一个binary tree， 给定一个值，然后求出从root开始的和为target value的
path我这段程序为什么不对呢？voidTree::findPath(No........
★ Sent from iPhone App: iReader Mitbbs Lite 7.39 |
|
b********s
发帖数: 1676 | 15 没看懂，还是多谢code了。测试了一下，貌似second max不对。。。不管k换成3还是4
，都给第一个72，第二个是69，第三个是70.
int main()
{
int a[10]={39,31,34,53,24,70,42,69,72,44};
int *p;
int size = 0;
p = findPath(a,0,10,size);
cout<<"max="<
cout<<"second max="<
cout<<"p[3]="<
cout<<"p[4]="<
getchar();
return 1;
} |
|
