DSA interview question - GrabAjobs.co
Sticky

DSA interview question: Topic Wise ( 50+Questions )

Hi Guzz.. Today we are talk about 50+ DSA interview questions on Arrays ,Matrices and Linked list. So before going to below questions you must know the Arrays ,Matrices and Linked list. Then only you should able to give the answers

DSA interview questions on Arrays and Matrices

Arrays and Matrices: Arrays are collections of elements of the same data type, while matrices are two-dimensional arrays. They are fundamental data structures used to store and manipulate data

25 DSA interview questions on Arrays and Matrices

1.  Write a function to find the maximum element in an array.

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;
}

2. Write a function to find the second largest element in an array.

int findSecondLargest(int arr[], int n) {
int max = arr[0];
int secondMax = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
secondMax = max;
max = arr[i];
} else if (arr[i] > secondMax && arr[i] != max) {
secondMax = arr[i];
}
}
return secondMax;
}

3. Write a function to reverse an array.

void reverseArray(int arr[], int n) {
int start = 0;
int end = n - 1;
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}

4.  Write a function to find the sum of all elements in an array.

int findSum(int arr[], int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
return sum;
}

5.  Write a function to find the average of all elements in an array.

double findAverage(int arr[], int n) {
double sum = findSum(arr, n);
return sum / n;
}




6. Write a function to find the product of all elements in an array.

int findProduct(int arr[], int n) {
int product = 1;
for (int i = 0; i < n; i++) {
product *= arr[i];
}
return product;
}

7. Write a function to find the index of a given element in an array.

int findIndex(int arr[], int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}

8. Write a function to remove duplicates from an array.

int removeDuplicates(int arr[], int n) {
int j = 0;
for (int i = 0; i < n; i++) {
if (arr[i] != arr[j]) {
j++;
arr[j] = arr[i];
}
}
return j + 1;
}

9. Write a function to rotate an array by a given number of positions.

void rotateArray(int arr[], int n, int k) {
k = k % n;
reverseArray(arr, n);
reverseArray(arr, k);
reverseArray(arr + k, n - k);
}

10. Write a function to find the minimum and maximum elements in an array using the minimum number of comparisons.

void findMinMax(int arr[], int n, int& min, int& max) {
int i;
if (n % 2 == 0) {
if (arr[0] > arr[1])




11. Write a function to find the pair of elements with the maximum sum in an array

void findMaxPairSum(int arr[], int n, int& first, int& second) {
first = second = INT_MIN;
for (int i = 0; i < n; i++) {
if (arr[i] > first) {
second = first;
first = arr[i];
} else if (arr[i] > second && arr[i] != first) {
second = arr[i];
}
}
}

12. Write a function to count the number of occurrences of a given element in an array

int countOccurrences(int arr[], int n, int x) {
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
count++;
}
}
return count;
}

13. Write a function to find the kth smallest element in an array

int findKthSmallest(int arr[], int n, int k) {
priority_queue<int> pq;
for (int i = 0; i < n; i++) {
pq.push(arr[i]);
if (pq.size() > k) {
pq.pop();
}
}
return pq.top();
}

14.Write a function to find the median of an array

int findKthSmallest(int arr[], int n, int k) {
priority_queue<int> pq;
for (int i = 0; i < n; i++) {
pq.push(arr[i]);
if (pq.size() > k) {
pq.pop();
}
}
return pq.top();
}




15. Write a function to merge two sorted arrays into a single sorted array.

void mergeArrays(int arr1[], int n1, int arr2[], int n2, int merged[]) {
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2) {
if (arr1[i] < arr2[j]) {
merged[k++] = arr1[i++];
} else {
merged[k++] = arr2[j++];
}
}
while (i < n1) {
merged[k++] = arr1[i++];
}
while (j < n2) {
merged[k++] = arr2[j++];
}
}

16. Write a function to find the maximum subarray sum

int findMaxSubarraySum(int arr[], int n) {
int maxSum = INT_MIN, sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
maxSum = max(maxSum, sum);
sum = max(sum, 0);
}
return maxSum;
}

17.  Write a function to find the maximum product subarray.

int findMaxProductSubarray(int arr[], int n) {
int maxProduct = 1, minProduct = 1, ans = 1;
for (int i = 0; i < n; i++) {
if (arr[i] > 0) {
maxProduct *= arr[i];
minProduct = min(minProduct * arr[i], 1);
} else if (arr[i] == 0) {
maxProduct = minProduct = 1;
} else {
int temp = maxProduct;
maxProduct = max(minProduct * arr[i], 1);
minProduct = temp * arr[i];
}
ans = max(ans, maxProduct);
}
return ans;
}

18. Write a function to find the number of subarrays with a given sum.

int countSubarraysWithSum(int arr[], int n, int targetSum) {
unordered_map<int, int> mp;
int sum = 0, count = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
if (sum == targetSum) {
count++;
}
if (mp.find(sum - targetSum) != mp.end()) {
count += mp[sum - targetSum];
}
mp[sum]++;
}
return count;
}

19. Write a function to rotate a matrix by 90 degrees in clockwise direction

void rotateMatrixClockwise(int mat[][MAX], int n) {
for (int i = 0; i < n / 2; i++) {
for (int j = i; j < n - i - 1; j++) {
int temp = mat[i][j];
mat[i][j] = mat[n - j - 1][i];
mat[n - j - 1][i] = mat[n - i - 1][n - j - 1];
mat[n - i - 1][n - j - 1] = mat[j][n - i - 1];
mat[j][n - i - 1] = temp;
}
}
}




20. Write a function to find the maximum sum rectangle in a matrix

int findMaxSumRectangle(int mat[][MAX], int n, int m) {
int ans = INT_MIN;
for (int i = 0; i < n; i++) {
int rowSum[m] = {0};
for (int j = i; j < n; j++) {
for (int k = 0; k < m; k++) {
rowSum[k] += mat[j][k];
}
int sum = rowSum[0], maxSum = rowSum[0];
for (int k = 1; k < m; k++) {
sum = max(rowSum[k], sum + rowSum[k]);
maxSum = max(maxSum, sum);
}
ans = max(ans, maxSum);
}
}
return ans;
}

21. Write a function to find the intersection of two arrays.

vector<int> findIntersection(int arr1[], int n, int arr2[], int m) {
vector<int> ans;
unordered_map<int, bool> mp;
for (int i = 0; i < n; i++) {
mp[arr1[i]] = true;
}
for (int i = 0; i < m; i++) {
if (mp.find(arr2[i]) != mp.end() && mp[arr2[i]]) {
ans.push_back(arr2[i]);
mp[arr2[i]] = false;
}
}
return ans;
}

22. Write a function to find the median of two sorted arrays

double findMedianSortedArrays(int arr1[], int n, int arr2[], int m) {
if (n > m) {
swap(arr1, arr2);
swap(n, m);
}
int l = 0, r = n, mid = (n + m + 1) / 2;
while (l <= r) {
int i = (l + r) / 2, j = mid - i;
if (i < n && arr2[j - 1] > arr1[i]) {
l = i + 1;
} else if (i > 0 && arr1[i - 1] > arr2[j]) {
r = i - 1;
} else {
int maxLeft = (i == 0) ? arr2[j - 1] :
(j == 0) ? arr1[i - 1] :
max(arr1[i - 1], arr2[j - 1]);
if ((n + m) % 2 == 1) {
return maxLeft;
}
int minRight = (i == n) ? arr2[j] :
(j == m) ? arr1[i] :
min(arr1[i], arr2[j]);
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}

23. Write a function to find the maximum sum subarray with at least k elements

int findMaxSumSubarrayWithK(int arr[], int n, int k) {
int sum = 0;
for (int i = 0; i < k; i++) {
sum += arr[i];
}
int ans = sum;
for (int i = k; i < n; i++) {
sum += arr[i] - arr[i - k];
ans = max(ans, sum);
sum = max(sum, 0);
}
return ans;
}

24. Write a function to find the count of subarrays with maximum element less than K

int countSubarraysWithMaxLessThanK(int arr[], int n, int k) {
int ans = 0, j = 0;
for (int i = 0; i < n; i++) {
if (arr[i] < k) {
ans += (i - j + 1);
} else {
j = i + 1;
}
}
return ans;
}

DSA interview questions on Linked Lists

Linked Lists: A linked list is a collection of nodes that contain data and a pointer to the next node in the list. They are used to represent dynamic data structures and enable efficient insertion and deletion operations.




25 DSA interview questions on Linked list

1. Write a function to print a linked list

void printLinkedList(ListNode* head) {
while (head != NULL) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}

2. Write a function to reverse a linked list

ListNode* reverseLinkedList(ListNode* head) {
ListNode* prev = NULL;
ListNode* curr = head;
while (curr != NULL) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}

3. Write a function to merge two sorted linked lists

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* tail = dummy;
while (l1 != NULL && l2 != NULL) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
if (l1 != NULL) {
tail->next = l1;
} else {
tail->next = l2;
}
return dummy->next;
}

4.  Write a function to remove Nth node from the end of a linked list

ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* slow = dummy;
ListNode* fast = head;
for (int i = 0; i < n; i++) {
fast = fast->next;
}
while (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
slow->next = slow->next->next;
return dummy->next;
}




5. Write a function to detect a cycle in a linked list

bool hasCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return true;
}
}
return false;
}

6. Write a function to find the start of a cycle in a linked list

ListNode* detectCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
ListNode* start = head;
while (start != slow) {
start = start->next;
slow = slow->next;
}
return start;
}
}
return NULL;
}

7. Write a function to remove duplicates from a sorted linked list

ListNode* deleteDuplicates(ListNode* head) {
ListNode* curr = head;
while (curr != NULL && curr->next != NULL) {
if (curr->val == curr->next->val) {
curr->next = curr->next->next;
} else {
curr = curr->next;
}
}
return head;
}




8. Write a function to remove all elements from a linked list that have a given value.

ListNode* remove

9. Write a function to swap nodes in a linked list without swapping data

ListNode* swapNodes(ListNode* head, int x, int y) {
if (x == y) {
return head;
}
ListNode* prevX = NULL;
ListNode* currX = head;
while (currX != NULL && currX->val != x) {
prevX = currX;
currX = currX->next;
}
ListNode* prevY = NULL;
ListNode* currY = head;
while (currY != NULL && currY->val != y) {
prevY = currY;
currY = currY->next;
}
if (currX == NULL || currY == NULL) {
return head;
}
if (prevX != NULL) {
prevX->next = currY;
} else {
head = currY;
}
if (prevY != NULL) {
prevY->next = currX;
} else {
head = currX;
}
ListNode* temp = currX->next;
currX->next = currY->next;
currY->next = temp;
return head;
}

10.  Write a function to add two numbers represented by linked lists.

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* curr = dummy;
int carry = 0;
while (l1 != NULL || l2 != NULL) {
int val1 = (l1 != NULL) ? l1->val : 0;
int val2 = (l2 != NULL) ? l2->val : 0;
int sum = val1 + val2 + carry;
carry = sum / 10;
curr->next = new ListNode(sum % 10);
curr = curr->next;
if (l1 != NULL) {
l1 = l1->next;
}
if (l2 != NULL) {
l2 = l2->next;
}
}
if (carry > 0) {
curr->next = new ListNode(carry);
}
return dummy->next;
}

11. Write a function to partition a linked list around a given value.

ListNode* partition(ListNode* head, int x) {
ListNode* dummy1 = new ListNode(0);
ListNode* dummy2 = new ListNode(0);
ListNode* tail1 = dummy1;
ListNode* tail2 = dummy2;
while (head != NULL) {
if (head->val < x) {
tail1->next = head;
tail1 = tail1->next;
} else {
tail2->next = head;
tail2 = tail2->next;
}
head = head->next;
}
tail1->next = dummy2->next;
tail2->next = NULL;
return dummy1->next;
}

12. Write a function to rotate a linked list by k places to the right

ListNode* rotateRight(ListNode* head, int k) {
if (head == NULL) {
return NULL;
}
int n = 1;
ListNode* tail = head;
while (tail->next != NULL) {
n++;
tail = tail->next;
}
k = k % n;
if (k == 0) {
return head;
}
ListNode* newTail = head;
for (int i = 0




13. Write a function to remove duplicates from a sorted linked list

ListNode* deleteDuplicates(ListNode* head) {
ListNode* curr = head;
while (curr != NULL && curr->next != NULL) {
if (curr->val == curr->next->val) {
ListNode* temp = curr->next;
curr->next = curr->next->next;
delete temp;
} else {
curr = curr->next;
}
}
return head;
}

14. Write a function to detect if a linked list has a cycle and return the node where the cycle begins

ListNode* detectCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
ListNode* slow2 = head;
while (slow2 != slow) {
slow = slow->next;
slow2 = slow2->next;
}
return slow;
}
}
return NULL;
}

15. Write a function to reverse a linked list recursively

ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}

16. Write a function to merge two sorted linked lists into one sorted linked list

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* curr = dummy;
while (l1 != NULL && l2 != NULL) {
if (l1->val <= l2->val) {
curr->next = l1;
l1 = l1->next;
} else {
curr->next = l2;
l2 = l2->next;
}
curr = curr->next;
}
if (l1 != NULL) {
curr->next = l1;
}
if (l2 != NULL) {
curr->next = l2;
}
return dummy->next;
}

17. Write a function to remove the nth node from the end of a linked list

ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* slow = dummy;
ListNode* fast = dummy;
for (int i = 0; i <= n; i++) {
fast = fast->next;
}
while (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
ListNode* temp = slow->next;
slow->next = slow->next->next;
delete temp;
return dummy->next;
}

18. Write a function to find the middle node of a linked list

ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}




19. Write a function to remove all elements from a linked list that have a given value

ListNode* removeElements(ListNode* head, int val) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* curr = dummy;
while (curr->next != NULL) {
if (curr->next->val == val) {
ListNode* temp = curr->next;
curr->next = curr->next->next;
delete temp;
} else {
curr = curr->next;
}
}
return dummy->next;
}

20. Write a function to reverse a linked list between two specified nodes

ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* prev = dummy;
for (int i = 0; i < m - 1; i++) {
prev = prev->next;
}
ListNode* curr = prev->next;
for (int i = 0; i < n - m; i++) {
ListNode* temp = curr->next;
curr->next = temp->next;
temp->next = prev->next;
prev->next = temp;
}
return dummy->next;
}

21. Write a function to determine if two linked lists intersect and return the intersecting node

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
ListNode* currA = headA;
ListNode* currB = headB;
int lenA = 0;
int lenB = 0;
while (currA != NULL) {
lenA++;
currA = currA->next;
}
while (currB != NULL) {
lenB++;
currB = currB->next;
}
currA = headA;
currB = headB;
if (lenA > lenB) {
for (int i = 0; i < lenA - lenB; i++) {
currA = currA->next;
}
} else {
for (int i = 0; i < lenB - lenA; i++) {
currB = currB->next;
}
}
while (currA != NULL && currB != NULL) {
if (currA == currB) {
return currA;
}
currA = currA->next;
currB = currB->next;
}
return NULL;
}

22. Write a function to sort a linked list using merge sort

ListNode* merge(ListNode* l1, ListNode* l2) {
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
if (l1->val <= l2->val) {
l1->next = merge(l1->next, l2);
return l1;
} else {
l2->next = merge(l1, l2->next);
return l2;
}
}

ListNode* sortList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* slow = head;
ListNode* fast = head;
ListNode* prev = NULL;
while (fast != NULL && fast->next != NULL) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next =




23. Write a function to remove duplicates from a sorted linked list

ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL) {
return NULL;
}
ListNode* curr = head;
while (curr->next != NULL) {
if (curr->val == curr->next->val) {
ListNode* temp = curr->next;
curr->next = curr->next->next;
delete temp;
} else {
curr = curr->next;
}
}
return head;
}

24. Write a function to rotate a linked list to the right by k places

ListNode* rotateRight(ListNode* head, int k) {
if (head == NULL || k == 0) {
return head;
}
int len = 1;
ListNode* tail = head;
while (tail->next != NULL) {
len++;
tail = tail->next;
}
k = k % len;
if (k == 0) {
return head;
}
ListNode* curr = head;
for (int i = 0; i < len - k - 1; i++) {
curr = curr->next;
}
ListNode* newHead = curr->next;
curr->next = NULL;
tail->next = head;
return newHead;
}




25. Write a function to reverse a linked list recursively

ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}

If you find any error or want any post on any topic, write us on grabajobss@gmail.com.

THank yOu for visit GrabAjobs.co