-
Notifications
You must be signed in to change notification settings - Fork 2
Recursion Problems and Patterns
Mani Bhushan edited this page Sep 27, 2016
·
52 revisions
Given an array of positive numbers, find the maximum sum of a subsequence
with the constraint that no 2 numbers in the sequence should be adjacent in
the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should
return 15 (sum of 3, 5 and 7).
public Integer maxSumNonAdj(int[] A) {
if (A == null || A.length < 1) {
return null;
}
int index = 0;
return maxSumNonAdj(A, index);
}
private int maxSumNonAdj(int[] A, int index) {
if (index >= A.length) {
return 0;
}
return Math.max(A[index] + maxSumNonAdj(A, index + 2),
maxSumNonAdj(A, index + 1));
}
Given three strings A, B and C. Write a function that checks whether C is
an interleaving of A and B. C is said to be interleaving A and B, if it
contains all characters of A and B and order of all characters in individual
strings is preserved.
public boolean isInterleaved(String A, String B, String C) {
if (A == null && B == null && C == null) {
return true;
}
if (A.length() + B.length() != C.length()) {
return false;
}
int i = 0, j = 0, index = 0;
return isInterleaved(A.toCharArray(), B.toCharArray(), C.toCharArray(),
i, j, index);
}
private boolean isInterleaved(char[] A, char[] B, char[] C, int i, int j,
int index) {
if (i == A.length && j == B.length && index == C.length) {
return true;
}
boolean flag1 = false;
boolean flag2 = false;
if ((i < A.length) && (A[i] == C[index])) {
flag1 = isInterleaved(A, B, C, i + 1, j, index + 1);
}
if ((j < B.length) && (B[j] == C[index])) {
flag2 = isInterleaved(A, B, C, i, j + 1, index + 1);
}
return flag1 || flag2;
}
isInterleaved("XXY", "XXZ", "XXZXXXY"); //false
isInterleaved("XY", "WZ", "WZXY"); //true
isInterleaved("XY", "X", "XXY"); //true
isInterleaved("YX", "X", "XXY"); //false
isInterleaved("XXY", "XXZ", "XXXXZY"); //true
Given a set of possible change, such as {1, 5, 10, 25}, and an amount such as 13,
return all possible ways you can give change back to someone.
Output:
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 5]
[1, 1, 1, 5, 5]
[1, 1, 1, 10]
public void change(int [] coins, int amount) {
int index = 0;
List<Integer> result = new ArrayList<Integer>();
change(coins, amount, index, result);
}
private void change(int [] coins, int amount, int index, List<Integer> result) {
if (amount == 0) {
System.out.println(result);
return;
}
if (amount < 0) {
return;
}
if (index == coins.length) {
return;
}
result.add(coins[index]);
change(coins, amount - coins[index], index, result);
result.remove(result.size()-1);
change(coins, amount, index+1, result);
}
Given a dictionary, a method to do lookup in dictionary and a M x N board where
every cell has one character. Find all possible words that can be formed by a sequence
of adjacent charactersNote that we can move to any of 8 adjacent characters, but a word
should not have multiple instances of same cell.
Example:
Input: dictionary[] = {"GEEKS", "FOR", "QUIZ", "GO"};
boggle[][] = {{'G','I','Z'},
{'U','E','K'},
{'Q','S','E'}};
isWord(str): returns true if str is present in dictionary
else false.
Output: Following words of dictionary are present
GEEKS
QUIZ
public void playBoggle(char[][] boggle) {
if (boggle == null) {
return;
}
int row = boggle.length;
int col = boggle[0].length;
boolean[][] visited = new boolean[row][col];
List<String> result = new ArrayList<String>();
StringBuffer sb = new StringBuffer();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
findWords(boggle, i, j, visited, sb, result);
}
}
System.out.println(result.toString());
}
private void findWords(char[][] boggle, int i, int j, boolean[][] visited,
StringBuffer sb, List<String> result) {
if (i < 0 || i >= boggle.length || j < 0 || j >= boggle[0].length) {
return;
}
if (visited[i][j]) {
return;
}
sb.append(boggle[i][j]);
visited[i][j] = true;
if (dict.contains(sb.toString())) {
result.add(sb.toString());
}
for (int r = -1; r <= 1; r++) {
for (int c = -1; c <= 1; c++) {
if (r == 0 && c == 0) {
continue;
}
findWords(boggle, i + r, j + c, visited, sb, result);
}
}
visited[i][j] = false;
sb.deleteCharAt(sb.length() - 1);
}
PART-1
"Given a pattern and a string - find if the string follows the same pattern
Eg: Pattern : [a b b a], String : cat dog dog cat “
PART-2
"Given a pattern and a string input - find if the string follows the same
pattern and return 0 or 1.
Examples:
1) Pattern : "abba", input: "redblueredblue" should return true.
2) Pattern: "aaaa", input: "asdasdasdasd" should return true.
3) Pattern: "aabb", input: "xyzabcxzyabc" should return false.
public static void main(String[] args) {
CombinationRangeK cr = new CombinationRangeK();
String[] input = { "redbluebluered", "dogdogdogdog", "dogdogdogdog",
"dogcatcatdig" };
String[] pattern = { "abba", "abba", "aaaa", "abbc" };
for (int i = 0; i < input.length; i++) {
System.out.println("input: " + input[i]);
System.out.println("pattern: " + pattern[i]);
System.out.println("pattern match-2: "
+ cr.isPatternMatch(input[i], pattern[i]));
System.out.println();
}
}
public boolean isPatternMatch(String input, String pattern) {
if (input == null || pattern == null) {
return false;
}
List<ArrayList<String>> combos = combination(input, pattern);
for (ArrayList<String> list : combos) {
String[] data = list.toArray(new String[0]);
if (matchPattern(data, pattern)) {
return true;
}
}
return false;
}
public List<ArrayList<String>> combination(String data, String pattern) {
char[] input = data.toCharArray();
int K = 5;
int patLen = pattern.length();
List<String> result = new ArrayList<String>();
List<ArrayList<String>> combos = new ArrayList<ArrayList<String>>();
combination(input, result, K, 0, 0, patLen, combos);
return combos;
}
public void combination(char[] input, List<String> result, int K, int pos,
int index, int patLen, List<ArrayList<String>> combos) {
if (index > patLen) {
return;
}
if (pos == input.length) {
if (index != patLen) {
return;
}
combos.add(new ArrayList<String>(result));
return;
}
for (int i = pos; i < pos + K && i < input.length; i++) {
String str = formString(input, pos, i);
result.add(str);
combination(input, result, K, i + 1, index + 1, patLen, combos);
result.remove(result.size() - 1);
}
}
private String formString(char[] A, int start, int end) {
StringBuffer sb = new StringBuffer();
for (int i = start; i <= end; i++) {
sb.append(A[i]);
}
return sb.toString();
}
//PART-1 "Given a pattern and a string - find if the string follows the same
//pattern Eg: Pattern : [a b b a], String : cat dog dog cat “
public boolean matchPattern(String[] strArr, String pattern) {
if (strArr == null || pattern == null) {
return false;
}
char[] patArr = pattern.toCharArray();
if (patArr.length != strArr.length) {
return false;
}
Map<Character, String> hmap = new HashMap<Character, String>();
hmap.put(patArr[0], strArr[0]);
for (int i = 1; i < patArr.length; i++) {
if (hmap.containsKey(patArr[i])) {
if (!hmap.get(patArr[i]).equals(strArr[i])) {
return false;
}
} else if (hmap.containsValue(strArr[i])) {
return false;
} else {
hmap.put(patArr[i], strArr[i]);
}
}
return true;
}
input: redbluebluered
pattern: abba
pattern match-2: true
input: dogdogdogdog
pattern: abba
pattern match-2: false
input: dogdogdogdog
pattern: aaaa
pattern match-2: true
input: dogcatcatdig
pattern: abbc
pattern match-2: true
Given a total and coins of certain denominations with infinite supply, how many minimum
number of coins would it take to form this total.
Example:
int[] coins = { 1, 2, 3 };
int target = 5;
Result:
[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[2, 3] <- Answer (two coins of denomination 2 and 3)
public void coinChange(int[] coins, int target) {
int index = 0;
List<Integer> changes = new ArrayList<Integer>();
int sum = 0;
coinChange(coins, index, target, sum, changes);
}
private void coinChange(int[] coins, int i, int target, int sum,
List<Integer> changes) {
if (target == sum) {
System.out.println(changes.toString());
return;
}
if (sum > target) {
return;
}
if (i >= coins.length) {
return;
}
changes.add(coins[i]);
sum += coins[i];
coinChange(coins, i, target, sum, changes);
sum -= coins[i];
changes.remove(changes.size() - 1);
coinChange(coins, i + 1, target, sum, changes);
}
Given a string and a dictionary, return true if string can be split into multiple
words such that each word is in dictionary. If not return false.
String input = "thisissentence";
dict = {"this", "is", "sentence", "sent", "ence"};
Output:
[this, is, sent, ence]
[this, is, sentence]
public void wordBreak(String input) {
List<String> result = new ArrayList<String>();
wordBreak(input, 0, new StringBuffer(), result);
}
private void wordBreak(String text, int index, StringBuffer sb, List<String> result) {
if (index >= text.length()) {
int count = 0;
for (String st: result) {
count += st.length();
}
if (count >= text.length()) {
System.out.println(result);
}
return;
}
int len = text.length();
for (int i=index; i<len; i++) {
char ch = text.charAt(i);
sb.append(ch);
if (dict.contains(sb.toString())) {
result.add(sb.toString());
wordBreak(text, i+1, new StringBuffer(), result);
result.remove(result.size()-1);
}
}
}
0/1 Knapsack Problem - Given items of certain weights/values and maximum allowed weight,
how to pick items from this set to maximize sum of value of items such that sum of weights
is less than or equal to maximum allowed weight.
Example:
int [] weights = {2, 2, 4, 5};
int [] values = { 2, 4, 6, 9};
int total = 8;
Output:
result: [13, [4, 9]]
public void knapsack(int [] weights, int [] values, int target) {
int index = 0;
List<Integer> list = new ArrayList<Integer>();
int currSum = 0;
int maxValue = Integer.MIN_VALUE;
Result ans = new Result(maxValue);
knapsack(weights, values, target, currSum, index, list, ans );
System.out.println("result: " + ans);
}
public void knapsack(int [] weights, int [] values, int target, int currSum, int index, List<Integer> list, Result ans) {
if (currSum <= target) {
int sum = list.stream().mapToInt(Integer::intValue).sum();
if (sum > ans.maxValue) {
ans.maxValue = sum;
ans.indices = ((List<Integer>) ((ArrayList<Integer>) list).clone());
}
}
if (currSum > target) {
return;
}
if (index >= weights.length) {
return;
}
list.add(values[index]);
knapsack(weights, values, target, currSum+weights[index], index+1, list, ans);
list.remove(list.size()-1);
knapsack(weights, values, target, currSum, index+1, list, ans);
}
Given a string that contains only digits 0-9 and a target value, return all
possibilities to add binary operators (not unary) +, -, or * between the digits
so they evaluate to the target value.
Examples:
"123", 6 -> ["1+2+3", "1*2*3"]
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []
INPUT/OUTPUT:
ao.findExpression("105", 5);
combo: [[1, 0, 5], [1, 5], [10, 5]]
list data: [1, 0, 5]
stack: [1, 0, 5]
[+, *]
list data: [1, 5]
stack: [1, 5]
[*]
list data: [10, 5]
stack: [10, 5]
[-]
public void findExpression(String digits, int target) {
char [] chArr = digits.toCharArray();
int [] nums = new int[chArr.length];
for (int i=0; i<chArr.length; i++) {
nums[i] = Character.getNumericValue(chArr[i]);
}
List<ArrayList<Integer>> combo = validCombinations(nums);
System.out.println("combo: " + combo.toString());
for (List<Integer> list : combo) {
int index = 0;
Stack<Integer> stack = new Stack<Integer>();
int size = list.size();
for (int i = 0; i < size; i++) {
stack.push(list.get(i));
}
String[] buff = new String[stack.size()-1];
String[] operators = { "*", "+", "-" };
System.out.println("list data: " + list.toString());
System.out.println("stack: " + stack.toString());
expression(stack, index, target, operators, buff);
}
}
public void expression(Stack<Integer> stack, int index, int target, String [] operators, String [] buff) {
//System.out.println("stack: " + stack.toString());
if (stack.size() == 1 && stack.peek() == target) {
System.out.println(Arrays.toString(buff));
return;
}
if (index == buff.length) {
return;
}
if (stack.size() < 2) {
return;
}
for (int i=0; i<operators.length; i++) {
int x = stack.pop();
int y = stack.pop();
int ans = evaluate(x, y, operators[i]);
//if (ans <= target) {
stack.push(ans);
buff[index] = operators[i];
expression(stack, index+1, target, operators, buff);
stack.pop();
//}
stack.push(y);
stack.push(x);
}
}
private int evaluate(int x, int y, String operator) {
if (operator.equals("*")) {
return x*y;
} else if (operator.equals("+")) {
return x+y;
} else if (operator.equals("-")) {
return y-x;
}
//log error condition.
return 0;
}
There are n-pairs and therefore 2n people. everyone has one unique number ranging from 1 to 2n.
All these 2n persons are arranged in random fashion in an Array of size 2n. We are also given who
is partner of whom. Find the minimum number of swaps required to arrange these pairs such that all
pairs become adjacent to each other.
Example:
Input:
n = 3
pairs[] = {1->3, 2->6, 4->5} // 1 is partner of 3 and so on
arr[] = {3, 5, 6, 4, 1, 2}
Output: 2
We can get {3, 1, 5, 4, 6, 2} by swapping 5 & 6, and 6 & 1
public static void main(String[] args) {
MinimumSwaps ms = new MinimumSwaps();
int [] A = {1, 5, 6, 4, 3, 2};
Map<Integer, Integer> hmap = new HashMap<Integer, Integer>();
hmap.put(1, 3);
hmap.put(3, 1);
hmap.put(2, 6);
hmap.put(6, 2);
hmap.put(4, 5);
hmap.put(5, 4);
System.out.println("min swaps: " + ms.minSwaps(A, hmap));
}
public int minSwaps(int [] A, Map<Integer, Integer> pairs) {
if (A == null || A.length < 1) {
return 0;
}
Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
for (int i=0; i<A.length; i++) {
indexMap.put(A[i], i);
}
int index = 0;
return minSwap(A, pairs, indexMap, index);
}
private int minSwap(int [] A, Map<Integer, Integer> pairs, Map<Integer, Integer> indexMap, int index) {
if (index == A.length) {
return 0;
}
int v1 = A[index];
int v2 = A[index+1];
//first condition - v1 and v2 are pairs, if so recurse on remaining n-2 elements
if (pairs.get(v1) == v2) {
return minSwap(A, pairs, indexMap, index+2);
} else {
int idx1 = indexMap.get(v1);
int idx2 = indexMap.get(v2);
int idx3 = indexMap.get(pairs.get(v1));
int idx4 = indexMap.get(pairs.get(v2));
swap(A, indexMap, idx2, idx3, v2, pairs.get(v1));
int first = minSwap(A, pairs, indexMap, index+2);
swap(A, indexMap, idx2, idx3, v2, pairs.get(v1));
swap(A, indexMap, idx1, idx4, v1, pairs.get(v2));
int second = minSwap(A, pairs, indexMap, index+2);
swap(A, indexMap, idx1, idx4, v1, pairs.get(v2));
return 1 + Math.min(first, second);
}
}
private void swap(int [] A, Map<Integer, Integer> indexMap, int i, int j, int x, int y) {
indexMap.put(y, i);
indexMap.put(x, j);
int buff = A[i];
A[i] = A[j];
A[j] = buff;
}
Input -> {"Hello", "World"} , {"Game"}, {"Go","Home"}
Output:
[Hello, Game, Go]
[Hello, Game, Home]
[World, Game, Go]
[World, Game, Home]
private void cartesian(ArrayList<ArrayList<String>> list, int size, int index, List<String> result) {
if (result.size() == list.size()) {
System.out.println(result.toString());
return ;
}
ArrayList<String> currList = list.get(index);
int len = currList.size();
for (int j = 0; j < len; j++) {
result.add(currList.get(j));
cartesian(list, size, index + 1, result);
result.remove(result.size() - 1);
}
}
(17). Given an input and total, print all combinations with repetitions in this input which sums to given total.
Input - {2,3,5}
Total - 10
Output:
[2,2,2,2,2],
[2,2,3,3],
[2,3,5],
[5,5]]
public void combinationSum(int [] A, int target) {
int sum = 0;
int index = 0;
List<Integer> result = new ArrayList<Integer>();
combinationSum(A, target, index, sum, result);
}
private void combinationSum(int [] A, int target, int index, int sum, List<Integer> result) {
if (sum == target) {
System.out.println(result.toString());
return;
}
if (index >= A.length) {
return;
}
if (sum > target) {
return;
}
if (sum < target) {
sum += A[index];
result.add(A[index]);
combinationSum(A, target, index, sum, result);
sum -= A[index];
result.remove(result.size()-1);
combinationSum(A, target, index+1, sum, result);
}
}
Do regular permutation with repetition with additional constraint of keeping duplicates
away from each other.
Input:
"aab"
"abccc"
"aaab"
Output:
[a, b, a]
++++++++++++++++++++++++++++++++++++++++++
[c, b, c, a, c]
[c, b, c, a, c]
[c, a, c, b, c]
[c, a, c, b, c]
[c, b, c, a, c]
[c, a, c, b, c]
[c, b, c, a, c]
[c, a, c, b, c]
++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++
public void fancyShuffle(String input) {
char [] A = input.toCharArray();
int index = 0;
fancyShuffle(A, index);
}
private void fancyShuffle(char [] A, int index) {
if (index == A.length) {
System.out.println(Arrays.toString(A));
return ;
}
for (int i=index; i<A.length; i++) {
if (i != index && A[i] == A[index]) {
continue;
}
if (index > 0 && A[i] == A[index-1]) {
continue;
}
char ch = A[i];
A[i] = A[index];
A[index] = ch;
fancyShuffle(A, index+1);
ch = A[i];
A[i] = A[index];
A[index] = ch;
}
}
Input:
A = [to]
B = [my]
Output:
[t, o, m, y]
[t, m, o, y]
[t, m, y, o]
[m, t, o, y]
[m, t, y, o]
[m, y, t, o]
public void interleave(String A, String B) {
int i=0, j=0, index=0;
char [] data = new char[A.length() + B.length()];
interleave(A.toCharArray(), i, B.toCharArray(), j, index, data);
}
private void interleave(char [] A, int i, char [] B, int j, int index, char [] data) {
if (index == data.length) {
System.out.println(Arrays.toString(data));
return;
}
if (i < A.length) {
data[index] = A[i];
interleave(A, i+1, B, j, index+1, data);
}
if (j < B.length) {
data[index] = B[j];
interleave(A, i, B, j+1, index+1, data);
}
}
(14). Generate all permutations of string in lexicographically sorted order where repetitions of character is possible in string.
Input: [a, b, c]
Output:
[a, a, a]
[a, a, b]
[a, a, c]
[a, b, a]
[a, b, b]
[a, b, c]
[a, c, a]
[a, c, b]
[a, c, c]
[b, a, a]
[b, a, b]
[b, a, c]
[b, b, a]
[b, b, b]
[b, b, c]
[b, c, a]
[b, c, b]
[b, c, c]
[c, a, a]
[c, a, b]
[c, a, c]
[c, b, a]
[c, b, b]
[c, b, c]
[c, c, a]
[c, c, b]
[c, c, c]
public void permute(char [] A) {
char [] data = new char[A.length];
int index = 0;
permute(A, index, data);
}
private void permute(char [] A, int index, char [] data) {
if (index >= A.length) {
System.out.println(Arrays.toString(data));
return;
}
for (int i=0; i<A.length; i++) {
data[index] = A[i];
permute(A, index+1, data);
}
}
Input: {"abc"};
Output:
[abc, acb, bac, bca, cab, cba]
public void printPerms(char [] input) {
int index = 0;
List<String> perms = new ArrayList<String>();
permute(input, index, perms);
Collections.sort(perms);
System.out.println(perms.toString());
}
private void permute(char [] input, int index, List<String> perms) {
if (index == input.length) {
perms.add(new String(input));
System.out.println(Arrays.toString(input));
}
for (int i=index; i<input.length; i++) {
char ch = input[i];
input[i] = input[index];
input[index] = ch;
permute(input, index+1, perms);
ch = input[i];
input[i] = input[index];
input[index] = ch;
}
}
Custom Tree Problem
You are given a set of links, e.g.
a ---> b
b ---> c
b ---> d
a ---> e
Print the tree that would form when each pair of these links that has the same character as start and end point is joined together. You have to maintain fidelity w.r.t. the height of nodes, i.e. nodes at height n from root should be printed at same row or column. For set of links given above, tree printed should be –
-->a
|-->b
| |-->c
| |-->d
|-->e
Note that these links need not form a single tree; they could form, ahem, a forest. Consider the following links
a ---> b
a ---> g
b ---> c
c ---> d
d ---> e
c ---> f
z ---> y
y ---> x
x ---> w
The output would be following forest.
-->a
|-->b
| |-->c
| | |-->d
| | | |-->e
| | |-->f
|-->g
-->z
|-->y
| |-->x
| | |-->w
You can assume that given links can form a tree or forest of trees only, and there are no duplicates among links.
Below code output:
roots: [a]
map: {a=[b, e], b=[c, d]}
|-->a
|-->b
|-->c
|-->d
|-->e
--------------------------------------------------
roots: [a, z]
map: {a=[b, g], b=[c], c=[d, f], d=[e], x=[w], y=[x], z=[y]}
|-->a
|-->b
|-->c
|-->d
|-->e
|-->f
|-->g
|-->z
|-->y
|-->x
|-->w
*****************************CODE****************************
public static void main(String[] args) {
CustomTree ct = new CustomTree();
String [][] nodes = {
{"a", "b"},
{"b", "c"},
{"b", "d"},
{"a", "e"}
};
ct.printForest(nodes);
System.out.println("--------------------------------------------------");
String [][] nodes1 = {
{"a", "b"},
{"a", "g"},
{"b", "c"},
{"c", "d"},
{"d", "e"},
{"c", "f"},
{"z", "y"},
{"y", "x"},
{"x", "w"},
};
ct.printForest(nodes1);
}
public void printForest(String [][] nodes) {
Set<String> start = new HashSet<String>();
Set<String> end = new HashSet<String>();
Map<String, ArrayList<String>> hmap = new HashMap<String, ArrayList<String>>();
for (int i=0; i<nodes.length; i++) {
start.add(nodes[i][0]);
end.add(nodes[i][1]);
ArrayList<String> list = new ArrayList<String>();
if (hmap.containsKey(nodes[i][0])) {
list = hmap.get(nodes[i][0]);
}
list.add(nodes[i][1]);
hmap.put(nodes[i][0], list);
}
List<String> roots = new ArrayList<String>();
for (String st: start) {
if (!end.contains(st)) {
roots.add(st);
}
}
System.out.println("roots: " + roots.toString());
System.out.println("map: " + hmap.toString());
int step = 1;
HashSet<String> visited = new HashSet<String>();
for (String src: roots) {
printTree(src, hmap, visited, step);
}
}
private void printTree(String src, Map<String, ArrayList<String>> hmap, HashSet<String> visited, int step) {
visited.add(src);
StringBuffer sb = new StringBuffer();
for (int i = 0; i < step; i++) {
sb.append(" ");
}
sb.append("|-->");
System.out.println(sb.toString() + src);
if (hmap.containsKey(src)) {
List<String> neighbors = hmap.get(src);
for (String dest: neighbors) {
if (!visited.contains(dest)) {
printTree(dest, hmap, visited, step+4);
//System.out.println();
}
}
}
}
The problem is to print all the possible paths from top left to bottom right of a mXn matrix with the constraints that from each cell you can either move only to right or down.
The algorithm is a simple recursive algorithm, from each cell first print all paths by
going down and then print all paths by going right. Do this recursively for each cell encountered.
Input:
int[][] M = {
{ 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
Output:
[1, 4, 7, 8, 9]
[1, 4, 5, 8, 9]
[1, 4, 5, 6, 9]
[1, 2, 5, 8, 9]
[1, 2, 5, 6, 9]
[1, 2, 3, 6, 9]
public void printPaths(int [][] M) {
int i=0, j=0;
int len = M.length + M[0].length-1;
List<Integer> path = new ArrayList<Integer>();
for (int x=0; x<len; x++) {
path.add(0);
}
printPaths(M, i, j, path);
}
private void printPaths(int [][] M, int i, int j, List<Integer> path) {
if (i == M.length-1 && j == M[0].length-1) {
path.set(i+j, M[i][j]);
System.out.println(path.toString());
}
if (i >= M.length || j >= M[0].length) {
return;
}
path.set(i+j, M[i][j]);
printPaths(M, i+1, j, path);
printPaths(M, i, j+1, path);
}
An edit between two strings is one of the following changes.
Add a character
Delete a character
Change a character
Given two string s1 and s2, find if s1 can be converted to s2 with exactly one edit.
Expected time complexity is O(m+n) where m and n are lengths of two strings.
Examples:
Input: s1 = "geeks", s2 = "geek"
Output: yes
Number of edits is 1
Input: s1 = "geeks", s2 = "geeks"
Output: no
Number of edits is 0
Input: s1 = "geaks", s2 = "geeks"
Output: yes
Number of edits is 1
Input: s1 = "peaks", s2 = "geeks"
Output: no
Number of edits is 2
public boolean isOneEdit(String A, String B) {
if (A == null || B == null) {
return false;
}
int alen = A.length();
int blen = B.length();
if (Math.abs(alen - blen) > 1) {
return false;
}
int i = 0;
int j = 0;
int dist = isOneEdit(A.toCharArray(), i, B.toCharArray(), j);
return dist == 1;
}
private int isOneEdit(char[] A, int i, char[] B, int j) {
if (i == A.length) {
return B.length - j;
} else if (j == B.length) {
return A.length - i;
}
if (A[i] == B[j]) {
return isOneEdit(A, i + 1, B, j + 1);
} else {
return 1 + Math.min(
isOneEdit(A, i + 1, B, j + 1),
Math.min(isOneEdit(A, i + 1, B, j),
isOneEdit(A, i, B, j + 1)));
}
}
(9). Given nxn board place n queen on this board so that they dont attack each other. One solution is to find any placement of queens which do not attack each other. Other solution is to find all placements of queen on the board.
queen = 4;
queen placements:
[0, 1]
[1, 3]
[2, 0]
[3, 2]
public void placeQueens(int numQueen) {
Cell [] cells = new Cell[numQueen];
int row = 0;
placeQueens(numQueen, row, cells);
System.out.println("queen placements: ");
for (Cell cell: cells) {
System.out.println(cell.toString());
}
}
private boolean placeQueens(int numQueen, int row, Cell [] cells) {
if (row == numQueen) {
return true;
}
for (int col=0; col < numQueen; col++) {
boolean found = true;
for (int queen=0; queen<row; queen++) {
if (cells[queen].row == row || cells[queen].col == col || cells[queen].row - cells[queen].col == row-col ||
cells[queen].row + cells[queen].col == row+col) {
found = false;
break;
}
}
if (found) {
cells[row] = new Cell(row, col);
if (placeQueens(numQueen, row+1, cells)) {
return true;
}
}
}
return false;
}
class Cell {
int row;
int col;
Cell(int x, int y) {
this.row = x;
this.col = y;
}
public String toString() {
return "[" + this.row + ", " + this.col + "]";
}
}
Imagine x is an operand and * is a binary operator. We say a string
of x and * follows Reverse Polish notation if it is a postfix notation.
For example strings xx*, x, and xx*xx** follow Reverse Polish notation.
Given a string of x and *, how many insert, delete, and replace operations
are needed to make the string follow the RPN.
For example, xx* need 0 operation to follow RPN since it already follows RPN.
x*x needs two operations to become xx* which follows RPN.
*xx* needs one operation to become xx* which follows RPN.
public int minEdits(String input) {
if (input == null || input.length() < 1) {
return 0;
}
char [] A = input.toCharArray();
int index = 0;
int xCount = 0;
return minEdits(A, index, xCount);
}
private int minEdits(char [] A, int index, int xCount) {
if (index == A.length) {
return (xCount == 1) ? 0: Integer.MAX_VALUE;
}
if (A[index] == 'x') {
//we can use the x as it is, delete it or replace it with *
//a. using as it is
int v1 = minEdits(A, index+1, xCount+1);
//b. deleting it
int v2 = Integer.MAX_VALUE;
if (xCount > 1) {
v2 = minEdits(A, index+1, xCount-1);
v2 = (v2 != Integer.MAX_VALUE) ? v2+1: Integer.MAX_VALUE;
}
//c. replace it with *
int v3 = minEdits(A, index+1, xCount);
v3 = (v3 != Integer.MAX_VALUE) ? v3+1: Integer.MAX_VALUE;
return Math.min(v1, Math.min(v2, v3));
} else {
//if its * then we can reduce 2 x to 1 x, delete it or replace with x
int v0 = Integer.MAX_VALUE;
if (xCount >= 2) {
v0 = minEdits(A, index+1, xCount-1);
//v0 = (v0 != Integer.MAX_VALUE) ? v0 +1: Integer.MAX_VALUE;
}
int v1 = minEdits(A, index+1, xCount);
v1 = (v1 != Integer.MAX_VALUE) ? v1 +1: Integer.MAX_VALUE;
int v2 = minEdits(A, index+1, xCount+1);
v2 = (v2 != Integer.MAX_VALUE) ? v2+1: Integer.MAX_VALUE;
return Math.min(v0, Math.min(v1, v2));
}
}
(7). Letter Combinations of a Phone Number. Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given.
map.put(2, "abc");
map.put(3, "def");
map.put(4, "ghi");
map.put(5, "jkl");
map.put(6, "mno");
map.put(7, "pqrs");
map.put(8, "tuv");
map.put(9, "wxyz");
map.put(0, "");
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
public void letterCombinations(int [] A) {
int index = 0;
StringBuffer sb = new StringBuffer();
letterCombination(A, index, sb);
}
private void letterCombination(int [] A, int index, StringBuffer sb) {
if (index == A.length) {
if (sb.length() == A.length) {
System.out.print(sb.toString() + " ");
}
}
for (int i=index; i<A.length; i++) {
String str = map.get(A[i]);
char [] chArr = str.toCharArray();
for (int j=0; j<chArr.length; j++) {
sb.append(chArr[j]);
letterCombination(A, i+1, sb);
sb.deleteCharAt(sb.length()-1);
}
}
}
(6). Consider a coding system for alphabets to integers where ‘a’ is represented as 1, ‘b’ as 2, .. ‘z’ as 26. Given an array of digits (1 to 9) as input, write a function that prints all valid interpretations of input array.
Examples:
Input: {1, 1}
Output: ("aa", 'k")
[2 interpretations: aa(1, 1), k(11)]
Input: {1, 2, 1}
Output: ("aba", "au", "la")
[3 interpretations: aba(1,2,1), au(1,21), la(12,1)]
Input: {9, 1, 8}
Output: {"iah", "ir"}
[2 interpretations: iah(9,1,8), ir(9,18)]
public int countInterpretations(int []A) {
int index = 0;
StringBuffer sb = new StringBuffer();
return countInterpretations(A, index, sb);
}
private int countInterpretations(int [] A, int index, StringBuffer sb) {
if (index >= A.length) {
System.out.print(sb.toString() + " ");
return 1;
}
int count = 0;
sb.append(hmap.get(A[index]));
count += countInterpretations(A, index+1, sb);
sb.deleteCharAt(sb.length()-1);
if (index+1 < A.length) {
int num = A[index]*10 + A[index+1];
if (num > 9 && num < 27) {
sb.append(hmap.get(num));
count += countInterpretations(A, index+2, sb);
sb.deleteCharAt(sb.length()-1);
}
}
return count;
}
Input: {a,b,c};
Output:
* * *
a * *
a b *
a b c
a * c
* b *
* b c
* * c
public void printCombination(char[] A) {
int index = 0;
boolean[] result = new boolean[A.length];
printCombinationUtil(A, index, result);
}
private void printCombinationUtil(char[] A, int index, boolean[] result) {
for (int i = 0; i < result.length; i++) {
if (result[i]) {
System.out.print(A[i] + " ");
} else {
System.out.print("* ");
}
}
System.out.println();
for (int i = index; i < A.length; i++) {
result[i] = true;
printCombinationUtil(A, i + 1, result);
result[i] = false;
}
}
Input: {1, 2, 1, 3};
Output:
[1, 1]
[1, 2]
[1, 3]
[2, 3]
public void printCombination(int [] A, int k) {
int index = 0;
List<Integer> list = new ArrayList<Integer>();
Arrays.sort(A);
printCombinationUtil(A, k, index, list);
}
private void printCombinationUtil(int [] A, int k, int index, List<Integer> list) {
if (list.size() == k) {
System.out.println(list.toString());
}
if (index >= A.length) {
return;
}
for (int i=index; i<A.length; i++) {
if (i != index && A[i] == A[i-1]) continue;
list.add(A[i]);
printCombinationUtil(A, k, i+1, list);
list.remove(list.size()-1);
}
}
Input: {1,2,3,4}
Output:
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
public void printCombination(int [] A, int k) {
int index = 0;
List<Integer> list = new ArrayList<Integer>();
printCombinationUtil(A, k, index, list);
}
private void printCombinationUtil(int [] A, int k, int index, List<Integer> list) {
if (list.size() == k) {
System.out.println(list.toString());
}
if (index >= A.length) {
return;
}
for (int i=index; i<A.length; i++) {
//if (i != index && A[i] == A[i-1]) continue;
list.add(A[i]);
printCombinationUtil(A, k, i+1, list);
list.remove(list.size()-1);
}
}
Input: [a, b, c]
Output:
[a]
[a, b]
[a, b, c]
[a, c]
[b]
[b, c]
[c]
public void printCombinations(char [] input) {
int index = 0;
List<Character> list = new ArrayList<Character>();
printCombinationUtil(input, index, list);
}
private void printCombinationUtil(char [] input, int index, List<Character> list) {
if (list.size() > 0) {
System.out.println(list.toString());
}
for (int i=index; i<input.length; i++) {
if (i != index && input[i] == input[i-1]) {
continue;
}
list.add(input[i]);
printCombinationUtil(input, i+1, list);
list.remove(list.size()-1);
}
}
A string X can be put before another string Y in circle if the last character of X is same as first character of Y
Input: {"for", "geek", "rig", "kaf"}
Output: Yes
public boolean wordCircle(String [] words) {
int index = 1;
char prev = words[0].charAt(words[0].length()-1);
return wordCircle(words, index, prev);
}
private boolean wordCircle(String [] words, int index, char prev) {
if (index == words.length) {
System.out.println(Arrays.toString(words));
return prev == words[0].charAt(0);
}
for (int i=index; i<words.length; i++) {
if(words[i].charAt(0) == prev) {
String tmp = words[index];
words[index] = words[i];
words[i] = tmp;
boolean result = wordCircle(words, index+1, words[index].charAt(words[index].length()-1));
if (result) {
return true;
}
}
}
return false;
}