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

- Rahul July 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

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

- Eidolon.C July 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Coder July 27, 2015 | Flag
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?

- Coder July 27, 2015 | Flag Reply
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

- 0xF4 July 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this solution:

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

- Sumit December 10, 2015 | Flag Reply
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

- Learner January 09, 2016 | Flag Reply
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[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;
}

- sumathi May 18, 2017 | Flag Reply
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[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;
}

- sumathi May 18, 2017 | Flag Reply


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