Amazon Interview Question
SDE1sCountry: India
Interview Type: Phone Interview
Please correct me if I am wrong.
public static int permute(String prefix,String s)
{
int n=s.length();
if(n==0)
{
System.out.println(prefix+"\t");
}
for(int i=0;i<n;i++)
{
permute(prefix+s.charAt(i),s.substring(0,i)+s.substring(i+1,n));
}
}
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
void Amazone10()
{
string s("451");
cout << "Initial: " << s << endl;
sort(s.begin(), s.end());
cout << "Sorted: " << s << endl;
do
{
cout << "Perm: " << s << endl;
} while(next_permutation(s.begin(), s.end()));
}
#include <unistd.h>
#include <stdio.h>
#include <string.h>
#define MAX 100
void swap(char *c1, char c2 *);
void printStringPermutation(char *str, int i, int len);
int main(int argc, char **argv)
{
char str[MAX]={0};
unsigned int len = 0;
printf("\nEnter string:");
scanf("%s", str);
len = strlen(str);
len --;
printStringPermutation(str, 0, len);
return 0;
}
void swap(char *c1, char *c2)
{
char temp;
temp = *c1;
*c1 = *c2;
*c2 = temp;
}
void printStringPermutation(char *str, int i, int len)
{
if (i == len)
printf("\n%s", str);
else
for (j = i; j <= len; j++)
{
swap(str[i], str[j]);
printStringPermutation(str, (i+1), len))
swap(str[i], str[j]);//this backtrack to previous combination
}
}
Would take O(!n*n)
@Sugarcane yeah ..its not iterative...question doesn't mention about the approach which should be taken
public static void CombString(string strValue)
{
// Print the initial string
Console.WriteLine(strValue);
char[] array = strValue.ToCharArray();
int n = array.Length;
int[] permutationnInts = new int[n]; // Index control array initially all zeros
int i = 1;
while (i < n)
{
if (permutationnInts[i] < i)
{
int j = ((i%2) == 0) ? 0 : permutationnInts[i];
char temp = array[i];
array[i] = array[j];
array[j] = temp;
strValue = new string(array);
Console.WriteLine(strValue); // Print the string
permutationnInts[i]++;
i = 1;
}
else
{
permutationnInts[i] = 0;
i++;
}
}
}
#include <iostream>
using namespace std;
#include <cstring>
#include <string>
#include <unordered_map>
#include<stdlib.h>
#include<stdio.h>
#include <deque>
#include <vector>
void permu(deque<char> &i, deque<char> &o) {
if (i.empty()) {
// print the o list
for(int k =0; k <o.size(); k++) {
cout << o[k];
}
cout <<"\n";
return;
}
for(int it = 0; it < i.size(); it++) {
// pick one and insert into the out queue
o.push_back(i.front());
i.pop_front();
permu(i, o);
i.push_back(o.back());
o.pop_back();
}
}
void permutation_do(char *s) {
int slength = strlen(s);
deque<char> in;
deque<char> out;
for(int i = 0; i < slength; i++) {
in.push_back(s[i]);
}
permu(in, out);
}
int main() {
// your code goes here
char a[] = {"ABCD"};
permutation_do(a);
return 0;
}
#include <iostream>
using namespace std;
#include <cstring>
#include <string>
#include <unordered_map>
#include<stdlib.h>
#include<stdio.h>
#include <deque>
#include <vector>
void permu(deque<char> &i, deque<char> &o) {
if (i.empty()) {
// print the o list
for(int k =0; k <o.size(); k++) {
cout << o[k];
}
cout <<"\n";
return;
}
for(int it = 0; it < i.size(); it++) {
// pick one and insert into the out queue
o.push_back(i.front());
i.pop_front();
permu(i, o);
i.push_back(o.back());
o.pop_back();
}
}
void permutation_do(char *s) {
int slength = strlen(s);
deque<char> in;
deque<char> out;
for(int i = 0; i < slength; i++) {
in.push_back(s[i]);
}
permu(in, out);
}
int main() {
// your code goes here
char a[] = {"ABCD"};
permutation_do(a);
return 0;
}
Java approach. Takes O(n!):
}
- NL June 02, 2014