Re: [algogeeks] Amazon SDE onsite interview question

[anshu mishra]

explanation:

Node :
lock - that node is locked or not;
lockedDesc - number of descendents locked of that node
left, right,par as name sugest;

unLock():
when we unlock a node than all its ancestor has to decrease its lockedDesc
value by 1.

Lock():
when we lock a node than all its ancestor has to increase its lockedDesc
value by 1.

I hope now it should be clear. :)

-- 
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 from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Amazon SDE onsite interview question

[bharatkumar bagana]

@anush:
we should look at all descendants and ancestors. .. but u 'r looking at pars

In our structure we should have a parent pointer ..
and we should look at all our descendants --- takes O(n) time ..

correct me if I'm wrong ...

On Tue, Sep 20, 2011 at 10:54 AM, anshu mishra wrote:

> for simplicity i am doing it for binary tree (liittle modification)
>
>
> struct node
> {
>  bool lock;
>  int lockedDesc;
>  node *left, *right, *par;
> };
>
> bool Islock(node *cur)
> {
> return cur->bool;
> }
>
> void unLock(node *cur)
> {
>  node *temp;
>  cur->lock = false;
>  temp = cur->par;
>  while (temp != NULL)
>  {
>  temp->lockedDesc--;
>  temp = temp->par;
>  }
> }
>
> bool Lock(node *cur)
> {
>  if (cur->lockedDesc) return false;
>
>  node *temp = cur->par;
>  while (temp != NULL && temp->lock== false)
>  {
>  temp->lockedDesc++;
>  temp = temp->par;
>  }
> if (temp == NULL)
> {
> cur->lock = true;
> return true;
> }
> cur = cur->par;
> while (cur != temp)
> {
> cur->lockedDesc--;
> cur= cur->par;
> }
> return false;
> }
>
>  --
> 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 from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 

**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers <=> Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*


-- 
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 from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Amazon SDE onsite interview question

[anshu mishra]

for simplicity i am doing it for binary tree (liittle modification)

struct node
{
 bool lock;
 int lockedDesc;
 node *left, *right, *par;
};

bool Islock(node *cur)
{
return cur->bool;
}

void unLock(node *cur)
{
 node *temp;
 cur->lock = false;
 temp = cur->par;
 while (temp != NULL)
 {
 temp->lockedDesc--;
 temp = temp->par;
 }
}

bool Lock(node *cur)
{
 if (cur->lockedDesc) return false;
 node *temp = cur->par;
 while (temp != NULL && temp->lock== false)
 {
 temp->lockedDesc++;
 temp = temp->par;
 }
if (temp == NULL)
{
cur->lock = true;
return true;
}
cur = cur->par;
while (cur != temp)
{
cur->lockedDesc--;
cur= cur->par;
}
return false;
}

-- 
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 from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Amazon SDE onsite interview question

[anshu mishra]

for simplicity i doing it for binary tree

struct node
{
 bool lock;
 int lockedDesc;
 node *left, *right, *par;
};

bool Islock(node *cur)
{
return cur->bool;
}

void unLock(node *cur)
{
 node *temp;
 cur->lock = false;
 temp = cur->par;
 while (temp != NULL)
 {
 temp->lockedDesc--;
 temp = temp->par;
 }
}

bool Lock(node *cur)
{
 if (cur->anydesc) return false;
 node *temp = cur->par;
 while (temp != NULL && temp->lock== false)
 {
 temp->lockedDesc++;
 temp = temp->par;
 }
if (temp == NULL)
{
cur->lock = true;
return true;
}
cur = cur->par;
while (cur != temp)
{
cur->lockedDesc--;
cur= cur->par;
}
return false;
}

-- 
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 from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Amazon SDE onsite interview question

[saurabh agrawal]

Given an 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. You are 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.