Appearance
question:Employee Shift Scheduling You are tasked with developing a program to manage the shift schedules for employees at a company. Each employee has a unique ID and can work different shifts. A shift is represented by a time period in the format "hh:mm-hh:mm". Your goal is to implement functionalities to manage and query employee shift schedules. Requirements: 1. **Class `EmployeeShift`**: - **Attributes**: - `employee_id` (string): Unique identifier for the employee. - `shifts` (list of tuples): Each tuple represents a shift in the form like `('09:00', '17:00')`. - **Methods**: - `add_shift(shift: str)`: Parses the input string shift in the "hh:mm-hh:mm" format and adds it to the employee's shift list. - `remove_shift(shift: str)`: Removes the shift from the employee's shift list if it exists. - `get_shifts()`: Returns the list of shifts for the employee in the string format "hh:mm-hh:mm". 2. **Function `allocate_shift(employees: list, employee_id: str, shift: str) -> str`**: - Adds the specified shift to the employee's schedule. - Returns `f"Shift {shift} allocated to employee {employee_id}"` on successful addition. - If the employee does not exist, return `f"Employee {employee_id} not found"`. 3. **Function `deallocate_shift(employees: list, employee_id: str, shift: str) -> str`**: - Removes the specified shift from the employee's schedule. - Returns `f"Shift {shift} removed from employee {employee_id}"` on successful removal. - If the employee does not exist, return `f"Employee {employee_id} not found"`. Example: ```python class EmployeeShift: def __init__(self, employee_id: str): self.employee_id = employee_id self.shifts = [] def add_shift(self, shift: str): start, end = shift.split('-') self.shifts.append((start, end)) def remove_shift(self, shift: str): start, end = shift.split('-') if (start, end) in self.shifts: self.shifts.remove((start, end)) def get_shifts(self): return [f"{start}-{end}" for start, end in self.shifts] def allocate_shift(employees: list, employee_id: str, shift: str) -> str: for employee in employees: if employee.employee_id == employee_id: employee.add_shift(shift) return f"Shift {shift} allocated to employee {employee_id}" return f"Employee {employee_id} not found" def deallocate_shift(employees: list, employee_id: str, shift: str) -> str: for employee in employees: if employee.employee_id == employee_id: employee.remove_shift(shift) return f"Shift {shift} removed from employee {employee_id}" return f"Employee {employee_id} not found" if __name__ == "__main__": employees = [EmployeeShift("E001"), EmployeeShift("E002"), EmployeeShift("E003")] print(allocate_shift(employees, "E001", "09:00-17:00")) print(allocate_shift(employees, "E001", "18:00-22:00")) print(deallocate_shift(employees, "E001", "09:00-17:00")) print(deallocate_shift(employees, "E004", "09:00-17:00")) for emp in employees: print(f"{emp.employee_id}: {emp.get_shifts()}") ``` Constraints: - You may assume all input times are in 24-hour format. - Handle edge cases such as invalid shift time formats gracefully.
answer:class EmployeeShift: def __init__(self, employee_id: str): self.employee_id = employee_id self.shifts = [] def add_shift(self, shift: str): start, end = shift.split('-') self.shifts.append((start, end)) def remove_shift(self, shift: str): start, end = shift.split('-') if (start, end) in self.shifts: self.shifts.remove((start, end)) def get_shifts(self): return [f"{start}-{end}" for start, end in self.shifts] def allocate_shift(employees: list, employee_id: str, shift: str) -> str: for employee in employees: if employee.employee_id == employee_id: employee.add_shift(shift) return f"Shift {shift} allocated to employee {employee_id}" return f"Employee {employee_id} not found" def deallocate_shift(employees: list, employee_id: str, shift: str) -> str: for employee in employees: if employee.employee_id == employee_id: employee.remove_shift(shift) return f"Shift {shift} removed from employee {employee_id}" return f"Employee {employee_id} not found"
question:# Scenario You are developing a system that processes requests from multiple clients. Each request has a priority level, and the system needs to handle the highest priority requests first. You need to implement a priority queue to manage these requests efficiently. # Task Implement a class `PriorityQueue` that supports the following operations: 1. **insert(item, priority)**: Insert an item into the queue with an associated priority. 2. **extract_max()**: Remove and return the item with the highest priority from the queue. 3. **peek_max()**: Return (but do not remove) the item with the highest priority. 4. **change_priority(item, new_priority)**: Change the priority of a given item in the queue. 5. **size()**: Return the number of items in the queue. # Constraints - Implement all methods with consideration for efficiency. - When multiple items have the same highest priority, the queue should follow the order of insertion for those items. - If the item is not found in `change_priority`, handle the situation gracefully. # Input and Output - **insert(item, priority)**: Two parameters `item` (can be any type) and `priority` (a numeric value). - **extract_max()**: No parameters, returns the item with the highest priority. - **peek_max()**: No parameters, returns the item with the highest priority. - **change_priority(item, new_priority)**: Two parameters `item` and `new_priority` (both can be any type). - **size()**: No parameters, returns an integer representing the number of elements. # Example ```python pq = PriorityQueue() pq.insert("task1", 5) pq.insert("task2", 3) pq.insert("task3", 7) print(pq.size()) # Output: 3 print(pq.peek_max()) # Output: "task3" print(pq.extract_max()) # Output: "task3" print(pq.size()) # Output: 2 pq.change_priority("task2", 8) print(pq.peek_max()) # Output: "task2" ``` # Implementation Challenge Implement the `PriorityQueue` class ensuring each method adheres to the described behaviors efficiently in terms of time complexity. Use appropriate data structures to maintain the priority queue properties.
answer:import heapq class PriorityQueue: def __init__(self): self.heap = [] self.entry_finder = {} self.counter = 0 def insert(self, item, priority): entry = [-priority, self.counter, item] self.entry_finder[item] = entry heapq.heappush(self.heap, entry) self.counter += 1 def extract_max(self): while self.heap: priority, count, item = heapq.heappop(self.heap) if item is not None: del self.entry_finder[item] return item raise KeyError('pop from an empty priority queue') def peek_max(self): while self.heap: priority, count, item = self.heap[0] if item is not None: return item heapq.heappop(self.heap) # Remove placeholder raise KeyError('peek from an empty priority queue') def change_priority(self, item, new_priority): if item in self.entry_finder: self.remove_item(item) self.insert(item, new_priority) def remove_item(self, item): entry = self.entry_finder.pop(item) entry[-1] = None def size(self): return len(self.entry_finder)
question:# Problem Statement Create a function that determines the minimum spanning tree (MST) of a given undirected, connected, and weighted graph using Prim's Algorithm. The graph is represented using an adjacency list. Your implementation should handle basic edge cases and return an appropriate result or error for invalid inputs. # Function Signature ```python def prim_mst(graph: Dict[Any, List[Tuple[Any, float]]]) -> List[Tuple[Any, Any, float]]: pass ``` # Expected Input and Output Formats - **Input**: - `graph`: A dictionary where keys represent nodes and values are lists of tuples representing the edges. Each tuple contains a neighboring node and the weight of the edge (node, weight). - **Output**: - A list of tuples representing the edges in the MST. Each tuple contains two nodes and the weight of the edge (node1, node2, weight). # Constraints and Limitations 1. The graph is guaranteed to be undirected, connected, and weighted. 2. Each edge's weight is a positive float. 3. The input graph will have at least two nodes. 4. Ensure the algorithm processes the minimum spanning tree correctly. 5. If the graph is empty or has only one node, return an empty list. 6. Raise an appropriate exception for invalid inputs (like disconnected graphs). # Example ```python graph = { 'A': [('B', 1), ('C', 3)], 'B': [('A', 1), ('C', 1), ('D', 5)], 'C': [('A', 3), ('B', 1), ('D', 1)], 'D': [('B', 5), ('C', 1)] } assert prim_mst(graph) == [('A', 'B', 1), ('B', 'C', 1), ('C', 'D', 1)], "Test case failed" ``` - In this example, the MST comprises edges with a total weight of 3. The result corresponds to the nodes connected by the edges with the lowest weights to form a spanning tree without any cycles. # Performance Requirements The time complexity should be appropriate for handling graphs of typical size: - Efficiently process graphs with up to a few hundred nodes and edges. - Utilize priority queues for maintaining the lowest edge weights to enhance the performance of Prim's Algorithm. # Scenario Imagine you are working on a network design project that requires determining the optimal way to connect various servers in a data center to minimize the total cabling cost. Your implementation of Prim's Algorithm will provide the minimum spanning tree necessary to achieve a cost-effective and efficient network layout.
answer:import heapq from typing import Dict, List, Tuple, Any def prim_mst(graph: Dict[Any, List[Tuple[Any, float]]]) -> List[Tuple[Any, Any, float]]: if not graph: return [] start_node = next(iter(graph)) mst = [] visited = set() min_heap = [(0, start_node, start_node)] while min_heap: weight, start, end = heapq.heappop(min_heap) if end not in visited: visited.add(end) if start != end: mst.append((start, end, weight)) for next_node, next_weight in graph[end]: if next_node not in visited: heapq.heappush(min_heap, (next_weight, end, next_node)) if len(visited) != len(graph): raise ValueError("Graph is disconnected") return mst
question:# Linked List Intersection You are provided with two singly linked lists, and you need to determine if they intersect at any point. Two linked lists are said to intersect if they share at least one node. Note that the intersection is defined by reference, not value, so the exact node must be identical in both lists. Your task is to implement a function `get_intersection_node` that returns the node at which the two lists intersect. If the two linked lists do not intersect, return `None`. Function Signature ```python def get_intersection_node(headA: ListNode, headB: ListNode) -> Optional[ListNode]: ``` Input - `headA` (ListNode): The head of the first linked list. - `headB` (ListNode): The head of the second linked list. Output - Returns the intersecting node, or `None` if the lists do not intersect. Constraints - The number of nodes in the lists is not guaranteed to be equal. - The nodes are instances of the `ListNode` class, which is defined as follows: ```python class ListNode: def __init__(self, value=0, next=None): self.value = value self.next = next ``` - Both linked lists are non-empty. Example Consider the following linked lists: ``` List A: 1 -> 9 -> 1 -> 2 -> 4 List B: 3 -> 2 -> 4 ``` The two lists intersect at node with value `2`, as they share the nodes `2 -> 4`. ```python # Creating nodes node1 = ListNode(1) node9 = ListNode(9) node1_2 = ListNode(1) node2 = ListNode(2) node4 = ListNode(4) # Creating first linked list node1.next = node9 node9.next = node1_2 node1_2.next = node2 node2.next = node4 # Creating second linked list node3 = ListNode(3) node3.next = node2 # Intersection results assert get_intersection_node(node1, node3) == node2 ```
answer:class ListNode: def __init__(self, value=0, next=None): self.value = value self.next = next def get_intersection_node(headA: ListNode, headB: ListNode) -> ListNode: Return the node at which the two lists intersect. If the two linked lists do not intersect, return None. if not headA or not headB: return None pointerA, pointerB = headA, headB while pointerA != pointerB: # if either pointer hits the end, reset it to the head of the other list # if they both hit the end, pointerA == pointerB == None and the loop ends pointerA = pointerA.next if pointerA else headB pointerB = pointerB.next if pointerB else headA return pointerA