Amazon Interview Question
Software Engineer / DevelopersBool findelement() rcursively searches and return true if element found under the node
Bool findlocked() recursively checks if anything is locked in this tree
Bool Lock(Node* root, Node* element)
{
If (!findElement(root))
Return false;
Else If(root.isLocked())
{
return false;
}
Else
{
If (root == element)
{
If(findLocked(element)) return false;
Else
{
Element.lockElement(); // whatever is needed to actually lock that element
return true;
}
}
Else
{
Return (lock(root->l, element) || lock(root->r, element));
}
}
If (findElement(root->l, element)!= null )
}
Maintain tree like with argumented information which stores the information whether the node is locked or not ,while searching for a node in the given tree in recursive way if a node is locked , traverse back and update all the ancestors are locked. This can be done in log n time i think.
geekygospel.wordpress.com/2008/06/12/interesting-cs-interview-questions-2/
- Erik May 17, 2010