Interview Question
Software Engineer / DevelopersInterview Type: Written Test
4 3 1 2 ... the last one should not be included ... there will only be n!-((n-1)*(n-1)!) combinations
Ignore this
Note leave the 2 elements from (4,3,2,1) i.e take 2,1 (rotate the array 1 times i.e length(remainingarray)-1
4,3,1,2
Instead it should be :
Note leave the last element from (4,3,2,1) i.e take 4,3,2(rotate the array 2 times i.e length(array)-1
3,2,4,1
2,4,3,1
Keep removing one from either side till you reach 2 middle values. They should never be swapped as they will always violate the x, x+1 rule
How about this solution in Scala?
object Main {
def insert(x: Int, items: List[Int]): List[List[Int]] = {
if (items isEmpty) List(List(x))
else for {
i <- (0 to items.length).toList
val s = items.splitAt(i)
} yield s._1 ::: (x :: s._2)
}
def perms(a: List[Int]): List[List[Int]] = a match {
case Nil => List(List())
case x :: xs => for {
p <- perms(xs)
i <- insert(x, p)
} yield i
}
def special(items: List[Int]): Boolean = items match {
case Nil => true
case x :: xs => xs match {
case Nil => true
case y :: ys => x != y - 1 && special(xs)
}
}
def main(args: Array[String]) {
val items = List(1, 2, 3, 4)
println(perms(items))
println(perms(items).filter(special))
}
}
It simply filters from all possible permutations
Sol 1: create a circular array and print all elements of it and keep shifting the first index.
Sol 2: or create a string and every time eliminate front char and add it in last and print the complete string.
He means that out of all possible permutations of consecutive numbers beginning with 1 to N, find good ones where good ones are defined as the ones where x+1 does not occur after x.
eg: N = 3. Hence, input = {1,2,3} ie. {x, x+1, x+2}
Find all permutations of input and filter the good ones.
a general backtrack in c++
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
void print(vector<int> v){
for(int i = 0; i < v.size(); ++i )
cout<<v[i]<<" ";
cout<<endl;
}
bool isSolution(vector<int> s, int step, int n){
return step == n;
}
void processSolution(vector<int> s, int step, int n){
print(s);
}
void generateSpace(vector<int> s, int step, int n, vector<int> &space){
vector<int>::iterator sBegin = s.begin();
vector<int>::iterator sEnd = s.end();
int key = -1;
if(s.size()>0)
key = s.back(); // s.back() is unstable when s is empty
for(int i=1; i <=n; i++){
if( find(sBegin,sEnd, i) == sEnd and i != key-1)
space.push_back(i);
}
}
void backtrack(vector<int> s, int step, int n){
if( isSolution( s, step, n) ){
processSolution(s,step,n);
}
else{
++step;
vector<int> space;
generateSpace(s,step,n,space);
for(int i = 0;i < space.size(); i++){
s.push_back( space[i] );
backtrack(s,step,n);
s.erase(s.end()-1);
}
}
}
int main(){
vector<int> s;
int step = 0;
int n = 3;
backtrack(s,step,n);
return 0;
}
A good permutation is composed by pulling out an element from the list and then finding all "good" permutations of the remaining elements that don't begin with the pulled out element's successor. This is fairly easy to code up recursively, and the recursive solution prunes bad permutations effectively. A more naive solution would be to just generate all permutations and filter out bad permutations.
def good_permute(arr, bad_head = None):
if len(arr) == 1:
if arr[0] == bad_head:
return []
return [arr]
result = []
for i in range(len(arr)):
v = arr[i]
if v == bad_head: continue
others = arr[:i] + arr[i+1:]
for p2 in good_permute(others, v+1):
result.append([v] + p2)
return result
print good_permute([1,2,3,4])
int a[][4];//source array
int b[4]={4,3,2,1}
int i=0;//global value
for(int j=0;j<4;j++)//first array reverse
{
a[i][j]=b[j];
}
i++;
1 //first four elemnts shifting
for( ;i<4;i++)
{
for(int j=0,k=1;j<4;j++)
{
if(K==4)
k=0;
else{
a[i][j]=a[i-1][k];
k++;
}
}
}
2 //Right element constant remaing all element rotate two times
int f=i,k=0;
for(int a=0;a<2;a++)//this two time rotaion
{
if(a==0)
{
k=0;
}
else
k=f; //second time k value will last for i value
for(;k<4;k++)
{
for(int z=0;z<=4;z++)
{
if(z==0)
a[i][j]=a[k][z];
//last three are rotation
if(z==4)
z=0;
a[i][j]=a[k][z+1];
j++;
}
i++;
}
}
3 //left elemenmt constant remaing first three are one time rotation
for(int x=0;x<4;x++)
{ j=0;
for(int y=0;y<=3;y++)
{
if(y==3)
y=0;
a[i][j]=a[x][y+1];
j++;
}
a[i][j]=a[x][3];
i++;
}
}
o/p:explation workin of this
first rotation
4321 3214 2143 1432
second:right one constant remaing two times rotaion (rotation done obn the first four only if done on remaing same one will come again and again)
4213 3142 2431 1324
4132 3421 2314 1243
third :left one is constant remaing all (first three) rotaion
3241 2134 1432 4321
Arrange the array in descending order for eg n=4
- arpitg February 12, 20134,3,2,1
(rotate the array 3 times i.e length(array)-1
3,2,1,4
2,1,4,3
1,4,3,2
Note leave the first element from (4,3,2,1) i.e take 3,2,1 (rotate the array 2 times i.e length(array)-1
4,2,1,3
4,1,3,2
Note leave the 2 elements from (4,3,2,1) i.e take 2,1 (rotate the array 1 times i.e length(remainingarray)-1
4,3,1,2
I think this should work