chat

🔍

question:def rotate_matrix(matrix: list) -> None: Rotate the given n x n matrix 90 degrees clockwise in-place. Args: matrix (list): A list of lists representing a square 2D matrix of integers. Returns: None. The function modifies the input matrix in-place. Examples: >>> matrix1 = [ ... [1, 2, 3], ... [4, 5, 6], ... [7, 8, 9] ... ] >>> rotate_matrix(matrix1) >>> matrix1 [[7, 4, 1], [8, 5, 2], [9, 6, 3]] >>> matrix2 = [ ... [5, 1, 9, 11], ... [2, 4, 8, 10], ... [13, 3, 6, 7], ... [15, 14, 12, 16] ... ] >>> rotate_matrix(matrix2) >>> matrix2 [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]

answer:def rotate_matrix(matrix: list) -> None: Rotate the given n x n matrix 90 degrees clockwise in-place. n = len(matrix) for layer in range(n // 2): first = layer last = n - 1 - layer for i in range(first, last): offset = i - first # save top element top = matrix[first][i] # move left to top matrix[first][i] = matrix[last - offset][first] # move bottom to left matrix[last - offset][first] = matrix[last][last - offset] # move right to bottom matrix[last][last - offset] = matrix[i][last] # move top to right matrix[i][last] = top

question:from typing import List, NamedTuple, Callable class Talk(NamedTuple): start: int end: int def schedule_talks(talks: List[Talk], key: Callable[[Talk], int] = lambda x: x.end) -> int: Calculate the maximum number of non-overlapping talks that can be attended. Args: talks (List[Talk]): a list of Talk objects, each with a start and end time. key (Callable[[Talk], int], optional): a function that takes a Talk and returns a value used for sorting. Defaults to end time. Returns: int: the maximum number of non-overlapping talks that can be attended. Examples: >>> talks = [Talk(1, 3), Talk(2, 5), Talk(3, 9), Talk(6, 8)] >>> schedule_talks(talks) 2 >>> talks = [Talk(1, 2), Talk(2, 3), Talk(3, 4)] >>> schedule_talks(talks) 3 >>> schedule_talks([]) 0 >>> talks = [Talk(1, 5), Talk(2, 3), Talk(4, 6)] >>> schedule_talks(talks) 2 from solution import schedule_talks, Talk def test_schedule_talks_example_case(): talks = [Talk(1, 3), Talk(2, 5), Talk(3, 9), Talk(6, 8)] assert schedule_talks(talks) == 2 def test_schedule_talks_no_talks(): assert schedule_talks([]) == 0 def test_schedule_talks_non_overlapping(): talks = [Talk(1, 2), Talk(2, 3), Talk(3, 4)] assert schedule_talks(talks) == 3 def test_schedule_talks_some_overlapping(): talks = [Talk(1, 3), Talk(2, 4), Talk(3, 5)] assert schedule_talks(talks) == 2 def test_schedule_talks_back_to_back(): talks = [Talk(1, 5), Talk(2, 3), Talk(4, 6)] assert schedule_talks(talks) == 2 def test_schedule_talks_custom_sort(): talks = [Talk(1, 3), Talk(2, 5), Talk(3, 9), Talk(6, 8)] custom_key = lambda x: (x.end - x.start) assert schedule_talks(talks, key=custom_key) == 2 def test_schedule_talks_single_talk(): talks = [Talk(1, 2)] assert schedule_talks(talks) == 1

answer:from typing import List, NamedTuple, Callable class Talk(NamedTuple): start: int end: int def schedule_talks(talks: List[Talk], key: Callable[[Talk], int] = lambda x: x.end) -> int: # Sort the talks based on the given key (default is by the end time) sorted_talks = sorted(talks, key=key) max_talks = 0 last_end_time = 0 for talk in sorted_talks: if talk.start >= last_end_time: max_talks += 1 last_end_time = talk.end return max_talks

question:def generate_primes(n: int) -> list: Generate the first n prime numbers. Parameters: n (int): The number of prime numbers to generate. Returns: list: A list containing the first n prime numbers. >>> generate_primes(5) [2, 3, 5, 7, 11] >>> generate_primes(0) [] >>> generate_primes(1) [2] >>> generate_primes(-5) [] >>> generate_primes(7) [2, 3, 5, 7, 11, 13, 17]

answer:def generate_primes(n): Generate the first n prime numbers. Parameters: n (int): The number of prime numbers to generate. Returns: list: A list containing the first n prime numbers. if not isinstance(n, int) or n <= 0: return [] primes = [] candidate = 2 while len(primes) < n: is_prime = True for p in primes: if p * p > candidate: break if candidate % p == 0: is_prime = False break if is_prime: primes.append(candidate) candidate += 1 return primes

question:class Graph: Graph class to represent an undirected graph using an adjacency list. The class supports adding vertices and edges, and performs a Depth-First Search (DFS) traversal. Example usage: >>> graph = Graph() >>> graph.add_vertex("A") >>> graph.add_vertex("B") >>> graph.add_vertex("C") >>> graph.add_edge("A", "B") >>> graph.add_edge("A", "C") >>> graph.dfs("A") ['A', 'B', 'C'] >>> graph = Graph() >>> graph.add_vertex("A") >>> graph.add_edge("A", "B") # Assume add_vertex("B") is called implicitly Traceback (most recent call last): ... KeyError: 'B' Test cases for unit testing: def test_dfs_basic(): graph = Graph() graph.add_vertex("A") graph.add_vertex("B") graph.add_vertex("C") graph.add_vertex("D") graph.add_vertex("E") graph.add_edge("A", "B") graph.add_edge("A", "C") graph.add_edge("B", "D") graph.add_edge("C", "E") assert graph.dfs("A") == ['A', 'B', 'D', 'C', 'E'] assert graph.dfs("C") == ['C', 'A', 'B', 'D', 'E'] def test_dfs_cycle(): graph = Graph() graph.add_vertex("A") graph.add_vertex("B") graph.add_vertex("C") graph.add_edge("A", "B") graph.add_edge("B", "C") graph.add_edge("C", "A") assert graph.dfs("A") == ['A', 'B', 'C'] def test_dfs_single_vertex(): graph = Graph() graph.add_vertex("A") assert graph.dfs("A") == ['A'] def test_dfs_disconnected_graph(): graph = Graph() graph.add_vertex("A") graph.add_vertex("B") graph.add_vertex("C") graph.add_vertex("D") graph.add_vertex("E") graph.add_edge("A", "B") graph.add_edge("A", "C") graph.add_edge("D", "E") assert graph.dfs("A") == ['A', 'B', 'C'] assert graph.dfs("D") == ['D', 'E'] def test_dfs_complex_graph(): graph = Graph() graph.add_vertex("A") graph.add_vertex("B") graph.add_vertex("C") graph.add_vertex("D") graph.add_vertex("E") graph.add_vertex("F") graph.add_vertex("G") graph.add_edge("A", "B") graph.add_edge("A", "C") graph.add_edge("B", "D") graph.add_edge("B", "E") graph.add_edge("C", "F") graph.add_edge("E", "G") assert graph.dfs("A") == ['A', 'B', 'D', 'E', 'G', 'C', 'F'] def __init__(self): self.adjacency_list = {} def add_vertex(self, vertex): pass def add_edge(self, u, v): pass def dfs(self, start_vertex): pass

answer:class Graph: def __init__(self): self.adjacency_list = {} def add_vertex(self, vertex): if vertex not in self.adjacency_list: self.adjacency_list[vertex] = [] def add_edge(self, u, v): if u in self.adjacency_list and v in self.adjacency_list: self.adjacency_list[u].append(v) self.adjacency_list[v].append(u) def dfs(self, start_vertex): visited = set() traversal_order = [] def dfs_recursive(v): if v not in visited: visited.add(v) traversal_order.append(v) for neighbor in self.adjacency_list[v]: dfs_recursive(neighbor) dfs_recursive(start_vertex) return traversal_order