Data Structure Interview Questions | C/C++ Data Structures Interview Questions

C/C++ Data Structures Interview Question:

1.How to create a copy of a linked list?

Ans:

 
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));
    } }

2.What are the advantages and disadvantages of B-star trees over Binary trees?
Ans:A1 B-star trees have better data structure and are faster in search than Binary trees, but it’s harder to write codes for B-start trees.

3.Linked List: Find n-th element from the tail

Question: Given a singly linked list find the n-th node from the back.

Solution 1: Reverse the linked list and select the n-th node from the head of the linked list.

Solution 2: Maintain 2 pointers n nodes apart. When the 1st pointer reaches the tail, the second pointer will be pointing to the desired node.

Notes: Both solutions take O(n) time but Solution 2 is more elegant.

Code:

//define the list node
typedef struct _node
{
 int i;
 struct _node *next;
} Node;
 
Node * FindNthFromBack(Node *listHead, int n)
{
    Node *ptr1, *ptr2;  // we need 2 pointers
    ptr1 = ptr2 = listHead; // set the pointers to point to the list head initially
 
    while(ptr1->next != NULL) // keep looping until we reach the tail (next will be NULL for the last node)
    {
        if(n > 0)
        {
            ptr1 = ptr1->next; //increment only the 1st pointer
            n--;
        }
        else
        {
            ptr1 = ptr1->next; //increment both pointers
            ptr2 = ptr2->next;
        }
    }
    return ptr2;    //now return the ptr2 which points to the nth node from the tail
}

4.Linked List: Find the middle element

Solution 1: Walk the linked list to find the length of the list. Lets say n is the length of the list. Walk the list again upto ⌊ n/2 ⌋.

Solution 2: Use two pointers. Move one pointer at twice the speed of the second. When the 1st pointer reaches the end of the list, the 2nd pointer will be pointing to the middle node. Note: If the list has even number of nodes, the middle node will be floor of ⌊ n/2 ⌋.

Code:

Node * FindMiddle(Node *listHead)
{
  Node *ptr1, *ptr2;  // we need 2 pointers
  ptr1 = ptr2 = listHead; // set the pointers to point to the list head initially
 
  int i=0;
 
  while(ptr1->next != NULL) // keep looping until we reach the tail
                              // (next will be NULL for the last node)
  {
      if(i == 0)
      {
          ptr1 = ptr1->next; //increment only the 1st pointer
          i=1;
      }
      else if( i == 1)
      {
          ptr1 = ptr1->next; //increment both pointers
          ptr2 = ptr2->next;
          i = 0;
      }
  }
  return ptr2;        //now return the ptr2 which points to the middle node
}

JAVA Data Structures:

1.What are the steps to inserting a new item at the head of a linked list? Use one short English sentence for each step.
Solutions:Make a temporary IntNode variable called temp refer to a newly allocated node. Fill in the data of the new node. Make the link field of the new node equal to the old head pointer. Make the head pointer refer to the new node.
2.What is a spanning Tree? Does the minimum spanning tree of a graph give the shortest distance between any 2 specified nodes?
Solutions:A spanning tree is a tree associated with a network. All the nodes of the graph appear on the tree once. A minimum spanning tree is a spanning tree organized so that the total edge weight between nodes is minimized. Minimal spanning tree assures that the total weight of the tree is kept at its minimum. But it doesn’t mean that the distance between any two nodes involved in the minimum-spanning tree is minimum.

Click Here To More Data Structure Interview Questions

If you have questions, please ask below

One Comment


  1. kapil chauhan says:

    What is B_star tree?

Leave a Reply

If you have any questions headover to our forums

You can use these XHTML tags: <a href="" title=""> <abbr title=""> <acronym title=""> <blockquote cite=""> <code> <em> <strong>