Facebook Ebay Interview Question Software Engineer / Developers
Country: United States
Extending your soln to support repeating chars...
private static void printPermutations(char s[], int pos) {
if (pos == s.length) {
System.out.println(new String(s));
return;
}
Set<Character> set = new HashSet<Character>();
for (int i = pos; i < s.length; ++i) {
if (set.contains(s[i])) {
continue;
}
swap(s, i, pos);
printPermutations(s, pos + 1);
swap(s, i, pos);
set.add(s[i]);
}
}
Naive complexity would be n!
We could reduce the complexity via dynamic programming. Store the lesser components, so that you don't have to permute them again.
For example, if I have already permuted {abc} then I don't have to entirely permute {abcd}.
I think the solution says Perm(str) = Perm(str.substring(0)) + adding str.CharAt(0) at any posibile solution
so there is no need to double calculate permitations anyway
If all characters in the string are distinct there are exactly n! permutations that must be stored and computed. The niave answer is the optimal one for all choices of strings.
I think what you mean is that in the case of repeated letters you can reduce the complexity to (n \choose \lambda) where \lambda is the frequency count of the letters.
public class PermutationTest {
/**
* @param args
*/
public static void main(String[] args)
{
// TODO Auto-generated method stub
String permString = "ABCDE";
Set<String> se = permutations(permString);
Iterator<String> itr = se.iterator();
System.out.println("Total size of Permutations = " + se.size());
while(itr.hasNext()){
System.out.println("--" + itr.next());
}
}
public static Set<String> permutations(String str)
{
Set<String> se = new HashSet<String>();
permute(str.toCharArray(),"",se);
return se;
}
public static void permute(char[] rem, String str, Set<String> se)
{
if(rem.length == 1){
String str2 = str + rem[0];
se.add(str2);
return;
}
for(int i = 0 ; i < rem.length ; i++)
{
char[] rem2 = getRemainingArray(rem,i);
String s = "" + str + rem[i];
permute(rem2, s, se);
}
}
private static char[] getRemainingArray(char[] rem, int i)
{
char[] rem2 = new char[rem.length - 1];
int k = 0;
for(int j = 0 ; j < rem.length ; j++)
{
if(i!=j){
rem2[k] = rem[j];k++;
}
}
return rem2;
}
}
public static ArrayList<String> stringPermutation(String s){
if (s==null){
return null;
}
String first = s.substring(0,1);
String rest = null;
if(s.length() != 1){
rest = s.substring(1);
}
ArrayList<String> list = stringPermutation(rest);
ArrayList<String> permutation = new ArrayList<String>();
if(list == null) permutation.add(first);
else{
for(String str : list){
for(int i=0; i<str.length()+1; i++){
permutation.add(mutation(first,str,i));
}
}
}
return permutation;
}
public static String mutation(String ch, String s, int index){
if (index == 0) return ch + s;
else{
return s.substring(0,index) + ch + s.substring(index);
}
}
private static void allPermutationsOfGivenString_recursive() {
String s = "vibhorras";
allPermutationsOfGivenString_recursive(s, "");
System.out.println("\n"+count);
}
private static void allPermutationsOfGivenString_recursive(String s, String t) {
for (int i = 0; i < s.length(); i++) {
t = t + s.charAt(0);
if (s.length() > 1) {
allPermutationsOfGivenString_recursive(s.substring(1), t);
if (i + 1 < s.length()) {
s = rotate(s);
t = t.substring(0, t.length() - 1);
}
continue;
}
System.out.print(t+" ");
count++;
break;
}
}
#!/usr/bin/python
def permute(s,cur,pos,n):
#prints all permutation of a given string O(n*n!)
#assuming unique characters present it prints the lexicographic-unique sequence
#but it fails to print unique sequence if there are repeating characters
global visited
if pos==n:
print ''.join(cur)
return
for i in range(n):
if not visited[i]:
cur[pos]=s[i]
visited[i]=True
permute(s,cur,pos+1,n)
visited[i]=False
def permutations(s): #solution to the above problem
#prints all unique permutation of a given string in lexicographic order TIME:O(n*n!)
n=len(s)
def next():
k,l=-1,-1
for i in range(n-1):
if s[i]<s[i+1]: k=i
if k==-1: return None
for i in range(k+1,n):
if s[k]<s[i]: l=i
cur=list(s[k:])
cur[0],cur[l-k]=cur[l-k],cur[0]
return s[:k]+'%c%s'%(cur[0],''.join(cur[:0:-1]))
while s:
print s
s=next()
if __name__=='__main__':
s='aabcd'
n=len(s)
#visited=[False]*n
#permute(s,[0]*n,0,n)
permutations(s)
public static void getPermutations(String head,String tail)
{
if(tail.length()==0) System.out.println(head);
for(int i=0;i<tail.length();i++)
{
String newHead=head, newTail="";
for(int j=0;j<tail.length();j++)
{
if(i==j) newHead += (tail.charAt(j));
else newTail += tail.charAt(j);
}
getPermutations(newHead,newTail);
}
}
public static void permutation(String s) {
permutation("", s);
}
private static void permutation(String prefix, String s) {
int n = s.length();
if (n == 0)
System.out.println(prefix);
else {
for (int i = 0; i < n; i++) {
permutation(prefix + s.charAt(i),
s.substring(0, i) + s.substring(i + 1, n));
}
}
}
Generate all permutations in lexicographical order. That is going to take care of the duplicate characters in the string as well. Complexity of generating the next permutation is going to be high as compared to normal permutation as u involve sorting as well here.
In normal algorithm complexity for generating the next permutation is going to be O(n) in worst case. In the case of lexicographical sorting it is going to be o(n + logk)
public void printPermutations(char[] c) {
StringBuffer temp;
for (int i = 0; i < c.length; i++) {
temp = new StringBuffer();
temp.append(c[i]);
for (int k = 0, j = (i + 1) % (c.length); k < c.length-1; k++, j = (j + 1) % c.length) {
//System.out.println("j=" + j);
temp.append(c[j]);
}
System.out.println(temp);
System.out.println(temp.reverse());
}
}
What do you by the naive way would always be n!? In fact it is impossible to do better unless you managed to print a string in negative time lol. The question is rather how much worse does it get? And the solutions above seem to be a nightmare of memory allocation and copying. Mine is free of them all.
#include <vector>
#include <string>
#include <functional>
#include <iostream>
#include <stdint.h>
bool permutation_internal(std::vector<int>& perm, int offset, std::vector<int>& validIndices, std::function<bool()> callback)
{
if(offset == perm.size())
return callback();
for(int i = 0; i < validIndices.size(); i++)
{
if(validIndices[i] == -1)
continue;
validIndices[i] = -1;
perm[offset] = i;
if(!permutation_internal(perm, offset + 1, validIndices, callback))
return false;
validIndices[i] = i;
}
return true;
}
template<class TIter>
bool permutation(TIter begin, TIter end, std::function<bool (const std::vector<TIter::value_type>&)> predicate)
{
int s = (int)std::distance(begin, end);
std::vector<TIter::value_type> res(s);
std::vector<int> perm(s);
std::vector<int> validIndices(s);
for(int i = 0; i < s; i++) validIndices[i] = i;
return permutation_internal(perm, 0, validIndices, [&]()
{
for(int i = 0; i < perm.size(); i++)
res[i] = *(begin + perm[i]);
return predicate(res);
});
}
void printStringPerms(std::string str)
{
permutation(str.begin(), str.end(), [&](const std::vector<char>& perm)
{
for(auto c : perm) std::cout << c;
std::cout << std::endl;
return true;
});
}
int main(int argc, char** argv)
{
printStringPerms("Facebook");
return 0;
}
What do you by the naive way would always be n!? In fact it is impossible to do better unless you managed to print a string in negative time lol. The question is rather how much worse does it get? And the solutions above seem to be a nightmare of memory allocation and copying. Mine is free of them all.
#include <vector>
#include <string>
#include <functional>
#include <iostream>
#include <stdint.h>
bool permutation_internal(std::vector<int>& perm, int offset, std::vector<int>& validIndices, std::function<bool()> callback)
{
if(offset == perm.size())
return callback();
for(int i = 0; i < validIndices.size(); i++)
{
if(validIndices[i] == -1)
continue;
validIndices[i] = -1;
perm[offset] = i;
if(!permutation_internal(perm, offset + 1, validIndices, callback))
return false;
validIndices[i] = i;
}
return true;
}
template<class TIter>
bool permutation(TIter begin, TIter end, std::function<bool (const std::vector<TIter::value_type>&)> predicate)
{
int s = (int)std::distance(begin, end);
std::vector<TIter::value_type> res(s);
std::vector<int> perm(s);
std::vector<int> validIndices(s);
for(int i = 0; i < s; i++) validIndices[i] = i;
return permutation_internal(perm, 0, validIndices, [&]()
{
for(int i = 0; i < perm.size(); i++)
res[i] = *(begin + perm[i]);
return predicate(res);
});
}
void printStringPerms(std::string str)
{
permutation(str.begin(), str.end(), [&](const std::vector<char>& perm)
{
for(auto c : perm) std::cout << c;
std::cout << std::endl;
return true;
});
}
int main(int argc, char** argv)
{
printStringPerms("Facebook");
return 0;
}
char* putCharAt(const char* str, char c, int index)
{
int len = strlen(str);
if(index < 0 || index > len )
return NULL;
char* res = new char[len + 2];
for(int i=0;i<index;i++)
{
res[i] = str[i];
}
res[index] = c;
for(int i=index+1;i<len+1;i++)
{
res[i] = str[i-1];
}
res[len+1] = '\0';
return res;
}
void permute(const char* str)
{
if(str == NULL)
return;
vector<char*> res;
vector<char*> temp;
int len = strlen(str);
char* init_str = new char[2];
init_str[0] = str[0];
init_str[1] = '\0';
res.push_back(init_str);
for(int i=1;i<len;i++)
{
for(vector<char*>::iterator it = res.begin(); it != res.end(); it++)
{
char* st = *it;
int l = strlen(st);
for(int j=0;j<=l;j++)
{
char* temp_str = putCharAt(st,str[i],j);
temp.push_back(temp_str);
}
}
res.clear();
res = temp;
temp.clear();
}
//print the permutations
for(vector<char*>::iterator it = res.begin(); it != res.end(); it++)
{
cout<<*it<<", ";
}
cout<<endl;
cout<<"total perms = "<<res.size()<<endl;
//return res;
}
Here is a python code. It is a recursive function. If we have "abc", it calls the recursive function three times.
1- prefix = a; str = ''bc"
2- prefix = b; str = ''ac"
3- prefix = c; str = ''ab"
def prm(prefix, str):
if len(str) == 1:
print prefix + str;
return;
for i in range(len(str)):
temp = str[:i] + str[i+1:];
prm(prefix+str[i], temp)
Simple recursive C# solution.
public static void PrintPermutations(string s)
{
StringBuilder src = new StringBuilder(s);
StringBuilder dst = new StringBuilder();
DoRec(src, dst);
}
static void DoRec(StringBuilder src, StringBuilder dst)
{
if (src.Length == 0)
{
System.Console.WriteLine(dst.ToString());
return;
}
for (int i = 0; i < src.Length; ++i)
{
dst.Append(src[i]);
src.Remove(i, 1);
DoRec(src, dst);
src.Insert(i, dst[dst.Length - 1]);
dst.Remove(dst.Length - 1, 1);
}
}
Basically, think of the problem as a graph. For a string of length n, you have n sub-graphs. Each sub-graph then has n-1 sub-graphs. The total number of nodes in all of the sub-graphs is n!
So you start with a root and a remainder. You iteratively add each character from the remainder to the root, and then recurse down to the next level. When you have a remainder with only one character in it, you know you have hit a leaf, so you print the root plus the remainder.
In the case of no character repetitions, it's as simple as:
def get_perms(root, s):
if len(s) == 1:
print root+s
else:
for i in range(len(s)):
get_perms(root+s[i], s[:i]+s[i+1:])
get_perms("", "abcd")
I wrote a solution which also handles the case where the string includes duplicate characters:
def get_perms(root, s, items):
if len(s) == 1:
if root+s not in items:
items.append(root+s)
print root+s
else:
for i in range(len(s)):
get_perms(root+s[i], s[:i]+s[i+1:], items)
get_perms("", "abcdd", [])
It's pretty clear that this is O(n!) in time complexity, and if you have to handle duplicate characters, it becomes O(n!) space complexity as well.
Dynamic programming certainly could offer a solution here as well, but that requires storing all of the data. Therefore, in the case of no character repetitions, recursion will certainly be optimal, as you don't have to store anything other than the string. But in the case of repeated characters, perhaps there's a better way using dynamic programming.
standard solution :
- sonesh January 29, 2013void permute(char *a, int i, int n) // i is zero in first call and n is size of the string. { int j; if (i == n) printf("%s\n", a); else { for (j = i; j <= n; j++) { swap((a+i), (a+j)); permute(a, i+1, n); swap((a+i), (a+j)); //backtrack } } }