Appearance
question:You are tasked with writing a function to compute the number of ways to choose `r` items from `n` items without regard to the order. Referred to as `nCr` or combinations, this is a fundamental concept in combinatorics often represented by the binomial coefficient. To evaluate your understanding, you need to write two versions of the function: 1. A recursive version without any optimization. 2. A memoized version that optimizes calculation by storing intermediate results. Function Signature ```python def combination(n: int, r: int) -> int: Calculate nCr (number of ways to choose r items from n items). Uses a straightforward recursive approach. :param n: Total number of items. :param r: Number of items to choose. :return: The number of ways to choose r items from n items. pass def combination_memo(n: int, r: int) -> int: Calculate nCr using a memoized recursive approach. :param n: Total number of items. :param r: Number of items to choose. :return: The number of ways to choose r items from n items. pass ``` # Input Constraints * 0 <= `n` <= 100 * 0 <= `r` <= `n` # Output The function should return an integer representing the number of combinations. # Examples: * `combination(5, 2) # Output: 10` * `combination_memo(5, 2) # Output: 10` * `combination(10, 0) # Output: 1` * `combination_memo(10, 10) # Output: 1` # Performance Requirements The non-memoized solution is expected to work correctly for small inputs but may not be efficient for larger inputs. The memoized version should handle the upper constraint efficiently due to reduced overlapping subproblem calculations. Scenario You are building a combinatorics calculator for a mathematical application. This function will help users calculate how many ways they can choose subsets of items from a given set. Ensure that your implementation can handle edge cases and large values within the constraints.
answer:def combination(n: int, r: int) -> int: Calculate nCr (number of ways to choose r items from n items). Uses a straightforward recursive approach. :param n: Total number of items. :param r: Number of items to choose. :return: The number of ways to choose r items from n items. # Base cases if r == 0 or r == n: return 1 # Recursive cases return combination(n-1, r-1) + combination(n-1, r) def combination_memo(n: int, r: int) -> int: Calculate nCr using a memoized recursive approach. :param n: Total number of items. :param r: Number of items to choose. :return: The number of ways to choose r items from n items. memo = [[-1 for _ in range(r+1)] for _ in range(n+1)] def helper(n, r): # Base cases if r == 0 or r == n: return 1 # Check memo if memo[n][r] != -1: return memo[n][r] # Calculate and store in memo memo[n][r] = helper(n-1, r-1) + helper(n-1, r) return memo[n][r] return helper(n, r)
question:Given the following scenario, design and implement a class that calculates the moving average of a stream of integers with a fixed-size sliding window. Scenario You are tasked with developing a software system that monitors real-time sensor data in an industrial setting. Sensors provide readings at regular intervals, and you need to process these readings to calculate the moving average over a fixed window size. This average helps in signal smoothing and provides insights into recent trends. Requirements * Implement a class named `SensorMovingAverage` with the following methods: * `__init__(self, size: int)`: Initializes the class with a specified window size. * `add_reading(self, val: int) -> float`: Adds a sensor reading and returns the current moving average of the readings in the sliding window. Input and Output Formats * **Input**: * The `__init__` method will be called with an integer `size` representing the window size. * The `add_reading` method will be called repeatedly with integer readings from the sensor. * **Output**: * The `add_reading` method should return a floating-point number representing the current moving average of the values in the sliding window. Constraints * The input integer `size` will be at least 1. * The stream of integers provided to `add_reading` can be positive, negative, or zero. * Your implementation should ensure O(1) time complexity for adding a new reading and calculating the moving average. Example ```python # Initialize the moving average with a window size of 3 sma = SensorMovingAverage(3) # Add sensor readings and get the moving average print(sma.add_reading(1)) # Output: 1.0 print(sma.add_reading(10)) # Output: 5.5 print(sma.add_reading(3)) # Output: 4.6666... print(sma.add_reading(5)) # Output: 6.0 ``` Implement the `SensorMovingAverage` class below.
answer:from collections import deque class SensorMovingAverage: def __init__(self, size: int): self.size = size self.window = deque() self.sum = 0 def add_reading(self, val: int) -> float: if len(self.window) == self.size: self.sum -= self.window.popleft() self.window.append(val) self.sum += val return self.sum / len(self.window)
question:You are provided with a simplified nearest neighbor algorithm that finds the vector in a training set closest to a given input vector. The specific task is to extend the functionality of this basic implementation to handle a k-nearest neighbors (k-NN) algorithm, taking the k nearest neighbors into account and returning the most frequent class among them. # Task Implement a function `k_nearest_neighbors(x, tSet, k)` which extends the nearest neighbor approach to the k-nearest neighbors algorithm. - `x` is a tuple representing the input vector. - `tSet` is a dictionary where keys are tuples representing vectors and values are the respective class labels. - `k` is an integer denoting the number of nearest neighbors to consider. # Requirements 1. The function should use the Euclidean distance for measuring distance between vectors. 2. The function should handle edge cases, such as vectors of different lengths and empty training sets. 3. Ensure that ties in the most frequent class calculation (when two or more classes have the same frequency) are broken arbitrarily but consistently. # Expected Function Signature ```python def k_nearest_neighbors(x: tuple, tSet: dict, k: int) -> Any: pass ``` # Example ```python training_set = { (1, 2): 'ClassA', (3, 4): 'ClassB', (1, 1): 'ClassA', (2, 2): 'ClassC', (6, 6): 'ClassB' } x = (1, 3) k = 3 # Expected output could be 'ClassA', as it is the most frequent class among the 3 nearest vectors. print(k_nearest_neighbors(x, training_set, k)) ``` # Constraints * Vectors in the training set and the input vector are non-empty and of the same length up to 1000 dimensions. * The training set contains up to 100,000 vectors. * `k` is a positive integer not greater than the number of vectors in the training set. # Notes - Performance is key for larger values of `k` and larger datasets. Aim to write efficient and readable code. - You need to import any necessary modules and handle any possible edge cases in your implementation.
answer:import math from collections import Counter from typing import Any, Dict, Tuple def euclidean_distance(v1: Tuple[float], v2: Tuple[float]) -> float: Calculate the Euclidean distance between two vectors. return math.sqrt(sum((a - b) ** 2 for a, b in zip(v1, v2))) def k_nearest_neighbors(x: Tuple[float], tSet: Dict[Tuple[float], Any], k: int) -> Any: k-NN algorithm to classify the input vector x based on the k nearest neighbors in the training set tSet. # Handle edge cases if not tSet or k <= 0: raise ValueError("Training set cannot be empty and k must be positive.") if any(len(x) != len(vector) for vector in tSet.keys()): raise ValueError("All vectors must have the same length.") # Calculate distances from x to all vectors in the training set distances = [(euclidean_distance(x, vector), label) for vector, label in tSet.items()] # Sort by distance and select the k closest neighbors nearest = sorted(distances, key=lambda pair: pair[0])[:k] # Get the most frequent class among the k nearest neighbors counter = Counter(label for _, label in nearest) most_common = counter.most_common(1) return most_common[0][0]
question:Problem Description You are given an array of integers and a target integer value. Your task is to implement a function that searches for the target value in the array and returns its index if found. If the target value is not in the array, the function should return -1. Implement the search using the linear search algorithm described below. Function Signature ```python def linear_search(array: list[int], query: int) -> int: pass ``` Input * `array`: A list of integers. The array can be empty or contain up to 10^6 integers. * `query`: An integer, the target value to search for in the array. Output * An integer, the index of the target value in the array. If the target is not found, return -1. Constraints 1. The array can have duplicate values, but the function should return the index of the first occurrence of the target value. 2. Implement the solution using the linear search algorithm. 3. Do not use any built-in functions or methods that directly perform search operations. Examples ```python # Example 1 array = [10, 23, 45, 9, 33] query = 23 print(linear_search(array, query)) # Output: 1 # Example 2 array = [1, 2, 3, 4, 5, 6, 7] query = 5 print(linear_search(array, query)) # Output: 4 # Example 3 array = [8, 6, 7, 5, 3, 0, 9] query = 10 print(linear_search(array, query)) # Output: -1 ``` Edge Cases to Consider 1. The array is empty. 2. The target element is at the first or the last position of the array. 3. The array contains multiple instances of the target element.
answer:def linear_search(array: list[int], query: int) -> int: Perform a linear search to find the index of the query in the array. Return the index of the first occurrence of the query, or -1 if not found. for index, value in enumerate(array): if value == query: return index return -1