If you’re preparing for interviews at top MNCs like Google, Amazon, Microsoft, or Meta, mastering Data Structures and Algorithms (DSA) is crucial. These companies often test your problem-solving skills using classic Dsa Questions. Here’s a list of the top 10 most frequently asked questions, complete with detailed solutions and explanations.

1. Reverse a Linked List

Problem: Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Solution: Approach for Reversing a Subsection of a Linked List. The goal is to reverse a part of the linked list between positions left and right. Here’s the high-level approach:

Steps to Solve the Problem

1. Handle Edge Cases:
   • If head is NULL, return NULL (empty list).
   • If the left and right positions are the same, return the original list (no reversal needed).
2. Traverse to the Starting Point:
   • Use a pointer temp to traverse the list until position left.
   • Maintain a prev pointer to track the node just before left.
3. Locate the Endpoint:
   • Use another pointer temp1 to traverse the list until position right.
   • Store the node immediately after right in a pointer next for reconnection later.
4. Disconnect the Sublist:
   • Temporarily break the linked list into three parts:
     • Before left
     • Between left and right
     • After right
5. Reverse the Sublist:
   • Use the reverse function to reverse the nodes between left and right.
6. Reconnect the List:
   • Connect the reversed sublist back to the “before” and “after” parts of the original list.
7. Return the New Head:
   • If the prev pointer is NULL, the head of the reversed sublist becomes the new head of the list.
   • Otherwise, reconnect prev to the reversed sublist and return the original head.

2. Find the Intersection of Two Arrays

Problem: Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Solution: The task is to find the intersection of two arrays, nums1 and nums2, where each element in the result must appear as many times as it shows in both arrays. The solution uses a two-pointer technique after sorting the arrays.

Steps to Solve the Problem

1. Sort Both Arrays:
   • Sort nums1 and nums2 in ascending order using the built-in sort function.
   • Sorting helps in comparing elements sequentially and efficiently.
2. Initialize Two Pointers:
   • i for traversing nums1.
   • j for traversing nums2.
3. Traverse Both Arrays:
   • Use a while loop that continues as long as i is within the bounds of nums1 and j is within the bounds of nums2.
4. Compare Elements:
   • If nums1[i] < nums2[j]: Increment i (move the pointer in nums1 forward).
   • If nums1[i] > nums2[j]: Increment j (move the pointer in nums2 forward).
   • If nums1[i] == nums2[j]:
     • Add the common element (nums1[i]) to the result vector ans.
     • Increment both i and j.
5. Return the Result:
   • After the loop ends, ans contains the elements that appear in both arrays, with their frequencies matching.

3. Merge Two Sorted Arrays

Problem: The task is to merge two sorted arrays, nums1 and nums2, into one sorted array, where the merged array is stored in nums1. The function modifies nums1 in-place to save space.

Steps to Solve the Problem

1. Understand the Inputs:
   • nums1: A vector with enough space to hold elements of both arrays (m valid elements followed by n empty slots).
   • nums2: A vector containing n elements.
   • m: Number of valid elements in nums1.
   • n: Number of elements in nums2.
2. Start from the End:
   • Use three pointers:
     • i starts at the last valid element in nums1 (m−1).
     • j starts at the last element in nums2 (n−1).
     • k starts at the last position in nums1 (m+n−1).
3. Merge in Reverse:
   • Compare nums1[i] and nums2[j].
   • Place the larger value at the current position k in nums1.
   • Decrement the respective pointer (i or j) and k.
4. Handle Remaining Elements in nums2:
   • If there are elements left in nums2 (when j >= 0), copy them to nums1.
5. Return the Result:
   • The modified nums1 now contains all elements from both arrays, sorted in ascending order.

4. Longest Substring Without Repeating Characters

Problem: Given a string S, find the length of the longest substring without repeating characters.

Solution: This problem involves finding the longest substring in a string s such that no characters are repeated. The solution uses the sliding window technique with the help of an auxiliary array to track the last seen indices of characters.

Steps to Solve the Problem

1. Initialize Data Structures:
   • Create a map array of size 256 (for all ASCII characters) initialized to -1. This stores the last seen index of each character in the string.
   • Initialize variables:
     • left: Starting index of the current substring.
     • right: Pointer to iterate through the string.
     • length: Stores the maximum length of a substring found so far.
2. Iterate Through the String:
   • Use right as a pointer to traverse the string.
3. Handle Repeated Characters:
   • If the current character s[right] has been seen before (map[s[right]] != -1), update the left pointer to skip over the previous occurrence. Use left = max(map[s[right]] + 1, left) to ensure left only moves forward.
4. Update Last Seen Index:
   • Update map[s[right]] with the current index right.
5. Calculate the Current Window Length:
   • Compute the current window length as right - left + 1 and update length to store the maximum value found so far.
6. Return the Result:
   • After processing the string, length contains the length of the longest substring without repeating characters.

Introduction to DSA.

5. Find the Cycle in a Linked List

Problem: Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

Solution: The problem is to detect if a cycle exists in a linked list, and if it does, return the starting node of the cycle. The solution employs Floyd’s Cycle Detection Algorithm, also known as the tortoise and hare algorithm, which uses two pointers (slow and fast) to traverse the list.

Steps to Solve the Problem

1. Initialize Two Pointers:
   • slow and fast pointers are both initialized to point to the head of the linked list.
2. Traverse the Linked List:
   • Move slow one step at a time (slow = slow->next).
   • Move fast two steps at a time (fast = fast->next->next).
3. Detect a Cycle:
   • If slow and fast pointers meet, a cycle exists. Break out of the loop.
   • If fast becomes NULL or fast->next becomes NULL, the list has no cycle; return NULL.
4. Find the Starting Node of the Cycle:
   • Reset slow to head.
   • Move both slow and fast one step at a time until they meet. The meeting point is the start of the cycle.
5. Return the Result:
   • Return the node where slow and fast meet after the second traversal.
   • If no cycle is detected, return NULL.

6. Maximum Subarray (Kadane’s Algorithm)

Problem: Given an integer array nums, find the subarray with the largest sum, and return its sum.

Solution: This problem is about finding the maximum sum of a contiguous subarray in a given array of integers. The solution uses Kadane’s Algorithm, which efficiently computes the result in linear time by dynamically updating the subarray sums.

Steps to Solve the Problem

1. Initialization:
   • Define maxend to track the sum of the current subarray. Initialize it to 0.
   • Define res to store the maximum subarray sum found so far. Start with nums[0] (the first element) because even if the array has only one element, that’s the result.
2. Iterate Over the Array:
   • Loop through each element in nums.
3. Update the Current Subarray Sum:
   • Add the current element (nums[i]) to maxend.
4. Update the Maximum Subarray Sum:
   • If maxend is greater than res, update res to maxend.
5. Reset the Current Subarray Sum if Needed:
   • If maxend becomes negative, reset it to 0. A negative sum will not contribute positively to a larger subarray sum.
6. Return the Result:
   • At the end of the loop, return res as the maximum sum of a contiguous subarray.

7. Search in Rotated Sorted Array

Problem: Search for a target in a rotated sorted array. Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums. You must write an algorithm with O(log n) runtime complexity.

Solution: This code solves the problem of searching for a target value in a rotated sorted array. It uses a modified Binary Search approach to account for the rotated structure of the array.

Steps to Solve the Problem

1. Initialize Variables:
   • s (start) is set to the beginning of the array (0).
   • e (end) is set to the last index of the array (nums.size() - 1).
2. Binary Search Loop:
   • While s <= e, calculate the middle index, m = (s + e) / 2.
3. Check if the Middle Element is the Target:
   • If nums[m] == target, return m as the index where the target is found.
4. Determine the Sorted Half:
   • Check which side of the array (left or right of m) is sorted:
     • Left half is sorted: If nums[s] <= nums[m].
     • Right half is sorted: Otherwise (nums[s] > nums[m]).
5. Search in the Relevant Half:
   • For the sorted half:
     • Check if the target lies within the range of the sorted portion.
     • Adjust s or e accordingly to narrow the search.
6. Handle Equal Elements (Edge Case):
   • If nums[s] == nums[m], increment s to avoid an infinite loop (handles duplicate elements).
7. Target Not Found:
   • If the loop ends without finding the target, return -1.

Introduction to React.

8. Trapping Rainwater

Problem: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Solution: This problem aims to calculate the total water that can be trapped between the heights of the bars. The solution uses a pre-computation approach with two auxiliary arrays, left and right, to track the maximum height to the left and right of each bar.

Steps to Solve the Problem

1. Handle Edge Case:
   • If the input array height is empty (n == 0), return 0 as no water can be trapped.
2. Pre-compute Maximum Heights on the Left:
   • Create an array left where:
     • left[i] stores the maximum height from the left up to index i.
   • Initialize left[0] = height[0].
   • For each index i (from 1 to n−1), compute:
   • left[i]=max⁡(left[i−1],height[i]).
3. Pre-compute Maximum Heights on the Right:
   • Create an array right where:
     • right[i] stores the maximum height from the right up to index i.
   • Initialize right[n-1] = height[n-1].
   • For each index i (from n−2 to 0), compute:
   • right[i]=max⁡(right[i+1],height[i])
4. Calculate Trapped Water:
   • For each bar at index i, calculate the water trapped as: trapped_Water[i]=min⁡(left[i],right[i])−height[i]
   • Accumulate the trapped water in the variable trapped_Water.
5. Return the Total Water:
   • After iterating through all indices, return the total trapped_Water.

9. Two Sum

Problem: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Solution: The goal is to find two indices ‘i’ and ‘j’ such that nums[i]+nums[j]=target. This solution uses a nested loop to check all possible pairs in the array.

Steps to Solve the Problem

1. Initialize Variables:
   • Create an empty vector ans to store the indices of the two numbers that sum up to the target.
   • Get the size of the input array nums in variable n.
2. Nested Loops to Check Pairs:
   • Use the outer loop with index i to iterate through each element of nums from 0 to n−1.
   • Use the inner loop with index j starting from i+1 to iterate through the elements after i.
   • For each pair (i,j), check if:
   • nums[i]+nums[j]==target.
3. Store the Indices:
   • If the condition nums[i]+nums[j]==target is satisfied:
     • Add i and j to the ans vector.
4. Return the Result:
   • After iterating through all possible pairs, return the ans vector containing the indices of the two numbers.

10. Valid Parentheses

Problem: Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Solution: To solve this, we’ll use a stack data structure. The stack helps us keep track of the opening brackets, and when we encounter a closing bracket, we can easily check if it matches the most recent opening bracket.

Steps to Solve the Problem

1. Initialize a Stack:
   • Create a stack ans to keep track of the opening brackets.
2. Iterate Over the String:
   • Loop through each character ch in the string s.
3. Handle Opening Brackets:
   • If the current character is an opening bracket (‘(‘, ‘{‘, or ‘[‘), push it onto the stack.
4. Handle Closing Brackets:
   • If the current character is a closing bracket (‘)’, ‘}’, or ‘]’):
     • Check if the stack is empty. If it is, it means there’s no matching opening bracket, so return false.
     • If the stack is not empty, check the top element of the stack:
       • If the top matches the current closing bracket (i.e., if ch is ‘)’ and the top is ‘(‘, or ch is ‘}’ and the top is ‘{‘, etc.), pop the stack.
       • Otherwise, return false because the brackets do not match.
5. Final Check:
   • After iterating through the entire string, if the stack is empty, it means all opening brackets had matching closing brackets, so return true.
   • If the stack is not empty, return false, indicating there are unmatched opening brackets left.

These are the some important Dsa Questions that you atleast once face in your tech Interview or exam. You can also try to solve these questions with various different approaches, but also keep a rough flow chart of each approaches and solution that you can explain to someone in details.

Stay connected for more content like this.

Happy Coding!

Follow and contact us on Linkedin, Whatsapp, facebook.