Appearance
question:You are given an integer array `arr` and an integer `k`. Your task is to find the length of the longest subarray that contains at most `k` distinct integers. Implement the `Solution` class: * `int longestSubarrayWithKDistinct(int[] arr, int k)` - Returns the length of the longest subarray with at most `k` distinct integers. Example: ``` Input: arr = [1, 2, 1, 2, 3], k = 2 Output: 4 Explanation: The longest subarray with at most 2 distinct integers is [1, 2, 1, 2] with length 4. ``` Note: If `k` is zero or the input array is empty, the output should be 0.
answer:from collections import defaultdict def longestSubarrayWithKDistinct(arr, k): if k == 0 or not arr: return 0 left = 0 max_length = 0 char_count = defaultdict(int) for right in range(len(arr)): char_count[arr[right]] += 1 while len(char_count) > k: char_count[arr[left]] -= 1 if char_count[arr[left]] == 0: del char_count[arr[left]] left += 1 max_length = max(max_length, right - left + 1) return max_length
question:Given a list of `n` integers, where each integer represents the height of a histogram bar, find the area of the largest rectangle that can be formed within the bounds of the histogram. Each bar has a width of `1`. Design an algorithm that solves this problem efficiently, ideally in `O(n)` time complexity.
answer:def largest_rectangle_area(heights): Given a list of heights representing a histogram, return the area of the largest rectangle that can be formed within the bounds of the histogram. stack = [] # stack to store the indices of the histogram bars max_area = 0 index = 0 while index < len(heights): # If this bar is higher than the bar at stack top, push it to the stack if not stack or heights[index] >= heights[stack[-1]]: stack.append(index) index += 1 else: # Pop the top top_of_stack = stack.pop() # Calculate the area with heights[top_of_stack] as the shortest bar area = (heights[top_of_stack] * ((index - stack[-1] - 1) if stack else index)) # Update max_area, if needed max_area = max(max_area, area) # Now, pop the remaining bars from stack and calculate 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
question:You are given a string `s` containing only lowercase alphabetical characters. You need to partition the string into as few segments as possible such that each letter appears in at most one segment. Return _the list of integers representing the length of each segment_.
answer:def partition_labels(s): Returns a list of integers representing the length of each segment such that each letter appears in at most one segment. last_occurrence = {char: idx for idx, char in enumerate(s)} partitions = [] start, end = 0, 0 for i, char in enumerate(s): end = max(end, last_occurrence[char]) if i == end: partitions.append(end - start + 1) start = i + 1 return partitions
question:Implement a system to manage a parking lot. The parking lot has multiple levels, each level has multiple rows of spots, and each row has multiple spots. The parking lot can park motorcycles, cars, and buses. Design a class `ParkingLot` which has 4 methods: 1. `parkVehicle(vehicle)`: Parks the vehicle into the parking lot. The vehicle could be a motorcycle, car, or bus. Return `True` if the vehicle was successfully parked, otherwise return `False`. 2. `leaveVehicle(vehicle)`: Remove the vehicle from the parking lot. Return `True` if the vehicle was successfully removed, otherwise return `False`. 3. `getAvailableSpots()`: Returns the number of available spots in the parking lot. 4. `isFull()`: Returns `True` if the parking lot is full, otherwise `False`. Assume there are enough parking spots for the vehicles initially.
answer:class Vehicle: def __init__(self, vehicle_type): self.vehicle_type = vehicle_type class ParkingLot: def __init__(self, levels, rows_per_level, spots_per_row): self.levels = levels self.parking_space = [[[None for _ in range(spots_per_row)] for _ in range(rows_per_level)] for _ in range(levels)] self.spots_per_row = spots_per_row self.rows_per_level = rows_per_level def parkVehicle(self, vehicle): for level in range(self.levels): for row in range(self.rows_per_level): for spot in range(self.spots_per_row): if self.parking_space[level][row][spot] is None: self.parking_space[level][row][spot] = vehicle return True return False def leaveVehicle(self, vehicle): for level in range(self.levels): for row in range(self.rows_per_level): for spot in range(self.spots_per_row): if self.parking_space[level][row][spot] == vehicle: self.parking_space[level][row][spot] = None return True return False def getAvailableSpots(self): available_spots = 0 for level in self.parking_space: for row in level: available_spots += row.count(None) return available_spots def isFull(self): return self.getAvailableSpots() == 0