Skip to main content

Poridhi: Sorting & Searching


Sorting & Searching related problems:

This blog post presents efficient Python solutions to four commonly encountered algorithmic problems that involve arrays and linked lists. It begins with the Merge Intervals problem, which focuses on combining overlapping intervals into consolidated ranges—commonly used in scheduling or time-based tasks. Next, it addresses the Find Minimum in Rotated Sorted Array, helping identify the smallest element in a rotated array using binary search. The Search in Rotated Sorted Array problem is tackled next, showing how to locate a target value even when the array has been pivoted. Finally, the post explains how to Merge Two Sorted Linked Lists, a classic linked list problem often asked in coding interviews, which involves combining two already sorted lists into one while maintaining order. Together, these solutions reinforce understanding of sorting, binary search, and linked list traversal—all essential for technical interviews and real-world development.


✅ Merge Intervals

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

# Example
print(merge([[1,3],[2,6],[8,10],[15,18]]))  # Output: [[1,6],[8,10],[15,18]]

✅ Find Minimum in Rotated Sorted Array

def findMin(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]

# Example
print(findMin([3,4,5,1,2]))  # Output: 1

✅ Search in Rotated Sorted Array

def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:  # left side is sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # right side is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

# Example
print(search([4,5,6,7,0,1,2], 0))  # Output: 4

✅ Merge Two Sorted Lists

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

def mergeTwoLists(list1, list2):
    dummy = ListNode()
    tail = dummy
    while list1 and list2:
        if list1.val < list2.val:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next
    tail.next = list1 if list1 else list2
    return dummy.next

# Example usage for demonstration
def print_list(head):
    while head:
        print(head.val, end=' ')
        head = head.next
    print()

a = ListNode(1, ListNode(2, ListNode(4)))
b = ListNode(1, ListNode(3, ListNode(5)))
merged = mergeTwoLists(a, b)
print_list(merged)  # Output: 1 1 2 3 4 5


Comments

Post a Comment

Popular posts from this blog

Poridhi: Stacks & Queues

  Stacks & Queues related problems: This collection of solutions tackles three classic problems often encountered in technical interviews and competitive programming. The Valid Parentheses problem checks whether a string has properly matched and ordered brackets using a stack. The Sliding Window Maximum efficiently finds the maximum value in every window of size k across an array using a deque, a popular sliding window pattern that ensures optimal performance. The Stock Span Problem simulates a real-world stock analysis scenario and calculates the number of consecutive days before today for which the stock price was less than or equal to today's, also utilizing a stack for efficient computation. These problems test understanding of stacks, queues, and sliding window techniques. ✅ Valid Parentheses def isValid ( s: str ) -> bool : stack = [] mapping = { ')' : '(' , '}' : '{' , ']' : '[' } for char in s: ...
Post a Comment
Read more

Data Recovery: DevOps pre-state learning

  Data Backup Data backup is the practice of copying data from a primary to a secondary location, to protect it in case of equipment failure, cyberattack, natural disaster or other data loss events. This can include documents, media files, configuration files, machine images, operating systems, and registry files. Essentially, any data that we want to preserve can be stored as backup data. Data Restore Data restore is the process of copying backup data from secondary storage and restoring it to its original location or a new location. A restore is performed to return data that has been lost, stolen or damaged to its original condition or to move data to a new location. Pilot Light A pilot light approach minimizes the ongoing cost of disaster recovery by minimizing the active resources, and simplifies recovery at the time of a disaster because the core infrastructure requirements are all in place. Warm Standby The warm standby approach involves ensuring that there is a scaled down, ...
Post a Comment
Read more

Poridhi: Basic Programming & Math

Basic Programming and math related problems: Extracting digits means breaking a number like 1234 into [1, 2, 3, 4], often using string conversion or modulo/division. Counting digits involves finding how many digits are in a number using length of a string or repeated division. Reversing an integer flips its digits (e.g., 123 becomes 321), with care for signs and 32-bit limits. A palindrome number reads the same forward and backward, often checked by comparing the original and reversed number. Armstrong numbers are those equal to the sum of their digits each raised to the number of digits, like 153 = 1³ + 5³ + 3³. To find the sum of all divisors of a number, loop through integers and check which divide the number without a remainder. Prime numbers are only divisible by 1 and themselves, and checking up to the square root is efficient. GCD, the greatest common divisor of two numbers, can be found using a simple loop or more efficiently with the Euclidean algorithm, which uses repeated mo...
Post a Comment
Read more