2 DS Question
Platform - Hackerrank
Question 1:
Solution: (All test cases Passed)
public static int maximumLearning(List<Integer> iv, List<Integer> articles, int p) {
int n = iv.size();
int[] dp = new int[p + 1];
for (int i = 0; i < n; i++) {
int value = iv.get(i);
int weight = 2 * articles.get(i); // Must read TWICE!
// Traverse from right to left for 0/1 knapsack
for (int j = p; j >= weight; j--) {
dp[j] = Math.max(dp[j], dp[j - weight] + value);
}
}
return dp[p];
}Question 2:
Problem Statement:
Given a number line with positions labeled from 0 to n, and a sequence of movements consisting of instructions 'l' (move left by 1) and 'r' (move right by 1), determine how many distinct subsequences of these moves will take you from a starting position x to an ending position y. Return the result modulo (10^9 + 7).
Notes:
A subsequence is formed by deleting zero or more elements from the original sequence without changing the order of the remaining elements.
A subsequence is distinct if its sequence of characters differs from another subsequence. Subsequences from different indices are considered the same if counted only once, e.g., the subsequence containing 'rr' is only counted once.
Starting at position j, an instruction 'l' moves to position j - 1, and an instruction 'r' moves to position j + 1.
Function Description:
Complete the function distinctMoves in the editor with the following parameter(s):
string s: the sequence of moves
int n: the upper bound of the number line
int x: the starting point
int y: the ending point
Returns:
int: the number of distinct subsequences modulo (10^9 + 7)
Constraints:
1 ≤ |s| ≤ 10^5
0 ≤ x, y, n ≤ 2500
Sample Input For Custom Testing:
rrlrlr
6
1
2
Sample Output:
7
Solution : (Partial Test cases Got pass)
Please comment if you find the better approach.
public static int distinctMoves(String s, int n, int x, int y) {
int m = s.length();
// dp[j] = set of distinct move sequences that end at position j
// We use HashMap<String, Integer> where the key is the move sequence
// and value is 1 (just for counting distinct sequences)
Map<Integer, Set<String>> dp = new HashMap<>();
Map<Integer, Set<String>> newDp = new HashMap<>();
// Initialize
for (int i = 0; i <= n; i++) {
dp.put(i, new HashSet<>());
newDp.put(i, new HashSet<>());
}
// Base case: start at position x with empty move sequence
dp.get(x).add("");
for (int i = 0; i < m; i++) {
// Clear newDp
for (int j = 0; j <= n; j++) {
newDp.get(j).clear();
newDp.get(j).addAll(dp.get(j)); // Skip this character
}
// Process each position
for (int j = 0; j <= n; j++) {
for (String moveSeq : dp.get(j)) {
// Use this character
if (s.charAt(i) == 'l' && j > 0) {
newDp.get(j - 1).add(moveSeq + "l");
} else if (s.charAt(i) == 'r' && j < n) {
newDp.get(j + 1).add(moveSeq + "r");
}
}
}
// Swap dp and newDp
Map<Integer, Set<String>> temp = dp;
dp = newDp;
newDp = temp;
}
// Count distinct move sequences at position y (exclude empty sequence)
Set<String> result = dp.get(y);
result.remove(""); // Remove empty sequence if x == y
return result.size();
}