# Best Data structures and Algorithms Interview Questions – 2021

Here is an amazing Collection of most asked Data structures and algorithms interview questions.

**Data structures and algorithms interview Questions**

### What is an Algorithm?

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.

### What is probabilistic analysis?

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

### What is a Randomized 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.

### What is a Data structure?

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

### What is Heap Data structure?

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.

### What is a Priority Queue?

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

### What is Counting sort?

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.

### What is Bucket sort?

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.

### What are Stacks and Queues?

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

### What is a Linked list?

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

### What is a Binary tree?

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.

### What is a null tree?

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

### What is a full binary tree?

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

### What is K-ary tree?

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.

### What is a hash table?

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.

### What are collision and chaining?

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.

### What makes a good hash function?

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.

### What is universal hashing?

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.

### What is open addressing?

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.

### What is double hashing?

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.

### What is a binary search tree?

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

### What is the property of a binary-search tree?

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

### What is a red black tree?

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.

### What is an AVL tree?

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.

### What is a treap?

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.

### What is an order-statistic tree T?

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

### How do we augment a data structure?

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.

### What is an optimal binary search tree?

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.

### What is a Greedy algorithm?

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