Explore topic-wise InterviewSolutions in Current Affairs.

Heap is a special tree-based non-linear data structure in which the tree is a complete binary tree. A binary tree is said to be complete if all levels are completely filled except possibly the last level and the last level has all elements as left as possible. Heaps are of two types:

• 
  Max-Heap:
  
  
  • In a Max-Heap the data element present at the root node must be the greatest among all the data elements present in the tree.
  
  
  • This property should be recursively true for all sub-trees of that binary tree.
  
  
  
  


• 
  Min-Heap:
  
  
  • In a Min-Heap the data element present at the root node must be the smallest (or minimum) among all the data elements present in the tree.
  
  
  • This property should be recursively true for all sub-trees of that binary tree.
  
  
  
  

LRU cache or Least Recently Used cache allows quick identification of an element that hasn’t been put to use for the longest time by organizing items in order of use. In order to achieve this, two data structures are used:

• 
  Queue – This is implemented using a doubly-linked list. The maximum size of the queue is determined by the cache size, i.e by the total number of available frames. The least recently used pages will be near the front end of the queue whereas the most recently used pages will be towards the rear end of the queue.


• 
  Hashmap – Hashmap stores the page number as the key along with the address of the corresponding queue node as the value.

Red Black Trees are a type of self-balancing binary search tree. Rudolf Bayer invented it in 1972 and dubbed it "symmetric binary B-trees."

A red-black tree is a Binary tree in which each node has a colour attribute, either red or black. By comparing the node colours on any simple path from the root to a leaf, red-black trees ensure that no path is more than twice as long as any other, ensuring that the tree is generally balanced.

Red-black trees are similar to binary trees in that they both store their data in two's complementary binary formats. However, red-black trees have one important advantage over binary trees: they are faster to access. Because red-black trees are so fast to access, they are often used to store large amounts of data.

Red-black trees can be used to store any type of data that can be represented as a set of values.

Every Red-Black Tree Obeys the Following Rules: 

• Every node is either red or black.


• The tree's root is always black.


• There are no two red nodes that are adjacent.


• There is the same number of black nodes on every path from a node to any of its descendant's NULL nodes.


• All of the leaf nodes are black.

Following are some real-time applications for the Red-Black Tree data structure:

• The majority of self-balancing BST library functions in C++ or Java use Red-Black Trees.


• It is used to implement Linux CPU Scheduling.


• It is also used to reduce time complexity in the K-mean clustering algorithm in machine learning.


• MySQL also employs the Red-Black tree for table indexes in order to reduce searching and insertion time.

The word "Trie" is an abbreviation for "retrieval." Trie is a data structure that stores a set of strings as a sorted tree. Each node has the same number of pointers as the number of alphabet characters. It can look up a word in the dictionary by using its prefix. Assuming that all strings are formed from the letters 'a' to 'z' in the English alphabet, each trie node can have a maximum of 26 points.

Trie is also referred to as the digital tree or the prefix tree. The key to which a node is connected is determined by its position in the Trie. Trie allows us to insert and find strings in O(L) time, where L is the length of a single word. This is clearly faster than BST. Because of how it is implemented, this is also faster than Hashing. There is no need to compute a hash function. There is no need to handle collisions (like we do in open addressing and separate chaining)

Another benefit of Trie is that we can easily print all words in alphabetical order, which is not easy with hashing. Trie can also perform prefix search (or auto-complete) efficiently.

The main disadvantage of tries is that they require a large amount of memory to store the strings. We have an excessive number of node pointers for each node 

Following are some real-time applications for Trie data structure:

• Auto-Complete and Search for Search Engines


• Genome Analysis


• Data Analytics


• Browser History


• Spell Checker

A segment Tree is a binary tree that is used to store intervals or segments. The Segment Tree is made up of nodes that represent intervals. Segment Tree is used when there are multiple range queries on an array and changes to array elements.

The segment tree of array A[7] will look like this:

Following are key operations performed on the Segment tree data structure:

• Building Tree: In this step, we create the structure and initialize the segment tree variable.


• Updating the Tree: In this step, we change the tree by updating the array value at a point or over an interval.


• Querying Tree: This operation can be used to run a range query on the array.

Following are real-time applications for Segment Tree:

• Used to efficiently list all pairs of intersecting rectangles from a list of rectangles in the plane.


• The segment tree has become popular for use in pattern recognition and image processing.


• Finding range sum/product, range max/min, prefix sum/product, etc


• Computational geometry


• Geographic information systems


• Static and Dynamic RMQ (Range Minimum Query)


• Storing segments in an arbitrary manner

The B Tree is a type of m-way tree that is commonly used for disc access. A B-Tree with order m can only have m-1 keys and m children. One of the primary reasons for using a B tree is its ability to store a large number of keys in a single node as well as large key values while keeping the tree's height relatively small.

A B-tree of order 4 is shown below in the image:

Following are the key properties of a B-tree data structure:

• All of the leaves are at the same height.


• The term minimum degree 't' describes a B-Tree. The value of t is determined by the size of the disc block.


• Except for root, every node must have at least t-1 keys. The root must contain at least one key.


• All nodes (including root) can have no more than 2*t - 1 keys.


• The number of children of a node is equal to its key count plus one.


• A node's keys are sorted in ascending order. The child of two keys k1 and k2 contains all keys between k1 and k2.


• In contrast to Binary Search Tree, B-Tree grows and shrinks from the root.

Following are real-time applications of a B-Tree data structure:

• It is used to access data stored on discs in large databases.


• Using a B tree, you can search for data in a data set in significantly less time.


• The indexing feature allows for multilevel indexing.


• The B-tree approach is also used by the majority of servers.

AVL trees are height balancing binary search trees named after their inventors Adelson, Velski, and Landis. The AVL tree compares the heights of the left and right subtrees and ensures that the difference is less than one. This distinction is known as the Balance Factor.

BalanceFactor = height(left-subtree) − height(right-subtree)

We can perform the following two operations on AVL tree:

• 
  Insertion: Insertion in an AVL tree is done in the same way that it is done in a binary search tree. However, it may cause a violation in the AVL tree property, requiring the tree to be balanced. Rotations can be used to balance the tree.


• 
  Deletion: Deletion can also be performed in the same manner as in a binary search tree. Because deletion can disrupt the tree's balance, various types of rotations are used to rebalance it.

An AVL tree can balance itself by performing the four rotations listed below:

• 
  Left rotation: When a node is inserted into the right subtree of the right subtree and the tree becomes unbalanced, we perform a single left rotation.


• 
  Right rotation: If a node is inserted in the left subtree of the left subtree, the AVL tree may become unbalanced. The tree then requires right rotation.


• 
  Left-Right rotation: The RR rotation is performed first on the subtree, followed by the LL rotation on the entire tree.


• 
  Right-Left rotation: The LL rotation is performed first on the subtree, followed by the RR rotation on the entire tree.

Following are some real-time applications for AVL tree data structure:

• AVL trees are typically used for in-memory sets and dictionaries.


• AVL trees are also widely used in database applications where there are fewer insertions and deletions but frequent data lookups are required.


• Apart from database applications, it is used in applications that require improved searching.

A graph is a type of non-linear data structure made up of nodes and edges. The nodes are also known as vertices, and edges are lines or arcs that connect any two nodes in the graph.

The following are the two most common graph representations:

1. Adjacency Matrix: Adjacency Matrix is a two-dimensional array with the dimensions V x V, where V is the number of vertices in a graph. Representation is simpler to implement and adhere to. It takes O(1) time to remove an edge. Queries such as whether there is an edge from vertex 'u' to vertex 'v' are efficient and can be completed in O(1).

One of the cons of this representation is that even if the graph is sparse (has fewer edges), it takes up the same amount of space. Adding a vertex takes O(V^2). It also takes O(V) time to compute all of a vertex's neighbours, which is not very efficient.

2. Adjacency List: In this method, each Node holds a list of Nodes that are directly connected to that vertex. Each node at the end of the list is connected with null values to indicate that it is the last node in the list. This saves space O(|V|+|E|). In the worst-case scenario, a graph can have C(V, 2) edges, consuming O(V^2) space. It is simpler to add a vertex. It takes the least amount of time to compute all of a vertex's neighbours.

One of the cons of this representation is that ​queries such as "is there an edge from vertex u to vertex v?" are inefficient and take O (V) in the worst case.

The following table contains an asymptotic analysis of different implementations of a priority queue:

Priority Queue is an abstract data type that is similar to a queue in that each element is assigned a priority value. The order in which elements in a priority queue are served is determined by their priority (i.e., the order in which they are removed). If the elements have the same priority, they are served in the order they appear in the queue.

Following are some real-time applications for priority queue:

• Used in graph algorithms like Dijkstra, Prim’s Minimum spanning tree etc.


• Huffman code for data compression


• Finding Kth Largest/Smallest element

Following are the key operations available deque:

• 
  insertFront(): This adds an element to the front of the Deque.


• 
  insertLast(): This adds an element to the rear of the Deque.


• 
  deleteFront(): This deletes an element from the front of the Deque.


• 
  deleteLast():This deletes an element from the front of the Deque.


• 
  getFront(): This gets an element from the front of the Deque. 


• 
  getRear(): This gets an element from the rear of the Deque. 


• 
  isEmpty(): This checks whether Deque is empty or not.


• 
  isFull(): This checks whether Deque is full or not.

A deque can be thought of as an array of items, but with one important difference: Instead of pushing and popping items off the end to make room, deques are designed to allow items to be inserted at either end. This property makes deques well-suited for performing tasks such as keeping track of inventory, scheduling tasks, or handling large amounts of data.

There are two types of deque:

• 
  Input Restricted Deque: Insertion operations are performed at only one end while deletion is performed at both ends in the input restricted queue.

• 
  Output Restricted Deque: Deletion operations are performed at only one end while insertion is performed at both ends in the output restricted queue.

Following are some real-time applications for deque data structure: 

• It can be used as both stack and queue, as it supports all the operations for both data structures.


• Web browser’s history can be stored in a deque.


• Operating systems job scheduling algorithm.

Tree traversal is the process of visiting all the nodes of a tree. Since the root (head) is the first node and all nodes are connected via edges (or links) we always start with that node. There are three ways which we use to traverse a tree −

1. Inorder Traversal:

• Algorithm:
  
  
  • Step 1. Traverse the left subtree, i.e., call Inorder(root.left)
  
  
  • Step 2. Visit the root.
  
  
  • Step 3. Traverse the right subtree, i.e., call Inorder(root.right)
  
  
  
  


• Inorder traversal in Java:

• Uses: In binary search trees (BST), inorder traversal gives nodes in ascending order.

2. Preorder Traversal:

• Algorithm:
  
  
  • Step 1. Visit the root.
  
  
  • Step 2. Traverse the left subtree, i.e., call Preorder(root.left)
  
  
  • Step 3. Traverse the right subtree, i.e., call Preorder(root.right)
  
  
  
  


• Preorder traversal in Java:

• Uses:
  
  
  • Preorder traversal is commonly used to create a copy of the tree.
  
  
  • It is also used to get prefix expression of an expression tree.
  
  
  
  

3. Postorder Traversal:

• Algorithm:
  
  
  • Step 1. Traverse the left subtree, i.e., call Postorder(root.left)
  
  
  • Step 2. Traverse the right subtree, i.e., call Postorder(root.right)
  
  
  • Step 3. Visit the root.
  
  
  
  


• Postorder traversal in Java:

• Uses:
  
  
  • Postorder traversal is commonly used to delete the tree.
  
  
  • It is also useful to get the postfix expression of an expression tree.
  
  
  
  

Consider the following tree as an example, then:

• Inorder Traversal => Left, Root, Right : [4, 2, 5, 1, 3]


• Preorder Traversal => Root, Left, Right : [1, 2, 4, 5, 3]


• Postorder Traversal => Left, Right, Root : [4, 5, 2, 3, 1]

A binary search tree is a data structure that stores items in sorted order. In a binary search tree, each node stores a key and a value. The key is used to access the item and the value is used to determine whether the item is present or not. The key can be any type of value such as an integer, floating point number, character string, or even a combination of these types. The value can be any type of items such as an integer, floating point number, character string, or even a combination of these types. When a node is added to the tree, its key is used to access the item stored at that node. When a node is removed from the tree, its key is used to access the item stored at that node.

A binary search tree is a special type of binary tree that has a specific order of elements in it. It has three basic qualities:

• All elements in the left subtree of a node should have a value less than or equal to the parent node's value, and


• All elements in the right subtree of a node should have a value greater than or equal to the parent node's value.


• Both the left and right subtrees must be binary search trees too.

Following are some applications for binary tree data structure:

• It is used for indexing and multi-level indexing.


• It is used for implementing various search algorithms.


• It is helpful in organizing a sorted stream of data.

A binary tree is a data structure that is used to organize data in a way that allows for efficient retrieval and manipulation. It is a data structure that uses two nodes, called leaves and nodes, to represent the data. The leaves represent the data and the nodes represent the relationships between the leaves. Each node has two children, called siblings, and each child has one parent. The parent is the node that is closest to the root of the tree. When a node is deleted from the tree, it is deleted from both its child and its parent.

Following are some applications for binary tree data structure:

• It's widely used in computer networks for storing routing table information.


• Decision Trees.


• Expression Evaluation.


• Database indices.