50 вопросов и ответов на собеседовании по Python

Практическая практика — лучший способ подготовиться к собеседованию по программированию. К счастью, большинство рекрутеров будут проверять одни и те же темы: общие знания языка, структуры данных, Big O и сортировка.

Сегодня мы поможет вам подготовиться к следующему собеседованию по Python с 50 наиболее часто задаваемыми вопросами на собеседовании.

Вот что мы рассмотрим сегодня:

  • Основы языка Python
  • Вопросы для собеседования по программированию на Python
  • Дальнейшие действия
Содержание
  1. Научитесь решать любые вопросы собеседования.
  2. Вопросы по основам языка Python
  3. Вопрос 1. В чем разница между списком и кортежем?
  4. Вопрос 2: Как бы вы преобразовали список в кортеж?
  5. Вопрос 3: В чем разница между массивом и списком?
  6. Вопрос 4: Как бы вы преобразовали список в массив?
  7. Вопрос 5: Как памятью управляет Python?
  8. Вопрос 6. Как добиться многопоточности в Python?
  9. Вопрос 7: Что такое «обезьянье исправление»?
  10. Вопрос 8: Что такое лямбда-функция? Приведите пример того, когда это полезно, а когда нет.
  11. Вопрос 9: Что такое травление и распаковка?
  12. Вопрос 10: Какие преимущества массивы NumPy предлагают перед (вложенные) списки Python?
  13. Вопрос 11: Объясните наследование в Python на примере
  14. Вопрос 12: что такое полиморфизм в Python?
  15. Вопрос 13: объясните разницу между range () и xrange ()
  16. Вопрос 14: Объясните различия между Flask и Django
  17. Вопрос 15: Что такое PYTHONPATH?
  18. Вопрос 16: Что такое PEP 8?
  19. Вопрос 17: Что такое декораторы Python?
  20. Вопрос 18: Что такое init?
  21. Вопрос 19: Что такое тернарный оператор?
  22. Вопрос 20: что такое глобальные и локальные переменные в Python?
  23. Вопрос 21: Что такое @ свойство в Python?
  24. Вопрос 22: Как используется ли try/except в Python?
  25. Вопрос 23: Объясните различия между Python 2 и Python 3
  26. Вопрос 24: Что такое метод соединения в Python?
  27. Продолжайте обучение.
  28. Вопрос 25: Что такое понимание словаря?
  29. Вопрос 26: Как сделать глубокую копию в Python?
  30. Вопрос 27: Как бы вы проверили наличие ключа? sts в словаре Python?
  31. Вопрос 28: Как добиться мемоизации в Python?
  32. Вопрос 29: Как бы вы отсортировали словарь в Python?
  33. Вопрос 30: Как и когда вы будете использовать any () и all ()?
  34. Вопрос 31: Что такое строка документации Python?
  35. Вопрос 32: напишите функцию Python и объясните, что продолжается.
  36. Вопрос 33 : Объясните разницу между генератором и итератором в Python.
  37. Вопрос 34: что такое defaultdict в Python?
  38. Вопрос 35: Что такое модули Python?
  39. Вопросы на собеседовании по программированию на Python
  40. Вопрос 36: Переверните строку в Python
  41. Вопрос 37: проверьте, содержит ли строка Python другую строку
  42. Вопрос 38: Реализуйте поиск по ширине (BFS) в Python
  43. Вопрос 39: Реализуйте поиск по глубине (DFS) в Python
  44. Вопрос 40 : Реализация подстановочных знаков в Python
  45. Вопрос 41: Реализуйте сортировку слиянием в Python
  46. Вопрос 42: Реализуйте алгоритм Дейкстры в Python
  47. Вопрос 43: Объединить два отсортированных списка
  48. Вопрос 44: Найдите два числа, которые в сумме дают «k»
  49. Вопрос 45: Найдите первое неповторяющееся целое число в списке
  50. Вопрос 46: Найдите среднее значение связанного списка
  51. Вопрос 47: Обратить первые k элементов очереди
  52. Вопрос 48: Найдите высоту двоичного дерева поиска (BST)
  53. Вопрос 49: преобразовать максимальную кучу в минимальную кучу
  54. Вопрос 50: Обнаружить цикл в связанном списке
  55. Дальнейшие действия
  56. Продолжайте читать о Python и подготовке к собеседованию

Научитесь решать любые вопросы собеседования.

Отточите свои навыки собеседования с помощью практических проектов и практических задач

Расшифруйте собеседование по кодированию на Python: примеры из реальной жизни

Вопросы по основам языка Python

Вопрос 1. В чем разница между списком и кортежем?

Список Кортеж
Список состоит из изменяемых объектов. (Объекты, которые можно изменить после создания) Кортеж состоит из неизменяемых объектов. (Объекты, которые не могут измениться после создания)
У списка большой объем памяти. У кортежа мало памяти.
Список хранится в двух блоках памяти (один имеет фиксированный размер, а другой — переменный размер для хранения данных) Кортеж сохраняется в одном блоке памяти.
Создание списка происходит медленнее, поскольку требуется доступ к двум блокам памяти. Создание кортеж быстрее, чем создание списка.
Элемент в списке можно удалить или заменить. Элемент в кортеж нельзя удалить или заменить.
В списке есть данные, хранящиеся в скобках []. Например, [1,2,3] В кортеже данные хранятся в скобках (). Например, (1,2,3)

Когда использовать каждый:

Кортеж следует использовать всякий раз, когда пользователь знает, что вставлено в кортеж. Предположим, что колледж хранит информацию о своих студентах в структуре данных; чтобы эта информация оставалась неизменной, ее следует хранить в кортеже.

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

Вопрос 2: Как бы вы преобразовали список в кортеж?

 my_list = [50, «Двадцать», 110, «Пятьдесят»,  «Десять», 20, 10, 80, «Восемьдесят»] my_tuple = (my_list [0], my_list [len (my_list) - 1], len (my_list)) print (my_tuple) 

Все, что нам нужно сделать, это создать кортеж из трех элементов. Первый элемент кортежа — это первый элемент списка, который можно найти с помощью my_list [0] .

Второй элемент кортежа — это последний элемент в списке. my_list [len (my_list) - 1] предоставит нам этот элемент. Мы также могли бы использовать метод pop () , но это изменило бы список.

Вопрос 3: В чем разница между массивом и списком?

List Array
Списки Python очень гибкие и могут содержать произвольные данные. Массивы Python — это просто тонкая оболочка для массивов C.
Списки являются частью синтаксиса Python, поэтому их не нужно объявлять в первую очередь. Массивы необходимо сначала импортировать или объявить из других библиотек (например, numpy).
Списки также можно быстро изменить размер за определенное время — эффективным способом. Это связано с тем, что Python инициализирует некоторые дополнительные элементы в списке при инициализации. Размер массивов изменить нельзя. Вместо этого значения массива необходимо будет скопировать в другой массив большего размера.
Списки могут содержать разнородные данные. Массивы могут хранить только однородные данные. У них есть значения с одинаковыми типами данных.
Математические функции нельзя напрямую применять к спискам. Вместо этого их нужно применять индивидуально к каждому элементу. Массивы специально оптимизированы для арифметических вычислений.
Списки потребляют больше памяти, так как им выделяется несколько дополнительных элементов для более быстрого добавления элементов. Поскольку массивы остаются того же размера, что и при первой инициализации, они компактны.

Вопрос 4: Как бы вы преобразовали список в массив?

Во время программирования будут случаи, когда вам нужно будет преобразовать существующие списки в массивы, чтобы выполнять с ними определенные операции (массивы позволяют выполнять математические операции с ними так, как списки не делают).

Здесь мы будем использовать numpy.array () . Эта функция библиотеки numpy принимает список в качестве аргумента и возвращает массив, содержащий все элементы списка.. См. Пример ниже:

 import numpy as npmy_list = [2,4,6,8,10] my_array = np.array (my_list) # печать my_arrayprint my_array # печать типа my_arrayprint type (my_array) 

Вопрос 5: Как памятью управляет Python?

  1. Управление памятью в python управляется частным пространством кучи Python. Все объекты и структуры данных Python находятся в частной куче. У программиста нет доступа к этой частной куче. Вместо этого об этом позаботится интерпретатор python.
  2. Выделение пространства кучи для объектов Python выполняется диспетчером памяти Python. Базовый API предоставляет программисту доступ к некоторым инструментам для программирования.
  3. Python также имеет встроенный сборщик мусора, который перерабатывает всю неиспользуемую память и делает ее доступной для пространства кучи.

Вопрос 6. Как добиться многопоточности в Python?

  1. У Python есть многопоточный пакет, но если вы хотите использовать многопоточность для ускорения кода, то, как правило, использовать его не рекомендуется.
  2. У Python есть конструкция под названием Global Блокировка переводчика (GIL). GIL гарантирует, что только один из ваших «потоков» может выполняться одновременно. Поток получает GIL, выполняет небольшую работу, затем передает GIL следующему потоку.
  3. Это происходит очень быстро, поэтому человеческому глазу может показаться, что ваши потоки выполняются параллельно, но на самом деле они просто по очереди используют одно и то же ядро ​​ЦП.
  4. Вся эта передача GIL увеличивает накладные расходы на выполнение. Это означает, что если вы хотите, чтобы ваш код работал быстрее, то использование пакета потоковой передачи часто не является хорошей идеей.

Вопрос 7: Что такое «обезьянье исправление»?

В Python термин обезьяний патч относится только к динамическим модификациям класса или модуля во время выполнения.

Вопрос 8: Что такое лямбда-функция? Приведите пример того, когда это полезно, а когда нет.

Лямбда-функция — это небольшая анонимная функция, которая возвращает объект.

Лямбда-функция возвращает объект. обычно присваивается переменной или используется как часть других более крупных функций.

Вместо обычного ключевого слова def, используемого для создания функций, лямбда-функция определяется с помощью лямбда-выражения ключевое слово.

Назначение лямбда-выражений

Лямбда-выражение гораздо более читабельно, чем полная функция, поскольку оно может быть написано в строке. Следовательно, рекомендуется использовать лямбда-выражения, когда выражение функции маленькое.

Прелесть лямбда-функций заключается в том, что они возвращают функциональные объекты. Это делает их полезными при использовании с такими функциями, как map или filter , которым требуются объекты функций в качестве аргументов.

Лямбда-выражения не являются полезно, когда выражение превышает одну строку.

Вопрос 9: Что такое травление и распаковка?

Модуль Pickle принимает любой объект Python и преобразует его в строковое представление и выгружает его в файл с помощью функции дампа, этот процесс называется травлением. Хотя процесс извлечения исходных объектов Python из сохраненного строкового представления называется распаковкой.

Вопрос 10: Какие преимущества массивы NumPy предлагают перед (вложенные) списки Python?

  1. Списки Python являются эффективными контейнерами общего назначения. Они поддерживают (довольно) эффективную вставку, удаление, добавление и конкатенацию, а понимание списков Python упрощает их создание и управление.
  2. У них есть определенные ограничения: они не поддерживают «векторизованные» операции например, поэлементное сложение и умножение, и тот факт, что они могут содержать объекты разных типов, означает, что Python должен хранить информацию о типе для каждого элемента и должен выполнять код диспетчеризации типов при работе с каждым элементом.
  3. NumPy не просто более эффективен; это тоже удобнее. Вы получаете бесплатно множество векторных и матричных операций, которые иногда позволяют избежать ненужной работы. И они также эффективно реализованы.
  4. Массив NumPy работает быстрее, и вы получаете много встроенных функций с NumPy, БПФ, свертками, быстрым поиском, базовой статистикой, линейной алгеброй, гистограммами и т. Д.

Вопрос 11: Объясните наследование в Python на примере

Наследование позволяет Одному классу получить все члены (например, атрибуты и методы) другого класса. Наследование обеспечивает возможность повторного использования кода, упрощает создание и поддержку приложения. Класс, от которого мы наследуем, называется суперклассом, а наследуемый класс называется производным/дочерним классом.

Это разные типы наследования, поддерживаемые Python:

  1. Единое наследование — когда производный класс получает члены единственного суперкласса.
  2. Многоуровневое наследование — производный класс d1 унаследован от базового класса base1, и d2 наследуются от base2.
  3. Иерархическое наследование — от одного базового класса вы можете наследовать любое количество дочерних классов
  4. Множественное наследование — производный класс наследуется от нескольких чем один базовый класс.

Вопрос 12: что такое полиморфизм в Python?

Полиморфизм означает способность принимать разные формы. Так, например, если родительский класс имеет метод с именем ABC, тогда у дочернего класса также может быть метод с тем же именем ABC, имеющий свои собственные параметры и переменные. Python допускает полиморфизм.

Вопрос 13: объясните разницу между range () и xrange ()

По большей части xrange и range идентичны с точки зрения функциональности. Оба они предоставляют способ сгенерировать список целых чисел, который вы будете использовать. Единственное отличие состоит в том, что range возвращает объект списка Python, а xrange возвращает объект xrange.

Это означает, что xrange на самом деле не создает статический список во время выполнения, как range. Он создает ценности по мере необходимости с помощью специальной техники, называемой уступкой. Этот метод используется с типом объектов, известных как генераторы.

Вопрос 14: Объясните различия между Flask и Django

Django — это веб-фреймворк Python, который предлагает высокоуровневый фреймворк с открытым исходным кодом, который «способствует быстрой разработке и чистому, прагматичному дизайну». Это быстро, безопасно и масштабируемо. Django предлагает сильную поддержку сообщества и подробную документацию.

Фреймворк — это всеобъемлющий пакет, в котором вы получаете панель администратора, интерфейсы базы данных и структуру каталогов прямо при создании приложения. Кроме того, он включает в себя множество функций, поэтому вам не нужно добавлять отдельные библиотеки и зависимости. Некоторые функции, которые он предлагает, включают аутентификацию пользователя, механизм создания шаблонов, маршрутизацию, миграцию схемы базы данных и многое другое.

Фреймворк Django невероятно гибок, и вы можете работать с MVP для более крупных компаний. С некоторой точки зрения, некоторые из крупнейших компаний, использующих Django, — это Instagram, Dropbox, Pinterest и Spotify.

Flask считается микрофреймворком, который представляет собой минималистичный веб-фреймворк. В нем меньше «батарейки», что означает, что ему не хватает многих функций и функций, которые предлагают полнофункциональные фреймворки, такие как Django, таких как механизм веб-шаблонов, авторизация учетной записи и аутентификация.

Flask является минималистичным и легким, что означает, что вы добавляете расширения и библиотеки, которые вам нужны, по мере написания кода, не предоставляя их автоматически фреймворком. Философия Flask заключается в том, что он предоставляет только те компоненты, которые вам нужны для создания приложения, чтобы у вас была гибкость и контроль. Другими словами, это безоговорочно. Некоторые функции, которые он предлагает, — это встроенный сервер разработки, диспетчеризация запросов Restful, обработка HTTP-запросов и многое другое.

Вопрос 15: Что такое PYTHONPATH?

Это переменная среды, которая используется при импорте модуля. Всякий раз, когда модуль импортируется, PYTHONPATH также просматривается, чтобы проверить наличие импортированных модулей в различных каталогах. Интерпретатор использует его, чтобы определить, какой модуль загрузить..

Вопрос 16: Что такое PEP 8?

PEP расшифровывается как Python Enhancement Proposal. Это набор правил, которые определяют, как форматировать код Python для максимальной читаемости.

Вопрос 17: Что такое декораторы Python?

Декоратор — это шаблон проектирования в Python, который позволяет пользователю добавлять новые функции к существующему объекту без изменения его структуры. Декораторы обычно вызываются перед определением функции, которую вы хотите украсить.

Вопрос 18: Что такое init?

__ init__ — это метод или конструктор в Python. Этот метод автоматически вызывается для выделения памяти при создании нового объекта/экземпляра класса. Все классы имеют метод __ init__ .

Вопрос 19: Что такое тернарный оператор?

Тернарный оператор — это способ написания условных операторов в Python. Как следует из названия, этот оператор Python состоит из трех операндов.

Примечание. Тернарный оператор можно рассматривать как упрощенную однострочную версию if-else оператор для проверки условия.

Три операнда в тернарном операторе включают:

  • условие: Логическое выражение, которое принимает значение true или false.
  • true_val : значение, которое присваивается, если выражение оценивается как истинное.
  • false_val : значение, которое должно быть присвоено, если выражение оценивается как ложное.
  var = true_val if condition else false_val  

Переменная var в левой части оператора = (присваивание) будет присвоено:

  • value1 , если логическое выражение принимает значение true .
  • value2 , если логическое Выражение принимает значение false.
 # ИСПОЛЬЗОВАНИЕ ТЕРНАРНОГО ОПЕРАТОРАto_check = 6msg = "Даже" если  to_check% 2 == 0 else "Odd" print (msg) # ИСПОЛЬЗОВАНИЕ USUAL IF-ELSEmsg = "" if (to_check% 2 == 0): msg = "Even" else: msg = "Odd" print (msg) 

Объяснение

Приведенный выше код использует тернарный оператор, чтобы определить, является ли число четным или нечетным..

  • msg будет назначено «даже», если условие (to_check% 2 == 0) равно true .
  • msg будет назначено «нечетное», если условие (to_check% 2 == 0) равно false .

Вопрос 20: что такое глобальные и локальные переменные в Python?

Глобальные переменные:

Переменные, объявленные вне функции или в глобальном пространстве, называются глобальными переменными. Доступ к этим переменным может получить любая функция в программе.

Локальные переменные:

Любая переменная, объявленная внутри функции, известна как локальная переменная. Эта переменная присутствует в локальном пространстве, а не в глобальном.

Вопрос 21: Что такое @ свойство в Python?

@property — это декоратор. В Python декораторы позволяют пользователям использовать класс таким же образом (независимо от изменений, внесенных в его атрибуты или методы). Декоратор @property позволяет обращаться к функции как к атрибуту.

Вопрос 22: Как используется ли try/except в Python?

Исключением является ошибка, возникающая во время выполнения программы. Когда возникает эта ошибка, программа останавливается и генерирует исключение, которое затем обрабатывается, чтобы предотвратить сбой программы.

Исключения, сгенерированные программой, перехватываются в блок try и обрабатывается в блоке except .

  • Попробуйте : Позволяет проверить блок кода на наличие ошибок.

  • Except : позволяет обработать ошибку.

Вопрос 23: Объясните различия между Python 2 и Python 3

Python 2 Python 3
Кодировка строк
Python 2 хранит их как ASCII. Юникод является надмножеством ASCII и, следовательно, может кодировать больше символов, включая иностранные.
String Encoding
Python 3 по умолчанию сохраняет строки как Unicode .
Деление
Деление Python 2 применяет функцию пола к десятичному выводу и возвращает целое число. Таким образом, деление 5 на 2 вернет floor (2.5) = 2.
Division
Деление в Python 3 возвращает ожидаемый результат, даже если он находится в десятичном формате.
Печать
Python 2 не требует скобок.
Печать
Синтаксис оператора печати отличается в Python 2 и 3. Python 3 требует скобок вокруг того, что должно быть напечатано.
Библиотеки
Многие старые библиотеки были созданы специально для Python 2 и не имеют «прямой совместимости».
Библиотеки
Некоторые новые библиотеки созданы специально для Python 3 и не работают с Python 2.

Python 2 настолько прочно закрепился в программном ландшафте, что взаимозависимость между несколькими программами делает практически невозможным переход.

Вопрос 24: Что такое метод соединения в Python?

Соединение в Python принимает элементы повторяющейся структуры данных и соединяет их вместе с помощью определенного значения строкового соединителя.

Как работает join ?

Метод соединения в Python — это строковый метод, который соединяет элементы строковой итерируемой структуры, которая также содержит строки или символы (массив, список и т. д.), с помощью конкретная строка в качестве соединителя.

Пример: соединение элементов с помощью пустой строки

Это объединит элементы в массиве с помощью пустой строки между каждым элементом.

 array = ['H', 'E', 'L', 'L', 'O'] connector = "" connected_string = connector.join (массив) print (connected_string) 

Продолжайте обучение.

Практикуйте самые распространенные вопросы на собеседовании по Python и наблюдайте, как растет ваша уверенность. Текстовые курсы Educative легко просматривать, и они содержат живую среду программирования в браузере, что делает обучение быстрым и эффективным.

Расшифруйте собеседование по кодированию в Python: Real -Мировые примеры

Вопрос 25: Что такое понимание словаря?

Понимание словаря — это один из способов создания словаря в Python. Он создает словарь путем слияния двух наборов данных, которые находятся в форме списков или массивов.

Данные одного из двух списков/массивов будут действовать как ключи словаря, в то время как данные второго списка/массива будут действовать как значения. Каждый ключ действует как уникальный идентификатор для каждого значения, поэтому размер обоих списков/массивов должен быть одинаковым.

Здесь мы рассмотрим простое слияние:

Простое объединение — это объединение или объединение двух списков без каких-либо ограничений. Другими словами, это безусловное слияние.

Общий синтаксис следующий:

Следующий пример выполняется для базы данных колледжа и использует простое слияние. Представьте себе, что есть база данных колледжа, в которой хранится множество данных. Например, адрес студента, оценки, раздел, сборы, номер списка и т. Д. Теперь нам нужно уникально идентифицировать каждого ученика и создать новый словарь, в котором будут храниться только все ученики. Наше решение просто зависит от двух вопросов:

  • Что должно быть ключом?
  • Какое должно быть значение?

Здесь мы выберем номера рулонов в качестве ключа и имена в качестве значения, потому что номера рулонов уникальны, а имена могут повторяться. Итак, число выпадения Алекса — 122, поэтому кортеж будет выглядеть как 122: Alex. Это будет лучше объяснено, когда вы попробуете приведенный ниже код.

 rollNumbers = [122,233,353,456] names = ['alex', 'bob', 'can', 'don'] NewDictionary = {i: j for (i, j) in zip  (rollNumbers, names)} print (NewDictionary) 

Вопрос 26: Как сделать глубокую копию в Python?

Глубокая копия относится к клонированию объекта. Когда мы используем оператор =, мы не клонируем объект; вместо этого мы ссылаемся на нашу переменную на тот же объект (также известную как мелкая копия).

Это означает, что изменение значения одной переменной влияет на значение другой переменной, поскольку они ссылаются (или указывают) на один и тот же объект. Это различие между мелкой и глубокой копией применимо только к объектам, которые содержат другие объекты, например списки и экземпляры класса.

Метод

Чтобы сделать глубокую копию (или клон) объекта, мы импортируем встроенный модуль copy в Python. В этом модуле есть метод deepcopy () , который упрощает нашу задачу.

Синтаксис

Эта функция принимает в качестве единственного аргумента объект, который мы хотим клонировать, и возвращает клон.

Синтаксис копии. deepcopy ()

неглубокий копировать

глубокая копия

 import copy # Использование  '=' operatorx = [1, 2, 3] y = xx [0] = 5 # значение 'y' также изменяется, поскольку это ЖЕ объект x [1] = 15print "Shallow copy:", y # Использование копии.  deepcopy () a = [10, 20, 30] b = copy.deepcopy (a) a [1] = 70 # значение 'b' НЕ изменяется, потому что это ДРУГОЙ отпечаток объекта "Deep copy:", b 

Вопрос 27: Как бы вы проверили наличие ключа? sts в словаре Python?

Это безопасная практика — проверить, существует ли ключ в словаре, до извлечения значения этого ключа. Для этой цели Python предлагает две встроенные функции:

  • has_key ()

Метод has_key возвращает истину, если данный ключ доступен в словаре; в противном случае возвращается false.

 Fruits = {'a': «Яблоко», 'b': «Банан», 'c': «Морковь»} key_to_lookup = 'a'if Fruits.has_key (key_to_lookup): print «Ключ существует»  else: print «Ключ не существует» 

  • инструкция if-in

В этом подходе используется инструкция if-in для проверки наличия или в словаре не существует данного ключа.

 Фрукты  = {'a': «Яблоко», 'b': «Банан», 'c': «Морковь»} key_to_lookup = 'a'if key_to_lookup в Fruits: print «Ключ существует» else: print «Ключ не существует»  

Вопрос 28: Как добиться мемоизации в Python?

Рассмотрим этот дорогостоящий в вычислительном отношении код:

  # Fibonacci Numbersdef fib (num)  : if num == 0: return 0 elif num == 1: return 1 return fib (num - 1) + fib (n - 2)  

Запоминание может быть достигнуто через Python декораторы

Вот полная реализация.

 import timeitdef memoize_fib (func): cache = {} def inner (arg): if arg not in cache: cache [arg] = func (arg) return cache [arg] return internal def fib (  num): if num == 0: return 0 elif num == 1: return 1 else: return fib (num-1) + fib (num-2) fib = memoize_fib (fib) print (timeit.timeit ('fib (  30) ', globals = globals (), number = 1)) print (timeit.timeit (' fib (30) ', globals = globals (), number = 1)) print (timeit.timeit (' fib (30)  ', globals = globals (), number = 1)) 

Вопрос 29: Как бы вы отсортировали словарь в Python?

Мы можем отсортировать этот тип данных по ключу или значение, и это делается с помощью функции sorted ().

Во-первых, нам нужно знать, как получить данные из словаря для передачи этой функции.

Есть два основных способа получить данные из словаря:

Dictionary.keys (): возвращает только ключи в произвольном порядке. Dictionary.values ​​(): возвращает список значений. Dictionary.items (): возвращает все данные в виде списка пар ключ-значение.

Синтаксис Sorted () Этот метод принимает один обязательный и два необязательных аргумента:

Данные (обязательные): данные для сортировки. Мы передадим данные, которые мы получили, используя один из вышеуказанных методов.

Ключ (необязательно): функция (или критерии), на основе которых мы хотели бы отсортировать список. Например, критерием может быть сортировка строк по их длине или любая другая произвольная функция. Эта функция применяется к каждому элементу списка, и полученные данные сортируются.. Если оставить его пустым, список будет отсортирован по исходным значениям.

Обратный (необязательно): установка для третьего параметра значения true будет отсортировать список в порядке убывания. Оставляя это пустым, сортируем в порядке возрастания.

  • keys ()
  • keys ()
  • keys ()
  • values ​​()
  • values ​​()
  • items ()
  • items ()
 dict = {} dict ['1'] = 'apple'dict [' 3 '] =' оранжевый '  dict ['2'] = 'pango'lst = dict.keys () # Сортировано по отпечатку («Сортировано по ключу:», отсортировано (lst)) 

Вопрос 30: Как и когда вы будете использовать any () и all () ?

Что такое any () ?

any () — это функция, которая принимает итерируемый объект (например, список, кортеж, набор и т. д.) и возвращает True , если какой-либо из элементов оценивается как True , но возвращает False , если все элементы оцениваются как False .

Передача итерации в any () для проверки, является ли какой-либо из элементов True можно сделать так:

 one_truth = [True, False, False] three_lies = [0, '', None] print (any (one_truth)) print (any (three_lies)) 

Первый оператор печати выводит True , потому что один из элементов в one_truth равен True .

С другой стороны, второй оператор печати печатает False , поскольку ни один из элементов не является True , т. Е. Все элементы являются False .

Используйте any () , когда вам нужно проверить длинную серию условий или .

Что такое all()?

all () — еще одна функция Python, которая принимает итерацию и возвращает True , если все элементы оцениваются как True , но в противном случае возвращает False .

Аналогично any () , all () принимает список, кортеж, набор или любую итерацию, например:

 all_true = [True, 1, 'a', object ()] one_true = [True, False, False, 0] all_false = [Нет,  '', False, 0] print (all (all_true)) print (all (one_true)) print (all (all_false)) 

Первый вызов функции вернул True , потому что all_true был заполнен истинными значениями.

Передача one_true to all () вернул False , потому что список содержал одно или несколько ложных значений.

Наконец, передача all_false в all () возвращает False , поскольку он также содержит одно или несколько ложных значений.

Используйте all () , когда вам нужно проверить длинную серию условий и .

Вопрос 31: Что такое строка документации Python?

Строки документации Python предоставляют подходящий способ связывания документации с:

  • модули Python
  • функции Python
  • классы Python

Это указанный документ для написанного кода. В отличие от обычных комментариев кода, исправление должно описывать то, что функция делает, а не то, как она работает.

Доступ к строке документации можно получить с помощью

  • __ doc__ метод объекта
  • help функция

Пример

 def hello_world (): "" "Демонстрация строки документации." "" return None # печать с использованием метода __doc__ print "Использование метода __doc__:" print hello_world .__ doc__ # печать с использованием функции справки print "Использование функции справки:" help (  hello_world) 

Вопрос 32: напишите функцию Python и объясните, что продолжается.

Вот наша функция:

 def Examplefunc (str): # функция, которая выводит параметр str print "The value is", str # в этой функции не требуется инструкция возврата def Multiply (x, y): #function  который вычисляет произведение x и y return x * y # возвращение произведения x и y # Вызов функции Examplefunc (9) # 9, переданной в качестве параметра) answer = Multiply (4,2) # 4 и 2 переданы как параметры print  «Произведение x и y равно:», ответ 

Объяснение

Приведенная выше функция Examplefunc принимает переменную str в качестве параметра, а затем при nts это значение. Поскольку он только печатает значение, нет необходимости в команде возврата.

Функция Multiply принимает два параметра x и y в качестве параметров. Затем он вычисляет продукт и использует оператор return , чтобы вернуть ответ.

Вопрос 33 : Объясните разницу между генератором и итератором в Python.

Итератор в Python служит держателем для объектов, чтобы их можно было повторять; генератор упрощает создание настраиваемого итератора.

Отдельно Из очевидных синтаксических различий следует отметить некоторые важные отличия:

Generator Iterator
Реализовано с использованием функции. Реализовано с использованием класса.
Использует ключевое слово yield . Не использует ключевое слово yield .
Результатом использования является сжатый код. Использование приводит к относительно менее сжатому коду.
Сохраняются все локальные переменные до операторов yield . Локальные переменные не используются.

Impl создание итератора

 # Функция для генерации всех неотрицательных чисел # до заданного неотрицательного числа. class UpTo: # присвоение параметру значения по умолчанию 0 def __init __ (self, max = 0): self.  max = max def __iter __ (self): self. n = 0 return self def __next __ (self): # Следующий метод вызовет # исключение при достижении условия завершения.  if self.n> self.max: поднять StopIteration else: result = self.n self.n + = 1 вернуть результат для числа в UpTo (5): print (number) 

Реализация генератора

 # Функция для генерации всех неотрицательных чисел # до  заданный неотрицательный numberdef upto (n): for i in range (n + 1): # Оператор yield - это то, что делает функцию # генератором yield ifor number в upto (5): print (number) 

Вопрос 34: что такое defaultdict в Python?

Словарь Python, dict , содержит слова и значения, а также пары ключ-значение любого типа данных. defaultdict — это еще одно подразделение встроенного класса dict .

Как обстоят дела defaultdict другой?

defaultdict является подразделением класса dict . Его важность заключается в том, что он позволяет каждому новому ключу присваивать значение по умолчанию в зависимости от типа создаваемого словаря.

Может быть создан defaultdict давая свое объявление, аргумент, который может иметь три значения; list, set или int. В соответствии с указанным типом данных создается словарь, и когда любой ключ, который не существует в defaultdict , добавлен или доступен, ему присваивается значение по умолчанию, а не предоставление KeyError .

Пример

В первом фрагменте кода ниже показан простой словарь и показано, как при доступе к ключу, которого нет в dict, возникает ошибка.

 dict_demo = dict () print (dict_demo [3]) 

Теперь давайте представим defaultdict и посмотрим, что произойдет.

 из  коллекции import defaultdictdefaultdict_demo = defaultdict (int) print (defaultdict_demo [3]) 

В этом случае мы передали int как тип данных в defaultdict . Следовательно, любому ключу, который еще не существует в defaultdict_demo , будет присвоено значение 0, если для него не определено значение.

Примечание. Вы также можете использовать set или list в качестве параметров

Вопрос 35: Что такое модули Python?

Модуль Python — это файл Python, содержащий набор функций и переменных, которые будут использоваться в приложении. Переменные могут быть любого типа (массивы, словари, объекты и т. Д.)

Модули могут быть либо:

  1. Встроенный

  2. Пользовательский

Преимущества модулей в Python

Создание и использование модуля в Python дает несколько ключевых преимуществ:

  • Структурированный код

    • Код логически организован и сгруппирован в один файл Python, что упрощает разработку и снижает вероятность ошибок.
    • Код проще для понимания и использовать.
  • Возможность повторного использования

    • Функциональность, определенная в одном модуле, может быть легко повторно использована другие части приложения. Это избавляет от необходимости воссоздавать повторяющийся код.

Вопросы на собеседовании по программированию на Python

В этом разделе мы рассмотрим общие вопросы собеседования по кодированию, которые относятся к спискам, связанным спискам. , графики, деревья, многопоточность/параллелизм и многое другое.

Давайте углубимся.

Вопрос 36: Переверните строку в Python

Давайте перевернем строку «Python», используя метод нарезки.

Чтобы перевернуть строку, мы просто создаем фрагмент, который начинается с длины строки и заканчивается индексом 0.

Чтобы перевернуть строку с помощью нарезки, напишите:

  stringname [stringlength :: - 1]  # метод 1  

Или напишите без указания длины строки:

  stringname [:: - 1] # method2  

Оператор slice означает начало с длиной строки, конец в позиции 0, перемещение с помощью шаг -1 (или один шаг назад).

 str  = "Python" # начальная строка stringlength = len (str) # вычислить длину списковlicedString = str [stringlength :: - 1] # разрезать print (sledString) # распечатать перевернутую строку 

Это всего лишь один способ перевернуть строку в Python. Два других известных метода — это цикл и использование соединения.

Вопрос 37: проверьте, содержит ли строка Python другую строку

Есть несколько способов проверить это. В этой публикации мы рассмотрим метод find .

Метод find проверяет, содержит ли строка подстроку . Если это так, метод возвращает начальный индекс подстроки в строке; в противном случае возвращается -1.

Общий синтаксис:

  string.find (substring)  

 a_string = "Программирование на Python"  substring1 = "Программирование" substring2 = "Language" print ("Проверить, содержит ли" + a_string + "+ substring1 +": ") print (a_string.find (substring1)) print (" Проверить, содержит ли "+ a_string +" + substring2 + "  : ") print (a_string.find (substring2)) 

Два других известных метода проверки, содержит ли строка другую строку, — это использование оператора в или использование метода count .

Вопрос 38: Реализуйте поиск по ширине (BFS) в Python

Рассмотрим график, который реализован в приведенном ниже коде:

 graph = {'A': ['B', 'C'], 'B': ['D'  , 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': []} loaded = [] # Список для отслеживания  посещенные узлы.queue = [] # Инициализировать queuedef bfs (посещенный, граф, узел): посещенный.append (узел) queue.append (узел) while queue: s = queue.pop (0) print (s, end = "  ") для соседа в графе [ах]: если сосед не в очереди посещенных: посещено.append (сосед). append (сосед) # Код драйвера bfs (посещено, граф, 'A') 

Строки 3–10: Иллюстрированный график представлен с использованием списка смежности. Простой способ сделать это в Python — использовать структуру данных словаря, где каждая вершина имеет сохраненный список своих соседних узлов.

Строка 12: посещенные — это список, который используется для отслеживания посещенных узлов.

Строка 13: очередь — это список, который используется для отслеживания узлов, находящихся в настоящее время в очереди.

Строка 29: аргументы bfs — это список посещенных , график в виде словаря и начальный узел A .

Строки 15-26: bfs следует алгоритму, описанному выше:

  1. Проверяет и добавляет начальный узел в список посещенных и в очередь .
  2. Затем, пока очередь содержит элементы, она продолжает извлекать узлов из очереди, добавляет соседей этого узла в очередь, если они не были посещены, и отмечает их как посещенные.
  3. Этот недостаток сохраняется до тех пор, пока очередь не станет пустой.

Сложность времени

Поскольку все узлы и вершины посещаются , временная сложность для BFS на графе равна O (V + E); где V — количество вершин, а E — количество ребер.

Вопрос 39: Реализуйте поиск по глубине (DFS) в Python

Рассмотрим этот график, реализованный в приведенном ниже коде:

 # Использование словаря Python в качестве списка смежностиgraph = {'A': ['B', 'C'], 'B': ['  D ',' E '],' C ': [' F '],' D ': [],' E ': [' F '],' F ': []} visit = set () # Установить на  отслеживать посещенные узлы. def dfs (посещенный, граф, узел): если узел не в посещенном: печать (узел) посещен. добавить (узел) для соседа в графе [узел]: dfs (посещено, граф, сосед) # Driver Codedfs (посещено, граф, 'A') 

Объяснение

Строки 2-9: Иллюстрированный граф представлен с использованием списка смежности — простой способ сделать это в Python — использовать структуру данных словаря. У каждой вершины хранится список соседних узлов.

Строка 11: посещено — это набор, который используется для сохранения отслеживание посещенных узлов.

Строка 21: вызывается функция dfs , которой передается посещенный установите, график в виде словаря и A , который является начальным узлом.

Строки 13-18: dfs следует алгоритму, описанному выше:

  1. Сначала проверяется, текущий узел не посещается — если да, он добавляется в набор посещенный .
  2. Затем для каждого соседа текущего узла dfs функция вызывается снова.
  3. Базовый случай вызывается при посещении всех узлов. Затем функция возвращается.

Сложность времени

Поскольку все узлы и вершины посещаются, среднее время сложность DFS на графе составляет O (V + E), где V — количество вершин, а E — количество ребер. В случае DFS на дереве временная сложность составляет O (V), где V — количество узлов.

Вопрос 40 : Реализация подстановочных знаков в Python

В Python вы можете реализовать подстановочные знаки с помощью библиотеки регулярных выражений.

Точка . используется вместо вопросительного знака ? . Следовательно, для поиска всех слов, соответствующих цветовому шаблону, код будет выглядеть примерно так.

 # Библиотека регулярных выраженийimport re # Добавьте или удалите слова в этом списке, чтобы изменить результаты wordlist = ["color", "color", "  работа »,« рабочий »,« лиса »,« рабочий »,« рабочий »] на слово в словарном списке: # The.  символ используется вместо?  символ, если re.search ('col. r ', word): print (word) 

Вопрос 41: Реализуйте сортировку слиянием в Python

Вот код для сортировки слиянием в Python:

 def mergeSort (myList): if len (myList)  > 1: mid = len (myList)//2 left = myList [: mid] right = myList [mid:] # Рекурсивный вызов на каждой половине mergeSort (left) mergeSort (right) # Два итератора для обхода двух половин i =  0 j = 0 # Итератор для основного списка k = 0, в то время как i  

Объяснение

Это рекурсивный подход для реализации сортировки слиянием. Шаги, необходимые для получения отсортированного массива с помощью этого метода, можно найти ниже:

  1. Список разделен на left и right в каждом рекурсивном вызове, пока не будут получены два соседних элемента.

  2. Теперь начинается процесс сортировки. Итераторы i и j пересекают две половины при каждом вызове. Итератор k просматривает все списки и по ходу вносит изменения.

  3. Если значение в i меньше значения в j , left [i] присваивается myList [k] и увеличивается на единицу i . Если нет, то выбирается right [j] .

  4. Таким образом, значения присваиваются через k отсортированы.

  5. В конце этого цикла одна из половин может быть пройдена не полностью. Его значения просто присваиваются оставшимся слотам в списке.

Временная сложность

Алгоритм работает в O (n.logn). Это связано с тем, что список разделяется на вызовы log (n), и процесс слияния занимает линейное время в каждом вызове..

Вопрос 42: Реализуйте алгоритм Дейкстры в Python

Базовый алгоритм

  1. Из каждой непосещенной вершины выберите вершину с наименьшим расстоянием и посетите ее.
  2. Обновите расстояние для каждой соседней вершины, посещенной вершины, текущее расстояние которой больше ее суммы и веса ребра между ними.
  3. Повторяйте шаги 1 и 2, пока не будут посещены все вершины.

Чтобы узнать больше об алгоритмах Python для собеседований по кодированию, ознакомьтесь с нашей статьей Основные алгоритмы с Python для собеседований по кодированию

Вот реализация

 import sys # Функция для определения того, какой из непосещенных # узлов необходимо посетить nextdef to_be_visited (): global visit_and_distance v = -10 # Выбор th  Вершина с минимальным расстоянием для индекса в диапазоне (число_вершин): если посещенное_и_дистанция [индекс] [0] == 0  и (v  new_distance: visit_and_distance [neighbour_index] [1] = new_distance # Посещение вершины, найденной ранее посещенным_и_дистанции [to_visit] [0] = 1i =  0 # Распечатка кратчайшего расстояния от источника до каждой вершины для расстояния в visit_and_distance: print ("Кратчайшее расстояние", chr (ord ('a') + i),  "от исходной вершины a равно:",  расстояние [1]) i = i + 1 

Вопрос 43: Объединить два отсортированных списка

 # Объединить list1 и list2 и вернуть результат listdef merge_lists (lst1, lst2): index_arr1 = 0 index_arr2 = 0 index_result = 0 result = [] для i  in range (len (lst1) + len (lst2)): result.append (i) # Обойти оба списка и вставить меньшее значение из arr1 или arr2 # в список результатов, а затем увеличить индекс этого списка.  # Если список полностью пройден, а другой остался, просто # скопируйте все оставшиеся элементы в список результатов while (index_arr1  

Приведенное выше решение более интуитивный способ решения этой проблемы.

  1. Начните с создания нового пустого списка. Этот список будет заполнен всеми элементами обоих списков в отсортированном порядке и возвращен.

  2. Затем инициализируйте три переменные до нуля, чтобы сохранить текущий индекс каждого списка.

  3. Затем сравните элементы двух заданных списков с текущим индексом каждого, добавьте меньший в новый список и увеличьте индекс этого списка на 1.

  4. Повторяйте, пока не будет достигнут конец одного из списков, и добавьте другой список в объединенный список.

Сложность по времени Сложность по времени для этого алгоритма составляет O (n + m) O (n + m), где nn и mm — длины списков. Это связано с тем, что оба списка повторяются по крайней мере один раз.

Обратите внимание, что эту проблему также можно решить путем слияния на месте.

Вопрос 44: Найдите два числа, которые в сумме дают «k»

 def binarySearch (a, item, curr): first = 0 last = len (a) - 1 found = False index = -1 while first  
путь>
путь>

Эту проблему можно решить, предварительно отсортировав список. Затем для каждого элемента в списке используйте двоичный поиск, чтобы найти разницу между этим элементом и предполагаемой суммой. Другими словами, если предполагаемая сумма равна k , а первым элементом отсортированного списка является a 0 a_ {0} a 0, тогда мы выполним двоичный поиск k — a 0 a_ {0} а 0. Поиск повторяется для каждого a i a_ {i} a i до a n a_ {n} a n, пока он не будет найден. Вы можете реализовать функцию binarySearch () как хотите, рекурсивно или итеративно.

Сложность времени

Поскольку наиболее оптимальные функции сортировки на основе сравнения принимают O (nlogn), предположим, что функция Python .sort () принимает то же самое. Более того, поскольку двоичный поиск занимает время O (logn) для поиска одного элемента, поэтому двоичный поиск всех n элементов займет время O (nlogn).

Вопрос 45: Найдите первое неповторяющееся целое число в списке

Здесь вы можете использовать словарь Python для подсчета повторений

Пример ввод:

  [9,2,3,2,6,6]  

 def findFirstUnique (lst): counts = {} # Создание словаря # Инициализация словаря с помощью  пары вроде (lst [i], (count, order)) counts = counts.fromkeys (lst, (0, len (lst))) order = 0 для ele в lst: # counts [ele] [0] + = 1  # Приращение для каждого повторения # counts [ele] [1] = order counts [ele] = (counts [ele] [0] +1, order) order + = 1 # приращение порядка answer = None answer_key = None # фильтр не-  повторение с наименьшим порядком для элемента в lst: if (counts [ele] [0] равно 1) и (ответ None): ans  wer = counts [ele] answer_key = ele elif ответ None: continue elif (counts [ele] [0] is 1) and (counts [ele] [1]  

Ключи в словаре counts — это элементы данного списка, а значения — это количество раз, когда каждый элемент появляется в списке. Мы возвращаем элемент, который появляется не более одного раза в списке в строке 23. Нам нужно поддерживать порядок обновления для каждого ключа в значении кортежа.

Сложность времени

Поскольку список повторяется только дважды, а словарь counts инициализируется с линейной временной сложностью, поэтому временная сложность этого решения линейна, т.е. O (n).

Вопрос 46: Найдите среднее значение связанного списка

main.py
LinkedList.py
Node.py
 from Node import Nodeclass LinkedList: def __init __ (self): self.head_node = None def get_head (self): return self.head_node def is_empty (self): if (self.head_node is None):  # Проверяем, является ли голова None return True else: return False def insert_at_head (self, dt): temp_no  de = Node (dt) temp_node.next_element = self.head_node self.head_node = temp_node return self.head_node def print_list (self): if (self.is_empty ()): print («Список пуст») return False temp = self  .head_node, в то время как temp.next_element не имеет значения None: print (temp.data, end = "->") temp = temp.next_element print (temp. data, "-> None") return True def length (self): # начать с первого элемента curr = self.get_head () length = 0 # Обойти список и подсчитать количество узлов, пока curr не равно None: length +  = 1 curr = curr.next_element возвращаемая длина 

Здесь вы можете использовать два указателя, которые будут работать одновременно.

Подумайте об этом так:

  • Быстрый указатель перемещает два шага в время до конца списка
  • Медленный указатель перемещается на один шаг за раз
  • Когда быстрый указатель достигает конца, медленный указатель будет посередине

Используя этот алгоритм, вы можете ускорить процесс, потому что происходит вычисление длины и обход до середины. бок о бок.

Сложность времени

Вы просматриваете связанный список в два раза быстрее, так что это, безусловно, Быстрее. Однако сложность узкого места по-прежнему составляет O (n).

Вопрос 47: Обратить первые k элементов очереди

main.py
Stack.py
Queue.py
 from Queue import myQueuefrom Stack import myStack # 1. Вставить первые k элементов в очередь в стек. # 2. Поп-элементы стека и поставить их в очередь в конце очереди # 3  .Dequeue элементы очереди до "k" и добавить их в конец queuedef reverseK (queue, k): if queue.isEmpty () True или k> queue.size () или k  

Объяснение

  1. Проверить неверный ввод, т. е. если очередь пуста, если k больше, чем очередь, и если k отрицательное значение в строке2 . Если ввод действителен, начните с создания стека. Доступные функции стека:

    • Конструктор: myStack()
    • Push-элементы: push (int) для добавления элементов в стек.
    • Всплывающие элементы : pop () , чтобы удалить или вытолкнуть верхний элемент из стека.
    • Проверить, пуст ли: isEmpty () возвращает true, если стек пуст, и false в противном случае.
    • Возврат назад: назад () возвращает элемент, который был добавлен в конец, не удаляя его из стека.
    • Возврат вперед: front () возвращает верхний элемент (который был добавлен в начале), не удаляя его из стека.
  2. Наша функция reverseK (queue, k) принимает очередь в качестве входного параметра. k представляет количество элементов, которые мы хотим перевернуть. Доступные функции очереди:

    • Конструктор: myQueue (size) size должен быть целым числом, определяющим размер очереди.
    • Enqueue: enqueue(int)
    • Dequeue: dequeue()
    • Проверить, пусто ли: isEmpty ( )
    • Размер проверки: size()
  3. Теперь, переходя к реальной логике, удалите первые элементы k из передней части очереди и поместите их в стек, который мы создали ранее, используя stack.push (queue.dequeue ()) в строке 8.

  4. Как только все k значения были помещены в стек, начните их извлекать и последовательно помещать в конец очереди. Мы сделаем это с помощью queue.enqueue (stack.pop ()) в строке 12. В конце этого шага у нас останется пустой стек и k перевернутых элементов будут добавлены в конец очереди.

  5. Теперь нам нужно переместить эти перевернутые элементы в начало очереди. Для этого мы использовали queue.enqueue (queue.dequeue ()) в строке 16. Каждый элемент сначала удаляется из очереди сзади

Вопрос 48: Найдите высоту двоичного дерева поиска (BST)

Здесь вы можете использовать рекурсию, чтобы найти высоту левого и правого поддеревьев.

main.py
BinarySearchTree.py
Node.py
 Узел класса: def __init __ (self, val): self.val = val self.leftChild = None self.rightChild  = Нет def insert (self, val): if val  self.val: if self.  rightChild: return self.rightChild.search (val) else: return False else: return True return False def delete (self, val): if val  self.val: if (self.rightChild): self.rightChild = self.rightChild.delete (val)  else: print (str (val) + "not found in the tree") return self else: # удаление узла без дочерних узлов, если self.leftChild равно None, а self.rightChild равно None: self = None return None # удаление узла с правом  child elif self.leftChild is None: tmp = self.rightChild self = None return tmp # удаление узла с левым дочерним элементом elif self.rightChild is None: tmp = self.leftChild self = None return tmp # удаление узла с двумя дочерними элементами else: #  сначала получить inorder преемник current =  self.rightChild # цикл вниз, чтобы найти крайний левый лист while (current.leftChild не равно None): current = current.leftChild self.val = current.val self.rightChild = self.rightChild.delete (current.val) return self 

Пояснение

Здесь мы возвращаем -1, если данный узел равен None. Затем мы вызываем функцию findHeight () для левого и правого поддеревьев и возвращаем то, которое имеет большее значение плюс 1. Мы не вернем 0, если данный узел равен None, поскольку листовой узел будет иметь высоту 0.

Временная сложность

Временная сложность кода составляет O (n) O (n), поскольку все узлы всего дерево необходимо пройти.

Вопрос 49: преобразовать максимальную кучу в минимальную кучу

Здесь мы ‘ ll Min Heapify все родительские узлы.

 def  minHeapify (heap, index): left = index * 2 + 1 right = (index * 2) + 2 smallest = index # проверьте, существует ли левый дочерний элемент и меньше ли он наименьшего, если len (heap)> left and heap [smallest]>  heap [left]: smallest = left # проверяем, существует ли правый дочерний элемент и меньше ли он самого маленького, если len (heap)> right и heap [smallest]> heap [right]: smallest = right # проверяет, не является ли текущий индекс самым маленьким, если  наименьший! = индекс: # заменить текущее значение индекса наименьшим tmp = куча [наименьшая] куча [наименьшая] = куча [индекс] куча [индекс] = tmp # minHeapify новый узел minHeapify (куча, наименьший) return heapdef convertMax (maxHeap)  : # итерация от среднего к первому элементу # средний и первый индексы содержат все родительские узлы для i в диапазоне ((len (maxHeap))//2, -1, -1): # вызов minHeapify для всех родительских узлов maxHeap = minHeapify (  maxHeap, i) вернуть maxHeapmaxHeap = [9, 4, 7, 1, -2, 6, 5] p  rint (convertMax (maxHeap)) 

Объяснение

Помните, что мы можем рассматривать данный maxHeap как обычный список элементов и переупорядочивать его так, чтобы он точно представлял минимальную кучу . Мы делаем именно это в этом решении. Функция convertMax () восстанавливает свойство кучи на всех узлах из самого нижнего родительского узла, вызывая функцию minHeapify () для каждого.

Сложность времени Функция minHeapify () вызывается для половины узлов в куче. Функция minHeapify () занимает время O (log (n)) и вызывается в n 2 frac {n} {2} 2 n узлов, поэтому это решение занимает время O (nlog (n)).

Вопрос 50: Обнаружить цикл в связанном списке

main.py
LinkedList.py
Node.py
 из LinkedList импортировать LinkedListfrom Node import Nodef detect_loop (lst):  # Используется для хранения узлов, которые мы уже посетили посещенные_nodes = set () current_node = lst.get_head () # Обходим набор и помещаем каждый узел в набор посещенных узлов # и если узел появляется дважды на карте #, это означает, что существует  цикл в наборе while current_node: if current_node в visit_nodes: return Tru  e visit_nodes.add (current_node) # Вставить узел в visitNodes set current_node = current_node. next_element return False # ------------------------------ lst = LinkedList () lst.insert_at_head (21) lst.insert_at_head (14  ) lst.insert_at_head (7) print (detect_loop (lst)) head = lst.get_head () node = lst.get_head () # Добавление цикла для i в диапазоне (4): если node.next_element имеет значение None: node.next_element =  head.next_element break node = node.next_elementprint (detect_loop (lst)) 

Объяснение

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

По принципу, если узел повторно посещается, цикл существует!

Сложность времени

Мы повторяем список один раз. В среднем поиск в наборе занимает время O (1). Следовательно, среднее время выполнения этого алгоритма составляет O (n). Однако в худшем случае поиск может увеличиться до O (n), что приведет к тому, что алгоритм будет работать в O (n2 ) O (n ^ {2}) O (n 2).

Дальнейшие действия

Отличная работа с этими вопросами! Хотя собеседования могут вызывать стресс, практика — единственный способ подготовиться.

Образовательный курс Декодирование собеседования по программированию на Python: примеры из реальной жизни помог бесчисленному количеству людей. инженеры-программисты готовятся и получают работу в Microsoft, Amazon, Google и других. В этом курсе вы будете практиковаться в реальных проектах, выбранных для подготовки к самым сложным в отрасли собеседованиям.

К концу , у вас будет практический опыт работы со всеми наиболее проверенными навыками и вопросами.

Удачного обучения!

Продолжайте читать о Python и подготовке к собеседованию

  • Python Concurrency: понимание asyncio
  • Прекратите использовать Excel для анализа данных: перейдите на Python
  • Структуры данных и алгоритмы в Python
  • CodingInterview.com
Оцените статью
nanomode.ru
Добавить комментарий