Appearance
question:# Problem Statement: Counting Islands in a 2D Grid You are given a 2D binary grid where `1` represents land and `0` represents water. Your task is to create a function that counts the number of islands. An island is formed by connecting adjacent lands horizontally or vertically. Assume all four edges of the grid are surrounded by water. Function Signature ```python def count_islands(grid: List[List[int]]) -> int: Counts the number of islands in a 2D binary grid. :param grid: A 2D list representing the map where 1 indicates land and 0 indicates water. :return: The number of islands. pass ``` Input * `grid`: A 2D list of integers where each element is either `0` (water) or `1` (land). Output * The function should return an integer representing the number of islands in the grid. Constraints 1. The grid is rectangular and its dimensions are at most `300 x 300`. 2. The grid will always have at least one element. Example ```python grid = [ [1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 1] ] num_islands = count_islands(grid) # Output: 3 ``` Requirements 1. Implement the function with the specified constraints. 2. Ensure to handle edge cases such as grids full of water or land. 3. Optimize for typical grid sizes up to the maximum constraint. This question assesses the candidate's ability to work with 2D arrays, understand graph traversal algorithms such as Depth-First Search (DFS) or Breadth-First Search (BFS), and handle edge cases while maintaining efficiency.
answer:from typing import List def count_islands(grid: List[List[int]]) -> int: if not grid: return 0 def dfs(r, c): if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] == 0: return grid[r][c] = 0 # Mark as visited dfs(r - 1, c) dfs(r + 1, c) dfs(r, c - 1) dfs(r, c + 1) island_count = 0 for r in range(len(grid)): for c in range(len(grid[0])): if grid[r][c] == 1: island_count += 1 dfs(r, c) return island_count
question:# Problem Statement You are developing a component of a low-level operating system that requires converting signed integers into their binary two’s complement representation. Given a negative integer, your task is to implement a function that converts this integer into its corresponding two’s complement binary representation as a string. # Requirements: 1. Your function needs to throw an exception if the input is not a negative integer. 2. Do NOT use Python’s built-in functionalities such as `bin()` or `format()` for direct conversion in your final return statement. 3. You must calculate the binary length and two’s complement manually through bit manipulation. # Function Signature: ```python def twos_complement_custom(number: int) -> str: pass ``` # Expected Input and Output: 1. **Input**: A single integer `number` where -2^31 <= number < 0 2. **Output**: A string representing the two's complement binary code prefixed with `0b`. **Example**: ```python twos_complement_custom(-5) # Output: '0b11111111111111111111111111111011' twos_complement_custom(-17) # Output: '0b11111111111111111111111111101111' ``` # Constraints: 1. The input must be a negative integer. 2. The output must be a valid string of 32-bit two’s complement binary prefixed by `0b`. 3. The function should be optimized for both time and space complexities. **Note**: - Focus on the precise bit manipulation and manual conversion instead of relying on standard library functions for this operation.
answer:def twos_complement_custom(number: int) -> str: Converts a negative integer to its two's complement binary string representation. :param number: Negative integer :return: Two's complement binary string prefixed with '0b' if not isinstance(number, int): raise ValueError("Input must be an integer.") if number >= 0: raise ValueError("Input must be a negative integer.") # Inverting the bits using bitwise NOT (~) and adding one to get the two's complement. twos_complement_val = (1 << 32) + number binary_str = format(twos_complement_val, '032b') return '0b' + binary_str
question:# Coding Assessment Question **Context**: You are given a list of positive integers where each integer represents the height of a building. You need to calculate how much water would be trapped between these buildings after it rains. Water trapping between buildings is determined by finding the local valleys and the amount of water they can hold. This problem is commonly encountered in computational geometry and data analysis. **Function Specification**: **Function Name**: trap_water **Parameters**: * `heights: list[int]`: A list of positive integers representing the heights of the buildings. **Return**: * `int`: An integer representing the total amount of water trapped between the buildings. **Constraints**: * The length of the list `heights` will not exceed 10^5. * The integer values in the list will be positive and fit within the range of a standard 32-bit integer. **Example**: ```python # Example 1: print(trap_water([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])) # Output: 6 # Example 2: print(trap_water([4, 2, 0, 3, 2, 5])) # Output: 9 # Example 3: print(trap_water([1, 1, 1, 1, 1])) # Output: 0 # Example 4: print(trap_water([0, 0, 0, 0])) # Output: 0 # Example 5: print(trap_water([5, 4, 1, 2])) # Output: 1 ``` # Instructions: 1. Implement the function `trap_water` that takes in a list of building heights and returns the total amount of water that would be trapped between the buildings after it rains. 2. Handle edge cases, especially when the list contains all the same height or when there is no valley to trap any water. 3. Ensure the function is efficient and runs within acceptable time limits for large datasets.
answer:def trap_water(heights): if not heights: return 0 left, right = 0, len(heights) - 1 left_max, right_max = heights[left], heights[right] water_trapped = 0 while left < right: if left_max < right_max: left += 1 left_max = max(left_max, heights[left]) water_trapped += max(0, left_max - heights[left]) else: right -= 1 right_max = max(right_max, heights[right]) water_trapped += max(0, right_max - heights[right]) return water_trapped
question:# Question: Longest Increasing Subsequence **Context**: You are developing a feature for a playlist manager that needs to identify the longest sequences of songs, determined by their play counts, that have continually increasing popularity. **Task**: Implement a function `longest_increasing_subsequence` that finds the length of the longest increasing subsequence in a given list of play counts. **Function signature**: ```python def longest_increasing_subsequence(play_counts: List[int]) -> int: pass ``` **Input**: - `play_counts` (List[int]): A list of integers representing the play counts of the songs. **Output**: - Returns the length of the longest increasing subsequence of play counts. **Constraints**: - All input integers are non-negative. - The length of `play_counts` will not exceed 1,000. **Sample Input**: ```python play_counts = [10, 22, 9, 33, 21, 50, 41, 60, 80] ``` **Sample Output**: ```python 6 ``` **Explanation**: The longest increasing subsequence is [10, 22, 33, 50, 60, 80], and its length is 6. While there may be other increasing sequences, none are longer than this one.
answer:from typing import List def longest_increasing_subsequence(play_counts: List[int]) -> int: if not play_counts: return 0 n = len(play_counts) lis = [1] * n # Initialize LIS values for all indexes # Compute optimized LIS values in a bottom up manner for i in range(1, n): for j in range(0, i): if play_counts[i] > play_counts[j] and lis[i] < lis[j] + 1: lis[i] = lis[j] + 1 # Pick the maximum of all LIS values return max(lis)