If you are applying for the role of software developer as a fresher or as an experienced person, then it’s vital that you are fluent with the core of programming concepts, and the ability to write clean, and robust code.
In this article, you will come across some of the most asked interview questions that include coding and theoretical questions on Data Structures (array, strings, linked lists, trees, graphs, etc) and algorithms (sorting, searching, recursions, dynamic programming, etc).
If you are here, that means half your battle is already won! So without further, let’s dive in!
Table of Contents
Question Bank
1. What is a Data Structure? What kind of Data Structures are there in C++?
Data Structures are a way to store data in a certain format for calculation or manipulation.
Some important data structures In C++ are –
- Arrays
- Hash Maps
- LinkedLists
- Trees
- Graphs
2. How are arrays different from Linkedlists?
Array and Linked lists are linear data structures that store a group of values. However, they are still very different from each other. Let’s understand in detail.
Array
- Has fixed-size
- Needs contiguous memory allocation
- Any element can be accessed directly in O(1) Time Complexity
- No extra memory space is required other than for storing the values
- It is recommended to be used when the size of the data structure has to be fixed
Linked List
- Size varies
- Memory allocated can be non-contiguous or scattered
- Requires extra space in memory for storing pointers
- Any element can be accessed by traversing the full linked list in O(n) Time Complexity.
- It is recommended to be used when the size of the data structure can change
3. Write a code to find the second largest element in an array?
The code to find the second largest element in an array is as follows –
function findSecondLargest(arr) {
let first = -Infinity, second = -Infinity;
for (let num of arr) {
if (num > first) {
second = first;
first = num;
} else if (num > second && num < first) {
second = num;
}
}
return second;
}
console.log(findSecondLargest([3, 5, 1, 10, 4])) ;
Output: 5
Pseudo Code
Function findSecondLargest(arr):
# Initialize two variables to hold the largest and second largest values
first = -Infinity
second = -Infinity
# Loop through each element in the array
FOR num in arr:
IF num > first:
# Update second to hold the previous largest value
second = first
# Update first to the new largest value
first = num
ELSE IF num > second AND num < first:
# Update second if num is greater than second but less than first
second = num
# Return the second largest value
RETURN second
4. What are Stacks? Explain with examples how they are used?
Stack is known as LIFO i.e. Last In, First Out data structure. The element that goes into the stack at the end will be printed first. It can be understood as stacking of plates one on top of the other, and removing them from the top.
Operations performed on Stack
- Push: Will add element to the top of the stack
- Pop: Will removes element from the top of the stack
- Peek/Top: Will fetch the element, but not remove it from stack
- isEmpty: Checks if the stack contains no elements. It returns true or false.
#include <stack>
#include <iostream>
int main() {
std::stack<int> stack;
stack.push(10); // This will add 10 to the stack
stack.push(20); // This will add 20 to the stack
stack.push(30); // This will add 30 to the stack
std::cout << "Top element: " << stack.top() << "\n";
// This will print the top element i.e. 30
stack.pop(); // This will remove 30 from the stack’s top
std::cout << "Top element after pop: " << stack.top() << "\n";
// This will print 20
return 0;
}
5. What is a Queue? Explain with examples how they are used?
Queue is a data structure that follows FIFO, i.e First In First Out approach. So the element inserted first will come out first. It is like being in a line the first person gets the first chance.
Operation performed on Queue
- Enqueue (Push) – This will add a value to the end
- Dequeue (Pop) – This will remove value from the front
- Front – This is to access the first element in the Queue
- isEmpty – This checks if the queue is entirely empty or not. It returns true or false.
#include <queue>
#include <iostream>
int main() {
std::queue<int> queue;
queue.push(10); // This will add 10 to the Queue queue.push(20); // This will add 20 to the Queue
queue.push(30); // This will add 30 to the Queue
std::cout << "Front element: " << queue.front() << "\n"; // This will output 10
queue.pop(); // This will remove 10
std::cout << "Front element after pop: " << queue.front() << "\n"; // This will output 20
return 0;
}
6. What is the structure of a node in a Linked List?
A Linked List is basically a set of nodes. Each node stores data and a pointer to the next node.
The structure of each note looks like this –
struct Node {
int data;
Node* next;
};
7. Write a code to reverse a Linked List.
The code to reverse a Linked List is as follows –
function reverseLinkedList(head) {
let prev = null, current = head;
while (current) {
let next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
8. What is Floyd’s Cycle detection algorithm? Write a code for the same.
function hasCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
Explanation: This function detects if a cycle exists in a linked list using the Floyd’s Cycle Detection Algorithm (Tortoise and Hare approach).
- There are two Pointers – slow & fast
- slow moves one step at a time.
- fast moves two steps at a time.
- How Cycle is detected?
If there’s a cycle, the fast pointer will eventually meet the slow pointer at some node and slow pointer will return true.
- However, if no cycle exists, fast or fast.next will reach null, and the function will return false
Your Journey to Web Development Mastery Starts Here!
Enroll today and transform your future!
9. How can you implement a Stack using two queues?
The code to implement a Stack with two Queues is as follows-
class Stack {
constructor() {
this.q1 = [];
this.q2 = [];
}
push(x) {
this.q1.push(x);
}
pop() {
while (this.q1.length > 1) {
this.q2.push(this.q1.shift());
}
let popped = this.q1.shift();
[this.q1, this.q2] = [this.q2, this.q1];
return popped;
}
}
10. What is a Tree?
A Tree is a data structure that is made out of nodes. Each node in a tree has pointers to its child nodes. It is a non-linear structure that is used to represent relationships.
A tree has a Root node which is the entry point of a tree, which is the main node. It has various child nodes called leaf nodes.
11. What are the two ways to traverse a tree?
A tree can be traversed using BFS (Breadth First Search) or DFS (Depth First Search).
In Breadth-First Traversal a tree is traversed layer by layer, which means all its nodes at a certain level are first visited before going to the next level.
In Depth-First Traversal one branch of a tree is traversed to the very bottom before backtracking and coming to the next branch.
DFS can be done in three ways –
- Inorder Traversal – In this, we visit the left subtree, then go back to the root, and then to the right subtree.
- Preorder Traversal – In this first we visit the root, then the left subtree, and then the right subtree.
- Postorder Traversal – In this, we visit the left subtree, then the right subtree, and then the root.
12.
1
/ \
2 3
/ \
4 5
For the given binary tree, write down the traversal output for the following-
1. Inorder
2. Preorder
3. Postorder
4. Level Order
The output will be as follows-
- Inorder – 4 2 5 1 3
- Preorder – 1 2 4 5 3
- Postorder – 4 5 2 3 1
- Level Order – 1 2 3 4 5
13. Write a code to implement Quick sort.
function quickSort(arr) {
if (arr.length <= 1) return arr; let pivot = arr[arr.length - 1]; let left = arr.filter(el => el < pivot); let right = arr.filter(el => el > pivot);
return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log(quickSort([3, 6, 1, 8, 4]));
Output-
[1, 3, 4, 6, 8]
14. How to check if a string is a Palindrome?
Note: A palindrome string is one that reads the same forward and backward.
Example – MADAM
#include <iostream>
using namespace std;
bool isPalindrome(string str) {
int start = 0;
int end = str.length() - 1;
while (start < end) {
if (str[start] != str[end])
return false;
start++;
end--;
}
return true;
}
int main() {
string str = "racecar";
if (isPalindrome(str))
cout << str << " is a palindrome." << endl;
else
cout << str << " is not a palindrome." << endl;
return 0;
}
15. Write a code to check if two strings are anagrams.
Note: Two strings are anagrams if they contain the same characters in the same frequency in different or same order.
Example: LISTEN and SILENT
#include <iostream>
#include <algorithm>
using namespace std;
bool areAnagrams(string str1, string str2) {
// If the lengths of two strings are different, they cannot be anagrams
if (str1.length() != str2.length())
return false;
// Sort both strings
sort(str1.begin(), str1.end());
sort(str2.begin(), str2.end());
// Compare sorted strings
return str1 == str2;
}
int main() {
string str1 = "listen";
string str2 = "silent";
if (areAnagrams(str1, str2))
cout << "The strings are anagrams." << endl;
else
cout << "The strings are not anagrams." << endl;
return 0;
}
16. Write a code to swap two numbers without using a third.
#include <iostream>
using namespace std;
int main() {
int a = 5, b = 10;
cout << "Before swapping: a = " << a << ", b = " << b << endl;
a = a + b; // a now becomes 15
b = a - b; // b becomes 5 (original a)
a = a - b; // a becomes 10 (original b)
cout << "After swapping: a = " << a << ", b = " << b << endl;
return 0;
}
17. What is recursion?
Recursion is the process where a function keeps calling itself until it reaches a base case and returns a value from there back to the top.
18. Calculate Factorial using recursion?
#include <iostream>
using namespace std;
int factorial(int n) {
if (n == 0 || n == 1) // Base case: 0! = 1 and 1! = 1
return 1;
return n * factorial(n - 1); // Recursive case
}
int main() {
int num = 5;
cout << "Factorial of " << num << " is " << factorial(num) << endl;
return 0;
}
19. Write an efficient code to reverse a singly linked list.
function reverseLinkedList(head) {
let prev = null, current = head;
while (current) {
let next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
Unlock Your Web Development Potential!
Join now to start building your dream projects!
20. Write a code to check if a binary tree is balanced?
function isBalanced(root) {
function height(node) {
if (!node) return 0;
let left = height(node.left);
let right = height(node.right);
if (Math.abs(left - right) > 1) return -1;
return Math.max(left, right) + 1;
}
return height(root) !== -1;
}
21. What are OOPs concepts?
OOPs stands for Object Oriented Programming. This is a set of concepts that help users write standard, modular, and reusable code.
Object-Oriented Programming has four concepts –
- Abstraction – Abstraction refers to the process of hiding complex data from users and displaying the data that is of use to the developer and the users.
- Encapsulation – This is the process of bundling data and methods into a single unit called a class. By doing so we can restrict access to the data by other components creating a layer of security.
- Inheritance – Inheritance is the process by which a child class can access the methods and properties of the parent class.
- Polymorphism – Polymorphism is the process by which a single function displays different characteristics and performs different roles.
22. What is a Binary Search Tree? What are its key characteristics?
50
/ \
30 70
/ \ / \
20 40 60 80
A Binary Search Tree is a variant of a binary Tree. In this tree, the value of every node on the left is less than the root/parent node and the value of every node on the right is more than the root/parent node.
Characteristics –
- Each node in the Binary tree can have a maximum of two children
- The time complexity for operations like Search, Insert, and Delete operations is O(log n).
23. What is a Doubly Linked List?
A Doubly Linked List is a variant of the Linked List data structure that contains the following –
- Each node stores some data to be processed
- It contains a pointer to the next node
- It also contains a pointer to the previous node
24. Write a code to perform Depth First Search in a Graph.
We can perform Depth First Search in a Graph in the manner it is done in code below:
#include <iostream>
#include <vector>
using namespace std;
void dfs(int node, vector<int> adj[], vector<bool>& visited) {
visited[node] = true;
cout << node << " ";
for (auto neighbor : adj[node]) {
if (!visited[neighbor]) {
dfs(neighbor, adj, visited);
}
}
}
int main() {
int V = 5;
vector<int> adj[V];
vector<bool> visited(V, false);
// Adding edges
adj[0] = {1, 4};
adj[1] = {0, 2, 3, 4};
adj[2] = {1, 3};
adj[3] = {1, 2, 4};
adj[4] = {0, 1, 3};
cout << "DFS Traversal: ";
dfs(0, adj, visited);
cout << endl;
return 0;
}
25. Write a code to find the shortest path in an unweighted graph.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void shortestPath(int src, vector<int> adj[], int V) {
vector<int> dist(V, -1);
queue<int> q;
q.push(src);
dist[src] = 0;
while (!q.empty()) {
int node = q.front();
q.pop();
for (auto neighbor : adj[node]) {
if (dist[neighbor] == -1) {
dist[neighbor] = dist[node] + 1;
q.push(neighbor);
}
}
}
cout << "Shortest distances from node " << src << ": ";
for (int i = 0; i < V; i++) {
cout << dist[i] << " ";
}
cout << endl;
}
int main() {
int V = 5;
vector<int> adj[V];
adj[0] = {1, 4};
adj[1] = {0, 2, 3, 4};
adj[2] = {1, 3};
adj[3] = {1, 2, 4};
adj[4] = {0, 1, 3};
shortestPath(0, adj, V);
return 0;
}
26. What do you understand about HashMaps? Write a code to find the sum of two elements in an array using HashMaps.
A HashMap is a data structure that stores key-value pairs. It allows efficient retrieval, insertion, and deletion of data.
The code to find the sum of two elements in an array using Hashmaps is as follows-
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
vector twoSum(vector& nums, int target) {
unordered_map<int, int> numMap; // Value -> Index mapping
vector result;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (numMap.find(complement) != numMap.end()) {
result.push_back(numMap[complement]);
result.push_back(i);
return result;
}
numMap[nums[i]] = i;
}
return result; // No solution
}
int main() {
vector nums = {2, 7, 11, 15};
int target = 9;
vector result = twoSum(nums, target);
if (!result.empty()) {
cout << "Indices: " << result[0] << ", " << result[1] << endl;
} else {
cout << "No solution found." << endl;
}
return 0;
}
27. Write a code to find the longest common subsequence in two strings. Also, mention its space and time complexity.
Note – The LCS is the longest sequence that appears in the same relative order in both strings, but not necessarily consecutively.
Example – For the strings ABCBDAB and BDCAB, the LCS is BCAB.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string longestCommonSubsequence(string text1, string text2) {
int m = text1.length(), n = text2.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// Fill the dp table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// Reconstruct the LCS from the dp table
string lcs = "";
int i = m, j = n;
while (i > 0 && j > 0) {
if (text1[i - 1] == text2[j - 1]) {
lcs = text1[i - 1] + lcs; // Include this character in LCS
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--; // Move up in the table
} else {
j--; // Move left in the table
}
}
return lcs;
}
int main() {
string str1 = "ABCBDAB";
string str2 = "BDCAB";
string lcs = longestCommonSubsequence(str1, str2);
cout << "The Longest Common Subsequence is: " << lcs << endl;
return 0;
}
28. What do you understand about Time and Space Complexity?
Time Complexity is the time taken by an algorithm to complete a task. It is denoted using Big-O Notation.
- If a task is taking constant time, it will be denoted as O(1).
- If a task takes logarithmic time, it is denoted as O(log n).
- If a task takes linear time, it is denoted as O(n) and so on.
Space Complexity is the space taken in memory by an algorithm.
For example, an array will take up ‘n’ units of space in the memory. Where ‘n’ is the size of an array.
29. Write a code to find the frequency of each word in a sentence.
#include <iostream>
#include <unordered_map>
#include <sstream>
using namespace std;
int main() {
string sentence = "hello world hello everyone world";
unordered_map<string, int> wordCount;
// Split sentence into words and count frequencies
stringstream ss(sentence);
string word;
while (ss >> word) {
wordCount[word]++;
}
// Print word frequencies
for (auto &entry : wordCount) {
cout << entry.first << ": " << entry.second << endl;
}
return 0;
}
30. What do you understand about Dynamic Programming? Mention its characteristics and ways in which it can be used.
Dynamic Programming (DP) is one of the most powerful techniques to solve a complex problem by breaking it down into smaller solvable units. The crux of DP is to avoid solving a particular subproblem again and again and storing its value for future use.
Dynamic Programming has two characteristics –
- Overlapping Subproblems:
A bigger problem is broken down into smaller problems also known as subproblems.
- Optimal Substructure:
Getting the solution of bigger problems by using the solution of smaller problems.
Dynamic Programming can be solved in two ways –
- Memoization:
Memorization is known as the Top-Down Approach. In this, we make use of recursion. The problems are solved recursively until the base case is hit.
- Tabulation:
Tabulation is known as the Bottom-Up Approach. In this, the values are calculated from the bottom built up until we get the final value at the top.
31. Write a code to find the maximum sum of a contiguous array.
int maxSubArray(vector& nums) {
int maxSum = nums[0], currentSum = nums[0];
for (int i = 1; i < nums.size(); i++) {
currentSum = max(nums[i], currentSum + nums[i]);
maxSum = max(maxSum, currentSum);
}
return maxSum;
}
Explanation: The function maxSubArray finds the maximum sum of a contiguous subarray in a given array of integers. The entire process can be divided into 3 steps-
- Initialization:
- maxSum and currentSum are initialized with the first element of the array.
- Iterate through the array:
- For each element, update currentSum to be the maximum of the current element itself or the sum of currentSum and the current element. This helps to decide whether to start a new subarray or continue adding to the existing one.
- Update maxSum to be the maximum of maxSum and currentSum.
- Return the result:
- The maxSum at the end represents the maximum subarray sum.
Get 100% Hike!
Master Most in Demand Skills Now!
Conclusion
Coding interview questions are a stepping stone to showcasing your skills and landing your dream job. By preparing effectively and staying consistent, you can approach interviews with confidence. Remember, every question is an opportunity to learn and grow. If you want to discover more you can join Intellipaat’s Expert- led Programming Courses today and shape your career as a developer.