Не забудьте приобрести книгу Проектирование приложений, интенсивно использующих данные, самую важную книгу для подготовки к собеседованию по проектированию систем!
При подготовке к собеседованиям по разработке программного обеспечения в ведущих технологических компаниях, таких как Meta (ранее Facebook), очень важно оттачивать свои знания о структурах данных.
Стек, фундаментальная структура данных, является частой темой. Вот краткое изложение пяти основных вопросов, связанных со стеком, из интервью Meta и их решений Python.
1. Сбалансированные скобки:
Вопрос. Определите, допустима ли заданная строка, содержащая символы ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ и ‘]’. Строка действительна, если:
- Открытые скобки закрываются однотипными скобками.
- Открытые скобки закрываются в правильном порядке.
def isValid(s: str) -> bool: stack = [] mapping = {")": "(", "}": "{", "]": "["} for char in s: if char in mapping: top_element = stack.pop() if stack else '#' if mapping[char] != top_element: return False else: stack.append(char) return not stack
Получите преимущество в конкурентной борьбе с помощью курса Собеседование по продвинутому системному проектированию и получите работу своей мечты! Не тратьте часы на Leetcode. Изучите шаблоны с курсом Grokking the Coding Interview: Patterns for Coding Questions.
2. Реализуйте стек с помощью функции getMin()
Вопрос. Создайте стек с операциями push, pop, top и getMin, работающими за постоянное время.
class MinStack: def __init__(self): self.stack = [] self.min_stack = [] def push(self, x: int) -> None: self.stack.append(x) if not self.min_stack or x <= self.min_stack[-1]: self.min_stack.append(x) def pop(self) -> None: if self.stack.pop() == self.min_stack[-1]: self.min_stack.pop() def top(self) -> int: return self.stack[-1] def getMin(self) -> int: return self.min_stack[-1]