Facebook Interview Question
Front-end Software EngineersCountry: United States
Interview Type: Written Test
#include<iostream>
using namespace std;
bool flag[7][7],res[7][7];
int result[7][7],r=0,maxi=0,n,m,c,x,next=1,temp[7][7],z[4][2],in[7][7];
int visited[7][7],used[40];
int get_next()
{
while(used[next]==1)
next++;
used[next]=1;
return next;
}
void input()
{
char ch;
int i,j,k,p;
ch=getchar();
string s;
for(i=1;i<=n;i++)
{
p=1;
getline(cin,s);
for(j=0;j<s.length();j++)
{
if(s[j]=='?')
{
in[i][p++]=0;
j++;
}
else
{
k=0;
while(s[j]!=' ' && j<s.length() )
{
k=k*10+int(s[j])-48;
j++;
}
in[i][p++]=k;
}
}
}
}
inline bool isrange(int i,int j)
{
return (i<=n && j<=m && i>0 && j>0);
}
int mark_visited(int a,int b,int j,int k)
{
int i,p=0;
for(i=0;i<4;i++)
{
if(isrange(a+z[i][0],b+z[i][1]) && visited[a+z[i][0]][b+z[i][1]]==j)
{
visited[a+z[i][0]][b+z[i][1]]=k;
p++;
}
}
return p;
}
bool compare()
{
int i,j,k=0;
if(result[0][0]==1)
{result[0][0]=0;
return 1;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(temp[i][j]<result[i][j])
return 1;
if(result[i][j]<temp[i][j])
return 0;
}
}
return 1;
}
int count_ones(int a,int b)
{
int k=0,i,j;
for(i=0;i<4;i++)
{
if(isrange(a+z[i][0],b+z[i][1]) && flag[a+z[i][0]][b+z[i][1]])
{
k++;
if(temp[a+z[i][0]][b+z[i][1]]==0)
x=i;
}
}
return k;
}
void save()
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
res[i][j]=flag[i][j];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
result[i][j]=temp[i][j];
}
void fill()
{
int a=1,b=1,i,k,j;
for(i=0;i<=n;i++)
for(k=0;k<=m;k++)
{
temp[i][k]=in[i][k];
used[i*n+k]=0;
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(in[i][j]>0)
used[in[i][j]]=1;
}
next=1;
while(next<=n*m)
{
if(temp[a][b]==0)
temp[a][b]=get_next();
i=count_ones(a,b);
if(i==1 && a*b!=1)
break;
for(i=0;i<4;i++)
{
if(isrange(a+z[i][0],b+z[i][1]) && i!=x && temp[a+z[i][0]][b+z[i][1]]==0)
temp[a+z[i][0]][b+z[i][1]]=get_next();
}
if(x==2)
{
for(i=1;i<=b;i++)
temp[a][i]=(temp[a][i]==0 && flag[a][i]==0)?get_next():temp[a][i];
}
if(x==3)
{
for(i=1;i<=m;i++)
temp[a][i]=(temp[a][i]==0 && flag[a][i]==0)?get_next():temp[a][i];
}
a=a+z[x][0];
b=b+z[x][1];
}
}
void display()
{
int i,j,k;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
cout<<res[i][j]<<" ";
cout<<endl;
}
cout<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
cout<<result[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}
void compute(int a,int b,int i)
{
int p,j,k=r;
j=count_ones(a,b);
if(in[a][b]>0)
{
j=(in[a][b]>=c)?j:2;
}
if(isrange(a,b) && !flag[a][b] && j<=1 && c<=m*n)
{
flag[a][b]=1;
r++;
c=c+mark_visited(a,b,0,k+1);
compute(a,b-1,i);
compute(a,b+1,i);
compute(a-1,b,i);
compute(a+1,b,i);
c=c-mark_visited(a,b,k+1,0);
if(r==maxi && i==1)
{
fill();
if(compare())
save();
}
if(r>maxi)
maxi=r;
r=k;
flag[a][b]=0;
}
}
int main()
{
int i,j;
cin>>n>>m;
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
{
temp[i][j]=0;
flag[i][j]=0;
visited[i][j]=0;
}
z[0][1]=z[1][0]=z[2][0]=z[3][1]=0;
z[2][1]=z[3][0]=1;
z[0][0]=z[1][1]=-1;
result[0][0]=1;
visited[1][1]=1;
input();
c=(in[1][1]>0)?in[1][1]:1;
compute(1,1,0);
compute(1,1,1);
cout<<maxi<<endl;
display();
return 0;
}
it is really hard
- it is really hard September 26, 2013