Appearance
question:# Sum of Unique Squares Write a function that takes a list of integers as input and returns the sum of squares of the unique (non-duplicate) integers in the list. **Function Signature**: ```python def sum_of_unique_squares(numbers: list[int]) -> int: ``` **Input**: * `numbers`: A list of integers. **Output**: * Return the sum of squares of the unique integers in the list. **Constraints**: * The input list `numbers` will have at most 10^5 elements. * Each element in `numbers` will be between -10^3 to 10^3, inclusive. * The function should raise a `TypeError` if `numbers` is not a list of integers. **Examples**: * `sum_of_unique_squares([1, 2, 2, 3])` should return `1^2 + 3^2 = 1 + 9 = 10` * `sum_of_unique_squares([0, 0, -1, 1])` should return `(-1)^2 + 1^2 = 1 + 1 = 2` * `sum_of_unique_squares([1, 1, 1, 1, 1])` should return `0` (no unique elements) * `sum_of_unique_squares([-2, -1, 1, 2, -2])` should return `(-1)^2 + 1^2 + 2^2 = 1 + 1 + 4 = 6` * `sum_of_unique_squares([])` should return `0` (empty list) **Requirements**: * Ensure that the implementation efficiently handles large lists. * Handle non-integer inputs within the list by raising a `TypeError`.
answer:def sum_of_unique_squares(numbers: list[int]) -> int: Returns the sum of squares of the unique integers in the list. :param numbers: A list of integers. :return: Sum of squares of unique integers in the list. :raises TypeError: If the input is not a list of integers. if not isinstance(numbers, list): raise TypeError("Input must be a list.") for num in numbers: if not isinstance(num, int): raise TypeError("All elements in the list must be integers.") from collections import Counter counter = Counter(numbers) unique_integers = [num for num, count in counter.items() if count == 1] return sum(num ** 2 for num in unique_integers)
question:# Problem Statement # Course Schedule You are given an integer `numCourses` representing the number of courses you need to take, labeled from 0 to `numCourses - 1`. You are also given a list of `prerequisites` where prerequisites[i] = [ai, bi] indicates that you must take course `bi` before course `ai`. Determine if it is possible to finish all courses. Return `true` if you can finish all courses, or `false` otherwise. **Input:** * an integer `numCourses`: the number of courses (1 <= numCourses <= 1000). * a list of integers `prerequisites`: a list of pairs of integers where each pair represents a dependency. **Output:** * a boolean value indicating whether it is possible to complete all courses. **Example:** ```practical Input: numCourses = 4 prerequisites = [[1,0], [2,0], [3,1], [3,2]] Output: True ``` In this example, it is possible to complete all courses. One way to complete the courses is: - Take course 0. - Take course 1. - Take course 2. - Take course 3. **Example:** ```practical Input: numCourses = 2 prerequisites = [[1,0], [0,1]] Output: False ``` In this example, it is impossible to complete all courses due to the cycle in the prerequisites. # Constraints: * The list of prerequisites can be empty, meaning there are no prerequisites for any course. * There are no duplicate pairs in the list of prerequisites. # Task: 1. Implement a function `can_finish` that determines if you can finish all courses. 2. Ensure your solution follows the provided input and output formats. 3. Your function should efficiently handle the constraints provided. # Function Signature: ```python def can_finish(numCourses: int, prerequisites: List[List[int]]) -> bool: # your code here ``` **Note:** Consider edge cases, such as an empty list of prerequisites, and ensure your code handles them gracefully. Optimize your solution to manage the given input constraints effectively.
answer:from typing import List def can_finish(numCourses: int, prerequisites: List[List[int]]) -> bool: from collections import defaultdict, deque # Create adjacency list and in-degree count adj_list = defaultdict(list) indegree = [0] * numCourses # Build the graph for dest, src in prerequisites: adj_list[src].append(dest) indegree[dest] += 1 # Find all the courses with no prerequisites zero_indegree_queue = deque([i for i in range(numCourses) if indegree[i] == 0]) # Count of courses for which prerequisites are satisfied satisfied_courses = 0 # Process nodes with no prerequisites while zero_indegree_queue: course = zero_indegree_queue.popleft() satisfied_courses += 1 # Decrease the in-degree of adjacent courses by 1 for neighbor in adj_list[course]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: zero_indegree_queue.append(neighbor) # If the number of satisfied courses matches the total courses, it's possible to finish all courses return satisfied_courses == numCourses
question:Problem Statement You are given a string containing only lowercase letters and a dictionary specifying point values for each letter. Your task is to implement a function `max_points_sentence` that returns the maximum possible points for any word formed from the string. Words are defined by sequences of contiguous letters. # Function Signature ```python def max_points_sentence(s: str, points_dict: dict[str, int]) -> int: pass ``` # Input - `s`: A string consisting of only lowercase letters, with length `len(s) <= 10^5`. - `points_dict`: A dictionary where the keys are individual lowercase letters and the values are their corresponding point values. # Output - Returns an integer representing the maximum points for any word that can be formed from the string. # Constraints - Each letter in the string can appear multiple times. - Each letter in the string will always have a defined point value in `points_dict`. - Dictionary length will be exactly 26 elements (covering all lowercase letters). # Example Example 1: ```python s = "abcabc" points_dict = {'a': 1, 'b': 3, 'c': 2} max_points_sentence(s, points_dict) ``` **Output**: `6` *Explanation: The word "abcabc" gives the highest points, i.e., `1 + 3 + 2 + 1 + 3 + 2 = 12`. Example 2: ```python s = "xyz" points_dict = {'x': 5, 'y': 1, 'z': 7} max_points_sentence(s, points_dict) ``` **Output**: `13` *Explanation: The word "xyz" forms the word with the maximum points, i.e., `5 + 1 + 7 = 13`. Example 3: ```python s = "zzz" points_dict = {'z': 2, 'y': 8, 'x': 10} max_points_sentence(s, points_dict) ``` **Output**: `6` *Explanation: The word "zzz" gives the total points of `2 + 2 + 2 = 6`. # Additional Requirements - Your implementation should efficiently handle long strings. # Hints - Think about how you can traverse through the string and keep track of the maximum points using given values. - Consider using a sliding window approach or dynamic programming to calculate the maximum possible points.
answer:def max_points_sentence(s: str, points_dict: dict[str, int]) -> int: Returns the maximum possible points for any word formed from the string. max_points = 0 current_points = 0 for char in s: current_points += points_dict[char] if current_points > max_points: max_points = current_points return max_points
question:[New Question]: # Subarray with Given Sum **Context:** You are required to find a contiguous subarray in an integer list that adds up to a given sum `S`. This is a common problem in array manipulation and has many applications in data analysis. **Problem:** Write a function `find_subarray_with_sum(array: List[int], sum: int) -> Optional[Tuple[int, int]]` to identify the starting and ending indices of a contiguous subarray that sums to a given value. **Requirements:** * **Input:** - `array` (List[int]): A list of integers. - `sum` (int): The target sum to be achieved by the subarray. * **Output:** - A tuple `(start_index, end_index)` if such a subarray is found. - `None` if no such subarray exists. **Constraints:** * `array` will have a length between 1 and 1000. * Each element in `array` will be an integer between -10^6 and 10^6. * The sum will be an integer within the same range. **Example:** ```python from typing import List, Optional, Tuple def find_subarray_with_sum(array: List[int], sum: int) -> Optional[Tuple[int, int]]: # Your implementation here pass # Example test cases array = [1, 2, 3, 7, 5] sum = 12 result = find_subarray_with_sum(array, sum) print(result) # Output: (1, 3) array = [1, 2, 3, 4, 5] sum = 9 result = find_subarray_with_sum(array, sum) print(result) # Output: (1, 3) array = [1, 2, 3, 4, 5] sum = 20 result = find_subarray_with_sum(array, sum) print(result) # Output: None ``` # Notes: * Your solution should efficiently handle arrays with up to 1000 elements. * The function should return indices such that the subarray from `array[start_index]` to `array[end_index]` (inclusive) sums to the given `sum`. * If there are multiple possible answers, any correct subarray can be returned. * Utilize techniques such as the sliding window approach to achieve optimal performance. Good Luck!
answer:from typing import List, Optional, Tuple def find_subarray_with_sum(array: List[int], target_sum: int) -> Optional[Tuple[int, int]]: Finds a contiguous subarray which sums to the given target_sum. Parameters: - array: List[int], A list of integers. - target_sum: int, The target sum to be achieved by the subarray. Returns: - Tuple[int, int]: The starting and ending indices of the subarray that sums to target_sum. - None: If no such subarray is found. current_sum = 0 start_index = 0 sum_map = {} for end_index, value in enumerate(array): current_sum += value if current_sum == target_sum: return (start_index, end_index) if current_sum - target_sum in sum_map: return (sum_map[current_sum - target_sum] + 1, end_index) sum_map[current_sum] = end_index return None