Best Data structures and algorithms interview Questions

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