Facebook Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
This question is actually a little dumb because reading the input takes O(N^2) time, and so it doesn't matter if I solve it efficiently like I did or more naively. The adjacency matrix should have been presented as an adjacency list instead to remove this N^2 factor and make it N + E where E is the number of edges in the adjacency list.
#include<iostream>
#include<vector>
using namespace std;
vector<int> connected;
void connectedComponent1(vector<vector<int> > v,vector<bool> &visited,int condition,int j1)
{
visited[j1]=1;
for(int j=0;j<v[0].size();j++)
if(v[j1][j]==1&&visited[j]==0)
connectedComponent1(v,visited,1,j);
}
void connectedComponent(vector<vector<int> > v,vector<bool> &visited,int condition,int j1)
{
for(int i=0;i<v[0].size();i++)
{
if(visited[i]==0)
{
vector<bool> visited2=visited;
visited[i]=1;
for(int j=0;j<v[0].size();j++)
if(v[i][j]==1&&visited[j]==0)
connectedComponent1(v,visited,1,j);
for(int i1=0;i1<v[0].size();i1++)
{
if(visited2[i1]==0&&visited[i1]==1)
connected.insert(connected.end(),i1);
}
connected.insert(connected.end(),-1);
visited2.clear();
}
}
}
int main()
{
int n,condition=0;
cin>>n;
int array[n];
for(int i=0;i<n;i++)
cin>>array[i];
vector<vector<char> > v1(n,n);
vector<vector<int> > v(n,n);
vector<bool> visited(n);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cin>>v1[i][j];
visited[i]=0;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(v1[i][j]=='y'||v1[j][i]=='y')
v[i][j]=1;
else
v[i][j]=0;
}
}
connectedComponent(v,visited,0,0);
vector<int> v2;
for(int i=0;i<connected.size();i++)
{
if(connected[i]==-1)
{
sort(v2.begin(),v2.end());
v2.clear();
}
v2.insert(v2.end(),array[connected[i]]);
}
system("pause");
return 0;
}
Since the rule matrix is symmetric and the diagonal elements are 'n' all the time since [1][1]=n that means first digit cannot be exchanged with the first one,which doesn't permute the P.
so in your test case
[1][2]=y so first digit can be exchanged with the second one
so we get by applying rule
2 3 1
[1][3]=n so first digit cannot be exchanged with the third one
then we can directly consider
[2][3]=y so second digit can be exchanged with the third one
so we get
3 1 2
so between 3 2 1 (input ) and two obtained permutations 2 3 1 and 3 1 2 smaller is 2 3 1
Output:
2 3 1
@nikhi why are you just checking for upper right half of matrix ( right to diagonal ) and that too without comparing it with other string whether it is small or large. Is your solution correct or i am missing something here.
Small modification..The rules can be applied in the any order and any number of times ..
I used some greedy approach and believe me It was right ,that's why i was selected for next round .
Correct the greedy solution would work here. If rule can be applied only once then we need to see the first row which has true set with the minimum number. And that would be our answer. This is my code.
public int [ ] getSmallestPermutation ( int [ ] original, boolean [ ][ ] exchange ) {
if ( original == null || exchanged == nil )
return null;
int n = original.length;
for ( int i=0; i<n; i++ ) {
int number = original[i];
int min = number;
int minIndex = i;
for ( int j=0; j<n; j++) {
if ( exchange[i][j] ) {
if ( min > original[i] ) {
min = original[i];
minIndex = j;
}
}
}
if ( min != number ) {
original[minIndex] = original[i];
original[i] = min;
break;
}
}
return original;
}
#include<iostream>
#include<math.h>
using namespace std;
int toint(int arr[],int);
int main(){
int k,i,j,small,tm;
cin>>k;
int p[k],*r; char q[k][k];
for(i=0;i<k;i++)
{cin>>p[i];
}
small=toint(p,k);
for(i=0;i<k;i++)
{ for(j=0;j<k;j++)
{
cin>>q[i][j];
}
}
for(i=0;i<k;i++)
{for(j=0;j<k;j++)
{
if(q[i][j]=='y')
{ r=p;
int t=r[i];
r[i]=r[j];
r[j]=t;
int u=toint(r,k);
if(u<small)small=u;
}
}
}
cout<<small;
return 0;
}
int toint(int arr[],int size)
{
int tmp,num=0;
for(int l=size;l>0;l--)
{ tmp=(int)floor(pow(10,(l-1)));
num+=arr[size-l]*tmp;
}
return num;
}
/*
* FB.cpp
*
* Created on: 03-Sep-2012
* Author: Pavan
*/
/*
* Q2.cpp
*
* Created on: 03-Sep-2012
* Author: Pavan
*/
#include<iostream>
#include<string>
using namespace std;
int main()
{
int K;
cin>>K;
char *P = new char [K]();
for(int i=0;i<K;i++)
{
cin>>P[i];
}
string *matrix = new string [K] ();
for(int i=0;i<K;i++)
{
cin>>matrix[i];
}
for(int i=0;i<K;i++)
{
for(int j=i;j<K;j++)
{
if(P[i]>P[j] && i<j && matrix[i][j]=='Y')
{
char temp;
temp = P[i];
P[i]=P[j];
P[j]=temp;
}
if(P[i]<P[j] && i>j && matrix[i][j]=='Y')
{
char temp;
temp = P[i];
P[i]=P[j];
P[j]=temp;
}
}
}
for(int i=0;i<K;i++)
{
cout<<P[i];
if(i<(K-1))
cout<<" ";
}
delete [] P;
delete [] matrix;
return 0;
}
Make a graph where each vertex is a position in the array (0 to N-1). Let an edge connect two vertices whenever swapping the elements at those two positions is allowed. You need to get all the connected components of this graph, and then for each connected component, sort the elements available within that connected component so that the smallest positions have the lowest possible elements (smallest index within the connected component gets smallest element, second smallest index gets second smallest element, etc.). When this is done for all connected components, you will have the lowest possible permutation. This algorithm is about as efficient asymptotically as the sorting algorithm you use. Since all steps except sorting are O(N), it's asymptotically optimal.
- eugene.yarovoi July 20, 2012