m*******m
发帖数: 82 | 1 Interview Questions：
１．Given a node in a binary tree find the next greatest value in the entire
node.
２．Given a string with only ')' and '(' find if the string is complete or
not. If the string is complete means that each open paranthesis should have
a corresponding closed one.
Eg: String s= "((()))()"- Complete String
String s1=")()()()())))(()()()((" - Incomplete String |
r*****b
发帖数: 310 | 2 Do not understand the first question well. Any explanation?
Here is my answer to the second question:
http://basicalgos.blogspot.com/2012/03/19-testing-whether-strin
Please give out comments.
entire
have
【在 m*******m 的大作中提到】
: Interview Questions：
: １．Given a node in a binary tree find the next greatest value in the entire
: node.
: ２．Given a string with only ')' and '(' find if the string is complete or
: not. If the string is complete means that each open paranthesis should have
: a corresponding closed one.
: Eg: String s= "((()))()"- Complete String
: String s1=")()()()())))(()()()((" - Incomplete String
|
P*******U
发帖数: 203 | 3 The first one is BST or just binary tree? What do you mean by the next
greatest value? Is it the second largest value?
If BST and next means second largest, then easy.
Node* p=givenNode;
if(p->rightChild==null)
return FindLargestInLeftSubtree();
while(p->rightChild->rightChild!=null)
p=p->rightChild;
return p;
If not BST, you have to traverse the tree?
The second one can be solved with a stack. Once seen a "(", push into
stack;
seen a ")", pop. If the stack is empty when operating pop, return false.
When processed all symbols in the string, if the stack is not empty,
return
false, else return true. |
m*******m
发帖数: 82 | 4 The first question, I guess it is a binary search tree? And does each node
have a parent pointer?
for BST : get the node and find the inorder successor
if(n->right) : find minimum in n->right
else
find parent of n in loop, till n is parent->right :
(n = parent, find parent(n) |
r*****b
发帖数: 310 | 5 As for the second question, a counter should be sufficient. The stack is
not needed.
http://basicalgos.blogspot.com/2012/03/19-testing-whether-strin
【在 P*******U 的大作中提到】
: The first one is BST or just binary tree? What do you mean by the next
: greatest value? Is it the second largest value?
: If BST and next means second largest, then easy.
: Node* p=givenNode;
: if(p->rightChild==null)
: return FindLargestInLeftSubtree();
: while(p->rightChild->rightChild!=null)
: p=p->rightChild;
: return p;
: If not BST, you have to traverse the tree?
|
m******6
发帖数: 82 | 6 1-没大看明白
2- stack
在 musicworm (云淡了风轻) 的大作中提到: 】
entire
~~~~~tree??
have |
a****a
发帖数: 186 | 7 1.BST
2.one counter should be enough
【在 m******6 的大作中提到】
: 1-没大看明白
: 2- stack
: 在 musicworm (云淡了风轻) 的大作中提到: 】
: entire
: ~~~~~tree??
: have
|
m******6
发帖数: 82 | 8
2.one counter should be enough ~~good!
【在 a****a 的大作中提到】
: 1.BST
: 2.one counter should be enough
|
m*******m
发帖数: 82 | 9 another question:
what are the Google products? |
y*****n
发帖数: 243 | 10 1就是找floor吧。上数据结构的时候讲过- - |
m*****k
发帖数: 731 | 11 for Q2:
int sum=0;
for (char c in yourString)
{
if(c=='(')
{
sum++;
}
else
{
sum--;
}
if(sum<0)
{
return "invalid";
}
}
if(sum!=0)
{
return "invalid";
}
return "valid"; |
