Facebook Interview Question for Software Engineer / Developers


Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
5
of 7 vote

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

5
56321
nnyny
nnnny
ynnnn
nnnnn
yynnn
output=??

- mike August 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Neat Solution!!

- prakharavasthi August 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good discussion. not coding friendly.

- jiangok2006 August 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi September 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

#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;
}

- pankaj-iit roorkee August 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Question not clear.
3
3 2 1
nyn
yny
nyn
What will be the output? {2 3 1} or {1 2 3}

- Anonymus July 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Nikhita July 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- ninja July 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Small modification..The rules can be applied in the any order and any number of times ..

- Anonymous July 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ninja I am just guessing the solution and I am not sure of it !

- Anonymous July 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you apply any of the rules more then one?

- Anonymous July 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, you can apply only one at a time for the original permutation

- Nikhita July 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Small modification..The rules can be applied in the any order and any number of times ..

- Anonymous July 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

I used some greedy approach and believe me It was right ,that's why i was selected for next round .

- turi July 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- Zero2 December 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

warshall on yes no matrix and then starting from left in permutation bring up the least possible element available for swapping ahead of it.....hope it works well

- serverado July 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can i please get the full question? I'd help me understand the problem better. Thank you

- Vicky August 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is facebook Online First Round question asked in NIT Warangal and IIT BHU

- Anonymous August 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

oh yea

- Anonymous August 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
   }

- Kaushal Singh August 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

created function named "toint" to convet array into integer....isn't small code??

- Kaushal Singh August 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can u clarify if the permutations have to be applied to the original sequence always or they can be applied to the sequence generated from the previous steps
if yes, the permutations have to be applied in the same order or not ?

- Anonymous August 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Can anybody elaborate the question with more clear test cases...plsss

- kuldeep August 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

/*
* 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;
}

- PavaPatil September 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The logic is to sort the given input according to given constraints.

- PavaPatil September 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Fails for the given test case!!!! LOL!!!

- noname November 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

5
56321
nnyny
nnnny
ynnnn
nnnnn
yynnn
output=??

- Anonymous August 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

here is my friend's solution who cleared FB's 1st round....
codepad.org/BZFH0lae

- Anonymous September 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

copy - paste the link in your browser.

- Anonymous September 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

plz elaborate by giving some example.. i am unable to figure out..

- kunal.id89 July 19, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More