Appearance
question:# Maze Pathfinding You are tasked with navigating a maze represented by a 2D grid to reach a designated destination from a starting point. The grid cells may contain blocks, restricting movement, and movement is only allowed vertically or horizontally. Your objective is to find the shortest path from the start to the destination. **Function Signature**: ```python def shortest_path(grid: list, start: tuple, end: tuple) -> int: pass ``` **Expected Input and Output**: * **Input**: * `grid` - A 2D list of integers, where 0 represents an empty cell and 1 represents a block. * `start` - A tuple of two integers representing the starting cell's coordinates (row, column). * `end` - A tuple of two integers representing the destination cell's coordinates (row, column). * **Output**: * Return an integer representing the length of the shortest path from `start` to `end`. If no path is found, return -1. **Constraints**: * The grid will have at least one row and one column and at most 500 rows and 500 columns. * The grid contains only 0s and 1s. * The start and end points will always be valid and non-blocked cells. * The start and end points can be the same. **Example**: ```python >>> shortest_path([[0, 0, 1, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 1, 0], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0]], (0, 0), (4, 4)) 8 >>> shortest_path([[0, 1], [1, 0]], (0, 0), (1, 1)) -1 ``` **Instructions**: 1. Validate the input data to ensure the dimensions of the grid are non-empty and contain only 0s and 1s. 2. Use a breadth-first search (BFS) algorithm to find the shortest path from the start cell to the end cell. 3. Keep track of visited cells to avoid cycles. 4. If the destination is not reachable, return -1. 5. Implement edge case handling such as the grid being completely blocked or no possible path. **Note**: The solution must be efficient to handle the maximum constraints.
answer:from collections import deque def shortest_path(grid, start, end): # Check if the start and end points are the same if start == end: return 0 # Directions array for moving in 4 possible directions directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # Get the dimensions of the grid rows, cols = len(grid), len(grid[0]) # BFS initialization queue = deque([(start[0], start[1], 0)]) # (row, col, distance) visited = set() visited.add((start[0], start[1])) while queue: current_row, current_col, dist = queue.popleft() # Explore all possible 4 directions for dr, dc in directions: new_row, new_col = current_row + dr, current_col + dc if 0 <= new_row < rows and 0 <= new_col < cols and (new_row, new_col) not in visited and grid[new_row][new_col] == 0: if (new_row, new_col) == end: return dist + 1 queue.append((new_row, new_col, dist + 1)) visited.add((new_row, new_col)) return -1
question:# Problem Statement You need to implement a text editor feature that finds and replaces all occurrences of a word in a given text. This involves searching the target word, replacing it with the provided replacement, and ensuring that the function operates efficiently even for large volumes of text. # Function Signatures - Implement the function `find_and_replace(text: str, target: str, replacement: str) -> str`. This function will: - Take three strings: `text`, `target`, and `replacement`. - Return a new string where all occurrences of `target` in `text` are replaced with `replacement`. ```python def find_and_replace(text: str, target: str, replacement: str) -> str: pass ``` # Input and Output Input 1. `text` (str): The original text. Constraints: `1 ≤ len(text) ≤ 5000`. 2. `target` (str): The word to search for in the text. Constraints: `1 ≤ len(target) ≤ 100`. 3. `replacement` (str): The word to replace the target with. Constraints: `0 ≤ len(replacement) ≤ 100`. Output 1. Returns a new string where every occurrence of `target` in `text` has been replaced with `replacement`. # Example 1. `find_and_replace("hello world, hello universe", "hello", "hi")` - Returns: `"hi world, hi universe"` 2. `find_and_replace("abc abc abc", "abc", "xyz")` - Returns: `"xyz xyz xyz"` 3. `find_and_replace("hello", "world", "hi")` - Returns: `"hello"` 4. `find_and_replace("hello world", "world", "")` - Returns: `"hello "` # Constraints - You must handle edge cases where `target` is not found in `text`. - Ensure the function efficiently processes the text, even if the `target` and `replacement` strings significantly differ in length. - Handle cases where `replacement` is an empty string appropriately. # Notes - Utilize built-in string functions for efficient manipulation. - Consider special cases such as overlapping targets or targets at the boundaries of the text.
answer:def find_and_replace(text: str, target: str, replacement: str) -> str: Replaces all occurrences of target with replacement in the given text. if target == "": # If target is empty string, replacing it would cause infinite loop raise ValueError("Target string must not be empty") return text.replace(target, replacement)
question:# Scenario You need to implement a cache system for frequently accessed data in a web application. The cache should follow the Least Recently Used (LRU) eviction policy to ensure that the most frequently accessed items are quickly available, while less frequently accessed items are evicted when the cache size limit is reached. # Task Write a Python class `LRUCache` that implements an LRU cache using a combination of a doubly-linked list and a hash map. # Class Structure ```python class LRUCache: def __init__(self, capacity: int) -> None: Initialize the LRUCache with a given capacity. pass def get(self, key: int) -> int: Return the value of the key if it exists, otherwise return -1. pass def put(self, key: int, value: int) -> None: Insert a key-value pair into the cache. If the cache exceeds its capacity, evict the least recently used item. pass ``` # Constraints and Requirements * The cache should operate in O(1) time complexity for both `get` and `put` operations. * Expected input format: * `capacity` is an integer representing the maximum size of the cache. * `key` is an integer representing the key to be accessed/inserted. * `value` is an integer representing the value associated with the key. * Expected output: * For the `get` method, an integer representing the value associated with the key if it exists, otherwise -1. * The `put` method does not return anything. # Example ```python # Example usage cache = LRUCache(2) cache.put(1, 1) cache.put(2, 2) print(cache.get(1)) # Expected Output: 1 cache.put(3, 3) # Evicts key 2 print(cache.get(2)) # Expected Output: -1 cache.put(4, 4) # Evicts key 1 print(cache.get(1)) # Expected Output: -1 print(cache.get(3)) # Expected Output: 3 print(cache.get(4)) # Expected Output: 4 ``` # Important Note Ensure that the doubly-linked list and hash map are correctly synchronized to maintain the LRU order and handle edge cases such as cache underflow and overflow.
answer:class Node: def __init__(self, key: int = 0, value: int = 0): self.key = key self.value = value self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int) -> None: self.capacity = capacity self.cache = {} self.head = Node() self.tail = Node() self.head.next = self.tail self.tail.prev = self.head def _remove(self, node: Node) -> None: prev = node.prev next = node.next prev.next = next next.prev = prev def _add(self, node: Node) -> None: node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def get(self, key: int) -> int: if key in self.cache: node = self.cache[key] self._remove(node) self._add(node) return node.value return -1 def put(self, key: int, value: int) -> None: if key in self.cache: self._remove(self.cache[key]) node = Node(key, value) self._add(node) self.cache[key] = node if len(self.cache) > self.capacity: lru = self.tail.prev self._remove(lru) del self.cache[lru.key]
question:# Coding Assessment: Optimize Recursive Fibonacci Function Context The Fibonacci sequence is used in various algorithmic problems and optimization tasks. A common implementation of the Fibonacci sequence uses recursion, which can be inefficient for larger input values due to repeated calculations. Your task is to optimize the recursive Fibonacci function to improve its efficiency. Problem Statement Optimize the function `fib_recursive` to memoize previously computed values, thus reducing redundant calculations and improving performance. Function to Be Optimized ```python def fib_recursive(n: int) -> int: Calculate the nth Fibonacci number recursively. The Fibonacci sequence is defined as: F(0) = 0, F(1) = 1 F(n) = F(n-1) + F(n-2) for n >= 2 >>> fib_recursive(0) 0 >>> fib_recursive(1) 1 >>> fib_recursive(10) 55 if n <= 0: return 0 elif n == 1: return 1 else: return fib_recursive(n - 1) + fib_recursive(n - 2) ``` Requirements 1. **Optimization**: - Implement caching to store already computed values. - Use a suitable Python feature for memoization. 2. **Input Validation**: - Ensure the input `n` is a non-negative integer. - Raise a `ValueError` with an appropriate message for invalid inputs. Input/Output Format * **Input**: - `n`: An integer representing the position in the Fibonacci sequence (must be a non-negative integer). * **Output**: - An integer value representing the nth Fibonacci number. Constraints 1. The input value `n` must be a non-negative integer. Example ```python try: print(fib_recursive(10)) # Outputs: 55 print(fib_recursive(20)) # Outputs: 6765 print(fib_recursive(-5)) # Raises ValueError except ValueError as ve: print(f"ValueError: {ve}") ``` Optimized Function Template ```python from functools import lru_cache @lru_cache(None) def fib_recursive(n: int) -> int: Calculate the nth Fibonacci number recursively with memoization. The Fibonacci sequence is defined as: F(0) = 0, F(1) = 1 F(n) = F(n-1) + F(n-2) for n >= 2 >>> fib_recursive(0) 0 >>> fib_recursive(1) 1 >>> fib_recursive(10) 55 if n < 0: raise ValueError("Input must be a non-negative integer.") elif n == 0: return 0 elif n == 1: return 1 else: return fib_recursive(n - 1) + fib_recursive(n - 2) ```
answer:from functools import lru_cache @lru_cache(None) def fib_recursive(n: int) -> int: Calculate the nth Fibonacci number recursively with memoization. The Fibonacci sequence is defined as: F(0) = 0, F(1) = 1 F(n) = F(n-1) + F(n-2) for n >= 2 if not isinstance(n, int) or n < 0: raise ValueError("Input must be a non-negative integer.") elif n == 0: return 0 elif n == 1: return 1 else: return fib_recursive(n - 1) + fib_recursive(n - 2)