Amazon Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Stepan December 24, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- anup January 12, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ??

- hardtimes March 09, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- Erik March 20, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- Erik March 20, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- Erik March 20, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Kiran April 04, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous April 28, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'd propose securing the lock/unlock operations using some global lock in order to prevent corruptions due to the race conditions.

Using synchronized lock/unlock you can improve the performance of lock by doing the incrementAncestors and lockedAncestorsExists in a single run (decrementing ancestors if locked ancestor is found on the way)

- ja.ro May 25, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- nerd July 14, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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,

- kunal October 27, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- fragzilla March 10, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 }

- Sharad Pareek December 04, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 }

- sharad December 04, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 0 vote

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)

- anup January 12, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Seema August 31, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How abt u do the honors?

- Anonymous July 28, 2010 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More