Appearance
question:# Working with Heaps: Implementing a Min-Heap Objective Build and manage a Min-Heap data structure from scratch to understand the underpinning mechanics and algorithm implementations. Task Implement a `MinHeap` class that supports the following operations: 1. **Insert**: Insert a new element into the heap, ensuring the min-heap property is maintained. 2. **Extract-Min**: Remove and return the minimum element from the heap, ensuring the min-heap property is maintained. 3. **Decrease-Key**: Given an index and a new key, update the value at that index to the new key, assuming the new key is smaller than the current key. 4. **Heapify**: Convert an arbitrary list of integers into a valid Min-Heap. Requirements - Ensure that the heap is implemented using an underlying array (or list in Python). - Implement the operations with the following method signatures: ```python def insert(self, key: int) -> None: pass def extract_min(self) -> int: pass def decrease_key(self, i: int, new_key: int) -> None: pass def heapify(self, arr: list[int]) -> None: pass ``` Input and Output Formats - **Insert**: - **Input**: An integer `key` - **Output**: None - **Extract-Min**: - **Input**: None - **Output**: Minimum integer in the heap - **Decrease-Key**: - **Input**: An integer `i` (index in the heap) and an integer `new_key` - **Output**: None - **Heapify**: - **Input**: A list of integers `arr` - **Output**: None Constraints - The heap can have up to 10,000 elements. - The integer keys are between `-10^6` and `10^6`. - The `insert` and `extract_min` operations should perform in O(log n) time. - The `decrease_key` and `heapify` operations should handle edge cases and maintain O(log n) and O(n) time complexities, respectively. Example ```python # Initialize MinHeap min_heap = MinHeap() # Insert elements min_heap.insert(10) min_heap.insert(5) min_heap.insert(20) min_heap.insert(2) # Extract the minimum element print(min_heap.extract_min()) # Output: 2 # Decrease key at index 2 to 1 min_heap.decrease_key(2, 1) # Extract the minimum element print(min_heap.extract_min()) # Output: 1 # Heapify an arbitrary array arr = [10, 3, 15, 8, 2, 7] min_heap.heapify(arr) # After heapify, extract the minimum element print(min_heap.extract_min()) # Output: 2 ``` Implement and thoroughly test all the functionalities to ensure the robustness and efficiency of your `MinHeap` class.
answer:class MinHeap: def __init__(self): self.heap = [] def insert(self, key: int) -> None: self.heap.append(key) self._sift_up(len(self.heap) - 1) def extract_min(self) -> int: if len(self.heap) == 0: raise IndexError("Extracting from an empty heap") min_element = self.heap[0] if len(self.heap) > 1: self.heap[0] = self.heap.pop() self._sift_down(0) else: self.heap.pop() return min_element def decrease_key(self, i: int, new_key: int) -> None: if new_key > self.heap[i]: raise ValueError("new_key should be smaller than the current key") self.heap[i] = new_key self._sift_up(i) def heapify(self, arr: list[int]) -> None: self.heap = arr[:] for i in range((len(self.heap) // 2) - 1, -1, -1): self._sift_down(i) def _sift_up(self, index): parent = (index - 1) // 2 while index > 0 and self.heap[index] < self.heap[parent]: self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index] index = parent parent = (index - 1) // 2 def _sift_down(self, index): smallest = index left = 2 * index + 1 right = 2 * index + 2 if left < len(self.heap) and self.heap[left] < self.heap[smallest]: smallest = left if right < len(self.heap) and self.heap[right] < self.heap[smallest]: smallest = right if smallest != index: self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index] self._sift_down(smallest)
question:# Max Sum Rectangle in a 2D Matrix Context You are tasked with finding the maximum sum of any rectangle within a given 2D matrix. The rectangle can be of any size and can start and end at any row or column. Task Implement a function `max_sum_rectangle(matrix: List[List[int]]) -> int` that finds the maximum sum of any rectangle within the matrix. Input Specifications - `matrix` (List[List[int]]): A 2D grid of integers representing the input matrix. Output Specifications - (int): The maximum sum of any rectangle within the matrix. Constraints - The matrix will have dimensions `M x N`, where `1 <= M, N <= 100`. - The elements of the matrix will be integers in the range `[-10^5, 10^5]`. Example ```python matrix = [ [1, 2, -1, -4, -20], [-8, -3, 4, 2, 1], [3, 8, 10, 1, 3], [-4, -1, 1, 7, -6] ] max_sum_rectangle(matrix) ``` Output: ```python 29 ``` # Explanation The maximum sum rectangle is: ``` 3, 8, 10 -4, -1, 1, 7 ``` Which sums to: `3 + 8 + 10 + (-4) + (-1) + 1 + 7 = 24` # Implementation Implement the function `max_sum_rectangle` using the template below: ```python from typing import List def max_sum_rectangle(matrix: List[List[int]]) -> int: def kadane(arr: List[int]) -> int: max_end_here = max_so_far = arr[0] for x in arr[1:]: max_end_here = max(x, max_end_here + x) max_so_far = max(max_so_far, max_end_here) return max_so_far if not matrix or not matrix[0]: return 0 max_sum = float('-inf') rows, cols = len(matrix), len(matrix[0]) for left in range(cols): temp = [0] * rows for right in range(left, cols): for row in range(rows): temp[row] += matrix[row][right] current_max = kadane(temp) max_sum = max(max_sum, current_max) return max_sum ``` This function utilizes Kadane's algorithm to find the maximum sum sub-array in a 1D array, and then applies it to sum columns of subarrays for different start and end columns. This approach ensures that the function runs efficiently even for larger matrices.
answer:from typing import List def max_sum_rectangle(matrix: List[List[int]]) -> int: def kadane(arr: List[int]) -> int: max_end_here = max_so_far = arr[0] for x in arr[1:]: max_end_here = max(x, max_end_here + x) max_so_far = max(max_so_far, max_end_here) return max_so_far if not matrix or not matrix[0]: return 0 max_sum = float('-inf') rows, cols = len(matrix), len(matrix[0]) for left in range(cols): temp = [0] * rows for right in range(left, cols): for row in range(rows): temp[row] += matrix[row][right] current_max = kadane(temp) max_sum = max(max_sum, current_max) return max_sum
question:# Objective Write a function `floor` to implement the floor function, which will return the largest integer that is less than or equal to a given floating-point number. # Input & Output * **Input**: A single floating-point number `x`. * **Output**: An integer representing the floor of `x`. # Constraints 1. You may not use the math library's floor function. 2. Assume the input is always a valid floating-point number and within the range of typical float representation. 3. Optimize the function to have O(1) time complexity and O(1) space complexity. # Example ```python # Example 1 # Input: 3.7 # Output: 3 # Example 2 # Input: -1.2 # Output: -2 # Example 3 # Input: 4.0 # Output: 4 ``` # Scenario Imagine you are developing a data processing tool where you need to round down floating-point values to their nearest lower integer for certain cumulative calculations. Implementing a custom `floor` function will provide you with precise control over these calculations. # Function Signature ```python def floor(x: float) -> int: pass ```
answer:def floor(x): Returns the largest integer less than or equal to x. if x == int(x) or x > 0: return int(x) return int(x) - 1
question:Sorting a List of Custom Objects You are given a list of `Person` objects, where each object has three attributes: `first_name`, `last_name`, and `age`. Your task is to implement a function that sorts this list of `Person` instances first by `last_name` (in ascending order), then by `first_name` (in ascending order for those with the same `last_name`), and finally by `age` (in descending order for those with the same `first_name` and `last_name`). # Class Definition ```python class Person: def __init__(self, first_name: str, last_name: str, age: int): self.first_name = first_name self.last_name = last_name self.age = age def __repr__(self): return f"{self.first_name} {self.last_name} ({self.age})" ``` # Function Specification ```python def sort_people(people: list[Person]) -> list[Person]: # Implement your solution here ``` # Input * `people`: A list of `Person` objects. Each object has three attributes: `first_name` (a string), `last_name` (a string), and `age` (an integer). # Output * A sorted list of `Person` objects based on the specified criteria. # Constraints * The list will contain at least one `Person` object. * `1 <= len(people) <= 1000` * Any string attributes will have a length between 1 and 100 characters. * Age will be a non-negative integer (0 <= age <= 150). # Example ```python people = [ Person("John", "Doe", 30), Person("Jane", "Doe", 25), Person("Alice", "Smith", 25), Person("Alice", "Jones", 35), Person("Bob", "Smith", 20), Person("Alice", "Doe", 40) ] sorted_people = sort_people(people) assert sorted_people == [ Person("Alice", "Doe", 40), Person("Jane", "Doe", 25), Person("John", "Doe", 30), Person("Alice", "Jones", 35), Person("Alice", "Smith", 25), Person("Bob", "Smith", 20) ] ``` # Explanation Given a list of six `Person` objects with different `first_name`, `last_name`, and `age` attributes, the `sort_people` function returns a list of `Person` objects sorted first by `last_name`, then by `first_name`, and finally by `age` in descending order.
answer:from typing import List class Person: def __init__(self, first_name: str, last_name: str, age: int): self.first_name = first_name self.last_name = last_name self.age = age def __repr__(self): return f"{self.first_name} {self.last_name} ({self.age})" def __eq__(self, other): return (self.first_name, self.last_name, self.age) == (other.first_name, other.last_name, other.age) def sort_people(people: List[Person]) -> List[Person]: return sorted(people, key=lambda p: (p.last_name, p.first_name, -p.age))