Microsoft Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
1 #include <iostream>
2 #include <algorithm>
3
4 using namespace std;
5
6 bool comp(int a, int b) {
7 while(a>=10) a/=10;
8 while(b>=10) b/=10;
9 return (a>b);
10 }
11
12 void swap(int *a, int *b) {
13 int tmp = *a;
14 *a = *b;
15 *b = tmp;
16 }
17
18 void permutation(int arr[], int len, int *start, int *end) {
19 if(arr == 0) return;
20 if(start == end) {
21 for(int i = 0; i < len; i++)
22 cout << arr[i];
23 cout << endl;
24 return;
25 }
26
27 for(int *begin = start; begin < end ; begin++) {
28 if(begin!=start&&*begin==*start) continue;
29 swap(start, begin);
30 permutation(arr, len, start+1, arr+len);
31 swap(start, begin);
32 }
33 }
34
35 int main() {
36 int arr[] = {1,1,3};
37 // int arr[] = {1,2,3};
38 int len = sizeof(arr)/sizeof(int);
39 // sort(arr, arr+len, comp);
40
41 permutation(arr, len, arr, arr+len);
42
43 return 0;
44 }
Recursion version also be done, which is quite similar to the std::next_permutation implementation.
// initial call
// printAllPerms(perm, 0);
// perm is initially sorted.
static void printAllPerms(List<int> perm, int start)
{
if (start == perm.Count)
{
print<int>(perm);
return;
}
int j = start;
while (j < perm.Count)
{
printAllPerms(perm, start + 1);
if (j < perm.Count - 1)
{
perm.Reverse(start + 1, perm.Count - start - 1);
}
// skip over elements which have already been placed
// in the first position.
while (j < perm.Count && perm[start] >= perm[j])
{
j++;
}
// new element to swap.
if (j < perm.Count)
{
int tmp = perm[start];
perm[start] = perm[j];
perm[j] = tmp;
}
}
}
#include<iostream>
using namespace std;
void swap(int &a, int &b)
{
int temp;
temp = a;
a = b;
b = temp;
}
void permutations(int a[], int k, int m)
{
if(k==m)
{
for(int i=0; i<=m; i++)
cout<<a[i]<<"\t";
cout<<"\n";
}
else
{
for(int i=k; i<=m; i++)
{
if(k != i && a[k]==a[i])
continue;
else
{
swap(a[k], a[i]);
permutations(a, k+1, m);
swap(a[k], a[i]);
}
}
}
}
int main()
{
int a[] = {1, 1, 2};
permutations(a, 0, 2);
}
Here's a python code:
def permute(l):
if(len(l)==1):
return [l]
else:
history=[]
ans=[]
for l1 in l:
try:
i=history.index(l1)
except ValueError:
#not in history
history.append(l1)
j=l.index(l1)
m=l[:]
m[0],m[j]=m[j],m[0]
p=permute(m[1:])
for p1 in p:
ans.append([m[0]]+p1)
return ans
print permute([1,2,1])
#include <algorithm>
static void _print_arr(const int A[], int N)
{
std::cout << '[' << A[0] << std::endl;
for(int i = 0; i < N; i++)
std::cout << ',' << A[i];
std::cout << ']' << std::endl;
}
void static _print_combination(int A[], int k, int N)
{
if(k == N)
{
_print_arr(A, N);
return;
} // if
_print_combination(A, k + 1, N);
for(int i = k + 1; i < N; i++)
{
if(A[i] != A[k])
{
std::swap(A[k], A[i]);
_print_combination(A, i, N);
std::swap(A[k], A[i]);
}
} // for
} // _print_combination
void print_combination(const int A[], int N)
{
int* A2 = new int[N];
std::copy(A, A + N, A2);
std::sort(A2, A2 + N);
_print_combination(A2, 0, N);
} // print_combination
int main(void)
{
int A[] = {1, 2, 1};
print_combination(A, sizeof(A) / sizeof(A[0]));
return 0;
}
class Test{
static int count=0;
public static void main(String args[]){
System.out.println("Enter the digitized string");
Scanner scanner=new Scanner(System.in);
String numbers[]=scanner.nextLine().split(" ");
generateList(numbers,"","");
}
public static void generateList(String numbers[],String str,String currentIndex){
if(str.split(",").length==numbers.length)
System.out.println("String:"+ ++count+" "+str.substring(0,str.length()-1));
for(int l=0;l<numbers.length;l++)
if(!currentIndex.contains(String.valueOf(l))&& specialCheck(str,numbers,l))
generateList(numbers,str+numbers[l]+",",currentIndex+l);
}
public static boolean specialCheck(String str,String numbers[],int index){
int countInMainArray=0;
int countInGeneratedString=0;
for(int l=0;l<index;l++)
if(numbers[l].equals(numbers[index]))
countInMainArray++;
String tmpArray[]=str.split(",");
for(String tmp:tmpArray)
if(tmp.equals(numbers[index]))
countInGeneratedString++;
if(countInMainArray==countInGeneratedString)
return true;
return false;
}
}
The complexity would be n2
#include<iostream>
using namespace std;
void print(int *a, int size){
for(int i = 0;i < size; i++){
cout << a[i] << "\t";
}
cout << endl;
};
void permute(int *a, int k, int size){
//print();
//print(a,size);
if(k == size){
print(a,size);
}
int prev = 0;
for(int i = k; i < size; i++){
//cout << "HI" << endl;
if(a[i] == prev) {//cout << "continue " << a[i] << endl;
}
else{
swap(a[k], a[i]);
permute(a, k+1, size);
swap(a[k], a[i]);
prev = a[i];
}
}
}
int main(){
int a[] = {1,2,3,1};
sort(a+0, a+ 4);
permute(a, 0, sizeof(a)/sizeof(int));
system("pause");
return 0;
}
public class ArrayPermutation {
private int[] arr;
public ArrayPermutation(int[] arr){
this.arr = arr;
}
public void enumerate(int k){
if(k == arr.length){
process(); //print only when complete swap is done
return;
}
for(int i = k; i < arr.length; i++){//this part is very important. exchange from the point ahead of k
//enumerate(k + 1);
exchange(i , k);
enumerate(k + 1);
exchange(i , k); //clean up
}
}
private void exchange(int i, int k) {
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
private void process() {
for(int i : arr){
System.out.print(i + "\t");
}
System.out.println();
}
public static void main(String[] args){
int[] arr= {1 ,2, 3};
ArrayPermutation aPermutation = new ArrayPermutation(arr);
aPermutation.enumerate(0);
}
}
Read Narayana Pandit's method for generating permutations in lexicographic order on wikipedia
- Anonymous September 05, 2012