Appearance
question:# Question: Detect Cycles in a Directed Graph **Context**: In graph theory, a cycle is a path of edges and vertices wherein a vertex is reachable from itself. In many practical applications, it is important to detect cycles to prevent infinite loops, identify dependencies, or understand the structure of the graph. **Problem Statement**: Write a Python function `detect_cycle(graph: Dict[int, List[int]]) -> bool` that determines whether a directed graph contains a cycle. **Input Format**: - A directed graph represented as an adjacency list using a dictionary. The keys are integers representing nodes, and the values are lists of integers representing the nodes that each key node has directed edges to. **Output Format**: - Return `True` if the graph contains a cycle. - Return `False` otherwise. **Constraints**: - The graph will be non-empty and can consist of any number of nodes. - You can assume that node values are non-negative integers. - The graph may be disconnected, meaning there can be nodes that do not have any incoming or outgoing edges. **Performance Requirements**: - The solution should have O(V + E) time complexity, where V is the number of vertices and E is the number of edges in the graph. - Utilize O(V) space complexity due to the storage of visited and recursion stack data structures. # Function Signature ```python def detect_cycle(graph: Dict[int, List[int]]) -> bool: pass ``` # Example Consider the following directed graph: - Input: `{0: [1], 1: [2], 2: [0], 3: [4], 4: []}` - Output: `True` because the graph contains a cycle (0 -> 1 -> 2 -> 0). Additional Example: - Input: `{0: [1], 1: [2], 2: [], 3: [4], 4: []}` - Output: `False` because the graph does not contain any cycles. Use these definitions to implement the function and validate its correctness.
answer:def detect_cycle(graph): Function to detect a cycle in a directed graph. :param graph: Dict[int, List[int]], a directed graph represented as an adjacency list :return: bool, True if the graph contains a cycle, False otherwise def dfs(node, visited, rec_stack): visited[node] = True rec_stack[node] = True for neighbor in graph.get(node, []): if not visited[neighbor]: if dfs(neighbor, visited, rec_stack): return True elif rec_stack[neighbor]: return True rec_stack[node] = False return False visited = {node: False for node in graph} rec_stack = {node: False for node in graph} for node in graph: if not visited[node]: if dfs(node, visited, rec_stack): return True return False
question:# Coding Assessment Question: Context: You are developing an application for a local bakery that offers online ordering and delivery. To customize orders, the bakery wants to recommend additional items based on customers' current cart content. This requires analyzing purchase patterns from past orders to identify commonly bought-together items. Task: Implement a function called `recommend_additional_items` that analyzes previous orders and suggests additional items for a given cart. This function should: 1. Parse a list of previous orders and create a mapping of frequently bought-together items. 2. For a given cart (a list of items), recommend up to 5 additional items that are most commonly purchased together with the items in the cart. 3. Handle edge cases such as empty carts or items with no purchase history. Requirements: 1. Use provided library (`collections.Counter`) for counting occurrences and relationships between items. 2. Implement error-handling mechanisms for edge cases. 3. Optimize the function to efficiently process large lists of past orders and quickly generate recommendations. 4. Include docstrings and comments for clarity. Expected Input and Output: **Input**: - `past_orders` (List[List[String]]): A list where each element is an order containing a list of items purchased together. - `current_cart` (List[String]): A list of items currently in the customer's cart. **Output**: - List[String]: A list of up to 5 recommended items based on the current cart content. **Example**: ```python # Example Past Orders: past_orders = [ ['bread', 'butter', 'jam'], ['bread', 'butter'], ['bread', 'jam'], ['coffee', 'pastry'], ['coffee', 'bread'], ['pastry', 'jam'] ] # Function Call >>> recommend_additional_items(past_orders, ['bread']) ['butter', 'jam', 'coffee'] >>> recommend_additional_items(past_orders, ['coffee']) ['pastry', 'bread'] >>> recommend_additional_items(past_orders, []) [] ``` Constraints: - Consider the complexity of analyzing orders to ensure the function runs efficiently with large datasets. - If there are ties in item popularity, sort the items alphabetically. Implementation Notes: - Use a dictionary to maintain a mapping of item pairs and their co-occurrence counts. - Consider both individual items and their combinations when recommending additional items. - Use a priority queue or a similar structure to efficiently manage the top recommendations.
answer:from collections import Counter, defaultdict from itertools import combinations def recommend_additional_items(past_orders, current_cart): Recommends additional items based on past orders and the current cart content. Args: - past_orders (List[List[str]]): A list of past orders, each order is a list of items. - current_cart (List[str]): A list of items currently in the customer's cart. Returns: - List[str]: A list of up to 5 recommended items based on the current cart. # Edge case: Empty cart should return an empty list if not current_cart: return [] # Create a dictionary to count co-occurrences of items item_counter = defaultdict(Counter) # Populate the co-occurrence dictionary for order in past_orders: for item1, item2 in combinations(order, 2): item_counter[item1][item2] += 1 item_counter[item2][item1] += 1 # Count the potential recommendations recommendation_counter = Counter() for item in current_cart: for other_item, count in item_counter[item].items(): if other_item not in current_cart: recommendation_counter[other_item] += count # Get the top 5 most common recommendations, sorted alphabetically in case of tie most_common_recommendations = recommendation_counter.most_common() sorted_recommendations = sorted(most_common_recommendations, key=lambda x: (-x[1], x[0])) return [item for item, count in sorted_recommendations[:5]]
question:# Problem Statement Streamlining Data Processing with Custom Pipelines Overview You are given a data processing Pipeline class that consists of several steps, each representing a data transformation or processing task. Initially, this class supports simple built-in steps. Your task is to extend the Pipeline class to support custom processing steps provided by the user. Task Modify the provided `Pipeline` class to accept custom processing steps. A custom processing step should be a callable that takes a dataset and returns the processed dataset. You have to ensure that the pipeline can seamlessly integrate and execute custom steps alongside the built-in ones. Requirements 1. **Custom Step Function Parameter**: Add a new parameter for custom steps that should be a list of callables. 2. **Step Integration**: Update the pipeline to include the custom steps at the appropriate stage. 3. **Validation**: Validate that each custom step is a callable that takes one argument (the dataset) and returns a modified dataset. 4. **Execution**: Ensure that all steps, including the custom ones, are executed in sequence when the pipeline is run. Input - **Initialization Parameter**: ```python Pipeline(built_in_steps: list of str, custom_steps: list of callable = None) ``` - **Dataset**: ```text A pandas DataFrame. ``` Output - The pipeline should be able to: 1. Execute the `run` method that processes the dataset through all steps. 2. Return the final processed dataset after executing all steps. Constraints - The custom steps, if provided, must be callables that take a pandas DataFrame and return a modified pandas DataFrame. - The input dataset will always be a valid pandas DataFrame. - An empty dataset must be handled gracefully without throwing errors. Example ```python import pandas as pd import numpy as np class Pipeline: def __init__(self, built_in_steps, custom_steps=None): self.built_in_steps = built_in_steps self.custom_steps = custom_steps or [] def run(self, dataset): for step in self.built_in_steps: # Simple built-in steps implementation. if step == "drop_na": dataset = dataset.dropna() elif step == "fill_na": dataset = dataset.fillna(0) elif step == "normalize": dataset = (dataset - dataset.min()) / (dataset.max() - dataset.min()) for custom_step in self.custom_steps: if callable(custom_step): dataset = custom_step(dataset) return dataset # Define a custom processing step def custom_step_add_column(df: pd.DataFrame) -> pd.DataFrame: df['new_column'] = np.random.randn(len(df)) return df # Sample data data = { 'A': [1, 2, np.nan, 4], 'B': [5, np.nan, np.nan, 8], 'C': [9, 10, 11, np.nan] } df = pd.DataFrame(data) # Instantiate the Pipeline with built-in and custom steps pipeline = Pipeline(built_in_steps=["drop_na", "normalize"], custom_steps=[custom_step_add_column]) # Execute the pipeline and process the dataset processed_df = pipeline.run(df) print(processed_df) ``` **Note**: Ensure the custom steps are applied correctly without breaking the existing built-in step functionality. The processed DataFrame should reflect all transformations.
answer:import pandas as pd import numpy as np class Pipeline: def __init__(self, built_in_steps, custom_steps=None): self.built_in_steps = built_in_steps self.custom_steps = custom_steps or [] def run(self, dataset): for step in self.built_in_steps: # Simple built-in steps implementation. if step == "drop_na": dataset = dataset.dropna() elif step == "fill_na": dataset = dataset.fillna(0) elif step == "normalize": dataset = (dataset - dataset.min()) / (dataset.max() - dataset.min()) for custom_step in self.custom_steps: if callable(custom_step): dataset = custom_step(dataset) else: raise ValueError(f"Custom step {custom_step} is not callable") return dataset # Define a custom processing step def custom_step_add_column(df: pd.DataFrame) -> pd.DataFrame: df['new_column'] = np.random.randn(len(df)) return df # Sample data data = { 'A': [1, 2, np.nan, 4], 'B': [5, np.nan, np.nan, 8], 'C': [9, 10, 11, np.nan] } df = pd.DataFrame(data) # Instantiate the Pipeline with built-in and custom steps pipeline = Pipeline(built_in_steps=["drop_na", "normalize"], custom_steps=[custom_step_add_column]) # Execute the pipeline and process the dataset processed_df = pipeline.run(df) print(processed_df)
question:# Flatten Nested List Given a nested list of integers where some elements are integers and some are lists of integers, implement a function `flatten_list(nested_list: list) -> list` that returns a flattened version of the nested list. Input Format * A single list `nested_list` which contains integers and/or other lists of integers. Output Format * A list of integers which is a flattened version of the input list. Constraints * The depth of the nested lists can be up to 20 levels. * Each individual list contains at most 1000 elements. * The elements can be either integers or another list. Examples ```python assert flatten_list([1, [2, 3], [[4, 5], 6], 7]) == [1, 2, 3, 4, 5, 6, 7] assert flatten_list([1, [2, [3, 4]], 5]) == [1, 2, 3, 4, 5] assert flatten_list([1, [], [2, [3, [4, 5]]]]) == [1, 2, 3, 4, 5] assert flatten_list([]) == [] assert flatten_list([[[[[[6]]]]]]) == [6] ``` Guidelines 1. Use recursion to handle the nested structure. 2. Ensure the function can handle deeply nested lists efficiently. 3. Optimize the function to avoid exceeding maximum recursion depth where applicable.
answer:def flatten_list(nested_list): Flattens a nested list of integers. :param nested_list: List of integers or other lists. :return: A flat list of integers. flat_list = [] for element in nested_list: if isinstance(element, list): flat_list.extend(flatten_list(element)) else: flat_list.append(element) return flat_list