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