Appearance
question:# Problem Statement **Sorting a Nearly Sorted List** is a classic problem where an array is almost sorted in ascending order except that each element is at most `k` positions away from its sorted position. Given an array `arr` of `n` elements where each element is at most `k` positions away from its sorted position, your task is to sort the array efficiently. # Task Write a function `sort_nearly_sorted(arr: List[int], k: int) -> List[int]` that takes in an integer array `arr` and an integer `k`, and returns the sorted array. # Input * `arr (List[int])`: The array of integers. * `k (int)`: The maximum distance of each element from its sorted position. # Output * Return the sorted array in ascending order. # Example Consider the following examples to gain clarity: ```python >>> sort_nearly_sorted([6, 5, 3, 2, 8, 10, 9], 3) [2, 3, 5, 6, 8, 9, 10] >>> sort_nearly_sorted([10, 9, 8, 7, 4, 70, 60, 50], 4) [4, 7, 8, 9, 10, 50, 60, 70] ``` # Constraints 1. The input array length `n` will be between `1` and `10^5`. 2. The value `k` will be between `1` and `n-1`. 3. All elements in the array will be distinct integers within the range of `1` and `10^6`. # Performance Requirements Ensure your solution handles large inputs efficiently in both time and space complexities, ideally using a heap-based approach or a similar optimized algorithm.
answer:import heapq from typing import List def sort_nearly_sorted(arr: List[int], k: int) -> List[int]: Sorts a nearly sorted array where every element is at most k positions away from its sorted position. Parameters: arr (List[int]): The nearly sorted array. k (int): The maximum distance of each element from its sorted position. Returns: List[int]: The sorted array. if not arr: return [] # Create a min-heap with the first k+1 elements heap = arr[:k + 1] heapq.heapify(heap) # The index in the result array target_index = 0 # Process the remaining elements in the array for remaining_index in range(k + 1, len(arr)): arr[target_index] = heapq.heappop(heap) heapq.heappush(heap, arr[remaining_index]) target_index += 1 # Collect the remaining elements from the heap while heap: arr[target_index] = heapq.heappop(heap) target_index += 1 return arr
question:# Flight Itinerary Generator Scenario You have been hired by a travel agency to develop an itinerary generator for their customers. The itinerary must show the order of flights taken based on a given list of flight segments. Each flight segment indicates a departure and an arrival location, and proper sequencing is required to generate the complete route. Task Implement a function `generate_itinerary(flights: List[Tuple[str, str]]) -> List[str]` that takes in a list of flight segments and generates the complete flight itinerary in the correct order. Input and Output Formats * The input parameter `flights` is a list of tuples, where each tuple contains two strings representing the departure and arrival locations. * The output should be a list of strings representing the complete itinerary. Itinerary Generation Process 1. Identify the starting location (a location that does not appear as an arrival in any segment). 2. Sequence the flight segments to form a continuous route. 3. Ensure that all given segments are used exactly once and the itinerary correctly connects all locations. Constraints * Each flight segment is unique. * There is exactly one valid itinerary for each input. * The length of the list `flights` is between 1 and 10^4. * Each location string's length is between 1 and 30, and consists of English letters only. Example ```python def generate_itinerary(flights: List[Tuple[str, str]]) -> List[str]: # TODO: Implement this function pass >>> generate_itinerary([("JFK", "ATL"), ("ATL", "SFO"), ("SFO", "LAX")]) ['JFK', 'ATL', 'SFO', 'LAX'] >>> generate_itinerary([("LAX", "JFK"), ("SFO", "LAX"), ("ATL", "SFO")]) ['ATL', 'SFO', 'LAX', 'JFK'] ``` Notes * Use efficient data structures to manage lookup and insertion of segments. * Consider edge cases such as single segment flights or circular itineraries. * Ensure to handle the itinerary formation even if input segments are unordered.
answer:from typing import List, Tuple, Dict def generate_itinerary(flights: List[Tuple[str, str]]) -> List[str]: # Create a graph to represent the flights as an adjacency list graph = {} in_degree = {} out_degree = {} for departure, arrival in flights: if departure not in graph: graph[departure] = [] graph[departure].append(arrival) if departure not in out_degree: out_degree[departure] = 0 if arrival not in in_degree: in_degree[arrival] = 0 out_degree[departure] += 1 in_degree[arrival] += 1 if arrival not in out_degree: out_degree[arrival] = 0 if departure not in in_degree: in_degree[departure] = 0 # Find the starting point: the node with out_degree and no in_degree start = None for location in out_degree: if out_degree[location] == in_degree.get(location, 0) + 1: start = location break elif start is None: start = location if start is None: return [] # Hierholzer's algorithm to find Eulerian Path/Circuit def visit(airport: str, result: List[str]): while graph.get(airport): next_airport = graph[airport].pop() visit(next_airport, result) result.append(airport) result = [] visit(start, result) return list(reversed(result))
question:# Task Description: Write a function `reverse_even_sublists` that takes in a list of integers and returns a new list where all the contiguous sublists of even numbers are reversed in place, while odd numbers remain in their original position. # Function Signature: ```python def reverse_even_sublists(numbers: list) -> list: Given a list of integers, reverse the contiguous sublists of even numbers in place. Parameters: numbers (list): A list of integers. Returns: list: A new list with even number sublists reversed, and odd numbers unchanged. pass ``` # Constraints: 1. The input list will contain at least one integer and at most 10000 integers. 2. Each integer in the list will be between -1000 and 1000. # Example: ```python numbers = [1, 2, 8, 4, 3, 6, 6, 7, 9, 2, 2, 12, 1] print(reverse_even_sublists(numbers)) # Expected output: [1, 4, 8, 2, 3, 6, 6, 7, 9, 12, 2, 2, 1] numbers = [10, 12, 14, 17, 18, 20, 3] print(reverse_even_sublists(numbers)) # Expected output: [14, 12, 10, 17, 20, 18, 3] ``` # Notes: 1. The function should process the list in a single pass, without using additional library functions for reversing sublists. 2. Preserve the relative order of elements that are not part of any even sublist. 3. Consider the edge cases where there are no even-numbered sublists, or where the entire list comprises even numbers.
answer:def reverse_even_sublists(numbers: list) -> list: Given a list of integers, reverse the contiguous sublists of even numbers in place. Parameters: numbers (list): A list of integers. Returns: list: A new list with even number sublists reversed, and odd numbers unchanged. result = [] i = 0 n = len(numbers) while i < n: if numbers[i] % 2 == 0: even_start = i while i < n and numbers[i] % 2 == 0: i += 1 even_sublist = numbers[even_start:i][::-1] result.extend(even_sublist) else: result.append(numbers[i]) i += 1 return result
question:# Problem Statement You are given an array of integers that represents heights of columns of varied width, each with a width of 1 unit. Your task is to implement a function to find the area of the largest rectangle that can be formed within these columns. # Function Signature ```python def largest_rectangle_area(heights: List[int]) -> int: pass ``` # Input Format * A list of integers heights where `1 <= len(heights) <= 10^5` and `0 <= heights[i] <= 10^4`. # Output Format * Return an integer representing the area of the largest rectangle that can be formed. # Example ```python heights = [2, 1, 5, 6, 2, 3] print(largest_rectangle_area(heights)) # Output: 10 ``` # Explanation In the above example, the largest rectangle can be formed using the heights `[5, 6]`, which results in an area of `5 * 2 = 10`. # Notes * Ensure the function handles edge cases effectively, such as an array with all elements being the same height or heights containing zeroes. * Consider the algorithm's time complexity, given the input size limits. An optimal solution should aim to achieve a time complexity close to O(n).
answer:from typing import List def largest_rectangle_area(heights: List[int]) -> int: Function to find the area of the largest rectangle that can be formed within given heights. # Create a stack to keep indices of bars stack = [] max_area = 0 index = 0 while index < len(heights): if not stack or heights[stack[-1]] <= heights[index]: stack.append(index) index += 1 else: top_of_stack = stack.pop() area = (heights[top_of_stack] * ((index - stack[-1] - 1) if stack else index)) max_area = max(max_area, area) while stack: top_of_stack = stack.pop() area = (heights[top_of_stack] * ((index - stack[-1] - 1) if stack else index)) max_area = max(max_area, area) return max_area