Before I propose my solution I have a query.
Consider the following tree:-
a
/ \
b c
/ \ /
d e f
/ \ /\
g h i j
Initially all the nodes are in unlocked state.
Say user choses to lock node d.
Now by the given condition:-
i) none of its children {g,h} can be locked.
ii) none of the nodes which have d as child (ie. ancestors of d) can
be locked which are {b,a} // Since a node i cannot be locked if any of
its descendant is already locked.
Also note that a is ancestor of all the nodes in the tree, we end up
locking the WHOLE TREE (i.e. once d is locked no other node in the
tree can be locked)!!!
I think something is wrong here.
Nagendra/Priya any comments?
_dufus
On Aug 30, 11:10 am, priya k <[email protected]> wrote:
> @Dufus: You mean to say do preprocessing and hash all the nodes that cannot
> be locked, if am not wrong. And again, Everytime we lock a node, we need to
> update the hash and that would be O(n) worst case. Can we do anything better
> ?
>
> --Priya
>
>
>
> On Sun, Aug 30, 2009 at 10:26 AM, Dufus <[email protected]> wrote:
>
> > Priya, as mentioned by you your isLock() takes O(logn) time.
> > We need to use Hash table as auxillary DS for O(1) query time.
>
> > _dufus
>
> > On Aug 30, 8:35 am, priya k <[email protected]> wrote:
> > > // Data Structure for the n-ary tree
>
> > > struct node
> > > {
> > > int data;
> > > node * child[m];
> > > bool lockFlag; // Indicates if a node is locked or not
> > > node *parent; //Holds the immediate parent of the node
> > > int LockCount; //Holds how many nodes arrested this node
>
> > > };
>
> > > // Takes logm(N) in the worst case
>
> > > bool check(node *NodeToBeLocked)
> > > {
> > > node *m=NodeToBeLocked;
>
> > > if(m->flag==true || m->LockCount>0)
> > > return false; // since the node is already locked or any of its
> > > subtrees already locked, return false
>
> > > while(m && !m->lockFlag)
> > > m=m->parent;
>
> > > if(m && m->lockFlag)
> > > return false; // if any of its ancestors have been already locked
>
> > > return true;
>
> > > }
>
> > > // Takes logm(N) in the worst case
>
> > > bool lock(node *NodeToBeLocked)
> > > {
> > > if(check(NodeToBeLocked)) // If true, Node is free to be locked
> > > {
> > > node *m=NodeToBeLocked;
> > > m->lock=true;
> > > node *prevChild=m;
> > > m=m->parent;
> > > while(m)
> > > {
> > > m->LockCount++;
> > > prevChild=m;
> > > m=m->parent;
> > > }
> > > return true;
> > > }
> > > return false; //err.. cannot be locked
>
> > > }
>
> > > // Takes logm(N) in the worst case
>
> > > bool unlock(node *NodeToBeUnLocked)
> > > {
> > > node *m=NodeToUnBeLocked;
> > > m->lock=false; // Unlock the Node
> > > node *prevChild=m;
> > > m=m->parent;
> > > while(m)
> > > {
> > > m->LockCount--;
> > > prevChild=m;
> > > m=m->parent;
> > > }
>
> > > }
>
> > > Thanks,
> > > Priya
>
> > > On Sat, Aug 29, 2009 at 11:35 PM, nagendra kumar <[email protected]
> > >wrote:
>
> > > > Given a n-ary tree of resources arranged hierarchically. A process
> > > > needs to lock a resource node in order to use it. But,
> > > > A node cannot be locked if any of its descendant or ancestor is
> > > > locked.
> > > > I was supposed to
> > > > -> write the structure of node
> > > > -> write codes for
> > > > -> islock()- returns true if a given node is locked and false if it is
> > > > not
> > > > -> lock()- locks the given node if possible and updates lock
> > > > information
> > > > -> unlock()- unlocks the node and updates information.
> > > > Codes should be :
> > > > Islock –O(1)
> > > > Lock()- O(log n)
> > > > unLock()- O(log n)
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
