JP Morgan Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
public class PossibleCombinations {
public static void main(String[] arr) {
combination("", "1234");
}
private static void combination(String prefix, String str) {
int n = str.length();
if (n == 0)
System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
combination(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
}
}
}
Here is python solution:
def next_permutation(data):
size = len(data)
for i in reversed(range(size - 1)):
if data[i] < data[i+1]:
data[i+1:size] = reversed(data[i+1:size])
for j in range(i + 1, size):
if(data[i] < data[j]):
data[i], data[j] = data[j], data[i]
return True
return False
def all_permutation(inp):
ls = list(inp)
while True:
print ''.join(ls)
if not next_permutation(ls):
break
all_permutation('test')
We can solve the problem in recursive way, but it is dynamic programming so that we won't solve the same problem again and again.
e.g. consider string "abcd". We will make "ab" as prefix and try combination of "cd". Then we will make "ba" as prefix and try combination of "cd". So we are trying combinations of "cd" twice.
So as soon as we complete finding combination of sub-string it should be stored and reused.
Recursive solution in Swift with saving the string built so far :
var arr = Array("ABC".characters)
var permutations = [String]()
func computePerm(arr: [Character], prefix: String) {
if arr.count == 0 {
permutations.append(prefix)
} else {
var newPrefix = prefix
for i in (0..<arr.count) {
var newArr = arr
newArr.removeAtIndex(i)
computePerm(newArr, prefix: prefix + String(arr[i]))
}
}
}
computePerm(arr, prefix: "")
print(permutations)
public static void permutate(String s) {
if(s == null || s.length() == 0) {
return;
}
permutate(s.toCharArray(), 0);
}
private static void permutate(char[] str, int start) {
if(start >= str.length) {
System.out.println(new String(str));
return;
}
for(int i = start; i < str.length; i++) {
swap(str, i, start);
permutate(str, start+1);
swap(str, i, start);
}
}
private static void swap(char[] input, int i, int j) {
char c = input[i];
input[i] = input[j];
input[j] = c;
}
- NoOne October 07, 2016