Главная
Общие вопросы на собеседовании программиста: какие задают, что спрашивают, подготовка

Общие вопросы на собеседовании программиста: какие задают, что спрашивают, подготовка

Содержание

Как пройти собеседование программисту — новости и обзоры рынка HR

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

В классическом варианте собеседование программиста проходит в 2 этапа. Первый, как правило, проводит HR-специалист. Он просит рассказать об уровне вашей подготовки, опыте, целях, личных качествах. Далее вы выполняете тестовое задание и приходите на второе интервью – с техническим специалистом.

Если HR-а в компании нет, вас сразу протестирует программист, а затем вы получите тестовое задание (по результатам беседы). Есть и другие вариации – например, 3-этапное собеседование, итогом которого является интервью с руководителем организации. Но первые два – самые популярные.

Пласт общих вопросов может в себя включать следующие:

  • Дайте определение компилятору и интерпретатору;
  • Назовите типы констант;
  • Что представляет собой методология Agile;
  • В чем плюсы и минусы модульного программирования;
  • Какие нововведения были в последнее время в языке N и т.п.

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

Что касается проверки умения работать с крупными массивами, то здесь программистам на собеседовании могут ставить следующие задачи:

  • Найти максимум и минимум в массиве из 100 чисел с помощью короткой программы;
  • «Развернуть» массив целых чисел без применения специальных библиотек;
  • Написать программу вставки пропущенных значений и удаления дублей в массиве целых чисел без применения библиотек и т.д.

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

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

Такая проверка позволяет сразу отсеять неопытных кандидатов. А для IT-специалистов с высоким уровнем подготовки решить эти и более сложные задачи не составит труда. Однако потренироваться перед собеседованием тоже не помешает.

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

50 вопросов и ответов по программированию для подготовки к техническому интервью

Готовясь к собеседованию, многие начинающие программисты понятия не имеют, каких вопросов ожидать от интервьеюров — будь то собеседование в стартап или технологический гигант вроде Amazon, Microsoft или Google. В статье на Hacker Noon разработчик Джавин Пол собрал вопросы, которые любят задавать на таких интервью, а также ответы на них и дополнительные ресурсы для подготовки. Сайт DEV.BY опубликовал перевод статьи.

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

Но прежде чем приступить к ним, понадобится хорошо изучить эти темы, или по крайней мере освежить навыки решения задач по ним. Для этого можно пройти курс по алгоритмам и структурам данных Роберта Хорвика: часть 1 и часть 2.

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

1. Массивы

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

Главный плюс такой структуры данных, как массив — он обеспечивает быстрый поиск сложностью О(1) при знании индексов, но добавление и удаление элементов из него происходит медленно, потому что нельзя менять размер массива после создания. Чтобы увеличить или уменьшить массив, нужно создать новый и скопировать в него все элементы из старого.

Чтобы с лёгкостью отвечать на вопросы, связанным с массивами, нужно хорошо разбираться как с самими массивами, так и с базовыми конструкторами, такие как рекурсия и основные операторы.

Вот самые частые вопросы:

  1. Как найти пропущенное число в заданном массиве целых чисел от 1 до 100? (решение)
  2. Как найти повторяющееся число в заданном массиве целых чисел? (решение)
  3. Как найти наибольшее и наименьшее число в неотсортированном массиве? (
    решение    )
  4. Как найти все пары в массиве целых чисел, сумма которых равна заданному числу? (решение)
  5. Как найти повторяющиеся числа в массиве, если их несколько? (решение)
  6. Как удалить повторяющиеся элементы из заданного массива в Java? (решение)
  7. Как сортировать массив целых чисел без дополнительной памяти при помощи алгоритма быстрой сортировки? (решение)
  8. Как удалить повторяющиеся элементы из массива без дополнительной памяти? (решение
    )
  9. Как сделать поменять порядок элементов в массиве на обратный без дополнительной памяти в Java? (решение)
  10. Как удалить повторяющиеся элементы из массива без использования коллекций? (решение)

Эти вопросы помогут не только развить навыки решения задач, но и прокачать знания по массивам. Более сложные вопросы по теме можно найти в курсе по алгоритмам The Coding Interview Bootcamp: Algorithms + Data Structures, разработанном специально для подготовки к собеседованиям в таких технологических гигантах, как Google, Microsoft, Apple или Facebook.

Дополнительно можно поупражняться на этой подборке из 30 вопросов.

The Coding Interview Bootcamp

2. Связный список:

Ещё одна базовая структура данных — связный список. Как и массив, это линейная структура данных, и элементы в нём хранятся линейно, но в отличие от массива — не в непрерывных областях. Они разбросаны в памяти и соединяются с помощью узлов. Связный список — ничто иное, как список узлов, каждый из которых содержит собственно данные и ссылку на следующий узел.

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

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

Есть разные виды связных списков: односвязный список, который позволяет передвигаться только в одну сторону: в начало или в конец; двусвязный список, дающий возможность перемещения как вперёд, так и назад; кольцевой список, который формирует зацикленную структуру.

Чтобы успешно справляться с вопросами по линейным спискам, важно хорошо знать рекурсию. Если извлечь из связного списка один узел, оставшаяся структура по-прежнему будет связным списком, и поэтому для многих задач в этой теме более простыми являются рекурсивные решения, чем итеративные.

Вопросы для собеседования:

  1. Как найти центральный элемент в односвязном списке за один проход? (решение)
  2. Как проверить заданный связный список на цикличность? Как найти исходный узел цикла? (
    решение)
  3. Как сделать реверс связного списка? (решение)
  4. Как сделать реверс односвязного списка без рекурсии? (решение)
  5. Как удалить повторяющиеся узлы из несортированного связного списка? (решение)
  6. Как найти длину односвязного списка? (решение)
  7. Как найти 3-й узел с конца в односвязном списке? (решение)
  8. Как найти сумму двух связных списков, используя стек? (решение
    )

Эти вопросы помогут развить умение решать задачи на связные списки и углубить знание этой структуры данных. Если они вызывают трудности, можно обновить свои знания структур данных и алгоритмов, пройдя курс Data Structures and Algorithms: Deep Dive Using Java.

Кроме того, можно потренироваться на этом списке из 30 вопросов.

3. Строки

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

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

Вот наиболее частые из них:

  1. Как вывести повторяющиеся символы из строки? (решение)
  2. Как проверить, являются ли две строки анаграммами? (решение)
  3. Как вывести первый неповторяющийся символ из строки? (решение)
  4. Как сделать реверс заданной строки с использованием рекурсии? (решение)
  5. Как проверить, что строка состоит только из цифр? (решение)
  6. Как найти повторяющийся символ в строке? (решение)
  7. Как посчитать количество гласных и согласных звуков в заданной строке? (решение)
  8. Как посчитать, сколько раз в строке встречается заданный символ? (решение)
  9. Как найти все возможные перестановки элементов строки? (решение)
  10. Как сделать реверс слов в заданном предложении, не используя классы-коллекции? (решение)
  11. Как проверить, является ли одна строка перестановкой другой? (решение)
  12. Как проверить, является ли заданная строка палиндромом? (решение)

Способность решить эти вопросы говорит о достаточно хорошем уровне владений строками. Более продвинутые задачи можно найти в книге «Алгоритмы. Руководство по разработке» Стивена Скиены.

Ещё 20 вопросов можно найти здесь.

4. Двоичное дерево поиска

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

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

Секрет успешного прохождения вопросов, связанных с двоичным деревом — основательное знание теории, например, что такое размер или глубина двоичного дерева, что такое лист и узел, а также понимание основных алгоритмов обхода дерева: в прямом, симметричном и обратном порядке.

Наиболее распространённые вопросы по бинарным деревьям:

  1. Как реализуется двоичное дерево поиска? (решение)
  2. Как выполнить обход в прямом порядке в заданном двоичном дереве? (решение)
  3. Как обойти заданное двоичное дерево в прямом порядке без рекурсии? (решение)
  4. Как выполнить симметричный обход в заданном двоичном дереве? (решение)
  5. Как вывести все узлы заданного двоичного дерева, используя симметричный обход без рекурсии? (решение)
  6. Как применяется алгоритм обхода в обратном порядке? (решение)
  7. Как обойти заданное двоичное дерево в обратном порядке без рекурсии? (решение)
  8. Как вывести на печать все листья двоичного дерева поиска? (решение)
  9. Как посчитать количество листьев в заданном двоичном дереве? (решение)
  10. Как выполнить двоичный поиск в заданном массиве? (решение)

Если пройти эти вопросы самостоятельно слишком сложно, не помешает пройти какой-нибудь качественный курс по структурам данных и алгоритмам, например From 0 to 1: Data Structures & Algorithms in Java. Вот ещё два списка книг и курсов на эту тему.

From 0 to 1: Data Structures & Algorithms in Java

5. Прочие алгоритмы и вопросы

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

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

  1. Как реализуется сортировка пузырьком? (решение)
  2. Как реализуется итеративная быстрая сортировка? (решение)
  3. Как реализуется сортировка вставками? (решение)
  4. Как реализуется сортировка слиянием? (решение)
  5. Как реализуется блочная сортировка? (решение)
  6. Как реализуется сортировка подсчётом? (решение)
  7. Как реализуется поразрядная сортировка? (решение)
  8. Как поменять местами значения двух переменных без использования третьей? (решение)
  9. Как определить, пересекаются ли два прямоугольника? (решение)
  10. Как спроектировать торговый автомат? (решение)

Свыше 189 вопросов для прохождения собеседования по программированию с ответами можно найти в книге «Карьера программиста» (6-е издание) Гэйл Лакман Макдауэлл.

Здесь можно пройти ещё 50 вопросов по программированию для прохождения собеседований по телефону; закрепить навыки можно с помощью вот этих подборок книг и курсов.

Вот ещё несколько ресурсов и подборок, которые помогут подготовиться к собеседованию:

  • 10 книг для подготовки к техническому собеседованию по программированию/разработке
  • 10 книг по алгоритмам, которые должен прочитать каждый программист
  • 5 лучших книг по структурам данных и алгоритмам для Java-разработчиков
  • Онлайн-курс по анализу структур данных и алгоритмов с подготовкой к собеседованию



20 лучших вопросов для интервью по динамическому программированию с решениями | от javinpaul | Javarevisited

Подготовка к собеседованию по программированию? Вот 20 задач по динамическому программированию, чтобы проверить свои навыки и хорошо подготовиться.

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

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

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

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

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

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

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

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

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

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

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

Например, в задаче о подъеме по лестнице вы можете разбить задачу с n шагами на задачи с 1 или 2 шагами.

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

Вот 7 шагов решения основных задач динамического программирования (DP)

  1. Распознать проблему DP, разбив ее на подзадачи
  2. Идентифицировать переменные проблемы.
  3. Четко выразить отношение рекуррентности к применению рекурсии.
  4. Определите базовые варианты.
  5. Решите, хотите ли вы реализовать это итеративно или рекурсивно.
  6. Добавить памятку.
  7. Определить временную сложность.

Вы также можете использовать метод FAST для решения задач динамического программирования, который является аббревиатурой для 4 шагов, необходимых для решения любой задачи динамического программирования:

  • Поиск первого решения
  • Анализ первого решения
  • Определение подзадач
  • Изменение решения

Эти методы можно использовать для выявления и решения проблемы динамического программирования. Я также настоятельно рекомендую курс Master the art of Dynamic Programming на Udemy, чтобы попробовать решить пару пошаговых задач, чтобы понять, как эти шаги сочетаются друг с другом, особенно если вы никогда не решали задачу динамического программирования.

Если вам нужна книга, я настоятельно рекомендую книгу Адитьи Бхаргавы Grokking Algorithms, которая также подробно объясняет проблему Кнапсака и учит решать задачи динамического программирования.

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

Они не только отлично подходят для отработки этой сложной техники, но и дают вам возможность проверить свои навыки решения задач DP.

Если вы можете решить 5 из этих 10 вопросов без чьей-либо помощи, вы можете попробовать пройти собеседование по программированию.

1. Задача о подъеме по лестнице

Это одна из самых популярных задач кодирования, которую можно решить с помощью метода динамического программирования. В этой задаче вы поднимаетесь по лестнице. Требуется n шагов, чтобы добраться до вершины. Каждый раз вы можете подняться на 1 или 2 ступеньки. Вопрос в том, сколькими различными способами вы можете подняться на вершину?

Примечание. Заданное n будет положительным целым числом.

Пример 1:

Ввод: 2
Вывод: 2
Объяснение: Есть два способа взобраться на вершину.
1. 1 шаг + 1 шаг
2. 2 шага

Пример 2:

Ввод: 3
Вывод: 3
Пояснение: Есть три способа подняться на вершину.
1. 1 шаг + 1 шаг + 1 шаг
2. 1 шаг + 2 шага
3. 2 шага + 1 шаг.

Если вы застряли, вы также можете посмотреть это видео, чтобы получить некоторое представление, и если вам нужен курс, Master the Coding Interview: Big Tech (FAANG) Interviews от Андрея Негаойе — лучший курс, в котором вы найдете решение не только этой проблемы, но и многих других, подобных этой.

2. Задача о рюкзаке [решено]

Это еще одна распространенная задача кодирования на основе динамического программирования и шаблон, который может решить многие подобные вопросы. В этом типе задачи вам будут даны веса и прибыль «N» предметов, поместите эти предметы в рюкзак вместимостью «C». Ваша цель: получить максимальную прибыль от предметов в рюкзаке. Каждый элемент можно выбрать только один раз.

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

Предметы: { Яблоко, Апельсин, Банан, Дыня }
Вес: { 2, 3, 1, 4 }
Прибыль: { 4, 5, 3, 7 }
Вместимость рюкзака: 5

Попробуем положить в рюкзак разные комбинации фруктов, чтобы их общий вес был не более 5.

Яблоко + Апельсин (общий вес 5) => 9 прибыль
Яблоко + Банан (общий вес 3) => 7 прибыль
Апельсин + Банан (общий вес 4) => 8 прибыль
Банан + Дыня (общий вес 5) => 10 прибыль

Это показывает, что Банан + Дыня является лучшим комбинации, так как она дает нам максимальную прибыль и общий вес не превышает возможности. Вы также можете посмотреть этот бесплатный урок из курса динамического программирования на Educative для подробного решения этой проблемы.

3. Задача редактирования расстояния

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

Над словом разрешены следующие 3 операции:

  • Вставка символа
  • Удаление символа
  • Замена символа

Пример 1:
Ввод: слово1 = «лошадь», слово2 = «рос»
Выход: 3
Объяснение:
лошадь -> rorse (заменить 'h' на 'r')
rorse -> rose (убрать 'r')
rose -> ros (удалить 'e')

И, если если вы застряли, посмотрите этот учебник на YouTube, чтобы найти пошаговое решение:

4. Самая длинная палиндромная подпоследовательность Вопрос

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

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

Пример 1:
Ввод:
«bbbab»

Вывод:
4

Объяснение: LPS — это «bbbb».

И, если вам нужно решение, посмотрите этот видеоурок на YouTube, он бесплатный и предлагает пошаговое решение этой проблемы динамического программирования.

4. Лучшее время для покупки и продажи акций Задача

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

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

Обратите внимание, что вы не можете продать акцию до того, как купите ее.

Пример 1:
Ввод: [7,1,5,3,6,4]
Вывод: 5
Объяснение: Покупка в день 2 (цена = 1) и продажа в день 5 (цена = 6), прибыль = 6–1 = 5. 90 103 Не 7–1 = 6, поскольку цена продажи должна быть больше, чем цена покупки.

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

5. Задача Фибоначчи [Решение]

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

Числа Фибоначчи — это последовательность чисел, в которой каждое число является суммой двух предыдущих чисел. Первые несколько чисел Фибоначчи — это 0, 1, 2, 3, 5, 8 и так далее.

Мы можем определить числа Фибоначчи как:

Фибоначчи (n) = Фибоначчи (n-1) + Фибоначчи (n-2) для n > 1 (1) = 1

Вы также можете посмотреть мое решение о том, как вычислить N-е число Фибоначчи в Java, чтобы узнать больше о том, как решить эту проблему.

6. Задача на размен монет

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

Пример 1:
Ввод: монеты = [1, 2, 5], количество = 11
Вывод: 3
Объяснение: 11 = 5 + 5 + 1

И, если вы застряли, вот руководство, чтобы получить помощь

7. Самая длинная общая подстрока

Имея две строки 1' и 's2', найдите длину самой длинной общей подстроки в обеих строках.

Пример 1:

Ввод: s1 = «abdca»
s2 = «cbda»

Вывод: 2

Объяснение: Самая длинная общая подстрока — «bd».

А вот решение задачи о самой длинной общей подстроке:

8. Самая длинная общая подпоследовательность

Имея две строки 1’ и ‘s2’, найдите длину самой длинной подпоследовательности, которая является общей в обеих строках.

Пример 1:
Ввод: s1 = «abdca»
s2 = «cbda»

Вывод: 3
Объяснение: Самая длинная подстрока — «bda».

И, если вы застряли, вы всегда можете посмотреть это видео на YouTube, чтобы получить идеи о том, как решить эту проблему Вопрос по динамическому программированию :

9. Задача о разделении суммы подмножеств

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

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

Пример 1:

Ввод: {1, 2, 3, 4}

Вывод: True

Объяснение: Данный набор можно разделить на два подмножества с одинаковой суммой: {1, 4} и {2, 3}

Пример 2:

Ввод: {1, 1, 3, 4 , 7}

Вывод: True

Объяснение: Данный набор можно разделить на два подмножества с одинаковой суммой: {1, 3, 4} и {1, 7}

Пример 3:

Ввод: {2, 3, 4, 6}

Вывод: Ложь

Объяснение: Данное множество не может быть разделено на два подмножества с одинаковой суммой.

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

10. Непрерывная сумма подмассивов

Это еще одна популярная задача кодирования на основе динамического программирования из интервью. В этой задаче вам будет дан список неотрицательных чисел и целевое целое число k. Напишите функцию, проверяющую, есть ли в массиве непрерывный подмассив размера не менее 2, сумма которого кратна k, то есть суммируется до n*k, где n также является целым числом.

Пример 1:
Ввод: [23, 2, 4, 6, 7], k=6

Вывод: True
Объяснение: Поскольку [2, 4] является непрерывным подмассивом размера 2 и в сумме дает 6.

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

10 дополнительных вопросов для собеседования по динамическому программированию для практики

И вот еще 10 динамических программ Вопросы для интервью, которые вы можете попрактиковать

  • Проблема перерыва слов
  • Максимальный продукт при разрезании веревки
  • Проблема с броском кости
  • Укладки коробки
  • Загадка падения яиц
  • .

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

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

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

    Некоторые полезные ресурсы для собеседований по программированию:

    • 10 книг для подготовки к собеседованиям по техническому программированию/кодированию
    • 10 курсов по подготовке к программированию Собеседование
    • 10 книг по алгоритмам, которые должен прочитать каждый программист
    • 5 лучших книг по структуре данных и алгоритмам для Java-разработчиков
    • 5 лучших бесплатных курсов по структуре данных и алгоритмам
    • 20+ строковых алгоритмов 90 вопросов для собеседования 90 вопросов по алгоритмам 9054
    • Просмотрите эти вопросы для собеседования по Java для программистов
    • Более 20 задач на основе массивов для собеседований
    • 10 курсов по алгоритмам Младший разработчик должен присоединиться в 2021 г.
    • 7 лучших курсов для изучения структуры данных и алгоритмов
    • 25 вопросов для собеседования по дизайну программного обеспечения для программистов
    • 30 лучших вопросов по объектно-ориентированному программированию
    • 5 лучших курсов для изучения динамического программирования для собеседований
    • 10 лучших курсов для изучения системного дизайна для Интервью

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

    P. S. — Если вам нужно больше практики, включая десятки других задач и решений для каждого шаблона, ознакомьтесь с Grokking Dynamic Programming Patterns для интервью по кодированию на Educative. Это отличный текстовый интерактивный курс для развития ваших навыков динамического программирования.

    Образовательная платформа также является отличным ресурсом для интервью по программированию, и вы можете получить доступ ко всем их курсам всего за 14,9 долларов США в месяц . Я настоятельно рекомендую это всем, кто готовится к собеседованию по программированию.

    Grokking Шаблоны динамического программирования для собеседований по кодированию — учитесь в интерактивном режиме

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

    www.educative.io

    HR Вопросы для интервью для программистов

    • Время чтения: