kmp algo

def compute_lps(pattern):
    """
    Preprocess the pattern to create the longest prefix suffix (LPS) array.
    LPS[i] contains the length of the longest proper prefix of pattern[0...i]
    which is also a suffix of pattern[0...i].
    """
    m = len(pattern)
    lps = [0] * m  # LPS array
    length = 0  # Length of the previous longest prefix suffix
    i = 1

    # Build the LPS array
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1

    return lps

def kmp_search(text, pattern):
    """
    Perform KMP search to find occurrences of 'pattern' in 'text'.
    Returns a list of starting indices where pattern is found.
    """
    n = len(text)
    m = len(pattern)
    
    # Preprocess the pattern to get the LPS array
    lps = compute_lps(pattern)
    
    i = 0  # index for text
    j = 0  # index for pattern
    results = []
    
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        
        if j == m:  # Pattern found
            results.append(i - j)
            j = lps[j - 1]  # Use the LPS array to skip characters
        
        # Mismatch after j matches
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]  # Use the LPS array to skip characters
            else:
                i += 1
    
    return results

# Example usage:
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
matches = kmp_search(text, pattern)

print(f"Pattern found at indices: {matches}")



Tree
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.value = key

def find_maximum(root):
    """
    Function to find the maximum element in a binary tree.
    It performs a depth-first traversal (in-order, pre-order, or post-order).
    
    root: The root node of the binary tree.
    
    Returns: The maximum value in the tree.
    """
    if root is None:
        return float('-inf')  # If the tree is empty, return negative infinity
    
    # Recurse on left and right subtree
    left_max = find_maximum(root.left)
    right_max = find_maximum(root.right)
    
    # Return the maximum of the current node value, left max, and right max
    return max(root.value, left_max, right_max)

# Example Usage:

# Creating a binary tree
#       10
#      /  \
#     20   30
#    /  \
#   40   50
root = Node(10)
root.left = Node(20)
root.right = Node(30)
root.left.left = Node(40)
root.left.right = Node(50)

# Finding the maximum element
max_value = find_maximum(root)
print(f"The maximum value in the binary tree is: {max_value}")



def merge_dicts(dict1, dict2):
    """
    Merges two dictionaries by summing the values of common keys.
    
    dict1, dict2: The input dictionaries to be merged.
    
    Returns: A dictionary that contains the merged result.
    """
    # Create a new dictionary to store the result
    merged_dict = dict1.copy()
    
    # Iterate over the second dictionary
    for key, value in dict2.items():
        if key in merged_dict:
            # If the key exists in both dictionaries, sum the values
            merged_dict[key] += value
        else:
            # If the key does not exist in the first dictionary, just add it
            merged_dict[key] = value
    
    return merged_dict

# Example Usage:

dict1 = {'a': 5, 'b': 10, 'c': 15}
dict2 = {'a': 3, 'b': 20, 'd': 25}

merged_dict = merge_dicts(dict1, dict2)
print("Merged Dictionary:", merged_dict)


class Student:
    def __init__(self, name):
        # Initialize the student with a name and an empty list for grades
        self.name = name
        self.grades = []

    def add_grade(self, grade):
        # Add a grade to the student's grades list
        self.grades.append(grade)

    def calculate_average(self):
        # Calculate the average of the grades
        if len(self.grades) == 0:
            return 0  # Return 0 if no grades are added
        return sum(self.grades) / len(self.grades)

# Example usage:
student1 = Student("John")
student1.add_grade(90)
student1.add_grade(85)
student1.add_grade(88)

print(f"{student1.name}'s average grade: {student1.calculate_average()}")



def heapify(arr, n, i):
    """
    To maintain the heap property by recursively fixing the heap.
    """
    largest = i  # Initialize largest as root
    left = 2 * i + 1  # left child
    right = 2 * i + 2  # right child

    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left

    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right

    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # Swap
        heapify(arr, n, largest)  # Recursively heapify the affected subtree

def heap_sort(arr):
    """
    Main function to perform heap sort.
    """
    n = len(arr)

    # Build a max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # One by one extract elements from the heap
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # Swap the root (max) with the last element
        heapify(arr, i, 0)  # Heapify the reduced heap

# Example usage:
arr = [12, 11, 13, 5, 6, 7]
print("Original array:", arr)
heap_sort(arr)
print("Sorted array:", arr)


def swap_tuple_elements(tup, index1, index2):
    try:
        # Check if indices are within valid range
        if index1 < 0 or index1 >= len(tup) or index2 < 0 or index2 >= len(tup):
            raise IndexError("Invalid indices")
        
        # Convert the tuple to a list to make it mutable
        lst = list(tup)
        
        # Swap the elements at index1 and index2
        lst[index1], lst[index2] = lst[index2], lst[index1]
        
        # Convert the list back to a tuple and return it
        return tuple(lst)
    
    except IndexError as e:
        return str(e)

# Example usage:
tup = (1, 2, 3, 4, 5)
index1 = 1
index2 = 3

result = swap_tuple_elements(tup, index1, index2)
print(result)  # Output: (1, 4, 3, 2, 5)

# Handling invalid indices
invalid_result = swap_tuple_elements(tup, 1, 10)
print(invalid_result)  # Output: Invalid indices






Write the Python program to implement bubble sort 
def bubble_sort(arr):
    n = len(arr)
    
    # Traverse through all elements in the array
    for i in range(n):
        # Last i elements are already in place, no need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# Example usage:
arr = [64, 34, 25, 12, 22, 11, 90]
print("Original array:", arr)

bubble_sort(arr)

print("Sorted array:", arr)

find all email addresses in the following text using regular expression in python 
text ="contact us at support@example.com and sales@example.com"
import re

# Given text
text = "contact us at support@example.com and sales@example.com"

# Regular expression to match email addresses
email_pattern = r'\b[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,}\b'

# Find all email addresses in the text
emails = re.findall(email_pattern, text)

# Print the list of email addresses
print(emails)

 handle division operation with exception handling for 0 division error and type error in python 
def safe_divide(a, b):
    try:
        # Attempt to divide a by b
        result = a / b
        return result
    except ZeroDivisionError:
        # Handle division by zero
        return "Error: Cannot divide by zero."
    except TypeError:
        # Handle invalid types (e.g., non-numeric values)
        return "Error: Both operands must be numbers."
    
# Example usage:
print(safe_divide(10, 2))  # Valid division
print(safe_divide(10, 0))  # Division by zero
print(safe_divide(10, "a"))  # Invalid type (string instead of number)

Write a Python program to perform quick sort on a list 
def quick_sort(arr):
    # Base case: if the array has 1 or 0 elements, it's already sorted
    if len(arr) <= 1:
        return arr
    
    # Step 1: Choose a pivot element (we use the last element)
    pivot = arr[-1]
    
    # Step 2: Partition the array into two parts:
    # - Left: elements smaller than the pivot
    # - Right: elements greater than the pivot
    left = [x for x in arr[:-1] if x <= pivot]   # Elements smaller than or equal to pivot
    right = [x for x in arr[:-1] if x > pivot]   # Elements greater than pivot
    
    # Step 3: Recursively apply quick_sort on the left and right subarrays, and concatenate
    return quick_sort(left) + [pivot] + quick_sort(right)

# Example usage:
arr = [10, 7, 8, 9, 1, 5]
sorted_arr = quick_sort(arr)
print("Sorted array:", sorted_arr)

Python program write a Python program to solve the 0/1 knapsack problem using dynamic programming 
def knapsack(weights, values, capacity, n, memo):
    # Base case: If there are no items or capacity is 0, the value is 0
    if n == 0 or capacity == 0:
        return 0
    
    # If this subproblem has already been solved, return the cached value
    if memo[n][capacity] != -1:
        return memo[n][capacity]
    
    # If the weight of the current item is less than or equal to the current capacity
    if weights[n - 1] <= capacity:
        # Choose the maximum of including or excluding the current item
        include_item = values[n - 1] + knapsack(weights, values, capacity - weights[n - 1], n - 1, memo)
        exclude_item = knapsack(weights, values, capacity, n - 1, memo)
        # Store the result in the memo table and return the result
        memo[n][capacity] = max(include_item, exclude_item)
    else:
        # If the item can't be included, exclude it and solve the subproblem
        memo[n][capacity] = knapsack(weights, values, capacity, n - 1, memo)
    
    return memo[n][capacity]

# Example usage:
weights = [1, 3, 4, 5]  # Weights of the items
values = [1, 4, 5, 7]   # Values of the items
capacity = 7            # Maximum weight the knapsack can carry
n = len(weights)        # Number of items

# Create a memoization table initialized with -1
memo = [[-1 for _ in range(capacity + 1)] for _ in range(n + 1)]

max_value = knapsack(weights, values, capacity, n, memo)
print(f"The maximum value that can be carried in the knapsack is: {max_value}")


def knapsack(values, weights, capacity):
    n = len(values)  # Number of items
    
    # Initialize a DP table with 0 using two loops
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    # Build the DP table using two loops
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # If the current item can be included in the knapsack
            if weights[i - 1] <= w:
                # Take the maximum of excluding or including the item
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])
            else:
                # If the item can't be included, carry forward the value without including it
                dp[i][w] = dp[i - 1][w]
    
    # The bottom-right cell of the DP table will contain the result
    return dp[n][capacity]

# Example usage:
values = [3, 4, 5, 6]  # Values of the items
weights = [2, 3, 4, 5]  # Weights of the items
capacity = 5  # Capacity of the knapsack

# Call the knapsack function
max_value = knapsack(values, weights, capacity)
print("The maximum value that can be obtained is:", max_value)


Implement a function to find the length of longest substring without repeating character in Python 
def longest_substring_without_repeating(s: str) -> int:
    # Dictionary to store the last index of each character
    char_index = {}
    
    # Initialize the start pointer and max_length
    start = 0
    max_length = 0
    
    # Iterate over the string with the end pointer
    for end in range(len(s)):
        # If the character is already in the window, update start to avoid duplicates
        if s[end] in char_index and char_index[s[end]] >= start:
            # Move the start pointer to the right of the last occurrence of s[end]
            start = char_index[s[end]] + 1
        
        # Update the last seen index of the current character
        char_index[s[end]] = end
        
        # Update the maximum length of the substring
        max_length = max(max_length, end - start + 1)
    
    return max_length

# Example usage:
input_str = "abcabcbb"
print("Length of the longest substring without repeating characters:", longest_substring_without_repeating(input_str))




Implement a class rectangle with methods to calculate area and perimeter 
class Rectangle:
    def __init__(self, length, width):
        """Initialize the rectangle with length and width."""
        self.length = length
        self.width = width
    
    def area(self):
        """Return the area of the rectangle."""
        return self.length * self.width
    
    def perimeter(self):
        """Return the perimeter of the rectangle."""
        return 2 * (self.length + self.width)
    
    def __str__(self):
        """Return a string representation of the rectangle."""
        return f"Rectangle with length {self.length} and width {self.width}"

# Example usage:
rect = Rectangle(5, 3)  # Create a rectangle with length=5 and width=3

# Print the rectangle using __str__
print(rect)

# Calculate area and perimeter
print(f"Area of rectangle: {rect.area()}")
print(f"Perimeter of rectangle: {rect.perimeter()}")

Write a Python program to perform binary search on a sorted list 
def binary_search(arr, target):
    # Initialize the low and high pointers
    low = 0
    high = len(arr) - 1
    
    # Perform the binary search loop
    while low <= high:
        mid = (low + high) // 2  # Find the middle index
        
        # Check if target is at the middle
        if arr[mid] == target:
            return mid  # Target found, return index
        
        # If target is smaller, search the left half
        elif arr[mid] > target:
            high = mid - 1
        
        # If target is larger, search the right half
        else:
            low = mid + 1
    
    return -1  # Target not found

# Example usage:
sorted_list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 7

result = binary_search(sorted_list, target)

if result != -1:
    print(f"Target {target} found at index {result}")
else:
    print(f"Target {target} not found in the list.")

write a Python program to implement a stack using a list 
class Stack:
    def __init__(self):
        """Initialize an empty stack."""
        self.stack = []

    def push(self, item):
        """Push an item onto the stack."""
        self.stack.append(item)

    def pop(self):
        """Pop an item from the stack. Returns None if the stack is empty."""
        if not self.is_empty():
            return self.stack.pop()
        else:
            return None  # Return None if the stack is empty

    def peek(self):
        """Return the top item of the stack without removing it."""
        if not self.is_empty():
            return self.stack[-1]
        else:
            return None  # Return None if the stack is empty

    def is_empty(self):
        """Return True if the stack is empty, False otherwise."""
        return len(self.stack) == 0

    def size(self):
        """Return the size of the stack."""
        return len(self.stack)

# Example usage:
stack = Stack()

# Push items onto the stack
stack.push(10)
stack.push(20)
stack.push(30)

print(f"Stack size: {stack.size()}")  # Output: 3
print(f"Top item: {stack.peek()}")  # Output: 30

# Pop an item from the stack
popped_item = stack.pop()
print(f"Popped item: {popped_item}")  # Output: 30

# Check if the stack is empty
print(f"Is stack empty? {stack.is_empty()}")  # Output: False

# Pop remaining items
print(f"Popped item: {stack.pop()}")  # Output: 20
print(f"Popped item: {stack.pop()}")  # Output: 10

# Check if the stack is empty again
print(f"Is stack empty? {stack.is_empty()}")  # Output: True

Write a Python program to perform topological sorting of a directed a cyclic graph DAG
from collections import deque, defaultdict

def topological_sort(vertices, edges):
    # Create an adjacency list and an indegree dictionary
    adj_list = defaultdict(list)
    indegree = {v: 0 for v in vertices}
    
    # Build the graph and calculate indegrees
    for u, v in edges:
        adj_list[u].append(v)
        indegree[v] += 1
    
    # Initialize the queue with nodes having zero indegree
    queue = deque([v for v in vertices if indegree[v] == 0])
    
    topological_order = []
    
    while queue:
        # Remove a node from the queue
        node = queue.popleft()
        topological_order.append(node)
        
        # For each neighbor of the node, reduce its indegree
        for neighbor in adj_list[node]:
            indegree[neighbor] -= 1
            # If the neighbor's indegree becomes zero, add it to the queue
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    
    # If the length of topological_order is less than the number of vertices, a cycle exists
    if len(topological_order) != len(vertices):
        print("Cycle detected! Topological sort is not possible.")
        return None
    
    return topological_order

# Example usage:
vertices = ['A', 'B', 'C', 'D', 'E', 'F']
edges = [('A', 'D'), ('B', 'D'), ('C', 'E'), ('D', 'F'), ('E', 'F')]

result = topological_sort(vertices, edges)

if result:
    print("Topological Sort:", result)

write a Python program to implement the A* search algorithm for path finding
import heapq

# Define a Node class to store the state and costs for A* search
class Node:
    def __init__(self, position, g=0, h=0, parent=None):
        self.position = position  # Position in the grid
        self.g = g  # Cost from the start node
        self.h = h  # Heuristic (estimated cost to the goal)
        self.f = g + h  # Total cost (f = g + h)
        self.parent = parent  # Parent node for path reconstruction

    # To compare nodes based on their f value for the priority queue
    def __lt__(self, other):
        return self.f < other.f


def a_star(start, goal, grid):
    # Directions for movement (up, down, left, right)
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    # Heuristic function: Manhattan distance
    def heuristic(a, b):
        return abs(a[0] - b[0]) + abs(a[1] - b[1])

    # Open list (priority queue) and closed list
    open_list = []
    closed_list = set()

    # Start node
    start_node = Node(start, 0, heuristic(start, goal))
    heapq.heappush(open_list, start_node)

    while open_list:
        # Get the node with the lowest f value
        current_node = heapq.heappop(open_list)
        closed_list.add(current_node.position)

        # If we reach the goal, reconstruct the path
        if current_node.position == goal:
            path = []
            while current_node:
                path.append(current_node.position)
                current_node = current_node.parent
            return path[::-1]  # Return reversed path

        # Explore neighbors
        for direction in directions:
            neighbor_position = (current_node.position[0] + direction[0], current_node.position[1] + direction[1])

            # Check if neighbor is within bounds and not blocked
            if 0 <= neighbor_position[0] < len(grid) and 0 <= neighbor_position[1] < len(grid[0]) and grid[neighbor_position[0]][neighbor_position[1]] != 1:
                if neighbor_position in closed_list:
                    continue

                # Calculate g and h values
                g_cost = current_node.g + 1  # Assume cost is 1 for each move
                h_cost = heuristic(neighbor_position, goal)
                neighbor_node = Node(neighbor_position, g_cost, h_cost, current_node)

                # If neighbor is not in open list or has a lower f value, add it
                if not any(neighbor.position == neighbor_position and neighbor.f <= neighbor_node.f for neighbor in open_list):
                    heapq.heappush(open_list, neighbor_node)

    return None  # No path found


# Example Usage
grid = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 0, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0]
]

start = (0, 0)  # Start position
goal = (4, 4)   # Goal position

path = a_star(start, goal, grid)

if path:
    print("Path found:", path)
else:
    print("No path found")
 
Write a Python program to perform depth first search on a graph 
# Depth First Search (DFS) - Iterative version

def dfs_iterative(graph, start):
    visited = set()  # Set to track visited nodes
    stack = [start]  # Stack to manage the traversal

    while stack:
        node = stack.pop()  # Pop a node from the stack
        if node not in visited:
            visited.add(node)  # Mark it as visited
            print(node, end=" ")  # Process the node (for example, print it)
            
            # Push all unvisited neighbors to the stack
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

# Example usage
print("\nDFS Traversal (Iterative):")
dfs_iterative(graph, 'A')

Implement of function to detect a cycle in a linked list in Python 
class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def has_cycle(head):
    # Edge case: if the list is empty or has only one node
    if not head or not head.next:
        return False
    
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next          # Move slow pointer one step
        fast = fast.next.next     # Move fast pointer two steps
        
        if slow == fast:          # Cycle detected
            return True
    
    return False  # No cycle if we exit the loop

# Helper function to create a linked list
def create_linked_list(values):
    head = ListNode(values[0])
    current = head
    for value in values[1:]:
        current.next = ListNode(value)
        current = current.next
    return head

# Helper function to create a cycle in a linked list for testing
def create_cycle(head, pos):
    if pos == -1:
        return head
    current = head
    cycle_node = None
    count = 0
    while current.next:
        if count == pos:
            cycle_node = current
        current = current.next
        count += 1
    current.next = cycle_node  # Create a cycle
    return head

# Example usage
values = [3, 2, 0, -4]
head = create_linked_list(values)
head = create_cycle(head, 1)  # Creating a cycle at position 1

print("Cycle detected:", has_cycle(head))  # Should return True

# Test with a list without a cycle
head_no_cycle = create_linked_list([1, 2, 3, 4, 5])
print("Cycle detected:", has_cycle(head_no_cycle))  # Should return False

Write a function to perform binary search on a sorted list in python 
def binary_search(arr, target):
    """
    Perform binary search on a sorted list.

    :param arr: Sorted list to search
    :param target: The value to search for
    :return: Index of the target if found, otherwise -1
    """
    left, right = 0, len(arr) - 1  # Initializing the left and right pointers
    
    while left <= right:
        mid = left + (right - left) // 2  # Calculate the middle index
        
        # Check if the target is present at mid
        if arr[mid] == target:
            return mid  # Target found, return the index
        
        # If the target is smaller, ignore the right half
        elif arr[mid] > target:
            right = mid - 1
        
        # If the target is larger, ignore the left half
        else:
            left = mid + 1
    
    return -1  # If the target is not found, return -1

# Example usage
sorted_list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21]
target = 13

result = binary_search(sorted_list, target)

if result != -1:
    print(f"Element {target} found at index {result}")
else:
    print(f"Element {target} not found in the list")

Write a class person with attribute name and age and the method to display details in Python 
class Person:
    def __init__(self, name, age):
        """
        Initializes the Person object with name and age attributes.

        :param name: The name of the person
        :param age: The age of the person
        """
        self.name = name
        self.age = age

    def display_details(self):
        """
        Method to display the details of the person (name and age).
        """
        print(f"Name: {self.name}")
        print(f"Age: {self.age}")
    
    def __str__(self):
        """
        Returns a string representation of the person.
        """
        return f"Person(Name: {self.name}, Age: {self.age})"

# Example usage:
person1 = Person("Alice", 30)
person1.display_details()
print(person1)  # This will use the __str__ method

person2 = Person("Bob", 25)
person2.display_details()
print(person2)  # This will use the __str__ method

Implement of function to sort a list using merge sort algorithm
def merge_sort(arr):
    """
    Function to sort a list using the merge sort algorithm.
    
    :param arr: List to be sorted
    :return: Sorted list
    """
    # Base case: If the list has only one element, it is already sorted
    if len(arr) <= 1:
        return arr
    
    # Step 1: Divide the list into two halves
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # Step 2: Recursively sort both halves
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    # Step 3: Merge the sorted halves
    return merge(left_half, right_half)

def merge(left, right):
    """
    Function to merge two sorted lists into a single sorted list.
    
    :param left: Left sorted list
    :param right: Right sorted list
    :return: Merged sorted list
    """
    sorted_list = []
    i = j = 0
    
    # Merge the two lists while comparing the elements
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_list.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            j += 1
    
    # If there are remaining elements in left or right, append them
    sorted_list.extend(left[i:])
    sorted_list.exten

 write a Python program to perform merge sort on a list 
def merge_sort(arr):
    """
    Function to sort a list using the merge sort algorithm.
    
    :param arr: List to be sorted
    :return: Sorted list
    """
    # Base case: If the list has only one element or is empty
    if len(arr) <= 1:
        return arr
    
    # Step 1: Divide the list into two halves
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # Step 2: Recursively sort both halves
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    # Step 3: Merge the sorted halves
    return merge(left_half, right_half)

def merge(left, right):
    """
    Function to merge two sorted lists into one sorted list.
    
    :param left: Left sorted list
    :param right: Right sorted list
    :return: Merged sorted list
    """
    sorted_list = []
    i = j = 0
    
    # Merge the two lists while comparing the elements
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_list.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            j += 1
    
    # If there are remaining elements in left or right, append them
    sorted_list.extend(left[i:])
    sorted_list.extend(right[j:])
    
    return sorted_list

# Example usage
arr = [38, 27, 43, 3, 9, 82, 10]
print("Original List:", arr)
sorted_arr = merge_sort(arr)
print("Sorted List:", sorted_arr)

Implement a class bank account with methods to deposit withdraw and cheque balance 

class BankAccount:
    def __init__(self, account_holder, initial_balance=0):
        """
        Initializes the BankAccount with the account holder's name and an optional initial balance.
        
        :param account_holder: The name of the account holder
        :param initial_balance: The starting balance of the account (default is 0)
        """
        self.account_holder = account_holder
        self.balance = initial_balance

    def deposit(self, amount):
        """
        Deposits a specified amount into the account.

        :param amount: The amount to deposit
        :return: None
        """
        if amount > 0:
            self.balance += amount
            print(f"Deposited {amount}. New balance is {self.balance}.")
        else:
            print("Deposit amount must be positive.")

    def withdraw(self, amount):
        """
        Withdraws a specified amount from the account if sufficient balance exists.

        :param amount: The amount to withdraw
        :return: None
        """
        if amount > 0:
            if amount <= self.balance:
                self.balance -= amount
                print(f"Withdrew {amount}. New balance is {self.balance}.")
            else:
                print("Insufficient balance!")
        else:
            print("Withdrawal amount must be positive.")

    def check_balance(self):
        """
        Displays the current balance of the account. 

        :return: The current balance
        """
        print(f"Current balance is {self.balance}.")
        return self.balance

    def __str__(self):
        """
        Returns a string representation of the bank account.
        """
        return f"Bank Account of {self.account_holder} with balance: {self.balance}"


# Example usage
account1 = BankAccount("Alice", 1000)
account1.deposit(500)
account1.withdraw(300)
account1.check_balance()

account2 = BankAccount("Bob")
account2.deposit(1500)
account2.withdraw(200)
account2.check_balance()

# Print account details using __str__ method
print(account1)
print(account2)


Implement a Python program to find the shortest path in a graph using disajktra algorithm
 import heapq

def dijkstra(graph, start):
    """
    Find the shortest path in a graph using Dijkstra's algorithm.
    
    :param graph: The graph represented as an adjacency list. 
                  The graph is a dictionary where keys are nodes and values are lists of tuples (neighbor, weight).
    :param start: The starting node.
    :return: A dictionary with the shortest distances from the start node to each node.
    """
    # Initialize the distance table with infinity for all nodes, and 0 for the start node
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    # Priority queue (min-heap) to keep track of the node with the smallest tentative distance
    priority_queue = [(0, start)]  # (distance, node)
    
    while priority_queue:
        # Get the node with the smallest distance
        current_distance, current_node = heapq.heappop(priority_queue)
        
        # If this distance is greater than the recorded distance, skip it
        if current_distance > distances[current_node]:
            continue
        
        # Process each neighbor of the current node
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            
            # If a shorter path to the neighbor is found, update the distance and add the neighbor to the priority queue
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances


# Example graph represented as an adjacency list
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('A', 1), ('C', 2), ('D', 5)],
    'C': [('A', 4), ('B', 2), ('D', 1)],
    'D': [('B', 5), ('C', 1)]
}

# Find the shortest path from node 'A'
start_node = 'A'
shortest_paths = dijkstra(graph, start_node)

# Display the shortest distances from the start node to each node
print(f"Shortest paths from node {start_node}:")
for node, distance in shortest_paths.items():
    print(f"Distance to {node}: {distance}")

Create a decorator that reverses is the output string of a function 
# Define the decorator to reverse the output string
def reverse_output(func):
    def wrapper(*args, **kwargs):
        # Call the original function and get the result
        result = func(*args, **kwargs)
        # Reverse the string result before returning
        return result[::-1]
    return wrapper

# Example function using the decorator
@reverse_output
def greet(name):
    return f"Hello, {name}!"

# Example usage
print(greet("Alice"))  # Output will be the reversed string: "!ecilA ,olleH"

a python implement a class circle with method to calculate area and circumference 

import math

class Circle:
    # Constructor to initialize the radius of the circle
    def __init__(self, radius):
        self.radius = radius
    
    # Method to calculate the area of the circle
    def area(self):
        return math.pi * self.radius ** 2
    
    # Method to calculate the circumference of the circle
    def circumference(self):
        return 2 * math.pi * self.radius
    
    # Optional: __str__ method to return a string representation of the circle
    def __str__(self):
        return f"Circle with radius {self.radius}"

# Example usage
circle = Circle(5)  # Create a Circle object with radius 5
print(f"Area: {circle.area():.2f}")           # Print the area, rounded to 2 decimal places
print(f"Circumference: {circle.circumference():.2f}")  # Print the circumference, rounded to 2 decimal places
print(circle)  # Print the string representation of the circle



Write a Python program to find the minimum number of coin needed to make change for a given amount using a greedy approach 


def min_coins_greedy(coins, amount):
    # Sort the coin denominations in descending order
    coins.sort(reverse=True)
    
    # Initialize the number of coins to 0
    num_coins = 0
    
    # Iterate through the sorted coin denominations
    for coin in coins:
        # Find how many times the coin fits into the amount
        if amount >= coin:
            count = amount // coin  # Get the number of coins of this denomination
            num_coins += count      # Add to the total number of coins
            amount -= count * coin  # Decrease the amount accordingly

        # If the amount becomes zero, break out of the loop
        if amount == 0:
            break
    
    # If we were able to make the exact amount, return the number of coins
    if amount == 0:
        return num_coins
    else:
        # If we couldn't make the exact amount, return -1 (indicating it's not possible)
        return -1

# Example usage
coins = [25, 10, 5, 1]  # Coin denominations
amount = 63  # The amount we want to make change for

result = min_coins_greedy(coins, amount)

if result != -1:
    print(f"The minimum number of coins needed: {result}")
else:
    print("It is not possible to make change with the given coin denominations.")