Общие структуры данных и алгоритмы. Вопросы для собеседования с примерами кода.

  1. Реверс строки:
    Описание: напишите функцию для инвертирования заданной строки.
    Код:

    def reverse_string(s):
       return s[::-1]
  2. Проверка палиндрома:
    Описание: Напишите функцию, проверяющую, является ли данная строка палиндромом.
    Код:

    def is_palindrome(s):
       return s == s[::-1]
  3. Найди недостающее число:
    Описание: Дан массив, содержащий n различных чисел, взятых из 0, 1, 2, …, n, найдите недостающее число.
    Код:

    def find_missing_number(nums):
       n = len(nums)
       total_sum = (n * (n + 1)) // 2
       array_sum = sum(nums)
       return total_sum - array_sum
  4. Реализация стека:
    Описание: реализация структуры данных стека с помощью операций push, pop и peek.
    Код:

    class Stack:
       def __init__(self):
           self.stack = []
       def push(self, item):
           self.stack.append(item)
       def pop(self):
           if not self.is_empty():
               return self.stack.pop()
           else:
               return None
       def peek(self):
           if not self.is_empty():
               return self.stack[-1]
           else:
               return None
       def is_empty(self):
           return len(self.stack) == 0
  5. Найти максимальную сумму подмассива:
    Описание: Учитывая массив целых чисел, найдите непрерывный подмассив с наибольшей суммой.
    Код:

    def max_subarray_sum(nums):
       max_sum = float('-inf')
       current_sum = 0
       for num in nums:
           current_sum = max(num, current_sum + num)
           max_sum = max(max_sum, current_sum)
       return max_sum