Data Structures and Algorithms (Questions and Answers- II) - Tirthankar Pal - MBA from IIT Kharagpur, GATE, GMAT, IIT Written Test, Interview were a part of MBA Entrance, B.S. in Computer Science from NIELIT

Questions and Answers in Data Structures

a) What is the average and worst case complexity of binary search algorithm?

The best case of Binary Search occurs when:

• The element to be search is in the middle of the list

In this case, the element is found in the first step itself and this involves 1 comparison.Therefore, Best Case Time Complexity of Binary Search is O(1).

The worst case of Binary Search occurs when:

• The element is to search is in the first index or last index

In this case, the total number of comparisons required is logN comparisons.

Therefore, Worst Case Time Complexity of Binary Search is O(logN).

b) What is an adjacency list? When it is used?

Adjacency List: 
An array of lists is used. The size of the array is equal to the number of vertices. Let the array be an array[]. An entry array[i] represents the list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be represented as lists of pairs. Following is the adjacency list representation of the above graph. 
 

c) How do you test for an empty stack?

Stacks are a type of container adaptors with LIFO(Last In First Out) type of working, where a new element is added at one end and (top) an element is removed from that end only.

stack::empty()

empty() function is used to check if the stack container is empty or not. Syntax :

stackname.empty()
Parameters :
No parameters are passed.
Returns :
True, if stack is empty
False, Otherwise

Examples:

Input :   mystack
          mystack.empty();
Output :  True
 
Input :   mystack = 1, 2, 3
Output :  False

Check if the stack is empty, if not add the top element to a variable initialised as 0, and pop the top element. 2. Repeat this step until the stack is empty. 3. Print the final value of the variable. 
CPP
// CPP program to illustrate
// Application of empty() function
#include <iostream>
#include <stack>
using namespace std;
 
int main()
{
    int sum = 0;
    stack<int> mystack;
    mystack.push(1);
    mystack.push(8);
    mystack.push(3);
    mystack.push(6);
    mystack.push(2);
 
    // Stack becomes 1, 8, 3, 6, 2
 
    while (!mystack.empty()) {
        sum = sum + mystack.top();
        mystack.pop();
    }
    cout << sum;
    return 0;
}
Output:
20

d) Distinguish between DFS and BFS.

BFS vs DFS

S. No.	Parameters	BFS	DFS
1.	Stands for	BFS stands for Breadth First Search.	DFS stands for Depth First Search.
2.	Data Structure	BFS(Breadth First Search) uses Queue data structure for finding the shortest path.	DFS(Depth First Search) uses Stack data structure.
3.	Definition	BFS is a traversal approach in which we first walk through all nodes on the same level before moving on to the next level.	DFS is also a traversal approach in which the traverse begins at the root node and proceeds through the nodes as far as possible until we reach the node with no unvisited nearby nodes.
4.	Technique	BFS can be used to find a single source shortest path in an unweighted graph because, in BFS, we reach a vertex with a minimum number of edges from a source vertex.	In DFS, we might traverse through more edges to reach a destination vertex from a source.
5.	Conceptual Difference	BFS builds the tree level by level.	DFS builds the tree sub-tree by sub-tree.
6.	Approach used	It works on the concept of FIFO (First In First Out).	It works on the concept of LIFO (Last In First Out).
7.	Suitable for	BFS is more suitable for searching vertices closer to the given source.	DFS is more suitable when there are solutions away from source.
8.	Suitable for Decision Treestheirwinning	BFS considers all neighbors first and therefore not suitable for decision-making trees used in games or puzzles.	DFS is more suitable for game or puzzle problems. We make a decision, and the then explore all paths through this decision. And if this decision leads to win situation, we stop.
9.	Time Complexity	The Time complexity of BFS is O(V + E) when Adjacency List is used and O(V^2) when Adjacency Matrix is used, where V stands for vertices and E stands for edges.	The Time complexity of DFS is also O(V + E) when Adjacency List is used and O(V^2) when Adjacency Matrix is used, where V stands for vertices and E stands for edges.
10.	Visiting of Siblings/ Children	Here, siblings are visited before the children.	Here, children are visited before the siblings.
11.	Removal of Traversed Nodes	Nodes that are traversed several times are deleted from the queue.	The visited nodes are added to the stack and then removed when there are no more nodes to visit.
12.	Backtracking	In BFS there is no concept of backtracking.	DFS algorithm is a recursive algorithm that uses the idea of backtracking
13.	Applications	BFS is used in various applications such as bipartite graphs, shortest paths, etc.	DFS is used in various applications such as acyclic graphs and topological order etc.
14.	Memory	BFS requires more memory.	DFS requires less memory.
15.	Optimality	BFS is optimal for finding the shortest path.	DFS is not optimal for finding the shortest path.
16.	Space complexity	In BFS, the space complexity is more critical as compared to time complexity.	DFS has lesser space complexity because at a time it needs to store only a single path from the root to the leaf node.
17.	Speed	BFS is slow as compared to DFS.	DFS is fast as compared to BFS.
18.	When to use?	When the target is close to the source, BFS performs better.	When the target is far from the source, DFS is preferable.

e) Which sorting algorithm is of divide-and-conquer type? What is its average case complexity?

Divide-and-conquer

Both merge sort and quicksort employ a common algorithmic paradigm based on recursion. This paradigm, divide-and-conquer, breaks a problem into subproblems that are similar to the original problem, recursively solves the subproblems, and finally combines the solutions to the subproblems to solve the original problem. Because divide-and-conquer solves subproblems recursively, each subproblem must be smaller than the original problem, and there must be a base case for subproblems. You should think of a divide-and-conquer algorithm as having three parts:

1. Divide the problem into a number of subproblems that are smaller instances of the same problem.
2. Conquer the subproblems by solving them recursively. If they are small enough, solve the subproblems as base cases.
3. Combine the solutions to the subproblems into the solution for the original problem.

You can easily remember the steps of a divide-and-conquer algorithm as divide, conquer, combine. Here's how to view one step, assuming that each divide step creates two subproblems (though some divide-and-conquer algorithms create more than two):

If we expand out two more recursive steps, it looks like this:

Because divide-and-conquer creates at least two subproblems, a divide-and-conquer algorithm makes multiple recursive calls.

f) What are the various applications of graphs?

Applications of Graphs in Data Structure

Graphs data structures have a variety of applications. Some of the most popular applications are:

• Helps to define the flow of computation of software programs.
• Used in Google maps for building transportation systems. In google maps, the intersection of two or more roads represents the node while the road connecting two nodes represents an edge. Google maps algorithm uses graphs to calculate the shortest distance between two vertices.
• Used in social networks such as Facebook and Linkedin.
• Operating Systems use Resource Allocation Graph where every process and resource acts as a node while edges are drawn from resources to the allocated process.
• Used in the world wide web where the web pages represent the nodes.
• Blockchains also use graphs. The nodes are blocks that store many transactions while the edges connect subsequent blocks.
• Used in modeling data.

g) Which data structure is used to perform recursion and why?

Recursion and Stacks

Let's take a close look at the mechanism with which a recursive program is actually implemented by the compiler. In the previous example, we have seen how a recursion executes its forward and backing-out phases. The order in which the recursive process backs out is the reverse of the order in which it goes forward. Thus some action may be performed that involves recalling something that has been stored in the forward process. The compiler uses a stack to implement recursion.

• In the forwarding phase, the values of local variables and parameters, and the return address are pushed on the stack for every level of the recursion
• In the backing-out phase, the stacked address is popped and used to return to executing the rest of the code in the calling level, and the stacked local variables and parameters are popped and used to restore the state of that call

h) What are the different ways of representing a binary tree?

Given an array that represents a tree in such a way that array indexes are values in tree nodes and array values give the parent node of that particular index (or node). The value of the root node index would always be -1 as there is no parent for root. Construct the standard linked representation of given Binary Tree from this given representation. Do refer in order to understand how to construct binary tree from given parent array representation.

Ways to represent: 

Trees can be represented in two ways as listed below:

1. Dynamic Node Representation (Linked Representation).
2. Array Representation (Sequential Representation).
3. Now, we are going to talk about the sequential representation of the trees.  In order to represent a tree using an array, the numbering of nodes can start either from 0–(n-1) or 1– n, consider the below illustration as follows:

Illustration:

       A(0)    
     /   \
    B(1)  C(2)  
  /   \      \
 D(3)  E(4)   F(6) 
OR,
      A(1)    
     /   \
    B(2)  C(3)  
  /   \      \
 D(4)  E(5)   F(7)  

Procedure:

Note: father, left_son and right_son are the values of indices of the array.

 Case 1: (0—n-1) 

if (say)father=p; 
then left_son=(2*p)+1; 
and right_son=(2*p)+2;

Case 2: 1—n

if (say)father=p; 
then left_son=(2*p); 
and right_son=(2*p)+1; 

i) How you can measure the efficiency of an algorithm?

A good algorithm is correct, but a great algorithm is both correct and efficient. The most efficient algorithm is one that takes the least amount of execution time and memory usage possible while still yielding a correct answer.

Counting the operations

One way to measure the efficiency of an algorithm is to count how many operations it needs in order to find the answer across different input sizes.

Let's start by measuring the linear search algorithm, which finds a value in a list. The algorithm looks through each item in the list, checking each one to see if it equals the target value. If it finds the value, it immediately returns the index. If it never finds the value after checking every list item, it returns -1.

Here's what that algorithm looks like in pseudocode:

PROCEDURE searchList(numbers, targetNumber) {
  index ← 1
  REPEAT UNTIL (index > LENGTH(numbers)) {
    IF (numbers[index] = targetNumber) {
      RETURN index
    }
    index ← index + 1
  }
  RETURN -1
}

j) What are the limitations and advantages of two-way linked list over one-way linked list?

Advantages Of DLL:

• Reversing the doubly linked list is very easy.
• It can allocate or reallocate memory easily during its execution.
• As with a singly linked list, it is the easiest data structure to implement.
• The traversal of this doubly linked list is bidirectional which is not possible in a singly linked list.
• Deletion of nodes is easy as compared to a Singly Linked List. A singly linked list deletion requires a pointer to the node and previous node to be deleted but in the doubly linked list, it only required the pointer which is to be deleted.

Disadvantages Of DLL:

• It uses extra memory when compared to the array and singly linked list.
• Since elements in memory are stored randomly, therefore the elements are accessed sequentially no direct access is allowed.

Tirthankar Pal

MBA from IIT Kharagpur with GATE, GMAT, IIT Kharagpur Written Test, and Interview
2 year PGDM (E-Business) from Welingkar, Mumbai
4 years of Bachelor of Science (Hons) in Computer Science from the National Institute of Electronics and Information Technology
Google and Hubspot Certification
Brain Bench Certification in C++, VC++, Data Structure and Project Management
10 years of Experience in Software Development out of that 6 years 8 months in Wipro
Selected in Six World Class UK Universities:-
King's College London, Durham University, University of Exeter, University of Sheffield, University of Newcastle, University of Leeds