dl
BAN USERBelow is a recursive solution in Java. I've also added cache to avoid calculating the same things more than once.
In each step, we try to take both 1 character and 2 characters (in case it's in the legal range).
The complexity without the cache is: 2^n (since the recurrence relation is T(n) = T(n-1) + T(n-2) in case the 2 chars forms a valid key).
public static int countValidWords(String input) {
if (input == null || input.isEmpty()) {
return 0;
}
Map<String, String> dict = new HashMap<>();
for (int i = 0; i < 26; i++) {
char c = (char) ('A' + i);
dict.put(i + "", c + "");
}
// memorizing already calculated strings
Map<String, Integer> cache = new HashMap<>();
return countValidWordsHelper(input, dict, "", cache);
}
private static int countValidWordsHelper(String input, Map<String, String> dict, String currentWord, Map<String, Integer> cache) {
// you can comment out the if below to get a print of all options (using cache
// doesn't print the parts that are already in the cache
if (cache.containsKey(input)) {
return cache.get(input);
}
if (input.length() == 0) {
System.out.println(currentWord);
return 1;
}
if (input.length() == 1) {
System.out.println(currentWord + ", " + dict.get(input));
return 1;
}
String currentPartCode = input.substring(0, 2);
String currentPartStr = dict.get(currentPartCode);
int validaWordsMinusChar = countValidWordsHelper(input.substring(1), dict, currentWord + ", " + dict.get(input.substring(0, 1)), cache);
cache.put(input.substring(1), validaWordsMinusChar);
int validWordsMinusTwoChars = 0;
if (currentPartStr != null) {
validWordsMinusTwoChars = countValidWordsHelper(input.substring(2), dict, currentWord + ", " + currentPartStr, cache);
cache.put(input.substring(2), validWordsMinusTwoChars);
}
return validaWordsMinusChar + validWordsMinusTwoChars;
}
Below is the implementation in Java.
Iterative:
public static Set<String> getSubStringsIter(String input) {
Set<String> res = new HashSet<>();
if (input == null || input.isEmpty()) {
return res;
}
res.add("");
for (char c : input.toCharArray()) {
Set<String> resCopy = new HashSet<>();
for (String string : res) {
resCopy.add(string + c);
}
res.addAll(resCopy);
}
res.remove("");
return res;
}
Recursive Approach:
public static Set<String> getSubStringsRecursive(String input) {
if(input == null) {
return null;
}
Set<String> res = getSubStringsRecursiveHelper(input);
res.remove("");
return res;
}
public static Set<String> getSubStringsRecursiveHelper(String input) {
if (input.isEmpty()) {
return new HashSet<>(Arrays.asList(input));
}
Set<String> mergeResult = merge(input.substring(0,1), getSubStringsRecursiveHelper(input.substring(1)));
return mergeResult;
}
private static Set<String> merge(String substring, Set<String> res) {
Set<String> copy = new HashSet<>();
for (String string : res) {
copy.add(substring + string);
}
res.addAll(copy);
return res;
}
JUnit:
@Test
public void test_getSubStrings() {
String input = "abc";
Set<String> expectedRes = new HashSet<>(Arrays.asList("a","b","c","ab", "ac", "bc", "abc"));
Set<String> subStringsIter = InterviewQuestions.getSubStringsIter(input);
Assert.assertEquals((int) Math.pow(2, input.length())-1, subStringsIter.size());
Assert.assertEquals(expectedRes, subStringsIter);
Set<String> subStringsRecursiveRes = InterviewQuestions.getSubStringsRecursive(input);
Assert.assertEquals((int) Math.pow(2, input.length())-1, subStringsRecursiveRes.size());
Assert.assertEquals(expectedRes, subStringsRecursiveRes);
}
Code:
public static int[] sumArrays(int[] a, int[] b) {
int[] res = new int[Math.max(a.length, b.length) + 1];
int aIdx = a.length - 1;
int bIdx = b.length - 1;
int resIdx = res.length - 1;
int carry = 0;
while (aIdx >= 0 || bIdx >= 0) {
int sum = (aIdx >= 0 ? a[aIdx--] : 0) + (bIdx >= 0 ? b[bIdx--] : 0) + carry;
res[resIdx--] = sum % 10;
carry = sum / 10;
}
res[0] = carry;
return res;
}
JUnit:
@Test
public void test_sumArrays() {
int[] a = {3,5,7};
int[] b = {6,1,3,9};
int[] expected = {0,6,4,9,6};
Assert.assertArrayEquals(expected, InterviewQuestions.sumArrays(a, b));
int[] a1 = {9,9,9};
int[] b1 = {9,9,9,9};
int[] expected1 = {1,0,9,9,8};
Assert.assertArrayEquals(expected1, InterviewQuestions.sumArrays(a1, b1));
int[] a2 = {9,9,2};
int[] b2 = {0,1,3};
int[] expected2 = {1,0,0,5};
Assert.assertArrayEquals(expected2, InterviewQuestions.sumArrays(a2, b2));
}
public static String valueOf(Integer input) {
if (input == null) return null;
if (input == 0) return input+"";
StringBuilder sb = new StringBuilder();
boolean negative = input < 0;
int remainingNum = input * (negative ? -1 : 1);
while (remainingNum % 10 != 0) {
sb.append((remainingNum % 10) + "");
remainingNum = currentNum / 10;
}
if (negative) {
sb.append("-");
}
return sb.toString().reverse();
}
This would be O(n) where n is the number of digits in the number.
- dl March 16, 2016private static void getValidLists(Map<Integer, String> charsMap, String s, List<List<String>> allPerms,
List<String> currentList) {
if (s == null) {
return;
}
if (s.length() == 0) {
allPerms.add(currentList);
return;
}
if (s.length() == 1) {
currentList.add(getEncodedString(charsMap, s.substring(0, 1)));
allPerms.add(currentList);
return;
}
List<String> copy = new ArrayList<>(currentList);
copy.add(charsMap.get(Integer.parseInt(s.substring(0, 1))));
getValidLists(charsMap, s.substring(1), allPerms, copy);
String subString = s.substring(0, 2);
if (Integer.parseInt(subString) <= 26) {
currentList.add(getEncodedString(charsMap, subString));
getValidLists(charsMap, s.substring(2), allPerms, currentList);
}
}
private static String getEncodedString(Map<Integer, String> charsMap, String rawString) {
return charsMap.get(Integer.parseInt(rawString));
}
public static void main(String[] args) {
Map<Integer, String> charsMap = new HashMap<>();
for (int i = 0; i < 26; i++) {
charsMap.put(i + 1, String.valueOf((char) ('a' + i)));
}
List<List<String>> allPerms = new ArrayList<>();
getValidLists(charsMap, "1123", allPerms, new ArrayList<>());
System.out.println(allPerms);
}
I have a solution of O(n) (linear in the number of nodes).
The basic approach is command and conquer (and from bottom to top) - I use recursion to start from the leaves and continue to count nodes as long as my merge of each two nodes and their parent results in having a legal BST (on my way up).
Java code:
And some Unit test:
Note that BinarySearchTree and Node are my own implementations.
- dl May 27, 2016