Appearance
question:# Context: Imagine you are developing software for a library to manage a dynamic catalog of books. You decide to use a Binary Search Tree (BST) to store and quickly retrieve book IDs. However, before implementing the full system, you need to ensure your BST is robust and handles all typical operations effectively. # Task: You are required to implement additional functionality for the `BST` class provided in the code snippet. Specifically, implement a method to delete a node from the BST. Ensure your method maintains the BST properties after deletion. # Detailed Requirements: 1. **Function Name**: `delete(self, data)` 2. **Inputs**: * `data` (int) - The value to be deleted from the BST. 3. **Outputs**: * `True` if the value was successfully deleted. * `False` if the value was not found in the tree. 4. **Constraints**: * The tree does not contain duplicate values. * The tree can handle up to 10,000 nodes efficiently. 5. **Edge Cases to Consider**: * Deleting from an empty tree. * Deleting a leaf node, node with one child, and node with two children. * Deleting the root node. * Ensure children nodes are properly reassigned to maintain the BST properties. 6. **Performance Requirement**: The deletion operation should maintain average-case O(log N) complexity. # Testing: Extend the `TestSuite` class provided to include tests for the `delete` function. Ensure that: * You test the deletion of values that are present and not present in the tree. * After deletion, the BST properties are maintained. # Example: ```python tree = BST() tree.insert(20) tree.insert(10) tree.insert(30) tree.insert(5) tree.insert(15) assert tree.delete(20) == True # Root node assert tree.search(20) == False assert tree.delete(5) == True # Leaf node assert tree.search(5) == False assert tree.delete(15) == True # Node with one child assert tree.search(15) == False assert tree.delete(100) == False # Node not in the tree ```
answer:class TreeNode: def __init__(self, key): self.left = None self.right = None self.val = key class BST: def __init__(self): self.root = None def insert(self, key): if self.root is None: self.root = TreeNode(key) else: self._insert_recursive(self.root, key) def _insert_recursive(self, node, key): if key < node.val: if node.left is None: node.left = TreeNode(key) else: self._insert_recursive(node.left, key) else: if node.right is None: node.right = TreeNode(key) else: self._insert_recursive(node.right, key) def search(self, key): return self._search_recursive(self.root, key) def _search_recursive(self, node, key): if not node: return False if key == node.val: return True elif key < node.val: return self._search_recursive(node.left, key) else: return self._search_recursive(node.right, key) def delete(self, key): self.root, deleted = self._delete_recursive(self.root, key) return deleted def _delete_recursive(self, node, key): if not node: return node, False if key < node.val: node.left, deleted = self._delete_recursive(node.left, key) elif key > node.val: node.right, deleted = self._delete_recursive(node.right, key) else: # Node found if not node.left: return node.right, True elif not node.right: return node.left, True temp_val = self._min_value_node(node.right) node.val = temp_val.val node.right, _ = self._delete_recursive(node.right, temp_val.val) return node, True return node, deleted def _min_value_node(self, node): current = node while current.left is not None: current = current.left return current
question:# Missing Number Finder **Objective**: Implement a function to determine the missing number in a given sequence of unique integers ranging from 0 to n. Scenario You are tasked with verifying and correcting a sequence of IDs assigned from a range [0..n] that might be missing a single number. You need to ensure data integrity by identifying this missing number efficiently. Function Signature ```python def find_missing_number(nums: List[int]) -> int: ``` Input * `nums` (List[int]): A list of unique integers where each element is within the range `[0..n-1]`. The sequence may be missing one number, or it may be complete (in which case the next number, `n` should be returned). Output * `int`: The missing number in the range `[0..n]`. Constraints 1. `1 ≤ len(nums) ≤ 10^5` 2. All elements in `nums` are unique. 3. Elements ranges from `0` to `n`. Example ```python # Example 1: nums = [3, 0, 1] # Missing number is 2 # Output: 2 # Example 2: nums = [0, 1, 2, 3, 4, 6, 7, 5] # The sequence is missing number 8, hence it’s 8. # Output: 8 ``` **Note**: Ensure that your implementation handles large inputs efficiently.
answer:from typing import List def find_missing_number(nums: List[int]) -> int: Find the missing number in the sequence of unique integers ranging from 0 to n. Args: nums (List[int]): List of unique integers where each element is within the range [0..n-1]. Returns: int: The missing number in the range [0..n]. n = len(nums) expected_sum = n * (n + 1) / 2 actual_sum = sum(nums) return int(expected_sum - actual_sum)
question:# Bucket and Enhanced Sorting In this task, you'll demonstrate your understanding of an advanced sorting technique by implementing Bucket Sort with a twist. The Bucket Sort algorithm provided uses a simple insertion sort for sorting individual buckets. Your goal is to enhance this by substituting the insertion sort with a more efficient sorting algorithm of your choice (e.g., Merge Sort, Quick Sort). # Problem Statement Implement the `bucket_sort` function which sorts an array of integers using the principle of bucket sorting. Each bucket should be sorted using Merge Sort instead of Insertion Sort for better performance. # Function Signature ```python def bucket_sort(arr: List[int]) -> List[int]: ``` # Input * `arr`: A list of integers `arr` where `1 <= len(arr) <= 10000` and `-10000 <= arr[i] <= 10000`. # Output * Returns a sorted list in non-decreasing order. # Example ```python bucket_sort([29, 25, 3, 49, 9, 37, 21, 43]) # Output: [3, 9, 21, 25, 29, 37, 43, 49] ``` # Constraints * The input list can contain negative numbers. * Use merge sort to sort the elements within each bucket. # Additional Notes * Consider edge cases such as an empty array or an array with duplicate elements. * Ensure your solution efficiently handles the upper limit of the constraints.
answer:from typing import List import math def merge_sort(arr: List[int]) -> List[int]: if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) def merge(left: List[int], right: List[int]) -> List[int]: result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] < right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result def bucket_sort(arr: List[int]) -> List[int]: if not arr: return [] # Determine minimum and maximum values min_value, max_value = min(arr), max(arr) bucket_count = len(arr) # Create buckets buckets = [[] for _ in range(bucket_count)] # Map values into buckets for num in arr: index = math.floor((num - min_value) / (max_value - min_value + 1) * bucket_count) buckets[index].append(num) # Sort each bucket and concatenate results sorted_arr = [] for bucket in buckets: sorted_arr.extend(merge_sort(bucket)) return sorted_arr
question:# Modular Exponential Function with Validation In cryptography and number theory, efficient computation of large powers modulo some number is crucial. You have been tasked to improve upon and implement the given `modular_exponential` function with additional validations. # Problem Statement: Implement a function `secure_modular_exponential(base, exponent, mod)` that calculates `(base ^ exponent) % mod` efficiently, ensuring proper input validations and handling edge cases correctly. # Input: * `base` (integer): The base integer, can be negative or positive. * `exponent` (integer): The exponent integer, must be non-negative. * `mod` (integer): The modulus, must be a positive integer. # Output: * An integer representing `(base ^ exponent) % mod`. # Constraints: * `0 <= base <= 10^9` * `0 <= exponent <= 10^9` * `1 <= mod <= 10^9` # Requirements: 1. **Input Validation**: * Raise `ValueError` if `exponent` is negative. * Raise `ValueError` if `mod` is not a positive integer. 2. **Performance**: * Ensure the implementation is efficient and runs in O(log n) time where n is the exponent. # Example: ```python >>> secure_modular_exponential(2, 10, 1000) 24 >>> secure_modular_exponential(2, -10, 1000) ValueError: Exponent must be non-negative >>> secure_modular_exponential(2, 10, 0) ValueError: Modulus must be a positive integer. ``` # Function signature: ```python def secure_modular_exponential(base, exponent, mod): pass ``` # Evaluation Criteria: * Correctness of input validation. * Efficiency and accuracy of the implemented algorithm. * Handling of edge cases. * Adherence to the specified constraints and requirements.
answer:def secure_modular_exponential(base, exponent, mod): Computes (base ^ exponent) % mod efficiently with input validation. Args: base (int): The base integer. exponent (int): The exponent integer, must be non-negative. mod (int): The modulus, must be a positive integer. Returns: int: Result of (base ^ exponent) % mod. Raises: ValueError: If exponent is negative or if mod is not a positive integer. if exponent < 0: raise ValueError("Exponent must be non-negative.") if mod <= 0: raise ValueError("Modulus must be a positive integer.") result = 1 base = base % mod while exponent > 0: if exponent % 2 == 1: result = (result * base) % mod exponent = exponent >> 1 base = (base * base) % mod return result