Динамическое программирование было горячей темой для интервью в ведущих технологических компаниях, а также в ведущих стартапах. Динамическое программирование включает в себя очень красивую концепцию суммирования решений небольших индивидуальных проблем в более крупную проблему.
Из 16 или около того собеседований мне задали один вопрос DP (возможно, два, но второй был настолько далек от стандартной проблемы DP, что я не очень считаю его одной). У моего друга было еще несколько интервью, но у него было примерно 8–10 проблем с DP. - одним из моих друзей
Позвольте мне задать вам некоторые из самых важных и часто задаваемых вопросов DP в интервью;
- Самая длинная общая подпоследовательность:
Для двух последовательностей найдите длину самой длинной подпоследовательности, присутствующей в обеих из них. Подпоследовательность - это последовательность, которая появляется в том же относительном порядке, но не обязательно непрерывно. Например, «abc», «abg», «bdf», «aeg», «acefg»,… и т. Д. Являются подпоследовательностями «abcdefg».
2. Самая длинная возрастающая подпоследовательность:
Задача самой длинной возрастающей подпоследовательности (LIS) состоит в том, чтобы найти длину самой длинной подпоследовательности данной последовательности, чтобы все элементы подпоследовательности были отсортированы в порядке возрастания. Например, длина LIS для {10, 22, 9, 33, 21, 50, 41, 60, 80} равна 6, а длина LIS - {10, 22, 33, 50, 60, 80}.
3. Изменить расстояние:
Учитывая две строки str1 и str2 и ниже операции, которые могут выполняться на str1. Найдите минимальное количество правок (операций), необходимых для преобразования «str1» в «str2».
Вставлять
Удалять
Заменять
Все вышеперечисленные операции имеют одинаковую стоимость.
4. Самый длинный путь в матрице:
Для матрицы размера n * n, в которой все числа различны, найдите путь максимальной длины (начиная с любой ячейки), чтобы все ячейки вдоль пути располагались в порядке возрастания с разницей в 1.
5. Задача суммы подмножества:
Учитывая набор неотрицательных целых чисел и значение sum, определите, существует ли подмножество данного набора с суммой, равной заданной sum.
6. 0–1 Рюкзак:
Учитывая вес и стоимость n предметов, положите эти предметы в рюкзак вместимостью W, чтобы получить максимальное общее значение в рюкзаке. Другими словами, заданы два целочисленных массива val [0..n-1] и wt [0..n-1], которые представляют значения и веса, связанные с n элементами соответственно. Также учитывая целое число W, которое представляет вместимость ранца, найдите подмножество максимального значения val [], чтобы сумма весов этого подмножества была меньше или равной W. Вы не можете сломать предмет, либо выбрать предмет целиком, либо не выбирайте его (свойство 0–1).
7. Умножение цепочки матриц:
Для данной последовательности матриц найдите наиболее эффективный способ умножения этих матриц вместе. Проблема не в том, чтобы выполнить умножение, а просто в том, чтобы решить, в каком порядке производить умножение.
8. Резка стержня:
Дан стержень длиной n дюймов и массив цен, содержащий цены на все предметы размером меньше n. Определите максимальную ценность, которую можно получить, разрезав стержень и продав его по частям. Например, если длина стержня равна 8, а значения различных частей указаны ниже, то максимальное достижимое значение будет 22 (путем разрезания на две части длиной 2 и 6).
length | 1 2 3 4 5 6 7 8 -------------------------------------------- price | 1 5 8 9 10 17 17 20
И если цены следующие, то максимальное доступное значение - 24 (путем разрезания на восемь частей длины 1)
length | 1 2 3 4 5 6 7 8 -------------------------------------------- price | 3 5 8 9 10 17 17 20
9. Обмен монет:
Учитывая значение N, если мы хотим внести сдачу на N центов и у нас есть бесконечный запас каждой из монет с номиналом S = {S1, S2, .., Sm}, сколькими способами мы можем внести сдачу? Порядок монет не имеет значения.
Например, для N = 4 и S = {1,2,3} существует четыре решения: {1,1,1,1}, {1,1,2}, {2,2}, {1, 3}. Таким образом, на выходе должно быть 4. Для N = 10 и S = {2, 5, 3, 6} есть пять решений: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} и {5,5}. Таким образом, на выходе должно быть 5.
10. Проблема опускания яйца:
Ниже приводится описание примера этой знаменитой головоломки с участием n = 2 яиц и здания с k = 36 этажами.
Предположим, мы хотим знать, с каких этажей 36-этажного здания можно безопасно сбрасывать яйца, а с каких они разбиваются при приземлении. Сделаем несколько предположений:
…… Яйцо, пережившее падение, можно использовать снова.
… .. Разбитое яйцо нужно выбросить.
… .. Эффект от падения одинаков для всех яиц.
… ..Если яйцо разобьется при падении, оно разобьется при падении с более высокого этажа.
… .. Если яйцо выживает при падении, оно выдержит более короткое падение.
… .. Не исключено, что окна первого этажа разбивают яйца, и не исключено, что на 36 этаже не разбиваются яйца.
Если доступно только одно яйцо, и мы хотим быть уверены в получении правильного результата, эксперимент может быть проведен только одним способом. Бросьте яйцо из окна первого этажа; если выживет, бросьте его из окна второго этажа. Продолжайте движение вверх, пока не сломается. В худшем случае для этого метода может потребоваться 36 помет. Допустим, есть 2 яйца. Какое наименьшее количество яичного помета гарантированно будет работать во всех случаях?
Проблема не в том, чтобы найти критический этаж, а просто в том, чтобы решить, с каких этажей следует сбрасывать яйца, чтобы общее количество испытаний сведены к минимуму.
Это самые важные проблемы DP, которые часто задают в интервью. Пройдите по каждому из них, и мы обсудим решение каждого в отдельных статьях.
Следуйте за мной, чтобы увидеть больше таких статей.
