Microsoft Interview Question
Software Engineer / DevelopersTeam: Bing
Country: India
Interview Type: In-Person
#include<iostream>
#include <cstring>
using namespace std;
#define MAX_CHAR 256
bool is_a_solution(int k, int n);
void process_solution(char solution[], int n);
void construct_all_candidates(char s[], int n, char sol[], int k, char candidates[], int& nCandidates);
void permute_string_imp(char s[], int k, int n, char sol[]);
bool exists_in_solution(char solution[], int k, char c);
void permute_string(char s[]);
int main(int argc, char *argv[])
{
if(argc != 2)
{
cout << "incorrect command line usage" << endl;
return 1;
}
permute_string(argv[1]);
return 0;
}
void permute_string(char s[])
{
char *sol;
int len;
if(s == NULL || s[0] == '\0')
return;
len = strlen(s);
sol = new char[len+1];
memset(sol, 0x00, sizeof(char) * (len+1));
permute_string_imp(s, 0, len, sol);
delete sol;
}
void permute_string_imp(char s[], int k, int n, char sol[])
{
char *candidates;
int nCandidates;
if(is_a_solution(k,n))
process_solution(sol, n);
else
{
candidates = new char[n-k+1];
memset(candidates, 0x00, sizeof(char) * (n-k+1));
k++;
construct_all_candidates(s, n, sol, k, candidates, nCandidates);
//iterate through all the possible candidates
for(int i = 0; i < nCandidates; i++)
{
// check if it is not present in the partial solution
if(!exists_in_solution(sol, k, candidates[i]))
{
sol[k-1] = candidates[i];
permute_string_imp(s, k, n, sol);
}
}
delete candidates;
}
}
bool is_a_solution(int k, int n)
{
return k == n;
}
void process_solution(char solution[], int n)
{
for(int i = 0; i < n; i++)
cout << solution[i];
cout << endl;
}
void construct_all_candidates(char s[], int n, char sol[], int k, char candidates[], int& nCandidates)
{
bool perm[MAX_CHAR];
for(int i = 0; i < MAX_CHAR; i++)
perm[i] = false;
for(int i = 0; i < k-1; i++)
perm[sol[i]] = true;
nCandidates = 0;
for(int i = 0; i < n; i++)
if(perm[s[i]] == false)
candidates[nCandidates++] = s[i];
}
bool exists_in_solution(char solution[], int k, char c)
{
for(int i = 0; i < k-1; i++)
if(solution[i] == c)
return true;
return false;
}
bool next_permutation(string& str)
{
int n = str.size();
int k = n-2;
while (k>=0) {
if (str[k] >= str[k+1]) k--;
else break;
}
if (k==-1) { return false; }
int l = n-1;
while (true) {
if (a[l] > a[k]) break;
else l--;
}
swap(a[k], a[l]);
reverse(str.begin() + k + 1, str.end());
return true;
}
sort(str.begin(), str.end());
do {
cout << str << endl;
} while(next_permutation(str));
static List<string> permutations(string s)
{
if (s == null)
return null;
List<string> temp = new List<string>();
if (s.Length == 1)
{
temp.Add(s);
return temp;
}
string sub = s.Substring(1);
List<string> perm = permutations(sub);
char ch = s[0];
foreach (string subs in perm)
{
for (int i = 0; i <= subs.Length; i++)
{
temp.Add(subs.Insert(i, ch.ToString()));
}
}
return temp;
}
code for permutation using backtracking
- getjar.com/todotasklist my android app December 06, 2011