-
Notifications
You must be signed in to change notification settings - Fork 2
Recursion Problems and Patterns
Mani Bhushan edited this page Aug 28, 2016
·
52 revisions
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;
}