Quiz: Can You Solve These Tricky Algorithm Problems?

Solution:

There are multiple ways to solve this problem, but one of the most efficient solutions uses the XOR operation. Here’s the step-by-step approach:

1. Initialize a variable result with 0.
2. XOR result with every number from 1 to n.
3. XOR result with every number in the given array.
4. The final value of result will be the missing number.

Here’s the implementation in Python:

def find_missing_number(arr):
    n = len(arr) + 1
    result = 0
    
    # XOR with numbers from 1 to n
    for i in range(1, n + 1):
        result ^= i
    
    # XOR with numbers in the array
    for num in arr:
        result ^= num
    
    return result

# Test the function
arr = [1, 2, 4, 6, 3, 7, 8]
print(find_missing_number(arr))  # Output: 5

Explanation: This solution works because of the properties of XOR operation:

• XOR of a number with itself is 0.
• XOR of a number with 0 is the number itself.
• XOR is associative and commutative.

By XORing all numbers from 1 to n and all numbers in the array, every number except the missing one will be XORed twice (canceling out to 0). The missing number will be XORed only once, leaving it as the result.

Time Complexity: O(n)
Space Complexity: O(1)

Solution:

We can solve this problem using dynamic programming. Here’s an efficient approach:

1. Create a 2D boolean table to store whether substrings are palindromes.
2. All substrings of length 1 are palindromes.
3. Check for substrings of length 2.
4. For substrings of length 3 or more, check if the first and last characters match and if the inner substring is a palindrome.
5. Keep track of the longest palindrome found.

Here’s the implementation in Python:

def longest_palindrome(s):
    n = len(s)
    # Table to store results of subproblems
    dp = [[False for _ in range(n)] for _ in range(n)]
    
    # All substrings of length 1 are palindromes
    for i in range(n):
        dp[i][i] = True
    
    start = 0
    max_length = 1
    
    # Check for substrings of length 2
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start = i
            max_length = 2
    
    # Check for lengths greater than 2
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                if length > max_length:
                    start = i
                    max_length = length
    
    return s[start:start + max_length]

# Test the function
print(longest_palindrome("babad"))  # Output: "bab" or "aba"
print(longest_palindrome("cbbd"))   # Output: "bb"

Explanation: This solution uses a bottom-up dynamic programming approach:

• We first initialize all substrings of length 1 as palindromes.
• Then we check for palindromes of length 2.
• For longer substrings, we check if the first and last characters match and if the inner substring is already a palindrome (which we’ve calculated in previous iterations).
• We keep track of the start index and length of the longest palindrome found.

Time Complexity: O(n^2), where n is the length of the string
Space Complexity: O(n^2) for the DP table

Solution:

We can solve this problem efficiently using a min-heap (priority queue). Here’s the approach:

1. Create a min-heap to store the head nodes of all lists.
2. Initialize the heap with the first node of each list.
3. While the heap is not empty:
   • Pop the smallest node from the heap.
   • Add it to the result list.
   • If the node has a next element, push it onto the heap.

Here’s the implementation in Python:

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeKLists(lists):
    # Custom comparator for the heap
    ListNode.__lt__ = lambda self, other: self.val < other.val
    
    heap = []
    dummy = ListNode(0)
    current = dummy
    
    # Add the head of each list to the heap
    for head in lists:
        if head:
            heapq.heappush(heap, head)
    
    while heap:
        node = heapq.heappop(heap)
        current.next = node
        current = current.next
        
        if node.next:
            heapq.heappush(heap, node.next)
    
    return dummy.next

# Helper function to create a linked list from a list
def create_linked_list(lst):
    dummy = ListNode(0)
    current = dummy
    for val in lst:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

# Helper function to convert linked list to list
def linked_list_to_list(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

# Test the function
lists = [
    create_linked_list([1,4,5]),
    create_linked_list([1,3,4]),
    create_linked_list([2,6])
]
merged = mergeKLists(lists)
print(linked_list_to_list(merged))  # Output: [1,1,2,3,4,4,5,6]

Explanation: This solution uses a min-heap to efficiently merge the sorted lists:

• We start by adding the head of each list to the min-heap.
• We then repeatedly pop the smallest node from the heap, add it to our result list, and push its next node (if it exists) onto the heap.
• This process continues until the heap is empty, at which point we’ve merged all the lists.

Time Complexity: O(N log k), where N is the total number of nodes and k is the number of linked lists
Space Complexity: O(k) for the heap

Solution:

We can solve this problem efficiently using a two-pointer approach. Here’s how it works:

1. Initialize two pointers, left and right, at the start and end of the array.
2. Keep track of the maximum height seen from both left and right.
3. Move the pointer pointing to the smaller height inward:
   • If the current height is less than the max height on that side, add the difference to the total water trapped.
   • Otherwise, update the max height for that side.
4. Repeat until the pointers meet.

Here’s the implementation in Python:

def trap(height):
    if not height:
        return 0
    
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    
    return water

# Test the function
print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))  # Output: 6

Explanation: This solution uses a two-pointer approach to efficiently calculate the trapped water:

• We maintain two pointers, left and right, and move them towards each other.
• We also keep track of the maximum height seen from both left and right.
• At each step, we move the pointer pointing to the smaller height:
  • If the current height is less than the max height on that side, we can trap water above the current position. We add the difference to our total.
  • If the current height is greater than or equal to the max height, we update the max height for that side.
• This approach works because the amount of water that can be trapped at any position is determined by the smaller of the maximum heights to its left and right.

Time Complexity: O(n), where n is the length of the height array
Space Complexity: O(1), as we only use a constant amount of extra space

Solution:

This is one of the most challenging algorithm problems often asked in technical interviews. We can solve it efficiently using a binary search approach. Here’s how it works:

1. Ensure nums1 is the smaller array. If not, swap them.
2. Perform binary search on the smaller array to find the partition point.
3. Calculate the partition point for the larger array based on the smaller array’s partition.
4. Compare the elements around the partition points to ensure correct order.
5. If the order is correct, we’ve found the median. If not, adjust the binary search range and repeat.

Here’s the implementation in Python:

def findMedianSortedArrays(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    
    m, n = len(nums1), len(nums2)
    low, high = 0, m
    
    while low <= high:
        partitionX = (low + high) // 2
        partitionY = (m + n + 1) // 2 - partitionX
        
        maxLeftX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
        minRightX = float('inf') if partitionX == m else nums1[partitionX]
        
        maxLeftY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
        minRightY = float('inf') if partitionY == n else nums2[partitionY]
        
        if maxLeftX <= minRightY and maxLeftY <= minRightX:
            if (m + n) % 2 == 0:
                return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2
            else:
                return max(maxLeftX, maxLeftY)
        elif maxLeftX > minRightY:
            high = partitionX - 1
        else:
            low = partitionX + 1
    
    raise ValueError("Input arrays are not sorted")

# Test the function
print(findMedianSortedArrays([1,3], [2]))  # Output: 2.0
print(findMedianSortedArrays([1,2], [3,4]))  # Output: 2.5

Explanation: This solution uses a binary search approach to find the correct partition point:

• We perform binary search on the smaller array to find a partition point.
• Based on this partition, we calculate the corresponding partition in the larger array.
• We then check if the elements around these partition points are in the correct order (i.e., all elements to the left are smaller than or equal to all elements to the right).
• If they are, we’ve found the median. If not, we adjust our binary search range and try again.
• Once we find the correct partition, the median is either the maximum of the left elements (for odd total length) or the average of the maximum left and minimum right elements (for even total length).

Time Complexity: O(log(min(m,n))), where m and n are the lengths of the input arrays
Space Complexity: O(1), as we only use a constant amount of extra space