Appearance
question:# Coding Assessment Question: Sum of Odd Fibonacci Numbers Objective Implement a function `sum_of_odd_fibonacci(upper_limit: int) -> int` that calculates the sum of all odd Fibonacci numbers less than or equal to a given upper limit. Fibonacci sequence is a series of numbers where the next number is found by adding up the two numbers before it. The sequence starts with 0 and 1. Function Signature ```python def sum_of_odd_fibonacci(upper_limit: int) -> int: ``` Input - **Single integer `upper_limit`**: The upper limit up to which odd Fibonacci numbers are to be summed (inclusive). This will always be a positive integer. Output - **Integer sum**: The sum of all odd Fibonacci numbers less than or equal to the given upper limit. Constraints - Efficiently generate Fibonacci numbers without causing performance degradation for large upper limits. - Handle large inputs efficiently to ensure the function performs well up to an upper limit of (10^{9}). - Raise a `TypeError` if `upper_limit` is not an integer. Performance Requirements - The function should be optimized for handling upper limits up to (10^{9}). Example Scenarios - `sum_of_odd_fibonacci(10)` should return `10` (since the odd Fibonacci numbers ≤ 10 are 1, 1, 3, 5) - `sum_of_odd_fibonacci(1)` should return `2` (since the odd Fibonacci numbers ≤ 1 are 1, 1) - `sum_of_odd_fibonacci(34)` should return `44` (since the odd Fibonacci numbers ≤ 34 are 1, 1, 3, 5, 13, 21) Use the following snippet to start the implementation: ```python def sum_of_odd_fibonacci(upper_limit: int) -> int: if not isinstance(upper_limit, int): raise TypeError("The upper limit must be an integer.") a, b = 0, 1 sum_odds = 0 while a <= upper_limit: if a % 2 != 0: sum_odds += a a, b = b, a + b return sum_odds ``` Through this question, the students should demonstrate: 1. Proper understanding of the Fibonacci sequence. 2. Handling edge cases, error conditions, and large inputs effectively. 3. Writing clear, efficient, and maintainable code.
answer:def sum_of_odd_fibonacci(upper_limit: int) -> int: if not isinstance(upper_limit, int): raise TypeError("The upper limit must be an integer.") a, b = 0, 1 sum_odds = 0 while a <= upper_limit: if a % 2 != 0: sum_odds += a a, b = b, a + b return sum_odds
question:# Question: Implement a Simple LRU (Least Recently Used) Cache You are required to implement a class `LRUCache` with methods to set and get values in a cache with a fixed capacity, using the LRU (Least Recently Used) replacement policy. Your implementation should reflect the requirements mentioned below: Class: `LRUCache` Methods: 1. **`__init__(self, capacity: int) -> None`**: * Input: An integer representing the capacity of the cache. * Output: None. * Example: `LRUCache(2)` should create an LRU cache with a capacity of 2. 2. **`get(self, key: int) -> int`**: * Input: An integer representing the key to retrieve. * Output: An integer representing the value associated with the key. If the key is not found, return -1. * Example: If you call `cache.get(1)` and the key `1` exists with a value of `10`, it should return `10`. If the key `1` does not exist, it should return `-1`. 3. **`set(self, key: int, value: int) -> None`**: * Input: Two integers, the key and the value to set. * Output: None. * Example: `cache.set(1, 10)` should set the value of the key `1` to `10`. Constraints: * All keys and values will be integers. * The capacity should always be a positive integer. * In case the cache reaches its capacity and you need to insert a new element, remove the least recently used element. ```python class LRUCache: def __init__(self, capacity: int) -> None: # Implement this method pass def get(self, key: int) -> int: # Implement this method pass def set(self, key: int, value: int) -> None: # Implement this method pass # Example Usage: # cache = LRUCache(2) # cache.set(1, 10) # cache.set(2, 20) # print(cache.get(1)) # Returns 10 # cache.set(3, 30) # Evicts key 2 # print(cache.get(2)) # Returns -1 (not found) # cache.set(4, 40) # Evicts key 1 # print(cache.get(1)) # Returns -1 (not found) # print(cache.get(3)) # Returns 30 # print(cache.get(4)) # Returns 40 ``` Your solution should manage the cache efficiently with both set and get operations running in O(1) time complexity.
answer:class LRUCache: def __init__(self, capacity: int) -> None: self.cache = {} self.capacity = capacity self.order = [] def get(self, key: int) -> int: if key in self.cache: self.order.remove(key) self.order.append(key) return self.cache[key] else: return -1 def set(self, key: int, value: int) -> None: if key in self.cache: self.order.remove(key) elif len(self.cache) >= self.capacity: oldest = self.order.pop(0) del self.cache[oldest] self.cache[key] = value self.order.append(key)
question:# Problem Statement Create a function `sum_missing_numbers(nums: list, n: int) -> int` that calculates the sum of all integers from 1 to `n` that are missing in the input list `nums`. Input - A list `nums` of integers (1 ≤ |nums| ≤ 10^4) representing a subset of the first `n` natural numbers. - An integer `n` (1 ≤ n ≤ 10^5) representing the upper limit of the natural number range. Output - An integer representing the sum of the missing numbers in the list. # Task Implement the function `sum_missing_numbers(nums: list, n: int) -> int` that computes the sum of all integers from 1 to `n` that are missing from the input list. Follow the example structure provided below: ```python def sum_missing_numbers(nums: list, n: int) -> int: # Your implementation here ``` Examples 1. **Input**: `sum_missing_numbers([1, 2, 4], 5)` - **Output**: `9` - **Explanation**: The numbers 3 and 5 are missing. Their sum is 3 + 5 = 8. 2. **Input**: `sum_missing_numbers([2, 3, 7, 4], 7)` - **Output**: `15` - **Explanation**: The numbers 1, 5, and 6 are missing. Their sum is 1 + 5 + 6 = 12. 3. **Input**: `sum_missing_numbers([1, 2, 3, 4, 5], 5)` - **Output**: `0` - **Explanation**: No numbers are missing; the sum is 0. 4. **Input**: `sum_missing_numbers([10, 1, 2, 5, 6], 10)` - **Output**: `38` - **Explanation**: The numbers 3, 4, 7, 8, and 9 are missing. Their sum is 3 + 4 + 7 + 8 + 9 = 31. Constraints - The input list `nums` may contain duplicates. - The input list `nums` will always contain numbers within the range 1 to `n`. - The length of the input list and the value of `n` will ensure that the sum of missing numbers can be computed efficiently. Please consider time and space optimal solutions. # Notes - You may use set operations, arithmetic progressions, or other methods as long as the final implementation adheres to the specified constraints.
answer:def sum_missing_numbers(nums: list, n: int) -> int: Computes the sum of all integers from 1 to n that are missing in the input list nums. total_sum = n * (n + 1) // 2 actual_sum = sum(set(nums)) return total_sum - actual_sum
question:**Context**: You are tasked to enhance a base `Trie` (prefix tree) structure for efficient word storage and retrieval by implementing additional methods for auto-completion and counting the number of words with a given prefix. **Objective**: Implement a class `EnhancedTrie` that inherits from `Trie` and extends its functionalities by adding the following methods: 1. `autocomplete`: Given a prefix, return all words in the trie that begin with that prefix. 2. `count_words_starting_with`: Given a prefix, return the number of words that start with that prefix. # Requirements: 1. **Class Hierarchy**: Your `EnhancedTrie` should inherit from `Trie`. 2. **Auto-completion**: Implement a method to retrieve all words that start with a given prefix. 3. **Counting Words**: Implement a method to count how many words start with a given prefix. # Define Class Structure ```python class EnhancedTrie(Trie): def __init__(self, *args, **kwargs): super().__init__(*args, **kwargs) # Define additional properties if needed def autocomplete(self, prefix: str) -> List[str]: Return a list of all words that start with the given prefix. # Implement auto-completion logic def count_words_starting_with(self, prefix: str) -> int: Return the number of words that start with the given prefix. # Implement counting logic ``` # Instructions 1. **Initialize**: On initialization, it should take the same parameters as the base class. 2. **Auto-completion Logic**: Implement `autocomplete` to traverse nodes starting from the end of the prefix, collecting all words that continue from those nodes. 3. **Counting Logic**: Implement `count_words_starting_with` to count all valid words starting from the end of the specified prefix. # Constraints * `prefix` is always a string. * Words in the trie are non-null strings consisting of lowercase alphabets. # Example ```python # Example usage trie = EnhancedTrie() trie.insert("apple") trie.insert("app") trie.insert("apricot") trie.insert("banana") print(trie.autocomplete("ap")) # Output: ['apple', 'app', 'apricot'] print(trie.count_words_starting_with("ap")) # Output: 3 print(trie.autocomplete("ban")) # Output: ['banana'] print(trie.count_words_starting_with("ban")) # Output: 1 ```
answer:class TrieNode: def __init__(self): self.children = {} self.is_end_of_word = False class Trie: def __init__(self): self.root = TrieNode() def insert(self, word): node = self.root for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] node.is_end_of_word = True def _search_node(self, prefix): node = self.root for char in prefix: if char not in node.children: return None node = node.children[char] return node class EnhancedTrie(Trie): def __init__(self): super().__init__() def autocomplete(self, prefix: str): Return a list of all words that start with the given prefix. node = self._search_node(prefix) if not node: return [] words = [] self._dfs(node, prefix, words) return words def _dfs(self, node, prefix, words): Depth-first search from the given node to collect all words. if node.is_end_of_word: words.append(prefix) for char, child_node in node.children.items(): self._dfs(child_node, prefix + char, words) def count_words_starting_with(self, prefix: str): Return the number of words that start with the given prefix. node = self._search_node(prefix) if not node: return 0 return self._count_words(node) def _count_words(self, node): Count all words from the given node. count = 1 if node.is_end_of_word else 0 for child_node in node.children.values(): count += self._count_words(child_node) return count