@Dufus.
if d is locked then only b,a,g,h cannot be locked .But
c,f,e,i,j can be locked.
On Sun, Aug 30, 2009 at 1:41 PM, Dufus<[email protected]> wrote:
>
> 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
-~----------~----~----~----~------~----~------~--~---
