Data Structure Algorithms Interview Questions And Answers - FAQ

Classify the Hashing Functions based on the various methods by which the key value is found.

2009-08-23T04:40:00.000-07:00

 Direct method,  Subtraction method,  Modulo-Division method, Digit-Extraction method, Mid-Square method, Folding method, Pseudo-random method.

What is the data structures used to perform recursion?

2009-08-22T04:39:00.000-07:00

Stack. Because of its LIFO (Last In First Out) property it remembers its ‘caller’ so knows whom to return when the function has to return. Recursion makes use of system stack for storing the return addresses of the function calls. Every recursive function has its equivalent iterative (non-recursive) function. Even when such equivalent iterative procedures are written, explicit stack is to be used.

Minimum number of queues needed to implement the priority queue?

2009-08-21T04:39:00.000-07:00

Two. One queue is used for actual storing of data and another for storing priorities.

What is a spanning Tree?

2009-08-19T04:38:00.000-07:00

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.

Given a binary search tree and a "target" value, search the tree to see if it contains the target.

2009-08-18T04:36:00.000-07:00

static int lookup(struct node* node, int target) { // 1. Base case == empty tree // in that case, the target is not found so return false if (node == NULL) { return(false); } else { // 2. see if found here if (target == node->data) return(true); else { // 3. otherwise recur down the correct subtree if (target <>data) return(lookup(node->left, target)); else return(lookup(node->right, target)); } }}

Given a binary search tree and a "target" value, search the tree to see if it contains the target.

2009-08-17T04:36:00.000-07:00

Generate a Mirror Image of a tree. Change a tree so that the roles of the left and right pointers are swapped at every node

2009-08-16T04:33:00.000-07:00

void mirror(struct node* node) {
if (node==NULL) {
return;
}
else {
struct node* temp; // do the subtrees
mirror(node->left); mirror(node->right); // swap the pointers in this node
temp = node->left;
node->left = node->right;
node->right = temp;
}
}

finding Nth Node in linked list..

2009-08-15T04:28:00.000-07:00

int GetNth(struct node* head, int index) {
struct node* current = head; int count = 0; // the index of the node we're currently looking at while (current != NULL) { if (count == index) return(current->data); count++; current = current->next; } assert(0); // if we get to this line, the caller was asking // for a non-existent element so we assert fail.}

Source code for Binary search method

2009-08-14T04:25:00.000-07:00

int binarySearch(int value) {
low = 0; high = N; while (low < mid =" (low" low =" mid" high =" mid-1:">= value, //so high can't be < mid if A[mid] == value high = mid; } // high == low, using high or low depends on taste if (low < N) and (A[low] == value) return low // found else return -1 // not found
}

Deletion of linked list

2009-08-13T04:22:00.000-07:00

void DeleteList(struct node** headRef) {
struct node* current = *headRef; // deref headRef to get the real
headstruct node* next;
while (current != NULL) {
next = current->next; // note the next pointer
free(current); // delete the node
current = next; // advance to the next node
}
*headRef = NULL; // Again, deref headRef to affect the real head back// in the caller.
}

Sorting Techniques with Algorithm analysis

2009-01-02T03:34:00.000-08:00

Heap Sort

Algorithm Analysis

The heap sort is the slowest of the O(n log n) sorting algorithms, but unlike the merge and quick sorts it doesn't require massive recursion or multiple arrays to work. This makes it the most attractive option for very large data sets of millions of items.

The heap sort works as it name suggests - it begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the sorted array. After removing the largest item, it reconstructs the heap and removes the largest remaining item and places it in the next open position from the end of the sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays - one to hold the heap and the other to hold the sorted elements.

To do an in-place sort and save the space the second array would require, the algorithm below "cheats" by using the same array to store both the heap and the sorted array. Whenever an item is removed from the heap, it frees up a space at the end of the array that the removed item can be placed in.

Pros: In-place and non-recursive, making it a good choice for extremely large data sets.
Cons: Slower than the merge and quick sorts.

As mentioned above, the heap sort is slower than the merge and quick sorts but doesn't use multiple arrays or massive recursion like they do. This makes it a good choice for really large sets, but most modern computers have enough memory and processing power to handle the faster sorts unless over a million items are being sorted.

The "million item rule" is just a rule of thumb for common applications - high-end servers and workstations can probably safely handle sorting tens of millions of items with the quick or merge sorts. But if you're working on a common user-level application, there's always going to be some yahoo who tries to run it on junk machine older than the programmer who wrote it, so better safe than sorry.

Source Code
Below is the basic heap sort algorithm. The siftDown() function builds and reconstructs the heap.

void heapSort(int numbers[], int array_size)

  int i, temp;

  for (i = (array_size / 2)-1; i >= 0; i--)

    siftDown(numbers, i, array_size);

  for (i = array_size-1; i >= 1; i--)

    temp = numbers[0];

    numbers[0] = numbers[i];

    numbers[i] = temp;

    siftDown(numbers, 0, i-1);

void siftDown(int numbers[], int root, int bottom)

  int done, maxChild, temp;

  done = 0;

  while ((root*2 <= bottom) && (!done))

    if (root*2 == bottom)

      maxChild = root * 2;

    else if (numbers[root * 2] > numbers[root * 2 + 1])

      maxChild = root * 2;

    else

      maxChild = root * 2 + 1;

    if (numbers[root] <>    {
      temp = numbers[root];
      numbers[root] = numbers[maxChild];
      numbers[maxChild] = temp;
      root = maxChild;
    }
    else
      done = 1;
  }
}

Quick Sort

Algorithm Analysis

The quick sort is an in-place, divide-and-conquer, massively recursive sort. As a normal person would say, it's essentially a faster in-place version of the merge sort. The quick sort algorithm is simple in theory, but very difficult to put into code (computer scientists tied themselves into knots for years trying to write a practical implementation of the algorithm, and it still has that effect on university students).

The recursive algorithm consists of four steps (which closely resemble the merge sort):

If there are one or less elements in the array to be sorted, return immediately.
Pick an element in the array to serve as a "pivot" point. (Usually the left-most element in the array is used.)
Split the array into two parts - one with elements larger than the pivot and the other with elements smaller than the pivot.
Recursively repeat the algorithm for both halves of the original array.

The efficiency of the algorithm is majorly impacted by which element is choosen as the pivot point. The worst-case efficiency of the quick sort, O(n²), occurs when the list is sorted and the left-most element is chosen. Randomly choosing a pivot point rather than using the left-most element is recommended if the data to be sorted isn't random. As long as the pivot point is chosen randomly, the quick sort has an algorithmic complexity of O(n log n).

Pros: Extremely fast.
Cons: Very complex algorithm, massively recursive.

The quick sort is by far the fastest of the common sorting algorithms. It's possible to write a special-purpose sorting algorithm that can beat the quick sort for some data sets, but for general-case sorting there isn't anything faster.

As soon as students figure this out, their immediate implulse is to use the quick sort for everything - after all, faster is better, right? It's important to resist this urge - the quick sort isn't always the best choice. As mentioned earlier, it's massively recursive (which means that for very large sorts, you can run the system out of stack space pretty easily). It's also a complex algorithm - a little too complex to make it practical for a one-time sort of 25 items, for example.

With that said, in most cases the quick sort is the best choice if speed is important (and it almost always is). Use it for repetitive sorting, sorting of medium to large lists, and as a default choice when you're not really sure which sorting algorithm to use. Ironically, the quick sort has horrible efficiency when operating on lists that are mostly sorted in either forward or reverse order - avoid it in those situations.

Source Code
Below is the basic quick sort algorithm.

void quickSort(int numbers[], int array_size)

  q_sort(numbers, 0, array_size - 1);

void q_sort(int numbers[], int left, int right)

  int pivot, l_hold, r_hold;

  l_hold = left;

  r_hold = right;

  pivot = numbers[left];

  while (left <>  {
    while ((numbers[right] >= pivot) && (left <>      right--;
    if (left != right)
    {
      numbers[left] = numbers[right];
      left++;
    }
    while ((numbers[left] <= pivot) && (left <>      left++;
    if (left != right)
    {
      numbers[right] = numbers[left];
      right--;
    }
  }
  numbers[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left <>    q_sort(numbers, left, pivot-1);
  if (right > pivot)
    q_sort(numbers, pivot+1, right);
}

Merge Sort

Algorithm Analysis

The merge sort splits the list to be sorted into two equal halves, and places them in separate arrays. Each array is recursively sorted, and then merged back together to form the final sorted list. Like most recursive sorts, the merge sort has an algorithmic complexity of O(n log n).

Elementary implementations of the merge sort make use of three arrays - one for each half of the data set and one to store the sorted list in. The below algorithm merges the arrays in-place, so only two arrays are required. There are non-recursive versions of the merge sort, but they don't yield any significant performance enhancement over the recursive algorithm on most machines.

Pros: Marginally faster than the heap sort for larger sets.
Cons: At least twice the memory requirements of the other sorts; recursive.

The merge sort is slightly faster than the heap sort for larger sets, but it requires twice the memory of the heap sort because of the second array. This additional memory requirement makes it unattractive for most purposes - the quick sort is a better choice most of the time and the heap sort is a better choice for very large sets.

Like the quick sort, the merge sort is recursive which can make it a bad choice for applications that run on machines with limited memory.

Source Code
Below is the basic merge sort algorithm.

void mergeSort(int numbers[], int temp[], int array_size)

  m_sort(numbers, temp, 0, array_size - 1);

void m_sort(int numbers[], int temp[], int left, int right)

  int mid;

  if (right > left)

    mid = (right + left) / 2;

    m_sort(numbers, temp, left, mid);

    m_sort(numbers, temp, mid+1, right);

    merge(numbers, temp, left, mid+1, right);

void merge(int numbers[], int temp[], int left, int mid, int right)

  int i, left_end, num_elements, tmp_pos;

  left_end = mid - 1;

  tmp_pos = left;

  num_elements = right - left + 1;

  while ((left <= left_end) && (mid <= right))

    if (numbers[left] <= numbers[mid])

      temp[tmp_pos] = numbers[left];

      tmp_pos = tmp_pos + 1;

      left = left +1;

    else

      temp[tmp_pos] = numbers[mid];

      tmp_pos = tmp_pos + 1;

      mid = mid + 1;

  while (left <= left_end)

    temp[tmp_pos] = numbers[left];

    left = left + 1;

    tmp_pos = tmp_pos + 1;

  while (mid <= right)

    temp[tmp_pos] = numbers[mid];

    mid = mid + 1;

    tmp_pos = tmp_pos + 1;

  for (i=0; i <= num_elements; i++)

    numbers[right] = temp[right];

    right = right - 1;

How do you reverse a singly linked list? How do you reverse a doubly linked list? Write a C program to do the same.

2008-12-09T21:03:00.000-08:00

This is THE most frequently asked interview question. The most!.

Singly linked lists

Here are a few C programs to reverse a singly linked list.

Method1 (Iterative)

#include

// Variables

typedef struct node

{

int value;

struct node *next;

}mynode;

// Globals (not required, though).

mynode *head, *tail, *temp;

// Functions

void add(int value);

void iterative_reverse();

void print_list();

// The main() function

int main()

{

head=(mynode *)0;

// Construct the linked list.

add(1);

add(2);

add(3);

//Print it

print_list();

// Reverse it.

iterative_reverse();

//Print it again

Q: Write a program base on user inputs wich performs these three functions:

2008-11-12T22:26:00.000-08:00

( 01 ) Check for Plindrome by using stack
( 02 ) convert singlty link list to a doubly link list
( 03 ) Insert elements in queue and then find and delete the target element

#include
#include
void STACK();
void doubly_link_list();
void Qeue();
#define size 100
int queue[size];
int rear=0;
void insert();
void del();
void Show();
const int SIZE=10000;
static char stack[SIZE];
int top=0;
void push(int c);
void show();
int w;
typedef struct item
{
int val;
item*prev;
int data;
item*next;
}item;
void main()
{
int choice;
cout<<"ENTER YOUR CHOICE \n\t1->Plindrome by using stack";
cout<<"\n\t2->Doubly link list \n\t3->Queue\n\t4->exit\n";
cout<<"YOUR CHOICE---> ";
cin>>choice;
while(choice)
{
switch(choice)
{
case 1:STACK();
break;
case 2:doubly_link_list();
break;
case 3:Qeue();
break;
case 4:
exit(0);
break;
default:
cout<<"\nINVALID OPTION!!!!!!!!!!!\n\n"; } cout<<"ENTER YOUR CHOICE \n\t1->Plindrome by using Stack \n\t2->Doubly link list \n\t3->Queue\n\t4-
>exit\n";
cout<<"\tYOUR CHOICE---> ";
cin>>choice;
};
}
////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////
void STACK()
{
char word[SIZE];
int i;
cout<<"NUMBER OF CHARACTERS IN YOUR WORDS ARE: "; cin>>w;
cout<<"NOW ENTER WORD OF "<<<" CHARACTERS: \n"; for(i=0;i<<"CHAR NO "<<<" "; cin>>word[i];
}
char temp;
for(i=0;i<<"YES IT IS A PALINDROM\n"; } else { cout<<"NO IT IS NOT A PALINDROM\n"; } } void push(int c) { stack[top]=c; top++; } void show() { if(top<=0) {cout<<"STACK is empty \n";} else cout<<"THE WORD IN STACK IS: "; for(int i=0;i<<<"\n\n"; } //////////////////////////////////////////////// /////////////////////////////////////////////// void doubly_link_list() { int i,n; item*head; item*curr; curr=new item; head=curr; head->next=NULL;
item*link;
link=new item;
link->prev=NULL;
cout<<"Enter numbers of nodes: "; cin>>n;
if(n<=0) { cout<<"NOT POSSIBLE \n"; } else { for(i=1;i<=n;i++) { curr=new item; link=new item; cout<<"ENTER INTEGER: "; cin>>curr->val;
cout<<"\n NODE NUMBER "<<<" \n"; cout<<"BY USING SINGL LINK LIST ----->"<val<<" \n\n"; link->data=curr->val;
cout<<"BY USING DOUBLY LINK LIST----->"<data<<" \n\n"; link->next=link;
link->prev=link->next;
curr->next=curr;
}
curr->next=NULL;
link->next=NULL;
}
}
//////////////////////////////////////////////
//////////////////////////////////////////////
void Qeue()
{
int option;
cout<<"\nENTER 1->Insert 2->Delete 3->Show 4->Go back to main() ";
cin>>option;
while(option)
{
switch(option)
{
case 1:insert();
break;
case 2:del();
break;
case 3:Show();
break;
case 4:main();
break;
default:cout<<"Invalid option!!!"; } cout<<"\nENTER 1->Insert 2->Delete 3->Show 4->Go back to main() ";
cin>>option;
};
}
void insert()
{
if(rear>=(size-1))
{
cout<<"Queue is full\n\n"; } cout<<"Enter element: "; cin>>queue[rear];
if(rear==(size-1))
{
cout<<"\nQueue is full\n\n"; } else rear++; } void Show() { if(rear==0) { cout<<"queue is empty\n"; } else for(int i=0;i<<" "<<<"queue is empty\n"; } cout<<"Enter element to delete "; cin>>search;
for(int j=0;j
{ if(search==queue[j])
{
cout<<"ELEMENT FOUND AT POSITION "<<<"\n"<<"AND HAS BEEN DELETED "<
queue[j]=0;
for(int k=0;k
{
if(j<=k)
{
queue[k]=0;
}
}rear--;
break;
}
}}