Не забудьте приобрести книгу Проектирование приложений, интенсивно использующих данные, самую важную книгу для подготовки к собеседованию по проектированию систем!

При подготовке к собеседованиям по разработке программного обеспечения в ведущих технологических компаниях, таких как 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]