I attended Goldman Sach's coderpad interview recently and I was unable to clear one of the two problems provided. Can someone help me on the approach here?
Problem statement: It was referred as "Magic Potion" by the interviewer
Combine ingredients in a specific order, any of which may be repeated. Encoding format: introduce * to indicate "repeat from beginning". Implement a function that takes as input an un-encoded potion and returns the minimum number of characters required to encode
Example Test Case:
Input:
ABABCABABCE
Output:
6
Explanation:
In the first part, ABAB, AB has repeated twice and it can be replaced as AB* and similarly ABABC is repeated twice and so it can be encoded as AB*C*. The last character is placed as it is and the final encoded format would be AB*C*E and so the length of the minimum encoded string is 6.
Thought Process #1:
My initial thought process was to provide a greedy solution. It was like to initialize our result to input.length() of the given string and, traverse through the string with index i ranging 1 <= i < input.length() and find if there is a substring match between the strings 0 to i - 1 and i to 2 * i - 1 and if there is a match, we can do result -= i + 1, meaning to reduce the matched length and + 1 to add the * character. This was a greedy O (n ^ 2) approach but it failed for the following test case.
input = "AAAAAA"
According to my approach, the encoding will be done like, A**AA which is having a length of 5. But the minimum solution would be, AAA* which is of length 4.
Thought Process #2:
Immediately I thought of a recursive approach to either choose to put a * when I find a match or it should continue by adding the current character as it is to the next index. Minimum of both would be the answer. Interviewer agreed to this approach, but this solution is having a TC of O (2 ^ n).
I was asked how I can reduce the complexity. I thought of memoization but I couldn't identify what parameters to use for memoizing the output. I even tried to think of a iterative DP solution but I couldn't. So I was asked to continue on the recursive approach and I came up with a solution something similar to below. This works for all the test cases with worst case TC but I was unable to provide a working recursive solution within the time during the interview :(.
class MagicPotion {
private static String minimalSteps(String ingredients, int index, StringBuilder encodedStringBuilder) {
if (index >= ingredients.length())
return encodedStringBuilder.toString(); // encoded String.
if (index != 0 && index * 2 <= ingredients.length()) {
String stringToCompare = ingredients.substring(0, index);
if (stringToCompare.equals(ingredients.substring(index, 2 * index))) { // On match from start of the String.
encodedStringBuilder.append("*");
String resultFromPath1 =
minimalSteps(
ingredients,
2 * index, // Encode and move forward
new StringBuilder(encodedStringBuilder.toString())
);
encodedStringBuilder.setLength(encodedStringBuilder.length() - 1); // Remove encoding.
encodedStringBuilder.append(ingredients.charAt(index));
String resultFromPath2 =
minimalSteps(
ingredients,
index + 1, // Append the character and move one step forward.
new StringBuilder(encodedStringBuilder.toString())
);
return resultFromPath1.length() < resultFromPath2.length() ? resultFromPath1 : resultFromPath2;
}
}
encodedStringBuilder.append(ingredients.charAt(index));
return minimalSteps(
ingredients,
index + 1, // Append the character and move one step forward.
new StringBuilder(encodedStringBuilder.toString())
);
}
private static Integer minimalSteps(String ingredients) {
String res = minimalSteps(ingredients, 0, new StringBuilder());
System.out.println(ingredients + ": " + res);
return res.length();
}
public static void main(String[] args) {
if (minimalSteps("ABABCABABCE") == 6
&& minimalSteps("ABCDABCE") == 8
&& minimalSteps("ABCABCE") == 5
&& minimalSteps("AAA") == 3
&& minimalSteps("AAAA") == 3
&& minimalSteps("BBB") == 3
&& minimalSteps("AAAAAA") == 4) {
System.out.println();
System.out.println("Pass");
} else {
System.out.println();
System.out.println("Fail");
}
}
}Can anyone help me with a better approach to solve this problem?