Data Structures Questions and Answers for Technical Interviews Part-1

Q: What are the major data structures used in the following areas : RDBMS, Network data model and Hierarchical data model.

A:

1. RDBMS = Array (i.e. Array of structures)
2. Network data model = Graph
3. Hierarchical data model = Trees

Q: What are the major data structures used in the following areas : RDBMS, Network data model and Hierarchical data model.

A:

1. RDBMS = Array (i.e. Array of structures)
2. Network data model = Graph
3. Hierarchical data model = Trees

Question: What is almost complete binary tree?.

Answer:An almost complete binary tree is a tree in which each nodethat has a right child also has a left child. Having a left child does not require a node to have a right child. Stated alternately, an almost complete binary tree is a tree where for a right child, there is always a left child, but for a left child there may not be a right child.The number of nodes in a binary tree can be found using this formula: n = 2^h Where n is the amount of nodes in the tree, and h is the height of the tree.

Question:

Given two numbers m and n, write a method to return the first number r that is
divisible by both (e.g., the least common multiple).

Answer:

The Approach:
What does it mean for r to be divisible by m and n? It means that all the primes in m must go into r, and all primes in n must be in r. What if m and n have primes in common?

For example, if m is divisible by 3^5 and n is divisible by 3^7, what does this mean about r? It means r must be divisible by 3^7.

The Rule: For each prime p such that p^a \ m (e.g., m is divisible by p^a) and p^b \ n, r must be divisible by p^max(a, b)

The Algorithm:
Define q to be 1.
for each prime number p less than m and n:
find the largest a and b such that p^a \ m and p^b \ n
let q = q * p^max(a, b)
return q

Q How would you check if a binary tree is balanced?

Solution:


A tree is considered balanced when the difference between the min depth and max depth does not exceed 1.
Recursive algorithms always work well on trees, so here’s some code.

int min_depth( Node * root ) {

    if( !root ) {

        return 0;

    }

    return 1 + min( min_depth( root->left ),

                    min_depth( root->right ));

}



int max_depth( Node * root ) {

    if( !root ) {

        return 0;

    }

    return 1 + max( max_depth( root->left ),

                            max_depth( root->right ));

} 



bool is_balanced( Node * root ) {

    return ( max_depth( root ) - min_depth( root ) ) <= 1

}

Q: Write a C program to delete a tree (i.e, free up its nodes)

Solutions:
 

clear(struct node* pNode)
{
if (pNode != NULL)
{
clear(pNode->left);
clear(pNode->right);
delete pNode;
}
}

Q Write a C program to determine the number of elements (or size) in a tree.

Solution:

int tree_size(struct node* node)  {
  if (node==NULL)
  {
    return(0);
  }
  else
  {
    return(tree_size(node->left) + tree_size(node->right) + 1);
  }  }

Q Write a C program to find the depth or height of a tree.


Solution:
  
tree_height(mynode *p) {
   if(p==NULL)return(0);
   if(p->left){h1=tree_height(p->left);}
   if(p=>right){h2=tree_height(p->right);}
   return(max(h1,h2)+1); }



The degree of the leaf is zero. The degree of a tree is the max of its element degrees. A binary tree of height n, h > 0, has at least h and at most (2^h -1) elements in it. The height of a binary tree that contains n, n>0, elements is at most n and atleast log(n+1) to the base 2.

Log(n+1) to the base 2 = h

n = (2^h - 1)




Q How to create a copy of a linked list? Write a C program to create a copy of a linked list.
copy_linked_lists(struct node *q, struct node **s) {
    if(q!=NULL)
    {
        *s=malloc(sizeof(struct node));
        (*s)->data=q->data;
        (*s)->link=NULL;
        copy_linked_list(q->link, &((*s)->link));
    } }

Q How to compare two linked lists? Write a C program to compare two linked lists.
int compare_linked_lists(struct node *q, struct node *r) {
    static int flag;
   
    if((q==NULL ) && (r==NULL))
    {
         flag=1;
    }
    else
    {
        if(q==NULL || r==NULL)
        {
            flag=0;
        }
        if(q->data!=r->data)
        {
            flag=0;
        }
        else
        {
           compare_linked_lists(q->link,r->link);
        }
    }
    return(flag); }
Q If you are using C language to implement the heterogeneous linked list, what pointer type will you use?

The heterogeneous linked list contains different data types in its nodes and we need a link, pointer, to connect them. It is not possible to use ordinary pointers for this. So we go for void pointer. Void pointer is capable of storing pointer to any type as it is a generic pointer type.

Q How would you detect a loop in a linked list? Write a C program to detect a loop in a linked list.

typedef struct node
{
void *data;
struct node *next;
}mynode;

mynode * find_loop(NODE * head)
{
mynode *current = head;
while(current->next != NULL)
{
mynode *temp = head;
while(temp->next != NULL && temp != current)
{
if(current->next == temp)
{
printf("\nFound a loop.");
return current;
}
temp = temp->next;
}
current = current->next;
}
return NULL;
}

Q How do you find the middle of a linked list? Write a C program to return the middle of a linked list

#include
#include
typedef struct node
{
int value;
struct node *next;
struct node *prev;
}mynode; 

void add_node(struct node **head, int value);
void print_list(char *listName, struct node *head);
void getTheMiddle(mynode *head);

int main()
{
mynode *head;
head = (struct node *)NULL;
add_node(&head, 1);
add_node(&head, 10);
add_node(&head, 5);
add_node(&head, 70);
add_node(&head, 9);
add_node(&head, -99);
add_node(&head, 0);
add_node(&head, 555);
add_node(&head, 55);
print_list("myList", head);
getTheMiddle(head);
getch();
return(0);
}

void getTheMiddle(mynode *head)
{
mynode *p = head;
mynode *q = head;
if(q!=NULL)
{
while((q->next)!=NULL && (q->next->next)!=NULL)
{
p=(p!=(mynode *)NULL?p->next:(mynode *)NULL);
q=(q!=(mynode *)NULL?q->next:(mynode *)NULL);
q=(q!=(mynode *)NULL?q->next:(mynode *)NULL);
}
printf("The middle element is [%d]",p->value);
}
}

void add_node(struct node **head, int value)
{
mynode *temp, *cur;
temp = (mynode *)malloc(sizeof(mynode));
temp->next=NULL;
temp->prev=NULL;
if(*head == NULL)
{
*head=temp;
temp->value=value;
}
else
{
for(cur=*head;cur->next!=NULL;cur=cur->next);
cur->next=temp;
temp->prev=cur;
temp->value=value;
}
}

void print_list(char *listName, struct node *head)


{


mynode *temp;


printf("\n[%s] -> ", listName);


for(temp=head;temp!=NULL;temp=temp->next)
{


printf("[%d]->",temp->value);
}


printf("NULL\n");
}

Q . How do you reverse a linked list without using any C pointers?

Solution:

 One way is to reverse the data in the nodes without changing the pointers themselves. One can also create a new linked list which is the reverse of the original linked list. A simple C program can do that for you. Please note that you would still use the "next" pointer fields to traverse through the linked list (So in effect, you are using the pointers, but you are not changing them when reversing the linked list).

  

Q: How to declare a structure of a linked list?

Solution:

   struct node
{

int value;
struct node *next;

 }; typedef struct node *mynode;