## Microsoft Interview Question for Software Engineer / Developers

• 0

Country: -

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````void PrintPermutations( std::vector< std::pair<int,bool> > & input
, std::vector<int> & current
, int currentI
, int maxN )
{
if ( maxN > currentI)
{
for ( int i = 0 ; i < maxN; ++i )
{
if ( input[i].second == false )
{
input[i].second = true;
current[currentI] = input[i].first;

PrintPermutations( input ,
current ,
currentI + 1 ,
maxN );

input[i].second = false;
}
}

}
else
{
std::for_each(
current.begin() ,
current.end() ,
[](int x )
{
std::cout << x << ' ';
});

std::cout << std::endl;
}
}

int _tmain(int argc, _TCHAR* argv[])
{
const int N = 4;
std::vector< std::pair<int,bool> > input;

for ( int i = 0 ; i < N ; ++i )
{
input.push_back( std::make_pair( i + 1 , false ) );
}

std::vector<int> current( N );

PrintPermutations( input , current ,  0 , N);

return 0;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

void permutations(vector<int> &vec,int i)
{
if ( i == vec.size() )
{
copy(vec.begin(), vec.end(), ostream_iterator<int>(cout," "));
cout<<endl;
return;
}

for (int j=i; j<vec.size(); j++)
{
swap(vec[i],vec[j]);
permutations(vec, j+1);
swap(vec[i], vec[j]);
}
}

void test1()
{
int arr[] = {1,2,3,4};
vector<int> vec(arr,arr+4);

permutations(vec, 0);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static void Combinations(ArrayList<Integer> indices, int n)
{
if(indices.size() < n)
{
for(int i = 0; i < n; i++)
{
if(!indices.contains(i))
{
Combinations(indices, n);
indices.remove(indices.size() - 1);
}
}
}
if(indices.size() == n)
{
for(int i = 0; i < n; i++)
System.out.print(indices.get(i) + 1);
System.out.println();
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>

template <class BidirectionalIterator>

bool permuteRec(BidirectionalIterator first,
BidirectionalIterator last) {
if (first == last) return false;
BidirectionalIterator i = first,jj=first;
++i;
if (i == last) return false;

std::cout<<"\n";
while(jj!=last){std::cout<<*jj; jj++;}

i = last;
--i;

for(;;) {
BidirectionalIterator ii = i--;
if (*i <*ii) {
BidirectionalIterator j = last;
while (!(*i <*--j));
std::iter_swap(i, j);
std::reverse(ii, last);
permuteRec(first,last);
return true;
}
if (i == first) {
std::reverse(first, last);
return false;
}
}
}

int main()
{
int permute[]={1,2,3,4};
permuteRec(permute,permute+4);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

List list;
int permut(int x,int n)//x is initially 1 and n is the maximum value
{
if(x==n)
print(list);
else
{
for(int i=0;i<x;i++)
{
add x to ith gap between numbers of list;
permut(x+1,n);
}
}
remove x from list;
}

example: lets we have to print permut of 1 to 4;

so we call permut(1,4)
if(x==n)//here its no
so in else list will have 1
again permut(2,4) will be called so
we have again if(x==n) not satisfied so in else we have

the loop will be executed twice for i=0 and i=1
for i=0 we have list 2,1 and call permut(3,4) & for i=1 we have list 1,2 and call permut(3,4)...
like this we will get once 4,3,2,1 then our for loop finishes so control will come out
and then remove will remove 4 to have in list 3,2,1 for loop continues which is left in recursion
and this time 4 will be inserted in 2nd pos to make the list 3,4,2,1
like this it continues

1
/ \
/ \
2,1 1,2
/|\ /|\
/ | \ / | \
/ | \ / | \
3,2,1 2,3,1 2,1,3
/ | | \
4,3,2,1

correct me if I m wrong

Comment hidden because of low score. Click to expand.
0
of 0 vote

a[] = "cab"
1. Sort the array to make it 'abc'
2. Using already permuted substrings that ends at last location, extend the solution by swapping characters in processed string with adjacent previous char

``````P(i)
if(i == 0)
print a[]
return
for each k from i to n-1
swap(i, k)
P(i-1)
swap(i,k)

main()
QS()
P(n-1)``````

Comment hidden because of low score. Click to expand.
0

Need to consider the order.

Once fix a position, the rest of array need to be sorted in lexical order, so that CAB precede CBA.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Howz this :

//
// main.c
// LexPrint
//
// Created by Srikant Aggarwal on 03/12/11.
//

#include <stdio.h>
#include <stdlib.h>

void swap(int A[], int index1, int index2)
{
if(index1 != index2)
{
A[index1] = A[index1] + A[index2];
A[index2] = A[index1] - A[index2];
A[index1] = A[index1] - A[index2];
}
}

void recurse_print(int A[], int n, int length)
{
if(length == 1)
{
for(int i = 0; i < n; i++)
printf(" %d", A[i]);
printf("\n");
}
else
{
for(int i = n - length; i < n; i++)
{
swap(A, n-length, i);

recurse_print(A, n, length-1);

swap(A, n-length, i);
}
}
}

int main (int argc, const char * argv[])
{
int *A;
int n;

scanf("%d", &n);

if(n > 0)
{
A = (int *)malloc(sizeof(int)*n);

for(int i = 1; i <= n; i++)
A[i-1] = i;

recurse_print(A, n, 4);
}

return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

One more method:

``````//
//  main.c
//  PrintPermutations
//
//  Created by Srikant Aggarwal on 09/12/11.
//

#include <stdio.h>
#include <stdlib.h>

void swap(int A[], int index1, int index2)
{
if(index1 != index2)
{
A[index1]=A[index1]^A[index2];
A[index2]=A[index1]^A[index2];
A[index1]=A[index1]^A[index2];
}
}

void reverse(int A[], int begin, int end)
{
int i = 0;

while((begin+i) <= (end+begin)/2)
{
swap(A, begin+i, end-i);
i++;
}
}

void print_permutations(int A[], int n)
{
int i = n-2, j=n-1, k=n-1, l;
unsigned char continue_loop = 1;

for(l=0; l < n; l++)
printf(" %d ", A[l]);

while(continue_loop)
{
i = n-2, j=n-1, k=n-1;
continue_loop = 0;
while(i >= 0)
{
if(A[i] < A[j])
{
while(k > i)
{
if(A[i] < A[k])
{
swap(A, i, k);
reverse(A, j, n-1);
printf("\n");
for(l=0; l < n; l++)
printf(" %d ", A[l]);
break;
}
k--;
}
continue_loop = 1;
break;
}
i--;
j--;
}
}

}

int main (int argc, const char * argv[])
{
int i = 0, n;
int *A;

scanf("%d", &n);
A = (int *)malloc(sizeof(int));

for(; i < n; i++)
A[i] = i+1;

print_permutations(A, n);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void permutate( char[] str, int index )
{
int i = 0;
if( index == strlen(str) )
{ // We have a permutation so print it
printf(str);
return;
}
for( i = index; i < strlen(str); i++ )
{
swap( str[index], str[i] ); // It doesn't matter how you swap.
permutate( str, index + 1 );
swap( str[index], str[i] );
}
}``````

taken from online, not by me

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.