Data Structures & Algorithms Interview Questions Part – 2

1.Enumerate several hashing methods.

Here are some hashing methods: a. division method b. middle square method c. multiplication method d. Fibonacci hashing

2.What is a scatter table?

A scatter table is an array-based hash table. The essential idea behind a scatter table is that all of the information is stored within a fixed size array and hashing is used to identify the position where an item should be stored.

3.Describe several collision resolution strategies in open addressing.

There are three resolution strategies in open addressing: a. linear probing – the interval between probes is fixed – usually at 1 b. quadratic probing – the interval between probes increases linearly. This way,the indices are described by a quadratic function. c. double hashing – the interval between probes is fixed for each record but is computed by another hash function

4.What is lazy deletion?

It is a method of deleting elements from a hash table which uses open addressing. Deletions are performed by marking an element as deleted,without erasing it entirely. Deleted locations are treated as empty when inserting and as occupied during a search.

5.Describe a splay tree.

A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion,look-up and removal in O(log n) amortized time. For many sequences of operations,splay trees perform better than other search trees,even when the specific pattern of the sequence is unknown.

6.Make a short comparison between AVL trees and red-black trees.

AVL trees are more rigidly balanced than red-black ones; this leads to slower insertion and removal but faster retrieval. The differences are anyway very small and notable only when using extremely large data structures that may be built once and loaded without reconstruction (e.g. language dictionaries).

7.What is the usage of red-black trees?

Red-black trees offer worst-case guarantees for insertion,deletion,and search time. This feature makes them valuable in time-sensitive applications such as real-time applications; for example,many data structures used in computational geometry can be based on red-black trees (e.g. the Completely Fair Scheduler used in current Linux kernels uses red-black trees).

8.What is a red-black tree?

A red-black tree is a binary search tree where each node has a color attribute,the value of which is either red or black. In addition to the ordinary requirements imposed on binary search trees,the following additional requirements apply to red-black trees: a. a node is either red or black b. the root is black c. all leaves are black d. both children of every red node are black e. every simple path from a given node to any of its descendant leaves contains the same number of black nodes

9.Define a self-balancing binary search tree.

An AVL tree is a binary search tree such that for every internal node v of T,the heights of the children of v can differ by at most
1. The basic operations of an AVL tree involve carrying out the same actions as would be carried out on an unbalanced binary search tree (search,insertion,deletion,traversal,sort),but modifications are preceded or followed by one or more operations called tree rotations,which help to restore the height balance of the subtrees.

10.Define the concept of a treap.

A treap is a form of binary search tree data structure that maintains a dynamic set of ordered keys and allows binary searches among the keys. After any sequence of insertions and deletions of keys,the shape of the tree is a random variable with the same probability distribution as a random binary tree; in particular,with high probability its height is proportional to the logarithm of the number of keys,so that each search,insertion,or deletion operation takes logarithmic time to perform.

11.Describe the procedure of removing an item from a binary search tree.

When removing an item from a search tree,it is imperative that the tree which remains satisfies the data ordering criterion. a. to remove a non-leaf node,it must be moved down in the tree until it becomes a leaf node since a leaf node is easily deleted. b. to move a non-leaf node down in the tree,we either swap it with the smallest key in the right subtree or with the largest one in the left subtree.

12.Describe the algorithm of inserting data into a binary search tree.

In order to insert data into a binary search tree you have to perform the following steps: a) pretend that the item is already in the tree and follow the path taken by the find routine to determine where the item would be. b) assuming that the item is not already in the tree,the search will be unsuccessful and will terminate with an external,empty node which is precisely where the item to be inserted is placed.

13.What is a binary search tree?

A binary search tree is a finite set of keys which satisfies the following properties: a. a) all the keys contained in left subtree are less than the value of the subtree root b. all the keys contained in the right subtree are greater than the value of the subtree root

14.Give example of some types of search trees.

AVL Search Trees,M-Way Search Trees,B-Trees.

15.What is a search tree?

A search tree is a tree which supports efficient search,insertion and withdrawal operations. In this context the tree is used to store a finite set of keys inserted after a data ordering criterion. No duplicate keys are allowed.

16.Provide a short description of a B-tree.

A B-tree is a generalization of a binary search tree which keeps data sorted and allows searches,sequential access,insertions,and deletions in logarithmic amortized time. It is commonly used in databases and filesystems.

17.What is a Fibonacci heap?

A Fibonacci heap is a collection of trees satisfying the minimum-heap property,that is,the key of a child is always greater than or equal to the key of the parent. This implies that the minimum key is always at the root of one of the trees.

18.Enumerate several heap specializations.

2-3 heap,Beap,Binary heap,Binomial heap,Brodal Queue,D-ary heap,Fibonacci heap,Leftist heap,Pairing heap,Pseudo Queue,Skew heap,Soft heap,Ternary heap,Treap.

19.Which are the operations usually performed on a heap?

The operations commonly performed on a heap are: a. find-max or find-min – find the maximum item of a max-heap or a minimum item of a min-heap b. delete-max or delete-min – removing the root node of a max/min-heap c. increase-key or decrease-key – updating a key within a max/min-heap d. insert – adding a new key to the heap e. merge – joining two heaps to form a valid new heap containing all the elements of both

20.Describe the inorder traversal algorithm.

Inorder traversal gets its name from the fact that it visits the root in between visiting the left and right subtrees. The steps are the following: a. traverse the left subtree b. visit the root c. traverse the right subtree

21.What is the difference between a max-heap and a min-heap?

a. A max-heap respects the property that if B is a child node of A,then key( A) >= key(B) – the greatest key is always in the root node b. A min-heap respects the property that if B is a child node of A,then key( A) <= key(B) – the smallest key is always in the root node

22.What is a heap?

A heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A,then key(A) >= key(B). This implies that an element with the greatest key is always in the root node.

23.Describe the breadth-first traversal algorithm.

The breadth-first traversal of a tree visits the nodes in the order of their depth in the tree. Breadth-first traversal first visits all the nodes at depth zero (i.e. the root),then all the nodes at depth one,and so on. At each depth the nodes are visited from left to right.

24.Describe the postorder traversal algorithm.

Postorder traversal gets its name from the fact that it visits the root last. The steps are the following: a. traverse the left subtree b. traverse the right subtree c. visit the root