Category: Data Structures


The Whole File: DS Interview

1. What is data structure?

A data structure is a way of organizing data that considers not only the items stored, but also their relationship to each other. Advance knowledge about the relationship between data items allows designing of efficient algorithms for the manipulation of data.

2. List out the areas in which data structures are applied extensively?

  1. Compiler Design,
  2. Operating System,
  3. Database Management System,
  4. Statistical analysis package,
  5. Numerical Analysis,
  6. Graphics,
  7. Artificial Intelligence,
  8. Simulation

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

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

4. 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.

5. Minimum number of queues needed to implement the priority queue?

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

6. What is the data structures used to perform recursion?

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.

7. What are the notations used in Evaluation of Arithmetic Expressions using prefix and postfix forms?

Polish and Reverse Polish notations.

8. Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to equivalent Prefix and Postfix notations.

  1. Prefix Notation: – * +ABC ^ – DE + FG
  2. Postfix Notation: AB + C * DE – FG + ^ –

9. Sorting is not possible by using which of the following methods? (Insertion, Selection, Exchange, Deletion)

Sorting is not possible in Deletion. Using insertion we can perform insertion sort, using selection we can perform selection sort, using exchange we can perform the bubble sort (and other similar sorting methods). But no sorting method can be done just using deletion.

****many more*****

Singly Link List

scan0001 scan0002 scan0003

Continue reading

Facilities of Array:

1.    ARRAY IS RANDOM: Since the elements of array are contiguous, thus any elements of array could be accessed randomly, accession of elements only requires the index of the element and the base address of the array, the address would be calculated using address arithmetic.

2.    ARRAY IS SIMPLE: Array is simple to program with, we don’t need any effort to manage the array in memory, no address manipulation, no additional maintenance is required.

Pitfall of ARRAY:

1.    ALLOCATION NOT GURANTEED: Since array is contiguous allocation thus, in run-time required memory may not be available contiguously for the successful allocation of array. If the no of elements to be processed is huge, then we cannot reply on array, as the allocation may turn into a failure.

2.    POOR MEMORY UTILIZATION: As we need to mention the size of the array while allocating the array, thus in run-time there may be a shortage or wastage of elements.

3.    POOR DYNAMIC BEHAVIOUR: Its tedious to insert or remove elements from an array in run-time…It requires reallocation of the array and copying from the old to new location and thus slows down the whole process.

Facilities Of Linked List:

1.    ALLOCATION OF ELEMENT GURANTEED: In linked list the elements are inserted “AS AND WHEN REQUIRED” basis dynamically, that is, when an element is required to be stored we allocate an element dynamically and insert the element into the linked list. Thus, if there is sufficient space to store at least one element, we can allocate an element.

2.    SMART MEMORY UTILIZATION: We do not need to mention the no of elements while starting with a linked list. Dynamically elements could be created and inserted into the linked list, thus as long as memory is available no shortage would be there, and with linked list the is no question of wastage elements. If an element is not required it is removed from the list and the dynamic memory is returned to free-store of the operating system.

3.    SMART MEMORY MANAGEMENT: Elements could be inserted and removed anywhere in the linked list. Only it requires address manipulation.

Pitfall of Linked List:

1.    SEQUENTIAL ACCESS: Each element of linked list contains the address of the next element in the list, as the elements are allocate dynamically in discrete order thus the elements most obviously may not be contiguous in the memory. The head/start pointer of the linked list holds the address of the first element, thus if we need to access the nth element of the linked list we need to traverse all n-1 th elements.

2.    NOT SO SIMPLE: It’s not simple-to-use like data-structure like array. In linked list each specific operation needs to be explicitly written by the programmer, no automatic memory management or manipulation is there for linked list.

Conclusion:

Both array and linked list are suitable data-structure depending on the situation of use and how they are used practically. In array we get the random access of the elements by sacrificing the memory efficiency on the other hand in linked list we have better and efficient utilization of memory but sacrificing the randomness, we need to access the elements in sequence in linked list. Like everywhere, Tradeoff Prevails.

Polish Notation:

Polish notation, also known as PREFIX or POSTFIX notations, is a form of notation for logic, arithmetic, and algebra. Its distinguishing feature is that it places operators to the left (for prefix) /right (for postfix) of their operands. The Polish logician Jan Łukasiewicz invented this notation around 1920 in order to simplify sentential logic.

The facility of POLISH notation is that we can represent a mathematical expression without any parenthesis or other brackets that can still be parsed without any ambiguity.

If we need to evaluate a mathematical expression programmatically then we can convert the expression into either PRE/POST fix notations and then apply the logic on it for evaluation, that reduces the complexity of evaluation code to a large extent as we don’t require to dig-out the task to be evaluated first on the basis of brackets.

Algorithm to evaluate POSTFIX Notation:

Let S is a stack and PUSH and POP operations are well defined on stack S.

S has been initialized properly.

1.     START OPERATION POSTFIX-EVALUATION (STRING POSTFIX)

2.     WHILE NOT END OF POSTFIX STRING LOOP

3.           SYMB:=NEXT ELEMENT OF POSTFIX STRING

4.           IF SYMB IS AN OPERAND THEN

5.               PUSH SYMB INTO THE STACK

6.           ELSE

7.                OPND1:= POP STACK

8.                OPND2:=POP STACK

9.                RESULT:=APPLY OPERATOR SYMB ON OPND1 AND OPND2

10.            PUSH RESULT INTO THE STACK.

11.       END IF

12.  END LOOP.

13.  VALUE:= POP STACK

14.   RETURN VALUE

15.   END OPERATION POSTFIX-EVALUATION.

.

//Algorithm in C style, courtesy “Data Structure with C and C++ by Tanenbaum”

Let stack is a user defined type and there are standard push and pop operations for the stack type.

while (! end of postfix string){

  symb = next element of the postfix string;

  if(symb is an operand)

   push(stack, symb);

 else{

     opnd2 = pop(stack);

     opnd1 = pop(stack);

     result=operate(opnd1,opnd2, symb);   //operate function returns the result of the arithmetical //operation defined by  symb.

    push(stack, symb);

  }    

 return pop(stack);

}

//***********C Implementation of Evaluating a Single digit PostFix Expression***************//

C Implementation of Evaluating PostFix Expression: EvalPostStringSingle

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define SIZE 100
//+++++++++++++++++++Define a stack to hold the operands++++++++++++++//
typedef struct {
double item[SIZE];
int top;
}Stack;

void push(Stack *sp, double value){
if (sp->top == SIZE-1){
printf(“Stack Overflow…xterminating operation\n”);
exit(0);
}
sp->item[++sp->top] = value;
}

double pop(Stack *sp){
if (sp->top == -1){
printf(“Stack Underflow…Terminating operation…”);
exit(0);
}
return sp->item[sp->top–];
}
//++++++++++++END OF STACK DEFINITION+++++++++++++++++//

//**************************Operate function *******************************//

double operate(double left, double right, char opr){
double result=0.0;
switch(opr){
case ‘+’: result=left+right;
break;
case ‘-‘: result=left-right;
break;
case ‘*’: result=left * right;
break;
case ‘/’:result=left/right;
break;
case ‘$’: result=pow(left,right);
break;
default:printf(“Invalid operator encountered…”);
exit(0);

}
return result;
}
//********************END OF OPERATE FUNCTION *********************************//
//58-98*/
double evaluatePostfix(char postfix[]){
Stack s;
int i;
double opnd1, opnd2, result;
char symb;
s.top = -1;
i = 0;
while(postfix[i]!=”){//iterate thru the postfix string till NULL
symb = postfix[i];
if(symb>=48 && symb<=57){
push(&s,(double)(symb-48));
}
else if(symb==’+’ || symb==’-‘ || symb==’*’ || symb==’/’ || symb==’$’){
opnd2 = pop(&s);
opnd1 = pop(&s);
result = operate(opnd1, opnd2,symb);
push(&s, result);
}
else{
printf(“Invalid symbol encountered…\nterminating program…\n”);
exit(0);
}
i++;
}
return pop(&s);
}
////—————————–END EVALUATE FUNCTION———————-//

int main(){
char postfix[SIZE];
printf(“Enter a postfix string: “);
scanf(“%s”,postfix);
printf(“Value of the postfix string: %lf\n”,evaluatePostfix(postfix));
getch();
return 0;
}

//***********C Implementation of Evaluating a Single digit PostFix Expression***************//

. Continue reading

C Implementation of  Handling TWO Stacks simultaneously :- Multiple Stack Handling

/*****C Implementation of  Handling TWO Stacks simultaneously*****/

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

#define size 6

typedef struct
{
int item[size];
int top;
}Stack;

void push(Stack *sp,int val)
{
if(sp->top ==size-1)
printf(“stack overflow\n”);

sp->top++;
sp->item[sp->top]=val;
printf(“the value is pushed\n”);

}

int pop(Stack *sp)
{
int value;

if(sp->top==-1)
//printf(“stact underflow\n”);
return -9999;

value= sp->item[sp->top];
sp->top–;
return value;

}

void display(Stack *sp)
{
int i;
printf(“\nstack\n”);
for(i=sp->top;i>=0;i–)
{
printf(“%d\n”,sp->item[i]);
}
}

void menu(Stack *s)
{

int choice,value;

while(1)

{
printf(” press 1 for Push\n press 2 for pop\n press 3 for display\n press 4 for exit\n\n”);
scanf(“%d”,&choice);

if(choice==4)
break;

switch(choice)
{
case 1:
printf(“enter the value which is to be pushed\n”);
scanf(“%d”,&value);
push(s,value);
break;

case 2:
value= pop(s);
if (value== -9999 && s->top == -1)
printf(“stack underflow\n\n\n”);
else
printf(“the poped data is %d\n”,value);

break;

case 3:
display(s);
break;

case 4:
//exit(0);
break;

default: printf(“invalid choice\n”);

}//end of switch
}//end of while

}

int main()
{
int i;
Stack s1,s2;
s1.top=-1;
s2.top=-1;
clrscr();

while(1)
{
printf(“Press 1 for 1st stack\nPress 2 for 2nd stack\nPress 3 for Exit\n”);
printf(“\nEnter your choice:”);
scanf(“%d”,&i);

switch(i)
{
case 1:
menu(&s1);
break;
case 2:
menu(&s2);
break;
case 3:
exit(0);
// break;

default:
printf(“\ninvalid choice\n”);
}

}

getch();
return 0;
}

/*****C Implementation of  Handling TWO Stacks simultaneously*****/

Continue reading

Circular Queue

In linear queue, since both rear and the front index-markers grows unidirectional, and the overflow condition becomes true immediately when the rear marker reaches the last element of the queue, but there could be vacant elements at the bottom of the queue if some retrieval would have taken place, further, the situation become worst when all elements of the queue would be retrieved, in such case both the underflow and the overflow would happen simultaneously and that is obviously absurd.

To do-away with such flaw of linear queue the conception of circular queue was proposed.

In a circular queue both the rear-index marker and the front-index marker moves circularly, that means when a marker reaches the last element it is taken back to the first element.

While implementing circular queue, we change the rear and front marker in the following way:

Q.rear=(Q.rear+1)%SIZE and

Q.front=(Q.front+1)%SIZE. So that the markers moves to the next element but except for one case, when the markers are at the last element of the QUEUE they are assigned to 0 by the above operation.

Queue q is an array of size=10 elements. rear is the poition/index of last inserted element intially rear =-1
front is the position/index of last retrived element intially front=0

Insert operation on queue
1.START Insert (Element e)
2.If (rear+1)%size :=front Then        ( If rear is the last element index)
3.Display “Queue OVERFLOW”
4.Goto END
5.END If
6.rear:=(rear+1)%size
7.q[rear]:=e
8.END Insert

Retrieve operation on queue
1.START Retrive()
2.If front=rear Then
3.Display “Queue UNDERFLOW”
4.GOTO END
5.END If
6.Element e:=q[front]
7.front:=(front+1)%size
8.Return e
9.END Retrieve

/*******************C IMPLEMENTATION OF CIRCULAR QUEUE********/

The code for implementing the Circular Queue : CircularQueue

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

#define size 6

int queue[size];
int front=size-1,rear=size-1;

void insert(int val)
{
if((rear+1)%size==front)
printf(“queue overflow\n”);
else
{
rear=(rear+1)%size;
queue[rear]=val;
printf(“the value is inserted\n”);
}
}

int retrive()
{
int value;

if(front==rear)
{
//printf(“queue underflow\n”);
return -9999;
}
else
{
front=(front+1)%size;
value= queue[front];
queue[front]=0;
return value;
}
}

void display()
{
int i;
for(i=0;i<=rear;i++)
{
printf(“%d\t”,queue[i]);

}
printf(“\n\n”);

}

void main()
{
int value,choice;
clrscr();
while(1)
{
printf(” press 1 for Insert\n press 2 for Retrive\n press 3 for diplay\n press 4 for exit\n\n”);
printf(“\nenter your choice:”);
scanf(“%d”,&choice);

switch(choice)
{
case 1:
printf(“enter the value which is to be inserted\n”);
scanf(“%d”,&value);
insert(value);
break;

case 2:
value= retrive();
if (value==-9999)
printf(“queue underflow\n\n\n”);
else
printf(“the retrive data is %d\n”,value);

break;

case 3:
display();
break;

case 4:
exit(0);
break;

default: printf(“invalid choice\n”);

}//end of switch
}//end of while

getch();
}

/***********C IMPLEMENTATION OF CIRCULAR QUEUE********/

Let us consider the following queue type.

type QUEUE is [

ELEMENT ITEM[SIZE]

INTEGER REAR

INTEGER FRONT

]

Let Q is a QUEUE of SIZE = 100 elements,

initially Q.REAR:= SIZE-1 and Q.FRONT:=SIZE-1

Insertion operation into a CIRCULAR QUEUE

1.START OPERATION INSERT (QUEUE S, ELEMENT e)

2.IF  (Q.REAR+1)%SIZE := Q.FRONT THEN

3.DISPLAY “QUEUE OVERFLOW”

4.GOTO END

5.END IF

6.  Q.REAR :=(Q.REAR + 1)%SIZE    //INCREMENT THE REAR OF THE QUEUE BY 1

7. Q.ITEM [Q.REAR] : = e  //ASSIGN THE ELEMENT AT THE TOP POSITION OF THE QUEUE

8.END OPERATION INSERT

Retrieve operation on CIRSULAR QUEUE

1.START OPERATION RETRIEVE (QUEUE Q)

2.IF Q.FRONT=Q.REAR THEN

3.DISPLAY “QUEUE UNDERFLOW”

4.GOTO END

5.END IF

6. Q.FRONT :=(Q.FRONT + 1)%SIZE

7. ELEMENT e:=Q.ITEM[Q.FRONT]

8.RETURN e

9.END OPERATION RETRIEVE

Continue reading

Data structures are the repository of data in primary memory. Programs are set of instructions written for processing data and where would one keep data so that the instruction could access them for processing purpose? It is data structures like Array, linked list or may be a tree which serves the purpose of storing data in primary memory so that the instruction could fetch and process them in a convenient way.

While learning the basics of C we had understanding of only one basic data structure and that is Array. As a data structure, Array, on one hand, has got some facilities on other hand it has some pit-falls. Array is contiguous, that’s why it is random and that is one of its facilities but this contiguous allocation becomes a problem when we suppose to process huge amount of data, in such cases the allocation of array in run-time might turn into a failure, further more, insertion, update, deletion of elements in an array becomes time consuming affair as we need to reallocate the whole array after such operations in run-time.Array is fixed, we need to mention the size  of the array during the allocation period, inserting an element afterward really becomes a time consuming affair. So the demand of writing efficient program needs better data structure than array and that is linked list. How to create, update, delete, search in a linked list that we learn in Data Structure. Further hierarchical representation of information enhance searching capabilities of code, How we coould represent data in hierarchical order, for that there is tree. There are various types of trees, Binary search Tree, B-Tree, B+ Tree, Game Tree, Threaded Binary Tree, AVL Tree  ,each having there own utility. We learn how to deal with all those data structures under this syllabus.
A program always needs to be an efficient program. The efficiency of any program is judged on the basis of two yard sticks – 1) the execution time of a program, 2) The resource (Memory) that it aquires for execution. Both execution time and Memory depends on the number of input that the program process, Increse the number of input, the possibility is that it is going to take more execution time and more memory. We need to try to keep execution time and memory as much as possible independent of the number of input, such that, the variation of input has little impact on execution time or the resources that it aquires, but not all the time one programmer can achieve that, with the demand of the logic it would not be possible to write a program whose execution time or memory dependance would be totally independent of input volume. Normally it happens that when we try to stabilize the execution time we need to sacrifice memory and when we try to stabilize memory we would require to sacrifice execution time, it is often said as TIME-SPACE trade off. In data structure we learn how to compare two algorithm on the basis of execution time and resource requirement where both as a function of the input data volume.

Now-a-days all the modern languages (JAVA / DOT NET/ C++) comes with rich library that has all the data structures inbuild within it.  As a programmer we would seldom require to build the operations on a data structure from the scratch. But the need of efficient state-of-art program the use of proper data structure is obvious, thus, understanding the data structures with all its functionality, to be a good programmer, is obvious without any doubt.

 Untitled
1.Primitive data structures
 These are the basic data structures and are directly operated upon by the machine instructions, which is in a primitive level. They are integers, floating point numbers, characters, string constants, pointers etc.
2. Non-primitive data structures

It is a more sophisticated data structure emphasizing on structuring of a group of homogeneous (same type) or heterogeneous(different type) data items. Array, list, files, linked list, trees and graphs fall in this category

Queue is a linear data structure where the elements could be inserted at one end called the “rear” of the queue and could be retrieved from the other end called “front” of the queue.

Queue implements First In First Our (FIFO)/ Last In Last Out  (LILO) Order on its elements, that is elements inserted first into the queue would be retrieved first from the queue and vice-versa.

Typically queue follows FIFO order, but there could a pre-defined priority for the elements that decides the deletion sequence of the queue elements, in such cases the queue does not follow the traditional FIFO order, such queues are termed as Priority Queue.

Basically FIFO queue are also priority queue as the element inserted first into the queue gets the highest priority.

Queue q is an array of size=10 elements. rear is the poition/index of last inserted element intially rear =-1
front is the position/index of last retrived element intially front=0

Insert operation on queue
1.START Insert (Element e)
2.If rear = size -1 Then        ( If rear is the last element index)
3.Display “Queue OVERDERFLOW”
4.Goto END
5.END If
6.rear:=rear+1
7.q[rear]:=e
8.END Insert

Retrieve operation on queue
1.START Retrive()
2.If front>rear Then
3.Display “Queue UNDERFLOW”
4.GOTO END
5.END If
6.Element e:=q[front]
7.front:=front+1
8.Return e
9.END Retrieve

/**************C- Implementation of LINEAR Queue ****************/
The code for implementing Queue is:-LinearQueue

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

#define size 6

int queue[size];
int front=0,rear=-1;

void insert(int val)
{
if(rear==size-1)
printf(“queue overflow\n”);

rear++;
queue[rear]=val;
printf(“the value is inserted\n”);
}

int retrive()
{
int value;

if(front>rear)
{
//printf(“queue underflow\n”);
return -9999;
}
value= queue[front];
queue[front]=0;
front++;
return value;
}

void display()
{
int i;
for(i=0;i<=rear;i++)
{
printf(“%d\t”,queue[i]);

}
printf(“\n”);

}

void main()
{
int value,choice;
clrscr();
while(1)
{
printf(” press 1 for Insert\n press 2 for Retrive\n press 3 for diplay\n press 4 for exit\n\n”);
printf(“\n enter your choice:”);
scanf(“%d”,&choice);

switch(choice)
{
case 1:
printf(“enter the value which is to be inserted\n”);
scanf(“%d”,&value);
insert(value);
break;

case 2:
value= retrive();
if (value==-9999 || front==0)
printf(“queue underflow\n\n\n”);
else
printf(“the retrive data is %d\n”,value);

break;

case 3:
display();
break;

case 4:
exit(0);
break;

default: printf(“invalid choice\n”);

}//end of switch
}//end of while

//getch();
}

Continue reading

Stack is a linear data structure where the elements could be inserted or retrieved only at one end, called the ‘top’ of the stack. Stack implements “First In Last Out/ Last In First Out” (FILO/ LIFO) order on its data elements, that is elements inserted first into the stack would be retrieved last from the stack or vice-versa.

Inserting an element into a stack is called ‘push’ , retrieving an element from the stack is termed as pop operation.

Algorithm for push and pop operations on a stack.

Stack s is an array of size element top is the position/index of last inserted element initially top =-1
Push operation on a stack

1.START Push (Element e)
2.If top = size -1 Then          ( If top is the last element index)
3.Display “STACK OVERFLOW”
4.Goto END
5.END If
6.top:=top+1                         (Increment the ‘top’ of the Stack s by 1)
7.s[top]:=e                             (assign the element at the ‘top’ position of the Stack)
8.END PUSH

Pop operation on a stack

1.START POP()
2.If top=-1 Then
3.Display “STACK UNDERFLOW”
4.Goto END
5.END If
6.Element e:=s[top]
7.top:=top-1                           (Decrement the ‘top’ of the Stack s by 1)
8.Return e
9.END POP

/************** C – Implementation of Stack ************************/

The code for implementing stack :- Stack

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

#define size 6

int stack[size];
int top=-1;

void push(int val)
{
if(top ==size-1)
printf(“stack overflow\n”);

else
{
top++;
stack[top]=val;
printf(“the value is pushed\n”);
}
}

int pop()
{
int value;

if(top==-1)
{
//printf(“stact underflow\n”);
return -9999;
}

else
{
value= stack[top];
top–;
return value;             //return stack[top–];
}
}

void display()
{
int i;
printf(“\nstack\n”);
for(i=top;i>=0;i–)
{
printf(“%d\n”,stack[i]);
}
printf(“\n\n”);
}

void main()
{
int value,choice;
clrscr();
while(1)
{
printf(” press 1 for Push\n press 2 for pop\n press 3 for display\n press 4 for exit\n\n”);
printf(“\nenter your choice:”);
scanf(“%d”,&choice);

switch(choice)
{
case 1:
printf(“enter the value which is to be pushed\n”);
scanf(“%d”,&value);
push(value);
break;

case 2:
value= pop();
if (value== -9999 && top == -1)
printf(“stack underflow\n\n\n”);
else
printf(“the poped data is %d\n”,value);

break;

case 3:
display();
break;

case 4:
exit(0);
break;

default: printf(“invalid choice\n”);

}//end of switch
}//end of while
//return 0;
getch();
}

Continue reading

data structure 1

data structure 2

data structure 3

data structure 4

data structure 5

data structure 6

data structure 7