Data Structures and Algorithms Interview Questions
Master the most important DSA concepts asked in technical interviews
Introduction
Data Structures and Algorithms (DSA) form the foundation of computer science and are crucial for technical interviews at top tech companies. This guide covers the most frequently asked DSA interview questions with detailed explanations and code examples.
Interview Strategy: Focus on understanding the problem-solving approach rather than memorizing solutions. Practice explaining your thought process clearly.
Arrays and Strings
Q1. Find the maximum element in an array
Approach: Iterate through array and keep track of maximum.
int findMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// Time Complexity: O(n)
// Space Complexity: O(1)Q2. Reverse an array
Approach: Use two pointers, swap elements from both ends.
void reverseArray(int arr[], int n) {
int start = 0, end = n - 1;
while (start < end) {
swap(arr[start], arr[end]);
start++;
end--;
}
}
// Time Complexity: O(n)
// Space Complexity: O(1)Q3. Find two numbers in array that sum to target
Approach 1: Brute force - check all pairs (O(n²))
Approach 2: Use hash map (O(n))
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (map.find(complement) != map.end()) {
return {map[complement], i};
}
map[nums[i]] = i;
}
return {};
}
// Time Complexity: O(n)
// Space Complexity: O(n)Q4. Find the longest substring without repeating characters
Approach: Sliding window technique with hash set.
int lengthOfLongestSubstring(string s) {
unordered_set<char> chars;
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
while (chars.find(s[right]) != chars.end()) {
chars.erase(s[left]);
left++;
}
chars.insert(s[right]);
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}
// Time Complexity: O(n)
// Space Complexity: O(min(n, m)) where m is charset sizeQ5. Rotate array by k positions
Approach: Reverse entire array, then reverse first k and last n-k elements.
void rotate(vector<int>& nums, int k) {
k = k % nums.size();
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
// Time Complexity: O(n)
// Space Complexity: O(1)Linked Lists
Q6. Reverse a linked list
Approach: Iterative - use three pointers (prev, curr, next).
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
// Time Complexity: O(n)
// Space Complexity: O(1)Q7. Detect cycle in linked list (Floyd's Algorithm)
Approach: Use two pointers - slow (moves 1 step) and fast (moves 2 steps).
bool hasCycle(ListNode *head) {
if (head == nullptr) return false;
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return true;
}
}
return false;
}
// Time Complexity: O(n)
// Space Complexity: O(1)Q8. Find middle of linked list
Approach: Use two pointers - slow and fast.
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
// Time Complexity: O(n)
// Space Complexity: O(1)Q9. Merge two sorted linked lists
Approach: Compare nodes and merge in sorted order.
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (list1 && list2) {
if (list1->val < list2->val) {
tail->next = list1;
list1 = list1->next;
} else {
tail->next = list2;
list2 = list2->next;
}
tail = tail->next;
}
tail->next = list1 ? list1 : list2;
return dummy.next;
}
// Time Complexity: O(n + m)
// Space Complexity: O(1)Stacks and Queues
Q10. Valid Parentheses
Approach: Use stack to match opening and closing brackets.
bool isValid(string s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '{' || c == '[') {
st.push(c);
} else {
if (st.empty()) return false;
if ((c == ')' && st.top() != '(') ||
(c == '}' && st.top() != '{') ||
(c == ']' && st.top() != '[')) {
return false;
}
st.pop();
}
}
return st.empty();
}
// Time Complexity: O(n)
// Space Complexity: O(n)Q11. Implement stack using queues
Approach: Use two queues, transfer elements for pop operation.
class MyStack {
queue<int> q1, q2;
public:
void push(int x) {
q2.push(x);
while (!q1.empty()) {
q2.push(q1.front());
q1.pop();
}
swap(q1, q2);
}
int pop() {
int val = q1.front();
q1.pop();
return val;
}
int top() {
return q1.front();
}
bool empty() {
return q1.empty();
}
};Trees and Binary Trees
Q12. Binary Tree Traversals (Inorder, Preorder, Postorder)
Approach: Recursive traversal.
// Inorder: Left, Root, Right
void inorder(TreeNode* root) {
if (root) {
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
}
// Preorder: Root, Left, Right
void preorder(TreeNode* root) {
if (root) {
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
}
// Postorder: Left, Right, Root
void postorder(TreeNode* root) {
if (root) {
postorder(root->left);
postorder(root->right);
cout << root->val << " ";
}
}
// Time Complexity: O(n)
// Space Complexity: O(h) where h is heightQ13. Maximum depth of binary tree
Approach: Recursively find depth of left and right subtrees.
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return 1 + max(leftDepth, rightDepth);
}
// Time Complexity: O(n)
// Space Complexity: O(h)Q14. Check if binary tree is balanced
Approach: For each node, check if height difference between left and right subtrees is at most 1.
int height(TreeNode* root) {
if (root == nullptr) return 0;
return 1 + max(height(root->left), height(root->right));
}
bool isBalanced(TreeNode* root) {
if (root == nullptr) return true;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return abs(leftHeight - rightHeight) <= 1 &&
isBalanced(root->left) &&
isBalanced(root->right);
}
// Time Complexity: O(n²)
// Space Complexity: O(h)Q15. Lowest Common Ancestor in BST
Approach: Use BST property - if both nodes are smaller, go left; if both larger, go right.
TreeNode* lowestCommonAncestor(TreeNode* root,
TreeNode* p, TreeNode* q) {
if (root->val > p->val && root->val > q->val) {
return lowestCommonAncestor(root->left, p, q);
} else if (root->val < p->val && root->val < q->val) {
return lowestCommonAncestor(root->right, p, q);
} else {
return root;
}
}
// Time Complexity: O(h)
// Space Complexity: O(h)Graphs
Q16. Depth First Search (DFS)
Approach: Recursive traversal using visited array.
void DFS(vector<vector<int>>& graph, int node,
vector<bool>& visited) {
visited[node] = true;
cout << node << " ";
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
DFS(graph, neighbor, visited);
}
}
}
// Time Complexity: O(V + E)
// Space Complexity: O(V)Q17. Breadth First Search (BFS)
Approach: Use queue to traverse level by level.
void BFS(vector<vector<int>>& graph, int start) {
vector<bool> visited(graph.size(), false);
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
cout << node << " ";
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
// Time Complexity: O(V + E)
// Space Complexity: O(V)Q18. Detect cycle in undirected graph
Approach: Use DFS, if we encounter a visited node that's not the parent, cycle exists.
bool hasCycle(vector<vector<int>>& graph, int node,
int parent, vector<bool>& visited) {
visited[node] = true;
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
if (hasCycle(graph, neighbor, node, visited)) {
return true;
}
} else if (neighbor != parent) {
return true;
}
}
return false;
}
// Time Complexity: O(V + E)
// Space Complexity: O(V)Sorting Algorithms
Q19. Quick Sort
Approach: Divide and conquer - choose pivot, partition, recursively sort.
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Time Complexity: O(n log n) average, O(n²) worst
// Space Complexity: O(log n)Q20. Merge Sort
Approach: Divide and conquer - divide into halves, sort, merge.
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[l + i];
for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
// Time Complexity: O(n log n)
// Space Complexity: O(n)Searching Algorithms
Q21. Binary Search
Approach: Divide array in half, compare with middle element.
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
// Time Complexity: O(log n)
// Space Complexity: O(1)Dynamic Programming
Q22. Fibonacci using DP
Approach: Store previously computed values to avoid recalculation.
int fibonacci(int n) {
if (n <= 1) return n;
vector<int> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// Time Complexity: O(n)
// Space Complexity: O(n)Q23. Longest Common Subsequence (LCS)
Approach: Build 2D DP table comparing characters.
int LCS(string s1, string s2) {
int m = s1.length(), n = s2.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
// Time Complexity: O(m * n)
// Space Complexity: O(m * n)Q24. 0/1 Knapsack Problem
Approach: For each item, decide to include or exclude based on weight constraint.
int knapsack(int W, vector<int>& weights,
vector<int>& values, int n) {
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= W; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = max(values[i - 1] +
dp[i - 1][w - weights[i - 1]],
dp[i - 1][w]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W];
}
// Time Complexity: O(n * W)
// Space Complexity: O(n * W)Greedy Algorithms
Q25. Activity Selection Problem
Approach: Sort by finish time, always select activity that finishes earliest.
int activitySelection(vector<pair<int, int>>& activities) {
sort(activities.begin(), activities.end(),
[](pair<int, int> a, pair<int, int> b) {
return a.second < b.second;
});
int count = 1;
int lastFinish = activities[0].second;
for (int i = 1; i < activities.size(); i++) {
if (activities[i].first >= lastFinish) {
count++;
lastFinish = activities[i].second;
}
}
return count;
}
// Time Complexity: O(n log n)
// Space Complexity: O(1)Time and Space Complexity
Common Time Complexities
| Complexity | Description | Example |
|---|---|---|
| O(1) | Constant | Array access |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Linear search |
| O(n log n) | Linearithmic | Merge sort, Quick sort |
| O(n²) | Quadratic | Bubble sort, Nested loops |
| O(2ⁿ) | Exponential | Recursive Fibonacci |
Interview Tips
- Always analyze time and space complexity
- Start with brute force, then optimize
- Explain your approach before coding
- Consider edge cases
- Practice on platforms like LeetCode, Codeforces
Sign up here with your email
ConversionConversion EmoticonEmoticon