Google 面题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Google 面题

Google 面题# JobHunting - 待字闺中

m*m2012-03-09 08:03

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*b2012-03-09 08:03

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*U2012-03-09 08:03

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*m2012-03-09 08:03

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*b2012-03-09 08:03

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*62012-03-09 08:03

6 楼

1-没大看明白
2- stack
在 musicworm (云淡了风轻) 的大作中提到: 】
entire
~~~~~tree??
have

a*a2012-03-09 08:03

7 楼

1.BST
2.one counter should be enough

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

: 1-没大看明白
: 2- stack
: 在 musicworm (云淡了风轻) 的大作中提到: 】
: entire
: ~~~~~tree??
: have

m*62012-03-09 08:03

8 楼

2.one counter should be enough ~~good!

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

: 1.BST
: 2.one counter should be enough

m*m2012-03-09 08:03

9 楼

another question:
what are the Google products?

y*n2012-03-09 08:03

10 楼

1就是找floor吧。上数据结构的时候讲过- -

m*k2012-03-09 08:03

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";