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

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.
Data Structure Interview Questions