Appearance
question:# Question: Validate Word Pattern Mapping Given a pattern string and a sentence string, your task is to implement the function `is_bijective_pattern(pattern: str, sentence: str) -> bool` that verifies if the sentence follows the same pattern as defined by the pattern string. A sentence follows the pattern if there is a one-to-one and onto mapping (bijection) between each letter in the pattern and each word in the sentence. Input - `pattern` (string): A string of lowercase letters where each character represents a unique element in the bijection. - `sentence` (string): A string of lowercase words separated by single spaces. Output - Return `True` if the sentence follows the pattern by the given rules. - Return `False` otherwise. Constraints - The `pattern` string will only contain lowercase English letters. - The `sentence` string will only contain lowercase English words separated by single spaces. Examples 1. `is_bijective_pattern("abba", "dog cat cat dog")` should return `True`. 2. `is_bijective_pattern("abba", "dog cat cat fish")` should return `False`. 3. `is_bijective_pattern("aaaa", "dog cat cat dog")` should return `False`. 4. `is_bijective_pattern("abba", "dog dog dog dog")` should return `False`. Notes - You can assume that the `pattern` and `sentence` inputs are always non-empty and contain no leading or trailing spaces. - Use appropriate data structures to maintain mappings and ensure one-to-one correspondence. Function Definition ```python def is_bijective_pattern(pattern: str, sentence: str) -> bool: pass ```
answer:def is_bijective_pattern(pattern: str, sentence: str) -> bool: words = sentence.split() if len(pattern) != len(words): return False char_to_word = {} word_to_char = {} for char, word in zip(pattern, words): if char in char_to_word: if char_to_word[char] != word: return False else: char_to_word[char] = word if word in word_to_char: if word_to_char[word] != char: return False else: word_to_char[word] = char return True
question:Context Given a directed graph, you need to identify all the strongly connected components (SCCs). Each SCC is a maximal subgraph where every vertex is reachable from every other vertex in the same SCC. Task Write a function `find_strongly_connected_components(V, edges)` that takes: - `V` (an integer representing the number of vertices), - `edges` (a list of tuples representing the directed edges in the graph). The function should return a list of lists, where each inner list represents a strongly connected component containing vertex indices. Function Signature ```python def find_strongly_connected_components(V: int, edges: List[Tuple[int, int]]) -> List[List[int]]: ``` Input - `V` (1 ≤ V ≤ (10^4)): The number of vertices. - `edges` (0 ≤ len(edges) ≤ (10^5)): A list of tuples where each tuple (u, v) indicates a directed edge from vertex ( u ) to vertex ( v ) (0 ≤ u, v < V). Output - A list of lists, where each list contains the vertices in one strongly connected component. Example ```python V = 6 edges = [(0, 2), (1, 0), (2, 3), (3, 1), (3, 4), (4, 5), (5, 4)] # Sample Output # [ # [1, 3, 2, 0], # [5, 4] # ] print(find_strongly_connected_components(V, edges)) ``` Constraints - You may assume the graph does not contain self-loops. - Ensure your algorithm runs in linear time complexity relative to the number of vertices and edges. Notes - The order of vertices within each SCC or the order of SCCs in the output list does not matter. - Think carefully about edge cases like completely disconnected vertices or graphs with no edges.
answer:from typing import List, Tuple def find_strongly_connected_components(V: int, edges: List[Tuple[int, int]]) -> List[List[int]]: index = [0] # single mutable integer to keep track of the index stack = [] indices = [-1] * V lowlink = [-1] * V on_stack = [False] * V sccs = [] def strongconnect(v): indices[v] = index[0] lowlink[v] = index[0] index[0] += 1 stack.append(v) on_stack[v] = True for (u, w) in edges: if u == v: if indices[w] == -1: strongconnect(w) lowlink[v] = min(lowlink[v], lowlink[w]) elif on_stack[w]: lowlink[v] = min(lowlink[v], indices[w]) if lowlink[v] == indices[v]: scc = [] while True: w = stack.pop() on_stack[w] = False scc.append(w) if w == v: break sccs.append(scc) for v in range(V): if indices[v] == -1: strongconnect(v) return sccs
question:# Question: Implement a Weighted Moving Average Calculator **Scenario**: You are working on a project for a financial analytics firm. One of the tasks is to implement a weighted moving average calculator that gives more importance to recent data points compared to older ones in a sliding window. **Task**: Write a Python class `WeightedMovingAverage` that calculates the weighted moving average of a stream of integers. Each integer has a corresponding weight, and the most recent integer should have the highest weight. **Class Definition**: 1. **Initialization**: The class should be initialized with `size` which defines the maximum number of recent values to consider. 2. **Method**: - `next(val, weight)`: Adds the new value and its weight to the data structure and returns the weighted moving average. **Input and Output Specifications**: * `size` (in the constructor) - an integer defining the window size. * `next(val, weight)` - a method where: - `val` is an integer. - `weight` is a float representing the weight of the new value. - Returns a float which is the weighted moving average of the current window. **Constraints**: * 1 <= `size` <= 1000 * -10^5 <= `val` <= 10^5 * 0 <= `weight` <= 1 **Example**: ```python wma = WeightedMovingAverage(3) assert wma.next(1, 0.1) == 1.0 assert wma.next(10, 0.5) == (1*0.1 + 10*0.5) / (0.1 + 0.5) assert wma.next(3, 0.3) == (1*0.1 + 10*0.5 + 3*0.3) / (0.1 + 0.5 + 0.3) assert wma.next(5, 0.8) == (10*0.5 + 3*0.3 + 5*0.8) / (0.5 + 0.3 + 0.8) ``` **Note**: * Consider implementing the class using optimized data structures to maintain efficient performance. * Ensure the weights are stored and utilized correctly to maintain the order and calculation relevancy.
answer:from collections import deque class WeightedMovingAverage: def __init__(self, size): self.size = size self.queue = deque() self.total_value = 0.0 self.total_weight = 0.0 def next(self, val, weight): # Adding the new value and weight self.queue.append((val, weight)) self.total_value += val * weight self.total_weight += weight # If the size exceeds the limit, remove the oldest value if len(self.queue) > self.size: old_val, old_weight = self.queue.popleft() self.total_value -= old_val * old_weight self.total_weight -= old_weight # Return the current weighted moving average if self.total_weight == 0: return 0 return self.total_value / self.total_weight
question:# Task Write a function `reverse_words_advanced` that reverses the order of words in a given sentence, taking into account multiple consecutive whitespaces and punctuation marks. # Detailed Specifications: 1. **Input**: A single string `sentence` which may contain leading, trailing, or multiple consecutive whitespaces. It may also include punctuation marks which should stay attached to their respective words. 2. **Output**: A string with words in reversed order, maintaining original punctuation and whitespaces. # Constraints: - Do not use additional libraries or built-in methods specifically for reversing strings or words (except for basic string operations like splitting and joining). - The function should handle up to 1000 words efficiently. # Function Signature: ```python def reverse_words_advanced(sentence: str) -> str: pass ``` # Example: ```python sentence = " Hello, world! This is a test. " # expected output: " test. a is This world! Hello, " print(reverse_words_advanced(sentence)) ``` # Hints: - Consider using a more sophisticated splitting that takes consecutive whitespaces into account. - Maintain punctuation marks attached to words during splitting. - Ensure that whitespaces between words are kept as in the original while reversing the words.
answer:def reverse_words_advanced(sentence: str) -> str: Reverses the order of words in a sentence, handling multiple whitespaces and punctuation. # Split the sentence into words and intermediate whitespaces/punctuation segments = [] word = '' whitespace = '' for char in sentence: if char.isspace(): if word: segments.append(word) word = '' whitespace += char else: if whitespace: segments.append(whitespace) whitespace = '' word += char if word: segments.append(word) if whitespace: segments.append(whitespace) # Reverse the segments list and join it back into a string reversed_sentence = ''.join(segments[::-1]) return reversed_sentence