FREE C PROGRAMS

Data Structures and C Programming

  DATA STRUCTURES USING C

 HOME PAGE

Data Structures Interview Questions

Pg : 1 , 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14

"Programming is an art form that fights back"

Data Structures Interview Questions - Page 4

What are the difference between a stack and a Queue?


Stack – Represents the collection of elements in Last In First Out order.
Operations includes testing null stack, finding the top element in the stack, removal of top most element and adding elements on the top of the stack.
Queue - Represents the collection of elements in First In First Out order.
Operations include testing null queue, finding the next element, removal of elements and inserting the elements from the queue.
Insertion of elements is at the end of the queue
Deletion of elements is from the beginning of the queue

If given a singly linked list …How will you find the n-th node from the back.?



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

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

Since both solutions take O(n) time but ans 2 is better. Here’s the code

typedef struct _node
{
int i;
struct _node *next;
} Node;

Node * FindNthFromBack(Node *listHead, int n)
{
Node *ptr1, *ptr2;
ptr1 = ptr2 = listHead;

while(ptr1->next != NULL)
{
if(n > 0)
{
ptr1 = ptr1->next;
n--;
}
else
{
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
}
return ptr2;
}
 

---------------------------------------------------------------------------------------