Placement training
Question. Here's a program that takes user input for two sorted arrays and merges them into a third sorted array:
import java.util.*;
public class MergeSortedArrays {
public static int[] mergeSortedArrays(int[] arr1, int[] arr2) {
int[] mergedArray = new int[arr1.length + arr2.length];
int i = 0, j = 0, k = 0;
while (i < arr1.length && j < arr2.length) {
if (arr1[i] <= arr2[j]) {
mergedArray[k] = arr1[i];
i++;
} else {
mergedArray[k] = arr2[j];
j++;
}
k++;
}
// Copy any remaining elements from both arrays
while (i < arr1.length) {
mergedArray[k] = arr1[i];
i++;
k++;
}
while (j < arr2.length) {
mergedArray[k] = arr2[j];
j++;
k++;
}
return mergedArray;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the size of the first sorted array: ");
int size1 = scanner.nextInt();
int[] arr1 = new int[size1];
System.out.println("Enter the elements of the first sorted array:");
for (int i = 0; i < size1; i++) {
arr1[i] = scanner.nextInt();
}
System.out.print("Enter the size of the second sorted array: ");
int size2 = scanner.nextInt();
int[] arr2 = new int[size2];
System.out.println("Enter the elements of the second sorted array:");
for (int i = 0; i < size2; i++) {
arr2[i] = scanner.nextInt();
}
int[] mergedArray = mergeSortedArrays(arr1, arr2);
System.out.println("Merged sorted array: " + Arrays.toString(mergedArray));
scanner.close();
}
}
Question1.The Climbing Stairs problem
This is one of the most popular coding problems which can be solved using the Dynamic Programming technique. In this problem, you are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. The question is, in how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step.
public class ClimbingStairs {
public static int climbStairs(int n) {
if (n <= 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
public static void main(String[] args) {
int n1 = 2;
int n2 = 3;
System.out.println("Number of ways to climb " + n1 + " stairs: " + climbStairs(n1));
System.out.println("Number of ways to climb " + n2 + " stairs: " + climbStairs(n2));
}
}
Question 2. The Knapsack problem [Solved]
This is another common Dynamic programming-based coding problem and a pattern which can solve many such questions. In this type of problem, you will be given the weights and profits of ’N’ items, put these items in a knapsack which has a capacity ‘C’. Your goal: get the maximum profit from the items in the knapsack. Each item can only be selected once.
A common example of this optimization problem involves which fruits in the knapsack you’d include getting maximum profit. Here’s the weight and profit of each fruit:
Items: { Apple, Orange, Banana, Melon }
Weight: { 2, 3, 1, 4 }
Profit: { 4, 5, 3, 7 }
Knapsack capacity: 5
Let’s try to put different combinations of fruits in the knapsack, such that their total weight is not more than 5.
Apple + Orange (total weight 5) => 9 profit
Apple + Banana (total weight 3) => 7 profit
Orange + Banana (total weight 4) => 8 profit
Banana + Melon (total weight 5) => 10 profit
This shows that Banana + Melon is the best combination, as it gives us the maximum profit and the total weight does not exceed the capacity. You can also see this free lesson from the Dynamic Programming course on Educative for a detailed solution to this problem.
Question 3. Edit Distance Problem
This is one of the easier dynamic programming problems. In this question, you will be given two words word1 and word2, to find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a character
Delete a character
Replace a character
Example 1:
Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
horse -> rorse (replace ‘h’ with ‘r’)
rorse -> rose (remove ‘r’)
rose -> ros (remove ‘e’)
Question 4. Longest palindromic subsequence Question
This is another common Dynamic programming question and pattern. In this type of DP question, you will be given a sequence, find the length of its Longest Palindromic Subsequence (or LPS). In a palindromic subsequence, elements read the same backward and forward.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input:
“bbbab”
Output:
4
Explanation: LPS is “bbbb”.
Question 4. Best Time to Buy and Sell Stock Problem
In this question, you will be given an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6–1 = 5.
Not 7–1 = 6, as the selling price needs to be larger than buying price.
Question 5. The Fibonacci problem [Solution]
This is one of the easiest dynamic programming questions and many of you have already solved it without even knowing that you are using Dynamic programming. This is also the most common example of DP and many instructors use Fibonacci numbers to teach Dynamic programming. In this question, you will be asked to write a function to calculate the nth Fibonacci number.
Fibonacci numbers are a series of numbers in which each number is the sum of the two preceding numbers. The first few Fibonacci numbers are 0, 1, 2, 3, 5, 8, and so on.
We can define the Fibonacci numbers as:
Fib(n) = Fib(n-1) + Fib(n-2) for n > 1
Given that: Fib(0) = 0, and Fib(1) = 1
Question 6. The Coin Change Problem
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up of any combination of the coins, return -1.
Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Question 7. Longest common substring
Given two strings ‘S1’ and ‘s2’, find the length of the longest substring common in both the strings.
Example 1:
Input: s1 = “abdca”
s2 = “cbda”
Output: 2
Explanation: The longest common substring is “bd”.
Question 8. Longest common subsequence
Given two strings ‘S1’ and ‘s2’, find the length of the longest subsequence which is common in both the strings.
Example 1:
Input: s1 = “abdca”
s2 = “cbda”
Output: 3
Explanation: The longest substring is “bda”.
Question 9. Equal Subset Sum Partition Problem
This is another popular Dynamic Programming question that is very similar to the Knapsack problem. If you know how to solve knapsack then you can solve this too.
In his problem you are given a set of positive numbers, find if we can partition it into two subsets such that the sum of elements in both the subsets is equal.
Example 1:
Input: {1, 2, 3, 4}
Output: True
Explanation: The given set can be partitioned into two subsets with equal sum: {1, 4} & {2, 3}
Example 2:
Input: {1, 1, 3, 4, 7}
Output: True
Explanation: The given set can be partitioned into two subsets with equal sum: {1, 3, 4} & {1, 7}
Example 3:
Input: {2, 3, 4, 6}
Output: False
Explanation: The given set cannot be partitioned into two subsets with an equal sum.
Question 10. Continuous Subarray Sum
This is another popular dynamic programming-based coding problem from interviews. In this problem, you will be given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of k, that is, sums up to n*k where n is also an integer.
Example 1:
Input: [23, 2, 4, 6, 7], k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.
Question 11. Word Break Problem
Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. See following examples for more details.
This is a famous Google interview question, also being asked by many other companies now a days.
Consider the following dictionary
{ i, like, sam, sung, samsung, mobile, ice,
cream, icecream, man, go, mango}
Input: ilike
Output: Yes
The string can be segmented as "i like".
Input: ilikesamsung
Output: Yes
The string can be segmented as "i like samsung"
or "i like sam sung".
Recursive implementation:
The idea is simple, we consider each prefix and search for it in dictionary. If the prefix is present in dictionary, we recur for rest of the string (or suffix).
Question 12. Maximal Product when Cutting Rope
Given a rope of length n meters, cut the rope in different parts of integer lengths in a way that maximizes product of lengths of all parts. You must make at least one cut. Assume that the length of rope is more than 2 meters.
Examples:
Input: n = 2
Output: 1 (Maximum obtainable product is 1*1)
Input: n = 3
Output: 2 (Maximum obtainable product is 1*2)
Input: n = 4
Output: 4 (Maximum obtainable product is 2*2)
Input: n = 5
Output: 6 (Maximum obtainable product is 2*3)
Input: n = 10
Output: 36 (Maximum obtainable product is 3*3*4)
This problem is similar to Rod Cutting Problem. We can get the maximum product by making a cut at different positions and comparing the values obtained after a cut. We can recursively call the same function for a piece obtained after a cut.
Let maxProd(n) be the maximum product for a rope of length n. maxProd(n) can be written as following.
maxProd(n) = max(i*(n-i), maxProdRec(n-i)*i) for all i in {1, 2, 3 .. n}
Question 13. Dice Throw Problem
Given n dice each with m faces, numbered from 1 to m, find the number of ways to get sum X. X is the summation of values on each face when all the dice are thrown.
The Naive approach is to find all the possible combinations of values from n dice and keep on counting the results that sum to X.
This problem can be efficiently solved using Dynamic Programming (DP).
Let the function to find X from n dice is: Sum(m, n, X)
The function can be represented as:
Sum(m, n, X) = Finding Sum (X - 1) from (n - 1) dice plus 1 from nth dice
+ Finding Sum (X - 2) from (n - 1) dice plus 2 from nth dice
+ Finding Sum (X - 3) from (n - 1) dice plus 3 from nth dice
And so on…………
+ Finding Sum (X - m) from (n - 1) dice plus m from nth dice
So we can recursively write Sum(m, n, x) as following
Sum(m, n, X) = Sum(m, n - 1, X - 1) +
Sum(m, n - 1, X - 2) +
.................... +
Sum(m, n - 1, X - m)
Question 14. Egg Dropping Puzzle
You are given k identical eggs and you have access to a building with n floors labeled from 1 to n.
You know that there exists a floor f where 0 <= f <= n such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break.
Each move, you may take an unbroken egg and drop it from any floor x (where 1 <= x <= n). If the egg breaks, you can no longer use it. However, if the egg does not break, you may reuse it in future moves.
Return the minimum number of moves that you need to determine with certainty what the value of f is.
Question 15. Boolean Parenthesization Problem
Given a boolean expression with the following symbols.
Symbols
'T' ---> true
'F' ---> false
And following operators filled between symbols
Operators
& ---> boolean AND
| ---> boolean OR
^ ---> boolean XOR
Count the number of ways we can parenthesize the expression so that the value of expression evaluates to true.
Let the input be in form of two arrays one contains the symbols (T and F) in order and the other contains operators (&, | and ^}
Comments
Post a Comment