Q1. Lowest Common Ancestor of a Binary Search Tree :
There’s only three cases you need to consider.
- Both nodes are to the left of the tree.
- Both nodes are to the right of the tree.
- 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 :
- invert the bits
- Add 1
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 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;
}
