Posts in category: Interview Questions

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

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

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.

Straight merging,
Natural merging,
Polyphase sort,
Distribution of Initial runs

The manipulation of Arithmetic expression,
Symbol Table construction,
Syntax analysis

Sparse matrix,
Index generation

Backtracking

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.

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

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.

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.

According to Access strategies Linked list is a linear one.
According to Storage Linked List is a Non-linear one

We call an algorithm randomized if its behavior is determined not only by its input but also by values produced by a random-number generator.

The (binary) heap data structure is an array object that can be viewed as a nearly complete binary tree. Each node of the tree corresponds to an element of the array that stores the value in the node.

A hash table is an effective data structure for implementing dictionaries. The expected time to search for an element in a hash table is O(1). A hash table is a generalization of the simple notion of an ordinary array.

It is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.

It is the method of using probability to analyze problems. We use probabilistic analysis to analyze the running time of an algorithm.

We call an algorithm randomized if its behavior is determined not only by its input but also by values produced by a random-number generator.

A data structure is a way to store and organize data in order to facilitate access and modifications.

The (binary) heap data structure is an array object that can be viewed as a nearly complete binary tree. Each node of the tree corresponds to an element of the array that stores the value in the node.

A priority queue is a data structure for maintaining a set of elements, each with an associated value called a key.

Counting sort assumes that each of the n input elements is an integer in the range 0 to k for some integer k, when k = O(n), the sort runs in O(n) time.

Bucket sort runs in linear time when the input is drawn from a uniform distribution. Bucket sort is fast because it assumes something about the input.

Stacks and queues are dynamic sets in which the element removed from the set by the DELETE operation is pre-specified. In a stack, the policy is LIFO (Last-in, First-out). In a queue, the policy is FIFO (First-in, First-out).

A linked list is a data structure in which the objects are arranged in a linear order.

A binary tree T is a structure defined on a finite set of nodes that either contains no nodes, or is composed of three disjoined sets of nodes: a root node, a binary tree called its left subtree, and a binary tree called its right subtree.

The binary tree that contains no nodes is called the empty tree or null tree.

It is a binary tree where each node is either a leaf or has degree exactly 2.

It is a positional tree in which for every node, all children with labels greater than k are missing. Thus, a binary tree is a k-ary tree with k=2. A complete k-ary tree is a k-ary tree in which all leaves have the same depth and all internal nodes have degree k.

A hash table is an effective data structure for implementing dictionaries. The expected time to search for an element in a hash table is O(1). A hash table is a generalization of the simple notion of an ordinary array.

A collision is a situation where the two keys may hash to the same slot. In chaining, we put all the elements that hash to the same slot in a linked list. The dictionary operations on a hash table T are easy to implement when collisions are resolved by chaining.

A good hash function satisfies the assumption of simple uniform hashing; each key is equally likely to hash to any of the m slots, independently of where any other key has hashed to.

Universal hashing is a technique of choosing the hash function randomly in a way that is independent of the keys that are actually going to be stored.

In open addressing, all elements are stored in the hash table itself. Each table entry contains either an element of the dynamic set or nil.

It is one of the best methods available for open addressing because the permutations produced have many of the characteristics of randomly chosen permutations. Double hashing
uses a hash function of the form h(k,I)=(h1(k)+Ih2(k)) mod m, where h1 and h2 are auxiliary
hash functions.

It is a binary tree where in addition to a key field and satellite data, each node contains
fields left, right and p that point to the nodes corresponding to its left child, its right child
and its parent, respectively. If a child or the parent is missing, the appropriate field
contains the value NIL. The root node is the only node in the tree whose parent field is

Let x be a node in a binary search tree. If y is a node on the left subtree of x, then
key[y] £ key[x]. If y is a node in the right subtree of x, then key[x] £ key[y].

A red black tree is a binary search tree with one extra bit of storage per node. Its color can be either RED or BLACK.

An AVL tree is a binary search tree that is height balanced: for each node x, the heights of the left and right subtrees of x differ by atmost 1. To implement an AVL tree, we maintain an extra field in each node: h[x] is the height of node x.

It is a binary search tree with a modified way of ordering the nodes. Each node x in the tree has a key value—key [x]. In addition, we assign priority [x], which is a random number chosen independently for each node. All priorities are distinct and also all keys are distinct.

It is simply a red-black tree with additional information stored in each node.

Augmenting a data structure can be broken into four steps:
(a) Choosing an underlying data structure;
(b) Determining additional information to be maintained in the underlying data structure;
(c) Verifying that the additional information can be maintained for the basic modifying operations on the underlying data structure;
(d) Developing new operations.

For a given set of probabilities, our goal is to construct a binary search tree whose expected search cost is smallest. We call such a tree an optimal binary search tree.

A greedy algorithm always makes the choice that looks best at the moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. Greedy algorithms do not always yield optimal solutions, but for many problems

It is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.

It is the method of using probability to analyze problems. We use probabilistic analysis to analyze the running time of an algorithm.

We call an algorithm randomized if its behavior is determined not only by its input but also by values produced by a random-number generator.

A data structure is a way to store and organize data in order to facilitate access and modifications.

The (binary) heap data structure is an array object that can be viewed as a nearly complete binary tree. Each node of the tree corresponds to an element of the array that stores the value in the node.

A priority queue is a data structure for maintaining a set of elements, each with an associated value called a key.

Counting sort assumes that each of the n input elements is an integer in the range 0 to k for some integer k, when k = O(n), the sort runs in O(n) time.

Bucket sort runs in linear time when the input is drawn from a uniform distribution. Bucket sort is fast because it assumes something about the input.

Stacks and queues are dynamic sets in which the element removed from the set by the DELETE operation is pre-specified. In a stack, the policy is LIFO (Last-in, First-out). In a queue, the policy is FIFO (First-in, First-out).

A linked list is a data structure in which the objects are arranged in a linear order.

A binary tree T is a structure defined on a finite set of nodes that either contains no nodes, or is composed of three disjoined sets of nodes: a root node, a binary tree called its left subtree, and a binary tree called its right subtree.

The binary tree that contains no nodes is called the empty tree or null tree.

It is a binary tree where each node is either a leaf or has degree exactly 2.

It is a positional tree in which for every node, all children with labels greater than k are missing. Thus, a binary tree is a k-ary tree with k=2. A complete k-ary tree is a k-ary tree in which all leaves have the same depth and all internal nodes have degree k.

A hash table is an effective data structure for implementing dictionaries. The expected time to search for an element in a hash table is O(1). A hash table is a generalization of the simple notion of an ordinary array.

A collision is a situation where the two keys may hash to the same slot. In chaining, we put all the elements that hash to the same slot in a linked list. The dictionary operations on a hash table T are easy to implement when collisions are resolved by chaining.

A good hash function satisfies the assumption of simple uniform hashing; each key is equally likely to hash to any of the m slots, independently of where any other key has hashed to.

Universal hashing is a technique of choosing the hash function randomly in a way that is independent of the keys that are actually going to be stored.

In open addressing, all elements are stored in the hash table itself. Each table entry contains either an element of the dynamic set or nil.

It is one of the best methods available for open addressing because the permutations produced have many of the characteristics of randomly chosen permutations. Double hashing
uses a hash function of the form h(k,I)=(h1(k)+Ih2(k)) mod m, where h1 and h2 are auxiliary
hash functions.

It is a binary tree where in addition to a key field and satellite data, each node contains
fields left, right and p that point to the nodes corresponding to its left child, its right child
and its parent, respectively. If a child or the parent is missing, the appropriate field
contains the value NIL. The root node is the only node in the tree whose parent field is

Let x be a node in a binary search tree. If y is a node on the left subtree of x, then
key[y] £ key[x]. If y is a node in the right subtree of x, then key[x] £ key[y].

A red black tree is a binary search tree with one extra bit of storage per node. Its color can be either RED or BLACK.

An AVL tree is a binary search tree that is height balanced: for each node x, the heights of the left and right subtrees of x differ by atmost 1. To implement an AVL tree, we maintain an extra field in each node: h[x] is the height of node x.

It is a binary search tree with a modified way of ordering the nodes. Each node x in the tree has a key value—key [x]. In addition, we assign priority [x], which is a random number chosen independently for each node. All priorities are distinct and also all keys are distinct.

It is simply a red-black tree with additional information stored in each node.

Augmenting a data structure can be broken into four steps:
(a) Choosing an underlying data structure;
(b) Determining additional information to be maintained in the underlying data structure;
(c) Verifying that the additional information can be maintained for the basic modifying operations on the underlying data structure;
(d) Developing new operations.

For a given set of probabilities, our goal is to construct a binary search tree whose expected search cost is smallest. We call such a tree an optimal binary search tree.

A greedy algorithm always makes the choice that looks best at the moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. Greedy algorithms do not always yield optimal solutions, but for many problems