Adobe Interview Question for MTSs

Country: India

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>

int main()
{
long int t,n,k,i,j,a;
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);
}
}

Comment hidden because of low score. Click to expand.
2

very brilliant answer, however the result is not the minimum count.

Comment hidden because of low score. Click to expand.
0

We can have a map which stores the dish number. For all the 1s encountered in a row, we can check, if the map already contains any one of this j (dish number). If yes, we don't increment 'm' else, we do and store this new 'j' in map. What say?

Comment hidden because of low score. Click to expand.
0
of 0 vote

It requires some clever bit manipulation, i feel !! What do u guys think?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

minDish(i,j) = min(minDish(i+1,j), 1+minDish(i+1, SetOf(j-F(i))))

Where i is the dish count
j is set of friends
F(i) is set of frnds who like i-th dish

And base conditions would be
minDish(i,0) = 0
minDish(0,j) = infinity

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
int main()
{
int n,k,t;int a;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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
int main()
{
int n,k,t;int a;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;
}

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.

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.