Appearance
question:# Question: Prime Number Generator with Caching You need to implement a class `PrimeGenerator` that generates prime numbers and caches the results to optimize further requests for prime numbers up to a specified limit. Your class should include a method `get_primes_up_to(self, n: int) -> List[int]` to return a list of all prime numbers up to `n`. # Constraints - The `n` parameter will be a positive integer. - The method should cache results to avoid redundant calculations for the same or smaller values of `n`. - If `n` is less than 2, the method should return an empty list. - Your class and method should handle standard inputs efficiently. # Input - `n: int` - The upper limit for prime number generation, where `n` can be up to 10^6. # Output - A list of integers representing the prime numbers up to `n`. # Examples Example 1 ```python prime_gen = PrimeGenerator() output = prime_gen.get_primes_up_to(10) # output should be [2, 3, 5, 7] ``` Example 2 ```python prime_gen = PrimeGenerator() output = prime_gen.get_primes_up_to(20) # output should be [2, 3, 5, 7, 11, 13, 17, 19] ``` Example 3 ```python prime_gen = PrimeGenerator() output = prime_gen.get_primes_up_to(1) # output should be [] ``` # Additional Notes - Use the Sieve of Eratosthenes algorithm or another efficient algorithm for prime number generation. - Ensure your class can handle multiple calls and utilizes caching effectively to optimize for repeated requests. - The solution should have a time complexity of O(n log log n) for prime number generation and constant time for caching checks. Implement the class `PrimeGenerator` with the method `get_primes_up_to(self, n: int) -> List[int]`, ensuring it adheres to all the given requirements and constraints.
answer:from typing import List class PrimeGenerator: def __init__(self): self.cached_primes = [] self.highest_calculated = 1 def _sieve_of_eratosthenes(self, limit: int) -> List[int]: is_prime = [True] * (limit + 1) p = 2 while (p * p <= limit): if (is_prime[p] == True): for i in range(p * p, limit + 1, p): is_prime[i] = False p += 1 primes = [p for p in range(2, limit + 1) if is_prime[p]] return primes def get_primes_up_to(self, n: int) -> List[int]: if n < 2: return [] if n <= self.highest_calculated: return [p for p in self.cached_primes if p <= n] new_primes = self._sieve_of_eratosthenes(n) self.cached_primes = new_primes self.highest_calculated = n return new_primes
question:Problem Statement: You are given a string representing a mathematical expression containing non-negative integers and the operators: `+`, `-`, `*`, and `/`. The task is to evaluate this expression and return the result as an integer. Note that the expressions are valid and properly formatted without any spaces. **Function Signature**: ```python def evaluate_expression(expression: str) -> int: ``` **Inputs**: - `expression`: A string representing a valid mathematical expression. The string length is between 1 and 10^5. **Outputs**: - Return an integer representing the result of the evaluated expression. **Constraints**: - The expression contains only non-negative integers and the operators `+`, `-`, `*`, and `/`. - Division should truncate towards zero. - The input string is guaranteed to be a valid expression. **Scenario**: Imagine you are developing a software for a financial calculator. The calculator needs to parse and evaluate arithmetic expressions entered by the user. Your task is to implement the functionality to correctly compute these expressions. **Examples**: ```python >>> evaluate_expression("3+2*2") 7 >>> evaluate_expression(" 3/2 ") 1 >>> evaluate_expression("3+5 / 2 ") 5 >>> evaluate_expression("10+2*6") 22 >>> evaluate_expression("100*2+12") 212 >>> evaluate_expression("14+2*3-6/2") 17 ``` **Requirements**: - Ensure that the division truncates towards zero. - The expression may not contain any spaces, and it's guaranteed to be valid. - Handle large expressions efficiently. --- This question aligns with the original set in terms of complexity and focus on efficient algorithm design and space optimization. It also ensures a similar level of difficulty, requiring understanding and implementation of arithmetic operations and expression evaluation while adding a unique challenge of parsing and computing with different operators.
answer:def evaluate_expression(expression: str) -> int: def apply_operator(operands, operator): b = operands.pop() a = operands.pop() if operator == '+': operands.append(a + b) elif operator == '-': operands.append(a - b) elif operator == '*': operands.append(a * b) elif operator == '/': operands.append(int(a / b)) # Ensure truncation towards zero # Initialize stacks for operands and operators operands = [] operators = [] current_number = 0 has_number = False for i, ch in enumerate(expression): if ch.isdigit(): current_number = current_number * 10 + int(ch) has_number = True elif ch in '+-*/': if has_number: operands.append(current_number) current_number = 0 has_number = False while operators and precedence(operators[-1]) >= precedence(ch): apply_operator(operands, operators.pop()) operators.append(ch) if has_number: operands.append(current_number) while operators: apply_operator(operands, operators.pop()) return operands[0] def precedence(op): if op in '+-': return 1 if op in '*/': return 2 return 0
question:Data Normalization **Context**: You are given a dataset represented as a 2D numpy array where each row is a sample and each column is a feature. Your task is to normalize this dataset feature-wise using z-score normalization. The z-score of each feature is computed by subtracting the mean of the feature and then dividing by the standard deviation of the same feature. Function Signature: ```python def normalize_dataset(dataset: np.ndarray) -> np.ndarray: ``` Parameters: - `dataset`: a 2D numpy array where each element represents a sample's feature value in the dataset. Output: - Return a 2D numpy array of the same shape as `dataset`, where each element is the z-score normalized value of the corresponding feature in the input dataset. Constraints: * The input dataset will only contain numerical values. * The dataset will have dimensions up to 10,000 x 1,000 (10,000 samples and 1,000 features). * Efficiently handle datasets with large dimensions and closely clustered numerical values. * Avoid using any third-party libraries for normalization other than numpy. Instructions: 1. Calculate the mean and standard deviation of each feature (column). 2. Implement a function `compute_z_score(value, mean, std_dev)` that computes the z-score using the given mean and standard deviation. 3. Use these mean and standard deviation values to normalize the dataset feature-wise. 4. Ensure your implementation correctly handles the case where the standard deviation is zero by returning a z-score of zero for such features. Example: ```python import numpy as np dataset = np.array([ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]) output = normalize_dataset(dataset) print(output) ``` Expected Output: ``` [[-1.22474487 -1.22474487 -1.22474487] [ 0. 0. 0. ] [ 1.22474487 1.22474487 1.22474487]] ``` Note: This problem is designed to assess your understanding of statistical data normalization techniques and your ability to implement algorithms that process substantial datasets efficiently.
answer:import numpy as np def normalize_dataset(dataset: np.ndarray) -> np.ndarray: Normalizes the dataset using z-score normalization. Parameters: dataset (np.ndarray): A 2D numpy array where each element represents a sample's feature value. Returns: np.ndarray: A 2D numpy array of the same shape as `dataset`, with z-score normalized values. mean = np.mean(dataset, axis=0) std_dev = np.std(dataset, axis=0) # Avoid division by zero: set std_dev to 1 where std_dev is zero std_dev[std_dev == 0] = 1 z_score_normalized_dataset = (dataset - mean) / std_dev return z_score_normalized_dataset
question:# **Coding Challenge: Optimal Water Distribution Network** In a city with an irregular network of water pipes, the city planners aim to make the skyline look aesthetically pleasing by ensuring that there are no intersecting pipelines while providing water to all the city locations. The challenge is to form a Minimum Spanning Tree (MST) of the connected locations, ensuring that the total pipeline length is minimized. **Problem Statement**: You need to write a function `minimum_pipeline_length(n: int, connections: List[Tuple[int, int, int]]) -> int` that takes the number of city locations and a list of tuples representing the connections. Each tuple contains three values: two integers representing the connected locations, and the third integer representing the length of the pipeline between these locations. The function should return the minimum total length of pipeline needed to ensure every city location has water. If it's not possible to connect all locations, the function should return -1. # **Hint** Use algorithms like Kruskal's or Prim's to find the Minimum Spanning Tree (MST). # **Input Format** * An integer `n` which represents the number of city locations. * A list of tuples `connections` where each tuple `(u, v, w)` represents an existing pipeline of length `w` between locations `u` and `v`. # **Output Format** * Returns the minimum total pipeline length (integer) required to connect all locations, or -1 if connection is not possible. # **Constraints** * 1 <= n <= 1000 * 1 <= len(connections) <= 100000 * 1 <= w <= 10^6 # **Example** * For n = 4, connections = [(1, 2, 1), (2, 3, 4), (3, 4, 3), (1, 4, 2), (1, 3, 5)]: ```python print(minimum_pipeline_length(4, [(1, 2, 1), (2, 3, 4), (3, 4, 3), (1, 4, 2), (1, 3, 5)])) # Output: 6 ``` # **Explanation** - The Minimum Spanning Tree for the given connections is: [(1, 2, 1), (1, 4, 2), (3, 4, 3)] - The total length of the MST is 1 + 2 + 3 = 6.
answer:def minimum_pipeline_length(n, connections): Returns the minimum total pipeline length using Kruskal's algorithm. If it's not possible to connect all locations, returns -1. # Function to find the parent of a node def find(parent, i): if parent[i] == i: return i return find(parent, parent[i]) # Function to union two subsets def union(parent, rank, x, y): root_x = find(parent, x) root_y = find(parent, y) if root_x != root_y: if rank[root_x] < rank[root_y]: parent[root_x] = root_y elif rank[root_x] > rank[root_y]: parent[root_y] = root_x else: parent[root_y] = root_x rank[root_x] += 1 # Kruskal's algorithm to find the MST connections.sort(key=lambda x: x[2]) parent = [] rank = [] mst_weight = 0 for node in range(n + 1): parent.append(node) rank.append(0) edges_in_mst = 0 for u, v, w in connections: root_u = find(parent, u) root_v = find(parent, v) if root_u != root_v: union(parent, rank, root_u, root_v) mst_weight += w edges_in_mst += 1 if edges_in_mst == n - 1: break if edges_in_mst != n - 1: return -1 return mst_weight