DSA Lab Exam Coding Questions
Uploaded by
tonoydas2025DSA Lab Exam Coding Questions
Uploaded by
tonoydas2025Common questions
Powered by AITwo strings are anagrams if they can be rearranged to become identical. To determine this, you can convert both strings to arrays of characters, sort these arrays, and compare them for equality. Alternatively, you can count the frequency of each character in both strings using a hash map or count array; if the frequency distributions match, the two strings are anagrams .
A string can potentially become a palindrome by removing a single character if, after removal, the rest of the string or any contiguous substring is a palindrome. Start by checking for mismatches from the beginning and end of the string; once a mismatch is found, check if removing either character forms the remainder into a palindrome. This check is best handled using a two-pointer technique that verifies sub-string integrity .
Compress a string by traversing it once, counting consecutive repeating characters, and appending each character followed by its count to a new string. If the generated string is not shorter than the original, return the original string to avoid increasing the size. This approach might not reduce the size if, for example, there are many distinct characters or short sequences, resulting in an output string longer than the input .
To find all permutations of a string, a backtracking algorithm can be employed. The process involves fixing one character at a time and recursively swapping it with each of the subsequent characters, then fixing the next and proceeding likewise. This generates permutations by swapping backtracked characters back to their original positions at each step to explore new permutations .
The longest palindromic substring can be found using dynamic programming or the expand-around-center approach. In dynamic programming, you create a table where each entry at i, j determines if the substring from i to j is a palindrome, filling this table based on whether the ends match and the inner substring is a palindrome. The expand-around-center method considers each character and each pair of consecutive characters as potential centers, expanding outward as long as a palindrome is detected. Both methods yield a time complexity of O(n^2).
An array is a palindrome if it reads the same forwards and backwards. To determine this, compare pairs of elements starting from the beginning and the end of the array. Specifically, for each index i, check if the element at the ith position is equal to the element at the (length-i-1)th position until the middle of the array is reached. If all corresponding pairs are equal, the array is a palindrome .
To determine if a string's parentheses are properly matched and ordered, you can use a stack data structure. As you iterate through the expression string, push each opening parenthesis ('{', '(', '[') onto the stack. For each closing parenthesis ('}', ')', ']'), check if the stack is not empty and if the top of the stack is the matching opening parenthesis. If so, pop the stack; otherwise, return false immediately. At the end of the iteration, if the stack is empty, the parentheses in the string are properly matched and ordered .
To determine if an array can be split into two subarrays with equal sum, first calculate the total sum of the array elements. If the total sum is not even, it is impossible to split the array as required. If the sum is even, iterate through the array, maintaining a running sum. If the running sum reaches half of the total sum at any point, the array can be split at that point, ensuring both subarrays have equal sums .
To merge two sorted arrays into one, maintain two pointers, one for each array, starting from the beginning. Compare the elements pointed to by these pointers and append the smaller element to the resulting merged array, then move the pointer forward in the array from which the element was taken. Continue this process until all elements in both arrays are exhausted. This approach runs in O(n + m) time complexity, where n and m are the lengths of the two arrays .
Matrix transposition involves swapping the row and column indices for each element, effectively turning all rows into columns and vice versa. In practical applications, transposition is used in mathematical computations, data processing for layout optimization, and input preparation for machine learning models where orientation impacts processing .