Data structure interview questions and answers with tips

Data structure interview questions Part 13

noreply@blogger.com (Anonymous) — Thu, 26 Jan 2012 07:59:00 -0800

Q: What's the major distinction in between Storage structure and file structure
and how?
A: The expression of an specific data structure inside memory of a computer system is termed storage structure in contrast to a storage structure expression in auxiliary memory is normally known as a file structure.

Q: Explain whether Linked List is actually linear or Non-linear data structure?
A: Link list is definitely obviously linear data structure simply because each and every element (NODE) acquiring specific place and as well each and every component has got its unique successor in addition to predecessor. furthermore, linear collection of data objects referred to as nodes and also the linear order is provided by means of pointers. Every node can be separated into two parts. First part includes information of the element and another part includes the address of the subsequent node in the list.

Q: Explain simulation?
A: Simulation is the procedure for developing an fuzy model from a real situation so as to understand the effects of modifications and the effect of introducing a variety of techniques on the situation. It is a rendering with real life system by another system, which represents the important characteristics of real system and allows experiments on it.

Q: Does the minimum spanning tree of the graph provide the shortest distance between any two given nodes?
A: Minimal spanning tree ensures that the total weight of the tree is actually kept at its minimum but it really would not signify the distance between any two nodes involved in the minimum-spanning tree is actually minimum.

Q: In an AVL tree, at exactly what situation the balancing will be done?
A: If the pivotal value (or the Height factor) is above 1 or less than 1. If the balance factor of any node is other than 0 or 1 or -1 then balancing is completed. The balancing factor will be height. The variation in height of the right subtree along with right subtree need to be +1, -1 or 0

Q: What is the significant difference between ARRAY and STACK?
A: Stack ensues LIFO. Thus the item that is certainly first entered would be the last removed. In array the items could be entered or removed in any order. Basically each and every member access is done making use of index and no strict order is to be followed here to remove a particular element. Array could be multi dimensional or one dimensional but stack really should be one-dimensional.
Size of array is fixed, while stack may be grow or shrink. We can say stack is actually dynamic data structure.

Data structure interview questions Part 12

noreply@blogger.com (Anonymous) — Sat, 16 Oct 2010 13:27:00 -0700

Data structure interview question:What is mean by d-queue?
Answer:D-queue stands for double ended queue. It is a abstract data structure that implements a queue for which elements can be added to front or rear and the elements can be removed from the rear or front. It is also called head-tail linked list

Data structure interview question:Example of linear and non-linear data structures?
Answer:The data structure is said to be a Linear data structure if its elements are in sequence and form a linear list.Ex. Arrays, Stacks, Queues,Linked Lists.
If the elements of data structure do not form a sequence or a linear list then that type of data structure is called as Non-Linear data structure.Ex. Trees, BST(Binary Search Trees) etc.

Data structure interview question:How to find the number of possible tree in the given tree.
Answer: The number of possible tree = (2 power of n) - n.
For example:A tree contain three node.So if n=3,the possible number of trees = 8 - 3 = 5.

Data structure interview question:What is hashing
Answer:Hashing is a way retrieving records from memory in faster way. Record is inserted into memory by using hash function(division, midsqure,folding,digit analysis)and also records are retrieved using same hash function.

Data structure interview question:What is almost complete binary tree?
Answer:An almost complete binary tree is a tree in which each nodethat has a right child also has a left child. Having a left child does not require a node to have a right child. Stated alternately, an almost complete binary tree is a tree where for a right child, there is always a left child, but for a left child there may not be a right child.The number of nodes in a binary tree can be found using this formula: n = 2^h Where n is the amount of nodes in the tree, and h is the height of the tree.

Data structure interview question:Classify the Hashing Functions based on the various methods by which the key value is found?
Answer:
Direct method,
Subtraction method,
Modulo-Division method,
Digit-Extraction method,
Mid-Square method,
Folding method,
Pseudo-random method.

Data structure interview question:What is almost complete binary tree?
Answer:An almost complete binary tree is a tree in which each node that has a right child also has a left child. Having a left child does not require a node to have a right child. Stated alternately, an almost complete binary tree is a tree where for a right child, there is always a left child, but for a left child there may not be a right child.The number of nodes in a binary tree can be found using this formula: n = 2^h Where n is the amount of nodes in the tree, and h is the height of the tree.

Data structure interview question::What is AVL tree?
Answer:Avl tree is self binary tree in which balancing factor lie between the -1 to 1.It is also known as self balancing tree.

Data structure interview questions Part 11

noreply@blogger.com (Anonymous) — Sat, 15 May 2010 00:50:00 -0700

Data structure interview question:What do you mean by: Syntax Error, Logical Error, Run time Error?

Answer:

Syntax Error-Syntax Error is due to lack of knowledge in a specific language. It is due to somebody does not know how to use the features of a language.We can know the errors at the time of compilation.logical

Error-It is due to the poor understanding of the requirement or problem.

Run time Error-The exceptions like divide a number by 0,overflow and underflow comes under this.

Data structure interview question :What is the maximum total number of nodes in a tree that has N levels? Note that the root is level (zero).

Answer:2^(N+1)-1..

if N=0; it is 2-1=1,1 is the max no of node in the tree
if N=1; it is 4-1=3, 3 is the max no of nodes in the tree
if N=2; it is 8-1=7, 7 is the max.

Data structure interview question:Explain about the types of linked lists?

Answer:Their are three linked lists1)linear or simple linked lists2)doubly linked lists3)circular linked listssimple linked list :This contains a node which has two parts, see that a node is a STRUCTURE.one is data and other one is a pointer which is called self reference pointers, so we must make it to point to the next location of second node created dynamically.double linked lists :A node will consists of previous node address , a data & next node address which can move backwards to the very first address.circular linked list :Here we will have the node consists of same thing but default when it finishes the last node and come to the first node.

Data structure interview question:What are the parts of root node?
Answer:A root node contains data part and has link part. i.e links to its child. If it is binary tree it has two links i.e left child and right child.

Data structure interview question:How will inorder, preorder and postorder traversals printthe elements of a tree?
Answer:
voidinorder(node * tree)
{
if(tree!=NULL)
{
inorder(tree->leftchild);
printf("%d",tree->data);
inorder(tree->rightchild);
}
else
return;
}
void postorder(node * tree)
{
if(tree!=NULL)
{
postorder(tree->leftchild);
postorder(tree->rightchild);
printf("%d",tree->data);
}
else
return;
}
void preorder(node * tree)
{
if(tree!=NULL)
{
printf("%d",tree->data);
preorder(tree->leftchild);
preorder(tree->rightchild);
}
else
return;
}

Data structure interview questions Part 10

noreply@blogger.com (Anonymous) — Sun, 7 Feb 2010 16:44:00 -0800

Data structure interview question:Create an singly linked lists and reverse the lists by interchanging the links and not the data?

Answer:

struct node{ int data;
node * next;
};
node *pt1,*pt2=NULL:
while(root!=NULL)
{
pt1=root;
root=root->next;
pt1->next=pt2;
pt2=pt1;
}

Data structure interview question::What is B+ tree?

Answer:A B+ tree is a type of tree which represents sorted data in a way that allows for efficient insertion, retrieval and removal of records, each of which is identified by a key. It is a dynamic, multilevel index, with maximum and minimum bounds on the number of keys in each index segment (usually called a 'block' or 'node'). In a B+ tree, in contrast to a B-tree, all records are stored at the lowest level of the tree; only keys are stored in interior blocks.
The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context. Given a storage system with a block size of b, a B+ tree which stores a number of keys equal to a multiple of b will be very efficient when compared to a binary search tree (the corresponding data structure for non-block-oriented storage
contexts).

Data structure interview question:Which one is faster? A binary search of an orderd set of elements in an array or a sequential search of the elements.
Answer:Binary search is faster because we traverse the elements by using the policy of Divide and Conquer. we compare the key element with the approximately center element, if it is smaller than it search is applied in the smaller elements only otherwise the search is applied in the larger set of elements. its complexity is as we all know is log n as compared to the sequential one whose complexity is n.

Data structure interview question:Parenthesis are never needed in prefix or postfix expressions. Why?
Answer:Basically Parenthesis indicate the operations which need to be carried out first ie according to the BODMAS rule..SO in case of postfix or prefix expression they are actualy conversions of the orginal standard equation.Where the brackets have already been taken into consideration,,,and the formed prefix/postfix expression is the correct order of expansion of a given mathematical statement.

Data structure interview question:How can one find a cycle in the linked list? IF found how to recognize the cycle and delete that cycle?

Answer: find_cycle(Node* head){

Node* ptr1 = head;

Node* ptr2 = head;

while(ptr1 != NULL && ptr2 != NULL && ptr2->next != NULL){

if(ptr1 == ptr2){

printf("\nClycle present in thr LinkList\n");

return true;

}

ptr1 = prt1->next;

ptr2 = ptr2->next->next;

}

return false;

}

Data structure interview questions Part 9

noreply@blogger.com (Anonymous) — Thu, 7 Jan 2010 16:48:00 -0800

Data structure interview question:Stack can be described as a pointer. Explain?
Answer:Because stack will contain a head pointer which will always point to the top of the Stack.All Stack Operations are done using Head Pointer. Hence Stack ca be Described as a Pointer

Data structure interview question:What do you mean by Base case, Recursive case, Binding Time, Run-Time Stack and Tail Recursion?
Answer:These terms are found in Recursion.1.Base Case:it is the case in recursion where the answer is known,or we can say the termination condition for a recursion to unwind back.For example to find Factorial of num using recursion:

int Fact(int num){
if(num==1 || num==0)//base case
return 1;
else // recursive case:
return num*Fact(num-1);
}
2.Recursive case:It is the case whcih brings us to the
closer answer.

Run Time Stack:It is a system stack us to save the frame stack of a function every recursion or every call.This frame stack consists of the return address,local variables and return value if any.

Tail Recursion:The case where the function consist of single recursive call and it is the last statement to be executed.A tail Recursion can be replace by iteration. The above funtion consists of tail recursion case.where as the below function does not.
void binary(int start,int end,int el){
int mid;
if(end>start){
mid=(start+end)/2;
if(el==ar[mid])
return mid;
else{
if(el>ar[mid])
binary(mid+1,end,ele);
else
binary(start,mid-11,ele);
}
}
}

Data structure interview question:What data structure would you mostly likely see in a non recursive implementation of a recursive algorithm?
Answer:Stack

Data structure interview question:what is binary tree?
Answer:Binary tree is a tree which has maximum no. of childrens either 0 or 1 or 2. i.e., there is at the most 2 branches in every node.

Data structure interview questions Part 8

noreply@blogger.com (Anonymous) — Sun, 13 Sep 2009 10:00:00 -0700

Data structure interview question:Convert the given graph with weighted edges to minimal spanning tree

Answer:The equivalent minimal spanning tree is:

Data structure interview question: Draw a binary Tree for the expression :
A * B - (C + D) * (P /Q)

Answer:

Data structure interview question: For the following COBOL code, draw the Binary tree?
01 STUDENT_REC.
02 NAME.
03 FIRST_NAME PIC X(10).
03 LAST_NAME PIC X(10).
02 YEAR_OF_STUDY.
03 FIRST_SEM PIC XX. 03 SECOND_SEM PIC XX
Answer:

Data structure interview questions Part 7

noreply@blogger.com (Anonymous) — Tue, 1 Sep 2009 09:50:00 -0700

Data structure interview question:Of the following tree structure, which is, efficient considering space and time complexities?
(a) Incomplete Binary Tree
(b) Complete Binary Tree
(c) Full Binary Tree
(d) Complete Binary Tree.
Answer:
By the method of elimination:
Full binary tree loses its nature when operations of insertions and deletions are done. For incomplete binary trees, extra storage is required and overhead of NULL node checking takes place. So complete binary tree is the better one since the property of complete binary tree is maintained even after operations like additions and deletions are done on it.

Data structure interview question:What is a spanning Tree?
Answer: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.

Data structure interview question:Does the minimum spanning tree of a graph give the shortest distance between any 2 specified nodes?
Answer:No. 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 question : Which is the simplest file structure?
(a) Sequential
(b) Indexed
(c) Random

Answer: Sequential

Data structure interview question:Whether Linked List is linear or Non-linear data structure?
Answer:According to Access strategies Linked list is a linear one.
According to Storage Linked List is a Non-linear one.

Data structure interview questions Part 6

noreply@blogger.com (Anonymous) — Sat, 1 Aug 2009 09:46:00 -0700

Data structure interview question|:Sort the given values using Quick Sort?

Sorting takes place from the pivot value, which is the first value of the given elements, this is marked bold. The values at the left pointer and right pointer are indicated using and respectively.

70^L

45^R

Since pivot is not yet changed the same process is continued after interchanging the values at and positions.

75^L

50^R

80^L

55^R

85^L

60^R

85^L

When the L and R pointers cross each other the pivot value is interchanged with the value at right pointer. If the pivot is changed it means that the pivot has occupied its original position in the sorted order (shown in bold italics) and hence two different arrays are formed, one from start of the original array to the pivot position-1 and the other from pivot position+1 to end.

60^L

55^R

85^L

70^R

55^L

50^R

70^R

80^L

50^L

45^R

80^L

75^R

In the next pass we get the sorted form of the array.

Data structure interview questions Part 5

noreply@blogger.com (Anonymous) — Wed, 1 Jul 2009 09:32:00 -0700

Data structure interview question: For the given graph, draw the DFS and BFS?

Answer:

Ø BFS: A X G H P E M Y J
Ø DFS: A X H P E Y M J G

Data structure interview question: Classify the Hashing Functions based on the various methods by which the key value is found.
Answer:
Ø Direct method,
Ø Subtraction method,
Ø Modulo-Division method,
Ø Digit-Extraction method,
Ø Mid-Square method,
Ø Folding method,
Ø Pseudo-random method.

Data structure interview question:What are the types of Collision Resolution Techniques and the methods used in each of the type?

Answer:
Ø Open addressing (closed hashing),
The methods used include:
Overflow block,
Ø Closed addressing (open hashing)

The methods used include:
Linked list,
Binary tree…

Data structure interview question: In RDBMS, what is the efficient data structure used in the internal storage representation?

Answer:B+ tree. Because in B+ tree, all the data is stored only in leaf nodes, that makes searching easier. This corresponds to the records that shall be stored in leaf nodes.

Data structure interview question: Draw the B-tree of order 3 created by inserting the following data arriving in sequence – 92 24 6 7 11 8 22 4 5 16 19 20 78

Answer:

Data structure interview questions Part 4

noreply@blogger.com (Anonymous) — Mon, 1 Jun 2009 09:21:00 -0700

Data structure interview question:What is the bucket size, when the overlapping and collision occur at same time?

Answer:One. If there is only one entry possible in the bucket, when the collision occurs, there is no way to accommodate the colliding value. This results in the overlapping of values.

Data structure interview question: Traverse the given tree using Inorder, Preorder and Postorder traversals.

Answer:

Ø Inorder : D H B E A F C I G J

Ø Preorder: A B D H E C F G I J

Ø Postorder: H D E B F I J G C A

Data structure interview question:There are 8, 15, 13, 14 nodes were there in 4 different trees. Which of them could have formed a full binary tree?

Answer:15.

In general:

There are 2n-1 nodes in a full binary tree.

By the method of elimination:

Full binary trees contain odd number of nodes. So there cannot be full binary trees with 8 or 14 nodes, so rejected. With 13 nodes you can form a complete binary tree but not a full binary tree. So the correct answer is 15.

Note:

Full and Complete binary trees are different. All full binary trees are complete binary trees but not vice versa.

Data structure interview question: In the given binary tree, using array you can store the node 4 at which location?

Answer:Left: 2i

Right:2i+1

i=location

At location 6

Root

LC1

RC1

LC2

RC2

LC3

RC3

LC4

RC4

where LCn means Left Child of node n and RCn means Right Child of node n.

Data structure interview questions Part 3

noreply@blogger.com (Anonymous) — Fri, 1 May 2009 08:57:00 -0700

Data structure interview question: How many different trees are possible with 10 nodes ?
Answer:1014
For example, consider a tree with 3 nodes(n=3), it will have the maximum combination of 5 different (ie, 23 - 3 = 5) trees.

i ii iii iv v

In general:
If there are n nodes, there exist 2n-n different trees.

Data structure interview question: List out few of the Application of tree data-structure?
Answer:
Ø The manipulation of Arithmetic expression,
Ø Symbol Table construction,
Ø Syntax analysis.

Data structure interview question: List out few of the applications that make use of Multilinked Structures?
Answer:Ø Sparse matrix,
Ø Index generation.

Data structure interview question: In tree construction which is the suitable efficient data structure?
Answer:(a) Array (b) Linked list (c) Stack (d) Queue (e) none
Answer:
(b) Linked list

Data structure interview question:What is the type of the algorithm used in solving the 8 Queens problem?

Answer:Backtracking

Data structure interview question:In an AVL tree, at what condition the balancing is to be done?

Answer:If the ‘pivotal value’ (or the ‘Height factor’) is greater than 1 or less than –1.

Data structure interview questions Part 2

noreply@blogger.com (Anonymous) — Wed, 1 Apr 2009 08:51:00 -0700

Data structure interview question:What are the notations used in Evaluation of Arithmetic Expressions using prefix and postfix forms?

Answer:Polish and Reverse Polish notations.

Data structure interview question: Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to equivalent Prefix and Postfix notations.
Answer:Prefix Notation: ^ - * +ABC - DE + FG
Postfix Notation: AB + C * DE - - FG + ^

Data structure interview question:Sorting is not possible by using which of the following methods?
Answer:(a) Insertion
(b) Selection
(c) Exchange (bubble sort)
(d) Deletion
(d) 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.

Q:Draw a binary tree with 20 nodes has 21 null branches?
Answer:Let us take a tree with 5 nodes (n=5)

It will have only 6 (ie,5+1) null branches. In general, a binary tree with n nodes has exactly n+1 null nodes.

Data structure interview question: What are the methods available in storing sequential files ?
Answer:Ø Straight merging,
Ø Natural merging,
Ø Polyphase sort,
Ø Distribution of Initial runs.

Data structure interview questions Part 1

noreply@blogger.com (Anonymous) — Sun, 1 Mar 2009 08:43:00 -0800

Data structure interview question: What is data structure?
Answer: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.

Data structure interview question: List out the areas in which data structures are applied extensively?

Answer: Ø Compiler Design,
Ø Operating System,
Ø Database Management System,
Ø Statistical analysis package,
Ø Numerical Analysis,
Ø Graphics,
Ø Artificial Intelligence,
Ø Simulation

Data structure interview question:What are the major data structures used in the following areas of RDBMS, Network data model & Hierarchical data model.
Answer: Ø RDBMS – Array (i.e. Array of structures)
Ø Network data model – Graph
Ø Hierarchical data model – Trees

Data structure interview question: If you are using C language to implement the heterogeneous linked list, what pointer type will you use?
Answer: 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.

Data structure interview question: Minimum number of queues needed to implement the priority queue?
Answer: Two. One queue is used for actual storing of data and another for storing priorities.

Data structure interview question: What is the data structures used to perform recursion?
Answer: 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.