Epic Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
you also can use next_permutation to eliminate the repeated output, but it needs to sort array first
vector<char> v;
sort(v.begin(), v.end());
do {
// output elements in v
} while (next_permutation(v.begin(), v.end());
This was very helpful. I spent a couple hours breaking my head trying to figure out what the code is doing. And it just blew me. This program is also careful not to print duplicates. Thanks!!
Just an improvement to save some unnecessary swap function calls. Call the swap function only if i is not equal to j. This holds for both the forward swap and the backtrack swap.
if ( i != j ) {
swap ( a + i , a + j ) ;
}
<pre lang="" line="1" title="CodeMonkey7469" class="run-this">class Perm {
static void p(char[] text, int i){
if (i==text.length)
System.out.println(text);
else for (int j=i;j<text.length; j++){
swap(text, i, j);
p(text, i+1);
swap(text, i, j);
}
}
static void swap(char[] text, int i, int j){
char c = text[i];
text[i]=text[j];
text[j]=c;
}
public static void main(String[] args) throws Exception{
p("tree".toCharArray(), 0);
}
}
</pre><pre title="CodeMonkey7469" input="yes">
</pre>
int Mycount = 0;
void permute(int n , bool *isVisited, int level, string crtString)
{
if(level == n)
{
Mycount++;
cout<<crtString<<endl;
}
else
{
for(int i = 0 ; i < n ; ++ i)
{
if(isVisited[i] == 0)
{
isVisited[i] = 1;
char tmp = i + '0';
permute(n, isVisited, level+1, crtString+tmp);
isVisited[i] = 0;
}
}
}
}
int main (int argc, const char * argv[])
{
int n = 5;
bool *isVisited = new bool[n];
for(int i = 0; i < n ; ++ i )
{
isVisited[i] = 0;
}
permute(n, isVisited, 0, "");
cout<<"count = "<<Mycount<<endl;
return 0;
}
public class Permutation {
public static void main(String[] args){
int a[]={1,2,3,4};
permute(a,0);
}
public static void permute(int[] a, int k){
if(k == a.length){
for(int i = 0; i < a.length; i++){
System.out.print(a[i]);
}
System.out.print("\n");
return;
}
else{
for(int i = k; i < a.length; i++){
int temp = a[k];
a[k] = a[i];
a[i] = temp;
permute(a,k+1);
temp = a[k];
a[k] = a[i];
a[i] = temp;
}
}
}
}
No duplication allowed in the output. or else what is the meaning of this interview question?
Either set or manual duplication check can be used to eliminate duplicate. I am not talking about generate all possible outputs and then eliminate duplicates. Duplication checking is done while generating permutation.
void helper(string s, int i, vector<string> &res) {
if (i == s.size() - 1) {
res.push_back(s);
return;
}
set<char> used;
for (int st = i; st < s.size(); ++st) {
if (used.count(s[st])) continue;
used.insert(s[st]);
swap(s[i], s[st]);
helper(s, i + 1, res);
swap(s[i], s[st]);
}
}
vector<string> perm(string s) {
if (!s.size()) return vector<string>();
vector<string> ret;
helper(s, 0, ret);
return ret;
}
Playble code at
ideone.com/umy4It
String text="tree";
char[] perm = text.toCharArray();
System.out.println();
int count=0;
int charLength = perm.length;
Set<String> set = new HashSet<String>();
while(charLength!=0){
charLength--;
for (int j = 0,i=1; j <perm.length-1; j++,i++) {
if(i!=j){
char temp = perm[j];
perm[j]= perm[i];
perm[i] = temp;
String x = new String(perm);
// System.out.println(x);
set.add(x);
// count++;
}
else{
System.out.println("i==j");
}
}
}
Iterator<String> it = set.iterator();
while(it.hasNext()){
count++;
System.out.println("Perm WOrds Are : "+it.next());
}
System.out.println("Total "+count);
}
here is the recursive code
- getjar.com/todotasklist my android app December 18, 2011