CareerCup

Reading 'Given a n-ary tree' and then seeing 'O(log n)' does not make sense. I presume it must have been 'O(log m)' where m is number of nodes in the tree.
Prashi, could you clarify, please.

I agree with stepan, n doesn't make sense here. It should be 'O(lg m).
If thats the case, you can implement a B+ tree to solve the problem, and keep isLocked as a boolean value for every node to get isLock() in O(1)

Hey , just wanted to know how exactly B+ trees will solve the problem.
lock() or unlock() in O(log m)are to be implemented and going by the
problem statement there is no restriction about the order of locking a node
except that its ancestors or children shouldn't be locked.
So while locking a node , checking for ancestors, assuming father field will
be log m but checking for ancestors will require checking of whole subtree below the node in context which will be of order O(m1) where m1 is no. of nodes in the subtree.
And when m1 = m i.e. root node is to be locked it will be O(m). Thus the complexity of the lock() would be O(log m + m). This can be done by any normal n-ary tree.
Would want to know how exactly is B+ helping to achieve a log(m) solutn ??

Why do u require a O(log n) complexity for unlocking a node.

I don't think we need to check ancestors or subtree for unlocking a node. Am i missing something or i dint understand the question properly?

Why do u require a O(log n) complexity for unlocking a node.

I don't think we need to check ancestors or subtree for unlocking a node. Am i missing something or i dint understand the question properly?

Why do u require a O(log n) complexity for unlocking a node.

I don't think we need to check ancestors or subtree for unlocking a node. Am i missing something or i dint understand the question properly?

Please tell me how the structure for such a node looks like?

I think the structure should look like this:

class Node {
   boolean isLocked;
   Node parent;
   Node[] children;
   int lockedDescendants;
}

isLocked probably looks like this:

public boolean isLocked() {
   return isLocked;
}

Lock probably looks like this:

public boolean lock() {
   if(!isLocked && lockedDescendants <= 0 || !lockedAncestorExists()) {
      incrementAncestors();
      isLocked = true;
   }
}

private boolean lockedAncestorExists() {
   Node current = parent;
   while(current != null) {
      if(current.isLocked) {
         return true;
      } else {
         current = current.parent;
      }
   }
   return false;
}

private void incrementAncestors() {
   Node current = parent;
   while(current != null) {
      current.lockedDescendant++;
      current = current.parent;
   }
}

unlock probably looks like this:

public void unlock() {
   if(isLocked) {
      isLocked = false;
      decrementAncestors();
   }
}

//code decrementAncestors here

i like anony's solution...sounds ok to me...

Here is my solution, let me know if that works?

public class Node
{
Node parent;
Node children[];
int lockSemaphore;
boolean lock;

public boolean isLock() // O(1)
{

return lock;
}

public boolean Lock()
{ //Requirement was to lock in O(log n) but I tried doing in O(1)
// Please let me know if I made any mistake
//Check if Parent is locked Or not
if( parent.isLock() )
{
return false ; //Condition you cannot lock it
}
else
{
//Check other conditions
if(lockSemaphore == 0 )
{
//Indicates none of the child node is locked
//Hence you can lock it
this.parent.semaphoreLock();
return true;
}
else
{
return false;
}
}
}

public void Synchronized semaphoreLock()
{
this.lockSemaphore ++;
}


public void Synchronized semaphoreUNLock()
{
this.lockSemaphore--;
}
}

Explanation:

Every node contains a lockSemaphore variable which indicates number of child nodes locked. Thus whenever a child node tries to lock, it increment the lockSemaphore count of its parent. By this every node can check if any of its child node is locked or not. Similarly unlock() can be implemented in O(1).

Please let me know if this works?

Thanks and Regards,

this can be solved using a design similar to huffman encoding ( dunno if it is exactly like that, didnt verify)

G
   / \
  B   H 
 / \
A   D
   /|\
  C E F

i hope the tree has remained intact with the formatting.

at each level, the node will be identified with a bit representation. there are two representations ( local and global). For every subtree, each node is represented as a bit representation, with the bit width being the number of nodes in that subtree.

Taking the above tree:

G - 1
B - 0
H - 1
A - 0
D - 1
C - 00
E - 01
F - 10

so under local representation, if we take the node B, all its children are identified uniquely. to be identified globally, walk up to the parent with appending the bit representation on its way up.

thus each node will be identified as:

G - 1
B - 10
H - 11
A - 100
D - 101
C - 10100
E - 10101
F - 10110

each node has a map that stores the bitmap that stores the child nodes lock status. now if we were to acquire a lock on say F, update D with the 2nd bit. we next go upto B and identify F with 0110 ( B'id , D's id , F's id) and set the 6th bit. we next go upto G and identify F with 10110 ( G's id B'id D's id F's id) and that bit.

This way lock / unlock will always be O(log N). And checking if the node is locked or not, just check the bit field at each node. <bit_field> & F<bit_field wide> and thus if the result is 0 then it is not locked else it is.

public class BinaryTreeWithLock {
 2     private class BinaryTreeNode {
 3         int val;
 4         boolean locked = false;
 5         BinaryTreeNode parent;
 6         BinaryTreeNode leftChild;
 7         BinaryTreeNode rightChild;
 8         int lockedDescendantCount = 0;
 9     }
10     
11     public boolean is_locked(BinaryTreeNode node) {
12         return node.locked;
13     }
14     public boolean lock(BinaryTreeNode node) {
15         if(is_locked(node)) {
16             return true;
17         }
18         if(!canLockOrUnlock(node)) {
19             return false;
20         }
21         node.locked = true;
22         BinaryTreeNode parentNode = node.parent;
23         while(parentNode != null) {
24             parentNode.lockedDescendantCount += 1;
25             parentNode = parentNode.parent;
26         }        
27         return true;
28     }
29     public boolean unlock(BinaryTreeNode node) {
30         if(!is_locked(node)) {
31             return true;
32         }
33         if(!canLockOrUnlock(node)) {
34             return false;
35         }
36         node.locked = false;
37         BinaryTreeNode parentNode = node.parent;
38         while(parentNode != null) {
39             parentNode.lockedDescendantCount -= 1;
40             parentNode = parentNode.parent;
41         }    
42         return true;
43     }        
44     private boolean canLockOrUnlock(BinaryTreeNode node) {
45         if(node.lockedDescendantCount > 0) {
46             return false;
47         }
48         BinaryTreeNode parentNode = node.parent;
49         while(parentNode != null) {
50             if(parentNode.locked) {
51                 return false;
52             }
53             parentNode = parentNode.parent;
54         }
55         return true;
56     }
57 }

public class BinaryTreeWithLock {
 2     private class BinaryTreeNode {
 3         int val;
 4         boolean locked = false;
 5         BinaryTreeNode parent;
 6         BinaryTreeNode leftChild;
 7         BinaryTreeNode rightChild;
 8         int lockedDescendantCount = 0;
 9     }
10     
11     public boolean is_locked(BinaryTreeNode node) {
12         return node.locked;
13     }
14     public boolean lock(BinaryTreeNode node) {
15         if(is_locked(node)) {
16             return true;
17         }
18         if(!canLockOrUnlock(node)) {
19             return false;
20         }
21         node.locked = true;
22         BinaryTreeNode parentNode = node.parent;
23         while(parentNode != null) {
24             parentNode.lockedDescendantCount += 1;
25             parentNode = parentNode.parent;
26         }        
27         return true;
28     }
29     public boolean unlock(BinaryTreeNode node) {
30         if(!is_locked(node)) {
31             return true;
32         }
33         if(!canLockOrUnlock(node)) {
34             return false;
35         }
36         node.locked = false;
37         BinaryTreeNode parentNode = node.parent;
38         while(parentNode != null) {
39             parentNode.lockedDescendantCount -= 1;
40             parentNode = parentNode.parent;
41         }    
42         return true;
43     }        
44     private boolean canLockOrUnlock(BinaryTreeNode node) {
45         if(node.lockedDescendantCount > 0) {
46             return false;
47         }
48         BinaryTreeNode parentNode = node.parent;
49         while(parentNode != null) {
50             if(parentNode.locked) {
51                 return false;
52             }
53             parentNode = parentNode.parent;
54         }
55         return true;
56     }
57 }

I agree with stepan, n doesn't make sense here. It should be 'O(lg m).
If thats the case, you can implement a B+ tree to solve the problem, and keep isLocked as a boolean value for every node to get isLock() in O(1)

All the solutions given so far are BS. Can someone please give a proper solution with detailed explanation?