I didn't check the correctness of it. I think this is how the count
field might improve the time.
1.Whenever you lock a node, increase the count field of all its
ancestors and the current node by 1.
2.Similarly when you unlock it, decrease the count field of all its
ancestors and the current
So where is the count?
And how it improves the time?
Regards
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe
If it is a B-Tree or similar structure that has a strict key order then this problem can be significantly improved.As suggested in the question keep an m-bit structure in each node. If the i-th bit is set to 1 then node pointed to (i + 1)th pointer cannot be locked. The key idea is to do this
This can be solved by two DFS traversals.The first from the root to the node N. Here you will get the path from root to N. Just go along the path and see whether there is any locked node. If there is a locked node then you cannot lock node N.
Next you do a complete DFS of the subtree starting
hiya thats what i too thought.but the interviewer insisted that theres a better algohe gave a hint as : keep a count in each node, which specifies the number of locks in the subtree rooted at that node
On 3/24/06, Dhyanesh [EMAIL PROTECTED] wrote:
This can be solved by two DFS traversals.The first
Hi All,If I have understood the question correctly, then this will work! DFS is recursive. So even though our tree has no parent pointers, we will get such a 'pointer for free' , due to recursion. (Remember recursion allows you to pass information from child to parent)
So a single highly pruned
Hi all,I think there can be one more solution... where a BFS is folowed by DFS works.Algo 2:IsLockable(Node N){ queue Q; if(root is not locked) Q.insert(root); while(!Q.empty()) {
Node n = Q.removeHead(); if(n == N) return DFS(n); for(each child a of N) If(a is not locked) Q.insert(a); } return
Hi all,The third solution is... (I hope there will not be any fourth ;) )Two BFSs...1. The first BFS will traverse all unlocked nodes (same as solution one)...2. The second BFS will traverse until one locked node is encountered.
Hey, guys... this is boring...It is always possible to convert
