Interview time ~2019.
Question 1:
-
Can you break the given string into words, provided by a given hashmap of frequency of word as <word: n>
Example 1:
HashMap -> {"abc":3, "ab":2, "abca":1} String: "abcabcabcabca" Output: true Explanation: "abc" + "abc" + "abc" + "abca"Example 2:
HashMap -> {"abc":3, "ab":2} String: "abcabab" Output: true Explanation: "abc" + "ab" + "ab"Example 3:
HashMap -> {"abc":3, "ab":2, "abca":1} String: "abcx" Output: false
My attempt so far is Backtracking Using map keys [and map as cache]
private static boolean canBreak(String str, Map<String, Integer> wordCount) {
if (str.isEmpty())
return true;
return canBreak(str, wordCount, new HashSet<>());
}
private static boolean canBreak(String str, Map<String, Integer> wordCount, Set<String> used) {
if (str.isEmpty())
return true;
/**
* find all the keys present in str and remove them as many times as said
*/
for (String key : wordCount.keySet()) {
int count = wordCount.get(key);
if (count > 0) {
int oldCount = count;
String oldString = str;
while (count > 0) {
if (str.contains(key))
str = str.replaceFirst(key, "");
else
break;
count--;
}
if (count == wordCount.get(key))
continue;
else {
wordCount.put(key, count);
if (canBreak(str, wordCount, used))
return true;
str = oldString;
wordCount.put(key, oldCount);
}
}
}
return false;
}Question 2:
My attempt:
public int[][] union(int[][] intervals) {
if (intervals == null || intervals.length == 0 || intervals[0].length == 0)
return intervals;
//Sort the interval on start time
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
int temp[][] = new int[intervals.length][2];
//start with first interval
temp[0][0] = intervals[0][0];
temp[0][1] = intervals[0][1];
int k = 0;
for (int i = 1; i < intervals.length; i++) {
//if start time of previous > end time of current, then merge
if (temp[k][1] >= intervals[i][0] && intervals[i][1] >= temp[k][0]) {
temp[k][0] = Math.min(temp[k][0], intervals[i][0]);
temp[k][1] = Math.max(temp[k][1], intervals[i][1]);
} else {
k++;
temp[k][0] = intervals[i][0];
temp[k][1] = intervals[i][1];
}
}
if (k == intervals.length)
return temp;
int res[][] = new int[k + 1][2];
for (int i = 0; i <= k; i++) {
res[i][0] = temp[i][0];
res[i][1] = temp[i][1];
}
return res;
}and intersection
public int[][] intersection(int[][] intervals) {
if (intervals == null || intervals.length == 0 || intervals[0].length == 0)
return intervals;
//Sort the interval on start time
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
int temp[][] = new int[intervals.length][2];
//start with first interval
temp[0][0] = intervals[0][0];
temp[0][1] = intervals[0][1];
int k = 0;
for (int i = 1; i < intervals.length; i++) {
//if start time of previous > end time of current, then merge
if (temp[k][1] >= intervals[i][0] && intervals[i][1] >= temp[k][0]) {
temp[k][0] = Math.max(temp[k][0], intervals[i][0]);
temp[k][1] = Math.min(temp[k][1], intervals[i][1]);
} else {
k++;
temp[k][0] = intervals[i][0];
temp[k][1] = intervals[i][1];
}
}
if (k == intervals.length)
return temp;
int res[][] = new int[k + 1][2];
for (int i = 0; i <= k; i++) {
res[i][0] = temp[i][0];
res[i][1] = temp[i][1];
}
return res;
}Comments (14)