Friday, August 24, 2012

Adobe Written Test



Q1. Lowest Common Ancestor of a Binary Search Tree :
There’s only three cases you need to consider.
  1. Both nodes are to the left of the tree.
  2. Both nodes are to the right of the tree.
  3. One node is on the left while the other is on the right.
For case 1), the LCA must be in its left subtree. Similar with case 2), LCA must be in its right subtree. For case 3), the current node must be the LCA.
Therefore, using a top-down approach, we traverse to the left/right subtree depends on the case of 1) or 2), until we reach case 3), which we concludes that we have found the LCA.
Node *LCA(Node *root, Node *p, Node *q) {
  if (!root || !p || !q) return NULL;
  if (max(p->data, q->data) < root->data)
    return LCA(root->left, p, q);
  else if (min(p->data, q->data) > root->data)
    return LCA(root->right, p, q);
  else
    return root;
}
Q2. Given a string of 0's & 1's complement . Return a string which is its 2's complement . To calculate 2's complement :
  1. invert the bits
  2. Add 1
Code :

char * TwoComplement(char a[])
{
int l = strlen(a);
char *b = malloc(l);
for(int i=0;i<l;i++)
{
  if(a[i]==0)
    {
     b[i]=1;
    }
  else
    {
     b[i]=0;
    }
}
int carry=1;
for(int i=0;i<l;i++)
{
  if(carry=='1')
   {
    if(b[i]=='0')
    {
      b[i]='1';
      carry='0';
    }
    else
    {
      b[i]='0';
      carry='1';
    }
   }
}
if(carry=='1')
 {
  realloc(b,l+2);
  memmove(b+1,b,strlen(b));
  b[0]=1;
 }
return b;
}

Q3:  GCD of two numbers using Recursion .

Code
// a>=b
int gcd(int a,int b)
{
   if(b==0)
     return a;
   else
     return gcd(b, a%b);
}

Q4 : A array of size (n-1) is filled with 1 to n numerals and only one of these r missing (no repetetion).Find the missing number in 1 traversal of array.

int find(int a[])
{ 
   int temp = 1;
   for(int i=1;i<=n;i++)
     temp&=i;
   for(int i=0;i<n-1;i++)
     temp&=i;
   return temp;
}

Q5 : Find half of a linked list in single traversal.

Node hasLoop(Node *head) {
  Node *slow = head, *fast = head;
  while (slow && fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
  }
  return slow;
}

Q6: Reverse a doubly linked list

void reverse(struct node **head)
{
     struct node *temp = NULL;  
     struct node *current = *head;
     while (current !=  NULL)
     {
       temp = current->prev;
       current->prev = current->next;
       current->next = temp;              
       current = current->prev;
     }      
     if(temp != NULL )
        *head = temp->prev;
}

1 comments:

Julia David said...

What a nice blog...I am really very impressed to read this..Thanks to admin for posting this nice blog....WOW!!!!!
access Mp3lemon in UK

Post a Comment

Total Pageviews

Print