Appearance
question:# Question: **AVL Tree Implementation** **Objective:** Write a class to manage an AVL Tree (Adelson-Velsky and Landis Tree). The class should support the insertion of nodes, re-balancing, and in-order traversal. **Function Specifications:** 1. `__init__(self)`: Initialize an empty AVL Tree. 2. `insert(self, key: int) -> None`: Insert a new `key` into the AVL Tree while maintaining the AVL balance property. 3. `in_order_traverse(self) -> List[int]`: Perform an in-order traversal of the AVL Tree and return the keys in a sorted list. **Input:** * The `insert` method will take an integer, `key`, which is to be inserted into the AVL Tree. **Output:** * The `in_order_traverse` method should return a list of keys in the tree in sorted order. **Constraints:** * Implement the AVL tree considering it will handle integers ranging from -10^5 to +10^5. * Trees can contain a maximum of 10^4 nodes. **Example:** ```python avl = AvlTree() avl.insert(10) avl.insert(20) avl.insert(5) avl.insert(4) avl.insert(15) assert avl.in_order_traverse() == [4, 5, 10, 15, 20] ``` **Notes:** * Ensure the tree remains balanced by performing the necessary rotations during insertions. * Pay attention to the height and balance factor updates. * Avoid duplicate values in the tree by not performing any insertion if a key already exists in the tree. **What you need to do:** * Implement the AVL Tree with appropriate methods. * Test with different insertion orders to make sure the tree remains balanced and the in-order traversal produces sorted results.
answer:class TreeNode: def __init__(self, key): self.key = key self.left = None self.right = None self.height = 1 class AvlTree: def __init__(self): self.root = None def insert(self, key: int) -> None: self.root = self._insert(self.root, key) def _insert(self, node, key): if not node: return TreeNode(key) elif key < node.key: node.left = self._insert(node.left, key) elif key > node.key: node.right = self._insert(node.right, key) else: return node node.height = 1 + max(self._height(node.left), self._height(node.right)) balance = self._get_balance(node) if balance > 1 and key < node.left.key: return self._right_rotate(node) if balance < -1 and key > node.right.key: return self._left_rotate(node) if balance > 1 and key > node.left.key: node.left = self._left_rotate(node.left) return self._right_rotate(node) if balance < -1 and key < node.right.key: node.right = self._right_rotate(node.right) return self._left_rotate(node) return node def _height(self, node): if not node: return 0 return node.height def _get_balance(self, node): if not node: return 0 return self._height(node.left) - self._height(node.right) def _left_rotate(self, z): y = z.right T2 = y.left y.left = z z.right = T2 z.height = 1 + max(self._height(z.left), self._height(z.right)) y.height = 1 + max(self._height(y.left), self._height(y.right)) return y def _right_rotate(self, z): y = z.left T3 = y.right y.right = z z.left = T3 z.height = 1 + max(self._height(z.left), self._height(z.right)) y.height = 1 + max(self._height(y.left), self._height(y.right)) return y def in_order_traverse(self): res = [] self._in_order_traverse(self.root, res) return res def _in_order_traverse(self, node, res): if not node: return self._in_order_traverse(node.left, res) res.append(node.key) self._in_order_traverse(node.right, res)
question:**Shortest Path Analysis with Bellman-Ford Algorithm** Context: You are a software engineer working on a sophisticated navigation system which requires determining shortest paths on a graph representing a city road network. However, some roads have special conditions resulting in negative tolls at certain times. Problem: Implement the **Bellman-Ford algorithm** to not only find the shortest paths from a single source node to all other nodes but also to detect if any negative weight cycle exists in the graph. Function Definition: Write a function `bellman_ford(graph, source)` that: - Takes a dictionary representation of the graph where keys are node identifiers and values are dictionaries of adjacent nodes with edge weights. - Takes a string parameter `source` representing the starting node. - Returns: - A dictionary with the shortest path distances from the source to each node if no negative weight cycle is detected. - An empty dictionary if a negative weight cycle reachable from the source, making shortest path calculation infeasible. Expected Input: - `graph`: A dictionary representing a weighted, directed graph. ``` graph = { 'A': {'B': 4, 'C': 2}, 'B': {'C': 3, 'D': 2}, 'C': {'B': 1, 'D': 4, 'E': 5}, 'D': {'E': 1}, 'E': {} } ``` - `source`: A string that represents the starting node (e.g., 'A'). Expected Output: - A dictionary showing the shortest path from the source to every other node. ``` output = { 'A': 0, 'B': 3, 'C': 2, 'D': 5, 'E': 6 } ``` Constraints: - Assume valid, non-null inputs. - The graph may contain negative weights but no negative weight cycles. Performance Requirements: - Complete within a reasonable time for graphs with up to 1000 vertices and 10,000 edges. ```python def bellman_ford(graph, source): # Your implementation here # Test Case graph = { 'A': {'B': 4, 'C': 2}, 'B': {'C': 3, 'D': 2}, 'C': {'B': 1, 'D': 4, 'E': 5}, 'D': {'E': 1}, 'E': {} } source = 'A' print(bellman_ford(graph, source)) # Expected Output: {'A': 0, 'B': 3, 'C': 2, 'D': 5, 'E': 6} ```
answer:def bellman_ford(graph, source): # Step 1: Initialize distances from source to all other nodes as infinity # and distance to source itself as 0. distances = {node: float('inf') for node in graph} distances[source] = 0 # Step 2: Relax all edges |V| - 1 times. for i in range(len(graph) - 1): for node in graph: for neighbor in graph[node]: if distances[node] + graph[node][neighbor] < distances[neighbor]: distances[neighbor] = distances[node] + graph[node][neighbor] # Step 3: Check for negative-weight cycles. for node in graph: for neighbor in graph[node]: if distances[node] + graph[node][neighbor] < distances[neighbor]: return {} return distances
question:# Question: You are given an array of integers and an integer k. Your task is to rotate the array to the right by k steps efficiently. You need to implement a function that modifies the array in place without using additional space for another array. Function Signature: ```python def rotate_array(array: List[int], k: int) -> None: ``` Input - `array`: A list of n integers (1 ≤ n ≤ 10^5). - `k`: An integer representing the number of steps to rotate the array (0 ≤ k ≤ 10^9). Output - The function should not return anything. It should modify the input array in-place. Constraints - Aim to achieve an optimal time complexity of O(n) and space complexity of O(1). - Handle edge cases such as k being larger than the length of the array, or when array is empty. Example ```python # Example 1 arr = [1, 2, 3, 4, 5, 6, 7] rotate_array(arr, 3) print(arr) # Expected output: [5, 6, 7, 1, 2, 3, 4] # Example 2 arr = [-1, -100, 3, 99] rotate_array(arr, 2) print(arr) # Expected output: [3, 99, -1, -100] # Example 3 arr = [] rotate_array(arr, 1) print(arr) # Expected output: [] # Example 4 arr = [1] rotate_array(arr, 10) print(arr) # Expected output: [1] ``` Note: Use an in-place algorithm to avoid utilizing extra space. Focus on optimizing your solution for scalability and efficiency.
answer:from typing import List def rotate_array(array: List[int], k: int) -> None: Rotates the array to the right by k steps in-place. if not array: return n = len(array) k %= n # In case k is larger than array length # Function to reverse the elements of the array from start to end indices inclusive def reverse(arr: List[int], start: int, end: int): while start < end: arr[start], arr[end] = arr[end], arr[start] start += 1 end -= 1 # Reverse the whole array reverse(array, 0, n - 1) # Reverse the first k elements reverse(array, 0, k - 1) # Reverse the remaining elements reverse(array, k, n - 1)
question:# Combination Sum Problem **Objective:** Write a function `combination_sum_unique` to find all unique combinations in a given list `candidates` where the candidate numbers sum to a given target. **Function Signature:** ```python def combination_sum_unique(candidates: List[int], target: int) -> List[List[int]]: ``` **Input:** * `candidates`: A list of positive integers `[c1, c2, ... , cn]` with no duplicates. 1 <= n <= 30 * `target`: A positive integer representing the target sum. 1 <= target <= 500 **Output:** * A list of lists containing unique combinations of numbers that sum to the target. Each combination should be in a non-decreasing order. **Constraints:** * The same number may be chosen from the candidates an unlimited number of times. * The solution set must not contain duplicate combinations. * All input numbers will be positive integers. **Example:** ```python candidates = [2, 3, 6, 7] target = 7 # Expected output # [ # [7], # [2, 2, 3] # ] ``` **Performance Requirements:** - Ensure your solution efficiently handles the worst-case scenarios within reasonable time and space limits. **Scenario:** You are an event organizer planning a fundraising event where people donate money in fixed denominations. You want to know all the possible ways in which the donations could sum up to a target amount to anticipate different scenarios. Write a function to help you plan these combinations.
answer:from typing import List def combination_sum_unique(candidates: List[int], target: int) -> List[List[int]]: def backtrack(remain, combo, start): if remain == 0: ans.append(list(combo)) return elif remain < 0: return for i in range(start, len(candidates)): combo.append(candidates[i]) backtrack(remain - candidates[i], combo, i) combo.pop() candidates.sort() ans = [] backtrack(target, [], 0) return ans