Adobe Interview Question
MTSsCountry: India
OK. If I were the interviewer asking this question, I'd expect ideal answer to be the following:
1) Prove that this problem is NP-hard by showing its equivalence to well known Set cover problem
2) Reason about limits (e.g. number of kids and dishes will be reasonably small), estimate the search space and conclude that "brute-force"-like solution (e.g. backtracking with pruning of the search space) will be likely practical.
3) Propose an approximated solution - a greedy algorithm. (E.g. at each step take most liked dish, remove"satisfied" kids and repeat). Prove some important properties of of this algorithm (for instance if answer is "1" or "2" then this it is guaranteed to be optimal)
4) Code a solution which
a) starts with a greedy algorithm to find the first estimation
b) terminate if answer is optimal (by the properties of algorithm)
c) run backtracking with pruning
d) optionally limit execution of backtracking by time, ending with best found solution
5) talk about possible alternatives of backtracking and mention at least one randomized search algorithms
We can use this algo:
1) find first 1 in string and its index, set it 1 in same index of final dishes string
2) set this string as all zero and find all other strings having 1 at same index and set them all zero too
3) keep iterating with step1 & step2 untill all strings are exhausted
4) final dishes string will contain minimum set of dishes
#include<iostream>
using namespace std;
int main()
{
int n,k,t;int a[500][10];int count;
cout<<"\n enter the test cases\n";
cin>>t;
if(1<=t&&t<=10)
{
for(int i=0;i<t;i++)//t=0
{ count=0;
cout<<"\n enter the number of friends\n";//2
cin>>n;
if(1<=n&&n<=500)
{
cout<<"\n enter the number of dishes\n";//2
cin>>k;
if(1<=k&&k<=10)
{
for(int j=1;j<=n;j++)//row 2
{
for(int p=1;p<=k;p++)//column2
{
cout<<"enter 1 or 0 for dislike or like ";
cin>>a[j][p];
}
}
}
else
cout<<"\n enter the number of dishes between 1 and 10";
}
else
cout<<"\n enter the number between 1 and 500";
int m=1;
while(m<=k)
{
for(int o=1;o<=n;o++)
{
if(a[o][m]==1)
{
count++;
break;
}
}
m++;
}
cout<<"\n"<<count;
}
}
else
cout<<"\n enter the number of test casesbetween 1 and 10";
return 0;
}
#include<iostream>
using namespace std;
int main()
{
int n,k,t;int a[500][10];int count;
cout<<"\n enter the test cases\n";
cin>>t;
if(1<=t&&t<=10)
{
for(int i=0;i<t;i++)//t=0
{ count=0;
cout<<"\n enter the number of friends\n";//2
cin>>n;
if(1<=n&&n<=500)
{
cout<<"\n enter the number of dishes\n";//2
cin>>k;
if(1<=k&&k<=10)
{
for(int j=1;j<=n;j++)//row 2
{
for(int p=1;p<=k;p++)//column2
{
cout<<"enter 1 or 0 for dislike or like ";
cin>>a[j][p];
}
}
}
else
cout<<"\n enter the number of dishes between 1 and 10";
}
else
cout<<"\n enter the number between 1 and 500";
int m=1;
while(m<=k)
{
for(int o=1;o<=n;o++)
{
if(a[o][m]==1)
{
count++;
break;
}
}
m++;
}
cout<<"\n"<<count;
}
}
else
cout<<"\n enter the number of test cases between 1 and 10";
return 0;
}
#include<stdio.h>
int main()
{
long int t,n,k,i,j,a[100][100];
scanf("%ld",&t);
for(i=1;i<=t;i++){
long int m=0;
printf("Enter number of dishes:");
scanf("%ld",&n);
printf("Enter number of friends:");
scanf("%ld",&k);
for(i=1;i<=n;i++)
{
for(j=1;j<=k;j++)
{
scanf("%ld",&a[i][j]);
}
}
j=1;
while(j<=k){
for(i=1;i<=n;i++)
{
if(a[i][j]==1)
{
m++;
break;
}
}
j++;
}
printf("%ld",m);
}
}
#include<stdio.h>
- Rahul July 27, 2015int main()
{
long int t,n,k,i,j,a[100][100];
scanf("%ld",&t);
for(i=1;i<=t;i++){
long int m=0;
printf("Enter number of dishes:");
scanf("%ld",&n);
printf("Enter number of friends:");
scanf("%ld",&k);
for(i=1;i<=n;i++)
{
for(j=1;j<=k;j++)
{
scanf("%ld",&a[i][j]);
}
}
j=1;
while(j<=k){
for(i=1;i<=n;i++)
{
if(a[i][j]==1)
{
m++;
break;
}
}
j++;
}
printf("%ld",m);
}
}