|
Data Structure Interview Questions with Answers posted on August
06, 2008 at 13:10 PM by Amit Satpute
Question - What is the recursion?
Answer
Recursion is an approach in which a function calls itself with an argument.
Upon reaching a termination condition, the control returns to the calling
function.
Question - What are priority queues?
Answer
A priority queue is essentially a list of items in which each item has
associated with it a priority
Items are inserted into a priority queue in any, arbitrary order. However,
items are withdrawn from a priority queue in order of their priorities starting
with the highest priority item first.
Priority queues are often used in the implementation of algorithms
Question - What is a circular singly linked list?
Answer
In a circular singly linked list, the last node of the list is made to point to
the first node. This eases the traveling through the list.
Question - What is a B tree?
Answer
A B-tree of order m (the maximum number of children for each node) is a tree
which satisfies the following properties :
1. Every node has <= m children.
2. Every node (except root and leaves) has >= m/2 children.
3. The root has at least 2 children.
4. All leaves appear in the same level, and carry no information.
5. A non-leaf node with k children contains k – 1 keys
Question - What are splay trees?
Answer
A splay tree is a self-balancing binary search tree. In this, recently accessed
elements are quick to access again
It is useful for implementing caches and garbage collection algorithms.
When we move left going down this path, its called a zig and when we move right,
its a zag.
Following are the splaying steps. There are six different splaying steps.
1. Zig Rotation (Right Rotation)
2. Zag Rotation (Left Rotation)
3. Zig-Zag (Zig followed by Zag)
4. Zag-Zig (Zag followed by Zig)
5. Zig-Zig
6. Zag-Zag
Question - What are red-black trees?
Answer
A red-black tree is a type of self-balancing binary search tree.
In red-black trees, the leaf nodes are not relevant and do not contain data.
Red-black trees, like all binary search trees, allow efficient in-order
traversal of elements.
Each node has a color attribute, the value of which is either red or black.
Characteristics:
The root and leaves are black
Both children of every red node are black.
Every simple path from a node to a descendant leaf contains the same number of
black nodes, either counting or not counting the null black nodes
Question - What are threaded binary trees?
Answer
In a threaded binary tree, if a node 'A' has a right child 'B' then B's left
pointer must be either a child, or a thread back to A.
In the case of a left child, that left child must also have a left child or a
thread back to A, and so we can follow B's left children until we find a
thread, pointing back to A.
This data structure is useful when stack memory is less and using this tree the
treversal around the tree becomes faster.
Question - What is the Huffman algorithm?
Answer
In Huffman Algorithm, a set of nodes assigned with values if fed to the
algorithm.
Initially 2 nodes are considered and their sum forms their parent node. When a
new element is considered, it can be added to the tree. Its value and the
previously calculated sum of the tree are used to form the new node which in
turn becomes their parent.
Question - What is merge sort algorithm?
Answer
A merge sort algorithm that splits the items to be sorted into two groups,
recursively sorts each group, and merges them into a final, sorted sequence.
Run time is T(n log n).
If n<2 then the array is already sorted. Stop now.
Otherwise, n>1, and we perform the following three steps in sequence:
Sort the left half of the the array.
Sort the right half of the the array.
Merge the now-sorted left and right halves.
Question - What is a B+ tree?
Answer
It is a dynamic, multilevel index, with maximum and minimum bounds on the
number of keys in each index segment. all records are stored at the lowest
level of the tree; only keys are stored in interior blocks.
Applications examples: XFS filesystem, JFS2 filesystem.
|