3284 просмотра
От 15 февраля

Разбор решений для задач с собеседований Python-разработчиков

1. Бинарный поиск

Бинарный поиск — это алгоритм, используемый для поиска элемента в отсортированном массиве путем многократного деления интервала поиска пополам. Принцип алгоритма бинарного поиска очень прост. Мы всегда имеем дело с упорядоченным массивом. Это позволяет прибегать к хитрости - на каждой итерации цикла, который мы запускаем, мы вычисляем индекс среднего элемента. Этот элемент сравниваем с искомым. Если элемент из середины массива оказался меньше, чем тот, что мы ищем, значит нужный нам находится правее по массиву, ведь массив упорядочен. Соответственно, нам нужно перейти в следующую итерацию цикла, "оставляя" ей лишь правую часть массива - в ней снова будет найден средний элемент и алгоритм повторится. Если же элемент из середины массива оказался больше искомого, то мы переходим к следующей итерации, отбрасывая правую часть массива, а оставляя левую. Если же элемент совпадает с искомым, мы выходим из цикла. def BinarySearch(lys, val): first = 0 last = len(lys)-1 index = -1 while (first <= last) and (index == -1): mid = (first+last)//2 if lys[mid] == val: index = mid else: if val<lys[mid]: last = mid -1 else: first = mid +1 return index Также, вместо цикла мы могли бы обратиться к рекурсии. Я не могу написать бинарный поиск

2. Сжатие строки (rle)

Задача: Необходимо реализовать функцию, принимающую в аргументах строку, состоящую из букв и вернуть новую строку, в которой повторяющиеся буквы заменены количеством повторений. # AAAABBCAA --> A4B2C1A2 Решение: def encode_message(message): encoded_string = "" i = 0 while (i <= len(message)-1): count = 1 ch = message[i] j = i while (j < len(message)-1): if (message[j] == message[j + 1]): count = count + 1 j = j + 1 else: break encoded_string = encoded_string + str(count) + ch i = j + 1 return encoded_string Приведенный фрагмент содержит функцию encode_message() с параметром message (строка), подлежащим кодированию. Переменная encoded_string используется для хранения закодированной строки. Цикл while инициализируется с счетчиком с значением 1 и итерируется по всем символам строки. Внутренний цикл while проверяет, совпадает ли символ текущего индекса с символом следующего индекса. Если символы совпадают, то счётчик инкрементируется. Если нет, то счетчик и символ конкатенируются в переменную encoded_string и возвращаются. Алгоритм имеет сложность O (n). Также можно воспользоваться функцией groupby из модуля itertools. Она превратит последовательность элементов в последовательность групп повторяющихся символов. from itertools import groupby def rle_encode(data: str) -> str: return "".join(str(len(list(group_items))) + key for key, group_items in groupby(data)) Простейшие алгоритмы сжатия: RLE и LZ77

3. Проверка на палиндром

Палиндром — это последовательность символов, которая одинаково читается в обоих направлениях. 1. Метод с использованием индексации Первый и самый простой способ проверить, является ли строка палиндромом, — использовать трюк с индексацией для получения «зеркальной» строки и сравнения её с исходной. s = "radar" if s == s[::-1]: print("Это палиндром") else: print("Это не палиндром") 2. Метод с использованием цикла Мы можем также использовать цикл для определения палиндрома, сравнивая символы на симметричных позициях. s = "radar" is_palindrome = True for i in range(len(s) // 2): if s[i] != s[-i - 1]: is_palindrome = False break if is_palindrome: print("Это палиндром") else: print("Это не палиндром") 3. Использование функции Проверку на палиндром можно также реализовать с помощью рекурсивной функции. def is_palindrome(s): if len(s) < 2: return True if s[0] != s[-1]: return False return is_palindrome(s[1:-1]) 4. Определение палиндрома с учетом пробелов и знаков препинания Если вы хотите проверить, является ли строка палиндромом, игнорируя пробелы, знаки препинания и регистр, вы можете использовать методы lower() и replace(), а также функцию isalnum() для удаления всех небуквенных символов. s = "A man, a plan, a canal: Panama" s = ''.join(c for c in s if c.isalnum()).lower() if s == s[::-1]: print("Это палиндром") else: print("Это не палиндром") 5. Использование стека Этот подход использует структуру данных «стек», чтобы сохранить первую половину строки и затем сравнить ее с обратной половиной. def is_palindrome(s): s = ''.join(c for c in s if c.isalnum()).lower() stack = list() for character in s: stack.append(character) for character in s: if character != stack.pop(): return False return True Алгоритмы для поиска палиндромов Алгоритм поиска самой длинной подстроки-палиндрома АТАТА: распутываем задачу про палиндром

4. Проверка на анаграмму

Анаграмма — это перестановка букв одного слова для получения нового слова. 1. Решение без оптимизации Для начала рассмотрим простейший способ. Для каждой строки мы создадим словарь, который будет хранить количество вхождений каждого символа. Затем мы сравним словари и выясним, являются ли строки анаграммами. Вот как может выглядеть код для реализации данного алгоритма: def is_anagram(str1, str2): # создаем словарь для первого слова dict1 = {} for char in str1: dict1[char] = dict1.get(char, 0) + 1 # создаем словарь для второго слова dict2 = {} for char in str2: dict2[char] = dict2.get(char, 0) + 1 # сравниваем словари return dict1 == dict2 На этом решение задачи поиска анаграмм без оптимизации можно считать выполненной. Однако этот алгоритм не оптимален. 2. Оптимизация алгоритма Можно заметить, что мы используем два словаря для каждого слова. Это может быть неэффективно, особенно, если слова достаточно длинные. Вместо хранения двух словарей мы можем использовать один словарь и удалять из него ключи, которые мы уже нашли. После этого мы снова сравниваем словари. Если они равны, значит слова являются анаграммами. Вот как может выглядеть оптимизированный код: def is_anagram(str1, str2): # создаем словарь для первого слова dict1 = {} for char in str1: dict1[char] = dict1.get(char, 0) + 1 # проверяем второе слово for char in str2: if char in dict1: dict1[char] -= 1 if dict1[char] == 0: del dict1[char] else: return False # если словарь пуст, значит слова являются анаграммами return not dict1 Теперь код выглядит более эффективно, но он все еще имеет недостатки. 3. Более сложная оптимизация Работа с словарями может быть медленной, особенно если слова достаточно длинные. Мы можем использовать более продвинутые алгоритмы, чтобы ускорить этот процесс. Один из таких алгоритмов — это использование массивов. Мы можем создать два массива фиксированной длины, которые будут хранить количество букв в каждом слове. Затем мы можем проходить по каждой букве в обоих словах и увеличивать счетчики в массиве. По завершении прохода мы можем сравнить массивы. Если они равны, значит слова являются анаграммами. Вот как может выглядеть код для этого алгоритма: def is_anagram(str1, str2): # создаем массивы count1 = [0] * 26 count2 = [0] * 26 # заполняем массивы for char in str1: index = ord(char) - ord('a') count1[index] += 1 for char in str2: index = ord(char) - ord('a') count2[index] += 1 # сравниваем массивы return count1 == count2 Поиск анаграмм и сабанаграмм во всех словах языка

5. Подсчёт гласных в строке

Первый способ — использование цикла for string = "Привет, мир!" count = 0 for char in string: if char in "аеёиоуыэюяАЕЁИОУЫЭЮЯ": count += 1 print("Количество гласных букв:", count) #Количество гласных букв: 3 Второй способ — использование метода count() # Введите строку input_string = "Пример строки на русском языке" # Преобразуем строку к нижнему регистру, чтобы учитывать гласные в верхнем и нижнем регистре input_string = input_string.lower() # Определите гласные для русского языка vowels = "аеёиоуыэюя" # Используйте sum() и count() для подсчета количества каждой гласной vowel_count = sum(input_string.count(vowel) for vowel in vowels) # Выведите результат print(f"Количество гласных в строке: {vowel_count}") #Количество гласных в строке: 10 Третий способ — использование регулярных выражений import re string = "Привет, мир!" count = len(re.findall("[аеёиоуыэюяАЕЁИОУЫЭЮЯ]", string)) print("Количество гласных букв:", count) #Количество гласных букв: 3 Четвертый способ — использование генераторов списков string = "Привет, мир!" vowels = [char for char in string if char in "аеёиоуыэюяАЕЁИОУЫЭЮЯ"] count = len(vowels) print("Количество гласных букв:", count) #Количество гласных букв: 3

6. Проверка симметричности двоичного дерева

Постановка: Напишите функцию для проверки симметричности двоичного дерева. Примеры деревьев: Дерево 1: 1 / \ / \ 2 2 / \ / \ 3 4 4 3 Дерево 2: 1 / \ / \ 2 2 / \ / \ 3 5 6 3 Дерево 3: 1 / \ / \ 2 2 / \ 5 5 Первое и третье деревья симметричны, а второе – нет. Решение: В соответствии с условием симметричным деревом считается дерево, которое симметрично и с точки зрения структуры, и с точки зрения значений узлов. Чтобы проверить дерево на симметричность, можно создать его зеркальное отражение и сравнить его с оригиналом. Временная и пространственная сложность такого алгоритма – O(n), где n – число узлов. Проверку можно оптимизировать, если вместо создания отражения целого дерева сравнивать пары поддеревьев – временная сложность такого подхода O(n), а пространственная – O(h), где h – высота дерева: def is_tree_symmetric(tree): def check_symmetric(subtree_0, subtree_1): if not subtree_0 and not subtree_1: return True elif subtree_0 and subtree_1: return (subtree_0.data == subtree_1.data and check_symmetric(subtree_0.left, subtree_1.right) and check_symmetric(subtree_0.right, subtree_1.left)) return False return not tree or check_symmetric(tree.left, tree.right) Пример использования с заданными в условии деревьями: from collections import namedtuple Node = namedtuple('Node', ['data', 'left', 'right']) tree1 = Node(1, Node(2, Node(3, None, None), Node(4, None, None)), Node(2, Node(4, None, None), Node(3, None, None))) tree2 = Node(1, Node(2, Node(3, None, None), Node(5, None, None)), Node(2, Node(6, None, None), Node(3, None, None))) tree3 = Node(1, Node(2, Node(5, None, None), None), Node(2, None, Node(5, None, None))) for t in [tree1, tree2, tree3]: print(is_tree_symmetric(t)) Вывод: True False True Структуры данных: бинарные деревья. Часть 1 Бинарные деревья поиска и рекурсия – это просто

7. Метод двух указателей

Поддержи проект и получи доступ ко всему контенту всего за 290

8. Мемоизация и факториал

Поддержи проект и получи доступ ко всему контенту всего за 290

9. Последовательность Фибоначчи

Поддержи проект и получи доступ ко всему контенту всего за 290

10. Каррирование и частичное применение

Поддержи проект и получи доступ ко всему контенту всего за 290

11. Распаковка вложенных списков неопределенной глубины

Поддержи проект и получи доступ ко всему контенту всего за 290

12. FizzBuzz

Поддержи проект и получи доступ ко всему контенту всего за 290

13. Удалить лишние пробелы

Поддержи проект и получи доступ ко всему контенту всего за 290

14. Преобразование словаря в список

Поддержи проект и получи доступ ко всему контенту всего за 290

15. Проверить валидность скобок

Поддержи проект и получи доступ ко всему контенту всего за 290

16. Перевернуть каждое слово в предложении

Поддержи проект и получи доступ ко всему контенту всего за 290

17. Найти сумму двух чисел в массиве

Поддержи проект и получи доступ ко всему контенту всего за 290

18. Проверка на число Армстронга

Поддержи проект и получи доступ ко всему контенту всего за 290

19. Проверка на совершенное число

Поддержи проект и получи доступ ко всему контенту всего за 290

20. Найти среднее арифметическое списка чисел

Поддержи проект и получи доступ ко всему контенту всего за 290

21. Вывести первые N простых чисел

Поддержи проект и получи доступ ко всему контенту всего за 290

22. Найти НОК двух чисел

Поддержи проект и получи доступ ко всему контенту всего за 290

23. Найти НОД двух чисел

Поддержи проект и получи доступ ко всему контенту всего за 290

24. Перевести десятичное число в двоичное

Поддержи проект и получи доступ ко всему контенту всего за 290

25. Найти пересечение отрезков

Поддержи проект и получи доступ ко всему контенту всего за 290

26. Определить тип треугольника по длинам сторон

Поддержи проект и получи доступ ко всему контенту всего за 290

27. Определить, високосный ли год

Поддержи проект и получи доступ ко всему контенту всего за 290

28. Найти наименьшее из четырёх чисел

Поддержи проект и получи доступ ко всему контенту всего за 290

29. Проверка на арифметическую прогрессию

Поддержи проект и получи доступ ко всему контенту всего за 290

30. Пересчитать временной интервал в часы и минуты

Поддержи проект и получи доступ ко всему контенту всего за 290

31. Заполнение матрицы по спирали

Поддержи проект и получи доступ ко всему контенту всего за 290

32. Единственный выживший

Поддержи проект и получи доступ ко всему контенту всего за 290

33. Определение магического квадрата

Поддержи проект и получи доступ ко всему контенту всего за 290

34. Разделить список на подсписки

Поддержи проект и получи доступ ко всему контенту всего за 290

35. Ходы шахматного ферзя

Поддержи проект и получи доступ ко всему контенту всего за 290

36. Анонимное письмо

Поддержи проект и получи доступ ко всему контенту всего за 290

37. Кэш для операций над ISBN номерами

Поддержи проект и получи доступ ко всему контенту всего за 290

38. Гипотеза Коллатца

Поддержи проект и получи доступ ко всему контенту всего за 290

39. Решатель судоку

Поддержи проект и получи доступ ко всему контенту всего за 290

40. Интервалы занятости

Поддержи проект и получи доступ ко всему контенту всего за 290

41. Перевернуть число

Поддержи проект и получи доступ ко всему контенту всего за 290

42. Найти индекс первого вхождения

Поддержи проект и получи доступ ко всему контенту всего за 290

43. Алгоритм вычисления расстояния Дамерау-Левенштейна

Поддержи проект и получи доступ ко всему контенту всего за 290
Хочешь стать частью сообщества Девстанции?
Вступай в наш чат в Telegram

Также в этой категории

Шпаргалка
  34 вопроса

Шпаргалка по вопросам о Python

Вопросы для собеседования Python-разработчика

562 просмотра
От 30 января
Викторина
  26 вопросов

Викторина по Python - Junior

Вопросы на собеседовании по Python для Junior-позиции

54 просмотра
От 30 мая 2023
Викторина
  20 вопросов

Викторина по Django - Junior/Middle

Базовые вопросы с собеседования по Django

15 просмотров
От 2 июня 2023
Викторина
  12 вопросов

Викторина по Python - Middle/Senior

Продвинутые вопросы для собеседования Python-разработчика

22 просмотра
От 30 мая 2023

Вам может быть интересно

Шпаргалка
  11 вопросов

Теория шардинга баз данных

О распределении данных между серверами

243 просмотра
От 10 октября 2023
Шпаргалка
  54 вопроса

Шпаргалка по вопросам о Go

Вопросы про Go на собеседовании

513 просмотров
От 30 января
Шпаргалка
  7 вопросов

Коллекция полезных команд для Docker

Большая шпаргалка по всем командам Docker

200 просмотров
От 12 октября 2023
Шпаргалка
  17 вопросов

Шпаргалка по вопросам о C

Вопросы для собеседования Си-разработчика

182 просмотра
От 30 мая 2023
Задачник
  21 задача

Топ 20 задач с собеседований по Go

Алгоритмические задачи для собеседований Go-разработчиков

1910 просмотров
От 25 февраля
Шпаргалка
  60 вопросов

60 вопросов про базы данных и SQL

Вопросы и ответы с собеседования по базам данных и SQL

312 просмотров
От 20 февраля

Топ тредов

Gravatar for 9tokio
Tokio:
то что раньше было бесплатным теперь платное - вот это я понимаю

Последнее сообщение:
Логотип Девстанции
Девстанция:
Спасибо за поддержку проекта :) Повышение качества контента - один из важнейших приоритетов. Этому м...
3 сообщения
213 просмотров

Логотип Девстанции
Девстанция:
Поиск людей для совместной разработки IT-стартапов

Последнее сообщение:
В этом треде пока нет сообщений
0 сообщений
107 просмотров

Логотип Девстанции
Девстанция:
Какой язык программирования выбрать в качестве первого?

Последнее сообщение:
Gravatar for 2kokke
Kokke:
Python или JS - универсально. Но по уму надо бы с чего-то строгого начинать и достаточно низкоуровне...
1 сообщение
139 просмотров

Все категории