  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;`
`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;`
`int secondMax = arr;`
`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 > arr)`

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, maxSum = rowSum;`
`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