Explore topic-wise InterviewSolutions in Current Affairs.

This section includes 7 InterviewSolutions, each offering curated multiple-choice questions to sharpen your Current Affairs knowledge and support exam preparation. Choose a topic below to get started.

1.

What is topological sorting in a graph?

Answer»

  • Topological sorting is a linear ordering of vertices such that for every directed edge ij, vertex i comes before j in the ordering.

  • Topological sorting is only possible for Directed Acyclic Graph (DAG).

  • Applications:

    1. jobs scheduling from the given dependencies among jobs.

    2. ordering of formula cell evaluation in spreadsheets

    3. ordering of compilation tasks to be performed in make files,

    4. data serialization

    5. resolving symbol dependencies in linkers.



  • Topological Sort Code in Java:

// V - total vertices
// visited - boolean array to keep track of visited nodes
// graph - adjacency list.
// Main Topological Sort Function.
void topologicalSort()
{
Stack<Integer> stack = new Stack<Integer>();

// Mark all the vertices as not visited
boolean visited[] = new boolean[V];
for (int j = 0; j < V; j++){
visited[j] = false;
}
// Call the util function starting from all vertices one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, stack);

// Print contents of stack -> result of topological sort
while (stack.empty() == false)
System.out.print(stack.pop() + " ");
}

// A helper function used by topologicalSort
void topologicalSortUtil(int v, boolean visited[],
Stack<Integer> stack)
{
// Mark the current node as visited.
visited[v] = true;
Integer i;

// Recur for all the vertices adjacent to the current vertex
Iterator<Integer> it = graph.get(v).iterator();
while (it.hasNext()) {
i = it.next();
if (!visited[i])
topologicalSortUtil(i, visited, stack);
}

// Push current vertex to stack that saves result
stack.push(new Integer(v));
} Conclusion

In this post, we covered the most important and frequently asked Data Structures interview questions. We've also included some pointers and tricks to help you prepare for the interview. When preparing for the product-based companies interview, keep in mind that the Data Structures interview is a critical component of the process. It is critical that you are well prepared for the interview because it will determine whether or not you are hired. As a result, it is critical to begin planning as soon as possible.

Additional Interview Resources

  • Programming: DSA - https://www.interviewbit.com/courses/programming/

  • Data Structure MCQ - https://www.interviewbit.com/data-structure-mcq/

  • Best Books for Data Structures and Algorithms - https://www.interviewbit.com/blog/data-structures-and-algorithms-books/

  • Best Data Structures and Algorithms Course - https://www.interviewbit.com/blog/best-courses-for-data-structures-and-algorithms/

  • Algorithm Interview Questions - https://www.interviewbit.com/algorithm-interview-questions/

  • Master Data Structures and Algorithms With the Scaler Academy Program - https://www.scaler.com/courses/data-structures-and-algorithms/
Discussion
2.

Given an m x n 2D grid map of '1’s which represents land and '0’s that represents water return the number of islands (surrounded by water and formed by connecting adjacent lands in 2 directions - vertically or horizontally).

Answer»
Assume that the boundary cases - which are all four edges of the grid are surrounded by water. Constraints are: m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] can only be ‘0’ or ‘1’. Example: Input: grid = [
[“1” , “1” , “1” , “0” , “0”],
[“1” , “1” , “0” , “0” , “0”],
[“0” , “0” , “1” , “0” , “1”],
[“0” , “0” , “0” , “1” , “1”]
] Output: 3 class InterviewBit {
public int numberOfIslands(char[][] grid) {
if(grid==null || grid.length==0||grid[0].length==0)
return 0;

int m = grid.length;
int n = grid[0].length;

int count=0;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(grid[i][j]=='1'){
count++;
mergeIslands(grid, i, j);
}
}
}

return count;
}

public void mergeIslands(char[][] grid, int i, int j){
int m=grid.length;
int n=grid[0].length;

if(i<0||i>=m||j<0||j>=n||grid[i][j]!='1')
return;

grid[i][j]='X';

mergeIslands(grid, i-1, j);
mergeIslands(grid, i+1, j);
mergeIslands(grid, i, j-1);
mergeIslands(grid, i, j+1);
}
}
Discussion
3.

Print Left view of any binary trees.

Answer»

  • The main idea to solve this problem is to traverse the tree in pre order manner and pass the level information along with it. If the level is visited for the first time, then we store the information of the current node and the current level in the hashmap. Basically, we are getting the left view by noting the first node of every level.

  • At the end of traversal, we can get the solution by just traversing the map.

  • Consider the following tree as example for finding the left view:

  • Left view of a binary tree in Java:

import java.util.HashMap;

//to store a Binary Tree node
class Node
{
int data;
Node left = null, right = null;

Node(int data) {
this.data = data;
}
}
public class InterviewBit
{
// traverse nodes in pre-order way
public static void leftViewUtil(Node root, int level, HashMap<Integer, Integer> map)
{
if (root == null) {
return;
}

// if you are visiting the level for the first time
// insert the current node and level info to the map
if (!map.containsKey(level)) {
map.put(level, root.data);
}

leftViewUtil(root.left, level + 1, map);
leftViewUtil(root.right, level + 1, map);
}

// to print left view of binary tree
public static void leftView(Node root)
{
// create an empty HashMap to store first node of each level
HashMap<Integer, Integer> map = new HashMap<>();

// traverse the tree and find out the first nodes of each level
leftViewUtil(root, 1, map);

// iterate through the HashMap and print the left view
for (int i = 0; i <map.size(); i++) {
System.out.print(map.get(i) + " ");
}
}

public static void main(String[] args)
{
Node root = new Node(4);
root.left = new Node(2);
root.right = new Node(6);
root.left.left = new Node(1);
root.left.left = new Node(3);
root.right.left = new Node(5);
root.right.right = new Node(7);
root.right.left.left = new Node(9);

leftView(root);
}
}
Discussion
4.

Write Java code to count number of nodes in a binary tree

Answer»
int countNodes(Node root)
{
int count = 1; //Root itself should be counted
if (root ==null)
return 0;
else
{
count += countNodes(root.left);
count += countNodes(root.right);
return count;
}
}
Discussion
5.

Write a recursive function to calculate the height of a binary tree in Java.

Answer»
  • Consider that every node of a tree represents a class called Node as given below:
public class Node{
int data;
Node left;
Node right;
}
  • Then the height of the binary tree can be found as follows:
int heightOfBinaryTree(Node node)
{
if (node == null)
return 0; // If node is null then height is 0 for that node.
else
{
// compute the height of each subtree
int leftHeight = heightOfBinaryTree(node.left);
int rightHeight = heightOfBinaryTree(node.right);
//use the larger among the left and right height and plus 1 (for the root)
return Math.max(leftHeight, rightHeight) + 1;
}
}
Discussion
6.

Write a function to determine whether duplicate elements in a given array are within a given distance of each other.

Answer»


  • Input: arr[] = {1, 2, 3, 4, 2, 1, 2} range=3


  • Output: True

class Solution {
public:

bool checkDuplicatesWithinRange(vector<int> arr, int range)
{
// Creating an empty hashset
unordered_set<int> myset;

// Traversing the input array
for (int i = 0; i < arr.size(); i++)
{
// If already present in hashset, then we found a duplicate within range distance
if (myset.find(arr[i]) != myset.end())
return true;

// Add this item to hashset
myset.insert(arr[i]);

// Remove the range+1 distant item from the hashset
if (i >= range)
myset.erase(arr[i-range]);
}
return false;
}
};


  • Time Complexity: O(n)


  • Space Complexity: O(n)
Discussion
7.

Implement LRU(Least Recently Used) Cache

Answer»
class LRUCache
{
private:
class node_t {
public:
int key;
int value;
node_t * next;
node_t * prev;
};

int cap;
node_t head;
unordered_map<int, node_t*> tbl;

void remove_node(node_t * node) {
node->next->prev = node->prev;
node->prev->next = node->next;
}
void add_node(node_t * node) {
node->next = head.next;
node->prev = &head;
head.next = node;
node->next->prev = node;
}
public:
//Constructor for initializing the cache capacity with the given value.
LRUCache(int cap): cap(cap)
{
// code here
head.prev = &head;
head.next = &head;
}

//Function to return value corresponding to the key.
int get(int key)
{
// your code here
unordered_map<int, node_t*>::iterator it = tbl.find(key);
if(it==tbl.end())
return -1;
remove_node(it->second);
add_node(it->second);
return it->second->value;
}

//Function for storing key-value pair.
void set(int key, int value)
{
// your code here
unordered_map<int, node_t*>::iterator it = tbl.find(key);
if(it!=tbl.end())
{
remove_node(it->second);
add_node(it->second);
it->second->value = value;
}
else {
node_t * node = new node_t;
node->key = key;
node->value = value;
add_node(node);
tbl[key] = node;
if(tbl.size()>cap) {
auto * old_node = head.prev;
tbl.erase(old_node->key);
remove_node(old_node);
delete old_node;
}
}
}
};


  • Time Complexity: O(1) to get an element


  • Space Complexity: O(n)
Discussion
8.

Write a function to find number of structurally unique binary trees are possible

Answer»

Input: N = 3 

Output: 5 for N = 3, there are 5 possible BSTs:

1           3      3        2 1

   \         /      /          /  \   \

     3     2      1      1    3     2

   /      /          \                     \

2      1         2                       3

class Solution
{
public:
//function to calculate binomial coefficient C(n,k)
long long int binomialCoefficient(long long int n, long long int k)
{
long long int res = 1;
if (k > n - k)
k = n - k;

for (long long int i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}

return res;
}

//function to calculate Nth Catalan Number
long long int catalanNumber(long long in n)
{
// Calculate value of 2nCn
long long int C = binomialCoefficient(2*n, n);

// return 2nCn/(n+1)
return C/(n+1);
}

//Function to return the total number of possible unique BST.
long long int numOfUniqueBinarySearchTrees(int n)
{
// find nth catalan number
long long int countOfUniqueBinarySearchTrees = catalanNumber(n);

// return nth catalan number
return countOfUniqueBinarySearchTrees;
}
};


  • Time Complexity: O(n) 


  • Space Complexity: O(1)
Discussion
9.

Write a function to connect nodes at the same level of a binary tree

Answer»

Input:              100    

                        /     \                

                   13      15   

                   /  \         \       

              14    1        20 

     

Output:          100-> NULL    

                        /      \                

                  13   ->  15   -> NULL

                  /      \           \       

               14  ->  1   -> 20 -> NULL

class Solution
{
public:
//Function to connect nodes at the same level.
void connect(Node *p)
{
map<int,vector<Node *> > m;
queue<Node *> q;
queue<int> l;
q.push(p);
l.push(0);
while(!q.empty())
{
Node *temp=q.front();
int level=l.front();
q.pop();
l.pop();
m[level].push_back(temp);
if(temp->left!=NULL)
{
q.push(temp->left);
l.push(level+1);
}
if(temp->right!=NULL)
{
q.push(temp->right);
l.push(level+1);
}
}
for(map<int,vector<Node *> > ::iterator it=m.begin();it!=m.end();it++)
{
vector<Node *> temp1=it->second;
for(int i=0;i<temp1.size()-1;i++)
{
temp1[i]->nextRight=temp1[i+1];
}
temp1[temp1.size()-1]->nextRight=NULL;
}
}
};


  • Time Complexity: O(n)


  • Space Complexity: O(n)
Discussion
10.

Write a function to implement Quicksort on Doubly Linked List

Answer»


  • Input: 8<->10<->1<->7<->6


  • Output: 1<->6<->7<->8<->10

class Solution{
public:
Node* partition(Node *l, Node *h){
//Your code goes here
Node*temp = h;
Node*tt = l;
Node*first = l;

while(tt != h){
if(tt->data <= temp->data){
swap(first->data, tt->data);
first = first->next;
}
tt = tt -> next;
}
swap(first-> data, h->data);
return first;

}
};

void _quickSort(struct Node* l, struct Node *h)
{
if (h != NULL && l != h && l != h->next)
{
Solution ob;
struct Node *p = ob.partition(l, h);
_quickSort(l, p->prev);
_quickSort(p->next, h);
}
}

void quickSort(struct Node *head)
{
struct Node *h = lastNode(head);
_quickSort(head, h);
}


  • Time Complexity: O(n^2) in the worst case when the list is already sorted. O(nlog(n)) in the best and average case.


  • Space Complexity: O(n)
Discussion
11.

Find the subsequence of length 3 with the highest product from a sequence of non-negative integers, with the elements in increasing order.

Answer»


  • Input: n = 8 arr[ ] = {6, 7, 10, 1, 2, 3, 11, 12}


  • Output: {10, 11, 12}

The three increasing elements of the given arrays are 10, 11, and 12, which form a three-size subsequence with the highest product.

vector<int> maxProductSubsequence(int *a , int n)
{
set<int> s;
long long largestOnLeft[n];
for(int i=0;i<n;i++)
{
s.insert(a[i]);
auto it=s.lower_bound(a[i]);
if(it==s.begin())
{
largestOnLeft[i]=-1;
continue;
}
it--;
largestOnLeft[i]=*it;
}
int m=0;
long long p=INT_MIN;
vector<int> result(3);
result[0]=-1;
for(int i=n-1;i>=0;i--)
{
if(a[i]>=m){
m=a[i];}
else
{
if(largestOnLeft[i] !=-1)
{
if(largestOnLeft[i]*a[i]*m >p)
{
p=largestOnLeft[i]*a[i]*m;
result[0]=largestOnLeft[i];
result[1]=a[i];
result[2]=m;
}
}
}
}
return v;
}


  • Time Complexity: O(nlog(n))


  • Space Complexity: O(n)
Discussion
12.

Write a function to find number of subarrays with product less than K

Answer»


  • Input: arr = [1, 6, 2, 3, 2, 1], k = 12


  • Output: 11

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int ans=0;
int pdt=1;
int left=0,right=0;
while(right<=nums.size()-1){

pdt*=nums[right];
while(pdt>=k and left<nums.size()){
pdt/=nums[left];
left++;

}
if(right-left>=0)
ans+=right-left+1;//since on adding a new element new subarrays formed is r-i+1;
right++;

}
return ans;
}


  • Time Complexity: O(n)


  • Space Complexity: O(1)
Discussion
13.

Write a function to print all unique rows of the given matrix.

Answer»

Input:

     {{1, 1, 1, 0, 0},

      {0, 1, 0, 0, 1},

      {1, 0, 1, 1, 0},

      {0, 1, 0, 0, 1},

      {1, 1, 1, 0, 0}}


Output:

    {{1, 1, 1, 0, 0},

     {0, 1, 0, 0, 1},

     {1, 0, 1, 1, 0}}

vector<vector<int>> uniqueRow(int M[MAX][MAX],int row,int col)
{
set<vector<int>> st;
vector<vector<int>> v;

for(int i=0; i<row; i++) {
vector<int> v1;
for(int j=0; j<col; j++) {
v1.push_back(M[i][j]);
}
if(st.count(v1) == 0) {
v.push_back(v1);
st.insert(v1);
}
}

return v;
}


  • Time Complexity: O( ROW x COL )


  • Space Complexity: O( ROW )
Discussion
14.

Write a function to merge two sorted binary search tree

Answer»

Input:

First BST 

       7

    /     \

   5       9

Second BST

    4

  /   \

3       12

Output: 3 4 5 6 7 9 12

//Function to return a list of integers denoting the node
//values of both the BST in a sorted order.
void inorder(Node*root,vector<int>&v){
if(root==NULL)
return;
inorder(root->left,v);
v.push_back(root->data);
inorder(root->right,v);
}
vector<int> merge(vector<int>v1,vector<int>v2){
vector<int>v;
int n1=v1.size(),n2=v2.size(),i=0,j=0;
while(i<n1&&j<n2){
if(v1[i]>v2[j]){
v.push_back(v2[j]);
j++;
}
else{
v.push_back(v1[i]);
i++;
}
}
while(i<n1){
v.push_back(v1[i]);
i++;
}
while(j<n2){
v.push_back(v2[j]);
j++;
}
return v;
}
vector<int> merge(Node *root1, Node *root2)
{
vector<int>v1,v2;
inorder(root1,v1);
inorder(root2,v2);
return merge(v1,v2);
}


  • Time Complexity: O(m+n) 


  • Space Complexity: O(height of the first tree + height of the second tree)
Discussion
15.

Write a function to find the maximum for each and every contiguous subarray of size k.

Answer»


  • Input: N = 9, K = 3 arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}


  • Output: {3, 3, 4, 5, 5, 5, 6}


  • Explanation: In the first subarray of size 3: {1,2,3}, the value 3 is maximum, similarly for all such subarrays for size 3.

//function to find maximum in each subarray using sliding window approach
vector<int> max_of_subarrays(vector<int> arr, int n, int k){
int i=0,j=0;
deque<int> dq;
dq.push_front(i++);
while(i<k)
{
while(!dq.empty()&&arr[dq.back()]<=arr[i])
dq.pop_back();
dq.push_back(i++);
}
vector<int> ans;
while(i<n)
{
ans.push_back(arr[dq.front()]);
while(!dq.empty()&&j>=dq.front())
{
dq.pop_front();

}
j++;
while(!dq.empty()&&arr[dq.back()]<=arr[i])
dq.pop_back();
dq.push_back(i++);
}
ans.push_back(arr[dq.front()]);
return ans;

}


  • Time Complexity: O(n)


  • Space Complexity: O(k)
Discussion
16.

Write a function to convert an infix expression to postfix expression

Answer»


  • Input: a+b*(c^d)


  • Output: abcd^*+

int prec(char c)
{
if (c == '^')
return 3;
else if (c == '/' || c == '*')
return 2;
else if (c == '+' || c == '-')
return 1;
else
return -1;
}
public:
// Function to convert an infix expression to a postfix expression.
string infixToPostfix(string s) {
stack<char> st; // For stack operations, we are using C++ built in stack
string result;

for (int i = 0; i < s.length(); i++) {
char c = s[i];

// If the scanned character is
// an operand, add it to the output string.
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
|| (c >= '0' && c <= '9'))
result += c;

// If the scanned character is an
// '(', push it to the stack.
else if (c == '(')
st.push('(');

// If the scanned character is an ')',
// pop and to output string from the stack
// until an '(' is encountered.
else if (c == ')') {
while (st.top() != '(') {
result += st.top();
st.pop();
}
st.pop();
}

// If an operator is scanned
else {
while (!st.empty()
&& prec(s[i]) <= prec(st.top())) {
if (c == '^' && st.top() == '^')
break;
else {
result += st.top();
st.pop();
}
}
st.push(c);
}
}

// Pop all the remaining elements from the stack
while (!st.empty()) {
result += st.top();
st.pop();
}

return result;
}


  • Time Complexity: O(n)


  • Space Complexity: O(n)
Discussion
17.

Write a function to detect cycle in an undirected graph

Answer»


  • Input: n = 4, e = 4 , 0 1, 1 2, 2 3, 3 1


  • Output: Yes


  • Explanation: The graph is represented as follows in adjacency list representation:
    0->1
    1->2
    2->3
    3->1

From the above representation, we can see that there exists a cycle: 1→2→3→1

//function to run dfs for a given node in the graph
int dfs(int v,vector<int> adj[],vector<int> &visited,vector<int> &rec,int i,int parent){
int ans=0;
visited[i]=1;
rec[i]=1;
for(auto x : adj[i]){
if(x!=parent) {
if(rec[x])
return 1;
ans=dfs(v,adj,visited,rec,x,i);
if(ans)
return 1;
}
}
rec[i]=0;
return 0;
}
// Function to detect cycle in an undirected graph.
// it takes adjacency list representation as an argument
bool isCycle(int v, vector<int> adj[]) {
vector<int> visited(v,0),rec(v,0);
int ans=0;
for(int i=0;i<v;i++){
if(visited[i]==0)
ans=dfs(v,adj,visited,rec,i,-1);
if(ans)
return 1;
}
return 0;
}


  • Time Complexity: O(V+E)


  • Space Complexity: O(V)
Discussion
18.

Write a function to sort a linked list of 0s, 1s and 2s

Answer»


  • Input: 0->1->0->2->1->0->2->1


  • Output: 0->0->0->1->1->1->2->2


  • Explanation: All 0’s will come first then 1s and then 2s. This can be done in O(n) time by counting the occurrences of all three and rearranging them in the linked list.

//structure of the linked list
struct Node {
int data;
Node *left;
Node *right;
}
//function take the head of the linked list as a parameter
void sortList(Node *head)
{
//if linked list is empty then return back
if(head==NULL)
return;
else
{
Node *temp=head;
Node *temp1=head;
//to store count of 0s, 1s, and 2s
int count0=0,count1=0,count2=0;
//calculating the count of 0s, 1s, and 2s
while(temp!=NULL)
{
if(temp->data==0)
count0++;
else if(temp->data==1)
count1++;
else
count2++;
temp=temp->next;
}
//iterating over count of 0s and filling the linked list
while(count0!=0)
{
temp1->data=0;
temp1=temp1->next;
count0--;
}
//iterating over count of 1s and filling the linked list
while(count1!=0)
{
temp1->data=1;
temp1=temp1->next;
count1--;
}
//iterating over count of 2s and filling the linked list
while(count2!=0)
{
temp1->data=2;
temp1=temp1->next;
count2--;
}
}
}


  • Time Complexity: O(n)


  • Space Complexity: O(1)
Discussion
19.

Write a function for zigzag traversal in a binary tree

Answer»

  • Input: 


  • Output: [1, 3, 2, 4, 5, 6, 8, 7]


  • Explanation: Zigzag Traversal first iterates the given level of the tree from left to right and then the next level as the right to the level.

// Tree Node
struct Node {
int data;
Node* left;
Node* right;
};

//Function to store the zigzag order traversal of a tree in a list.
vector <int> zigZagTraversal(Node* root)
{
//creating two stacks for level traversals in both order
stack<Node*> st1;
stack<Node*> st2;
//vector to store the zigzag traversal
vector<int> result;

//Initialize the first stack with the root element
st1.push(root);

//Iterate until either of the stack is not empty
while(!st1.empty() || !st2.empty()){
//iterate until the first stack is not empty
while(!st1.empty()){
Node* temp=st1.top();
st1.pop();
result.push_back(temp->data);

if(temp->left)
st2.push(temp->left);
if(temp->right)
st2.push(temp->right);
}
//Iterate until the second stack is not empty
while(!st2.empty()){
Node* temp=st2.top();
st2.pop();
result.push_back(temp->data);

if(temp->right)
st1.push(temp->right);
if(temp->left)
st1.push(temp->left);

}
}
return result;
}


  • Time Complexity: O(n)


  • Space Complexity: O(n)
Discussion
20.

Write a program to remove duplicates from a sorted array in place?

Answer»


  • Input: {1, 1, 1, 2, 3, 3, 6, 6, 7}


  • Output: {1, 2, 3, 6, 7}


  • Explanation: The given input has only 1,2,3,6, and 7 as unique elements, hence the output only lists them out.

#include <bits/stdc++.h>
using namespace std;

class Solution{
public:
//function that takes an array and its size as arguments
int removeDuplicates(int a[],int n){
int index=0;
for(int i=1;i<n;i++) {

if(a[i]!=a[index]) { //change index
index++; //swap next line
a[index]=a[i];
}
}
return index+1;
}
};

int main()
{
int T;
//taking the number of test cases from user
cin>>T;
//running the loop for all test cases
while(T--)
{
int N;
//taking size input from user
cin>>N;
int a[N];
//taking array input from user
for(int i=0;i<N;i++)
{
cin>>a[i];
}
Solution ob;
//calling the removeDuplicates in the Solution class
int n = ob.removeDuplicates(a,N);
//printing the array after removing duplicates
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
}


  • Time Complexity: O(n)


  • Space Complexity: O(1)
Discussion
Previous Next