Dynamic programming (DP) is a popular topic in coding interviews, especially with companies like Google. Here’s a set of 5 dynamic programming questions categorized into easy, medium, and hard levels, tailored for Go programming.
Table of Contents
1. Fibonacci Sequence
Level: Easy
Problem:
Write a function to calculate the nth Fibonacci number using dynamic programming. The Fibonacci sequence is defined as:
F(0) = 0,F(1) = 1- For
n > 1,F(n) = F(n-1) + F(n-2)
Example:
Input: n = 5
Output: 5
(Fibonacci numbers: 0, 1, 1, 2, 3, 5)
Approach:
You can solve this problem with a bottom-up approach to store intermediate results in an array or use two variables for space optimization.
2. Climbing Stairs
Level: Easy
Problem:
You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example:
Input: n = 3
Output: 3
(There are three ways: [1, 1, 1], [1, 2], and [2, 1])
Approach:
This is similar to the Fibonacci problem where the number of ways to climb n steps is the sum of ways to climb n-1 and n-2.
3. Unique Paths
Level: Medium
Problem:
A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. How many possible unique paths are there?
Example:
Input: m = 3, n = 2
Output: 3
(The robot can move down, down, right, or down, right, down, etc.)
Approach:
Use a 2D DP table to compute the number of ways to reach each cell by adding the values from the cell above and to the left.
4. Longest Increasing Subsequence
Level: Medium
Problem:
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
(The longest increasing subsequence is [2,3,7,101])
Approach:
Use a DP array where each element at index i represents the length of the longest increasing subsequence ending at i.
5. Coin Change
Level: Medium
Problem:
You are given coins of different denominations and a total amount of money. Write a function to compute the fewest number of coins needed to make up that amount. If that amount cannot be made up by any combination of the coins, return -1.
Example:
Input: coins = [1, 2, 5], amount = 11
Output: 3
(The amount 11 can be made using 3 coins: 5 + 5 + 1)
Approach:
Use a DP array where each index represents the fewest number of coins needed for that amount.
5.1 Detail Solution
6. Longest Palindromic Subsequence
Level: Hard
Problem:
Given a string s, find the longest palindromic subsequence’s length in s.
Example:
Input: s = "bbbab"
Output: 4
(The longest palindromic subsequence is "bbbb")
Approach:
Use a 2D DP table where dp[i][j] represents the length of the longest palindromic subsequence in the substring s[i:j].
7. Edit Distance (Levenshtein Distance)
Level: Hard
Problem:
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted:
- Insert a character
- Delete a character
- Replace a character
Example:
Input: word1 = "horse", word2 = "ros"
Output: 3
(One possible sequence is: horse -> rorse -> rose -> ros)
Approach:
Use a DP table where dp[i][j] represents the minimum edit distance between word1[0:i] and word2[0:j].
8. Burst Balloons
Level: Hard
Problem:
Given n balloons, each with a number on it, you burst balloons to maximize your score. When you burst a balloon, the score obtained is the product of the adjacent balloons. Maximize the total score.
Example:
Input: nums = [3,1,5,8]
Output: 167
(You might burst balloons in the order 1, 5, 8, 3 for maximum points.)
Approach:
Use a 2D DP table where dp[left][right] represents the maximum score for bursting balloons in the subarray between left and right.
9. Maximum Profit in Job Scheduling
Level: Hard
Problem:
You have n jobs. Each job has a start time, end time, and profit. You’re tasked with scheduling the jobs to maximize total profit, ensuring no overlapping jobs.
Example:
Input: startTime = [1, 2, 3, 3], endTime = [3, 4, 5, 6], profit = [50, 10, 40, 70]
Output: 120
(Select jobs [1, 3] and [3, 6] for maximum profit.)
Approach:
Use dynamic programming with a combination of sorting and binary search to handle overlapping intervals.
10. Minimum Cost to Merge Stones
Level: Hard
Problem:
Given an array stones where stones[i] represents the weight of the ith stone, and an integer K, merge exactly K consecutive stones into one pile until there is only one pile left. Return the minimum cost to do so.
Example:
Input: stones = [3, 2, 4, 1], K = 2
Output: 20
Approach:
Use dynamic programming with a 3D DP table to represent different states of the merge.
These questions will help you practice the most frequent types of dynamic programming problems often encountered in Google interviews. Let me know if you need help implementing or breaking down any of these problems!
Leave a Reply