Amazon Interview Question
SDE1sCountry: India
Interview Type: Phone Interview
One optimization might be that it is unlikely that num dishes is large, so we can store it in possibly 1 integer (64 bits).
Then we can build up partial solutions using the same 64 bit field.
And for filling person i , we can check that person i ' s preference (i.e., row of input matrix would be another bit field) against the partial solution so far using:
if ( partialSolSoFar & personPreference[i ] ) // no need to add...
We can also have a memo... mapping combinations of "i" and partialSolutions
... but this would have to be a hash table of sorts.
So I see 3 possible optimizations
1) use integer bit magic
2) prune recursion by checking if a partial solution already satisfies i-th person's preference
3) memo using a hash from (i, partialSolSoFar) to min
This problem is a variation of optimum sellers to ship the products. Here is the working solution,
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;
public class OptimumDish {
private Set<Integer> result = new HashSet<Integer>();
public void print(){
for(int r:result)
System.out.print(r + " ");
}
public void find(int[][] m, int r, int c, int mr, int mc, Stack<Integer> dishes) {
dishes.push(c);
if (r == mr) {
Set<Integer> d = new HashSet<>(dishes);
if(result.size() == 0 || result.size() > d.size())
result = d;
}
else if (r < mr) {
for (int i = 0; i <= mc; i++) {
if (m[r + 1][i] == 1) {
find(m, r+1, i, mr, mc, dishes);
break;
}
}
}
dishes.pop();
for (int i = c + 1; i <= mc; i++) {
if (m[r][i] == 1) {
find(m, r, i, mr, mc, dishes);
}
}
}
public static void main(String[] args) {
int[][] m = {
{ 0, 1, 1, 0, 0, 0, 0 },
{ 0, 1, 0, 1, 0, 0, 0 },
{ 0, 1, 1, 0, 0, 1, 0 },
{ 1, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 1, 0, 1, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 1 }
};
int mr = m.length - 1;
int mc = m[0].length - 1;
int c = 0;
for (int i = 0; i <= mr; i++) {
if (m[0][i] == 1) {
c = i;
break;
}
}
OptimumDish od = new OptimumDish();
Stack<Integer> dishes = new Stack<>();
od.find(m, 0, c, mr, mc, dishes);
od.print();
}
}
Possible Approach
Assuming each column as binary values get there decimal equivalent. For the given case the binary equivalents are {56,4,2,1,36,18,9}
The decimal value for the solution is 63(Binary:111111)
we need to get the minimum number of elements whose sum can make 63.
For that we can sort the array
{1,2,4,9,18,36,56}
and apply binary search to get minimum set of numbers to make 63
Check out my dp + bitmasking solution..... It, is designed to work when N is small i.e., 1 <= N <= 12 and 1 <= K <= 200
// Author :: Gaurav Ahirwar
#include<bits/stdc++.h>
#define FOR(i,n) for(int i=(0);i<(n);i++)
#define MOD 1000000007
#define INF 10000000
using namespace std;
vector<int> arr[201];
int dp[4096][201];
int allmask;
int getmindishes(int mask, int i) {
if(mask == allmask) return 0;
if(i > 200) return INF;
if(dp[mask][i] != -1) return dp[mask][i];
// Don't include this dish in set of ordered dishes
int ways = getmindishes(mask, i+1);
int size = arr[i].size();
// Include This Dish in set of orderd dishes
int newmask = mask;
for(int j = 0; j < size; j++) newmask = newmask | (1 << arr[i][j]);
ways = min(ways, 1 + getmindishes(newmask, i+1));
return dp[mask][i] = ways;
}
void solve(int n, int k) {
int x;
FOR(i,201) arr[i].clear();
FOR(i,n) {
FOR(j,k) {
cin >> x;
if(x) arr[j].push_back(i);
}
}
allmask = (1 << n) - 1;
memset(dp, -1, sizeof dp);
cout << getmindishes(0, 1) << endl;
}
/*
6 7
1 0 0 0 1 0 0
1 0 0 0 0 1 0
1 0 0 0 0 0 1
0 1 0 0 1 0 0
0 0 1 0 0 1 0
0 0 0 1 0 0 1
*/
int main() {
ios_base::sync_with_stdio(false);
int t, n, k;
cin >> n >> k;
solve(n, k);
return 0;
}
private static void min(int[][] arr) {
int n=arr.length; int m=arr[0].length;
Map<Integer,List<Integer>> dish=new HashMap<Integer,List<Integer>>();
Map<Integer,List<Integer>> person=new HashMap<Integer,List<Integer>>();
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(arr[i][j]==1){
if(person.containsKey(i)){
List<Integer> list=person.get(i);
list.add(j);
}
else{
List<Integer> list=new ArrayList<Integer>();
list.add(j);
person.put(i, list);
}
if(dish.containsKey(j)){
List<Integer> list=dish.get(j);
list.add(i);
}
else{
List<Integer> list=new ArrayList<Integer>();
list.add(i);
dish.put(j, list);
}
}
}
}
Set<Integer> set=new HashSet<Integer>();
for(int i=0;i<n;i++) set.add(i);
dfs(person,dish,set,0);
}
private static void dfs(Map<Integer, List<Integer>> person, Map<Integer, List<Integer>> dish, Set<Integer> set, int count) {
if(set.isEmpty()){
min=Math.min(min, count);
return;
}
int p=-1;
for(int i:set){
p=i;
break;
}
List<Integer> list=person.get(p);
for(int d:list){
List<Integer> pers=dish.get(d);
Set<Integer> setNext=new HashSet<Integer>(set);
setNext.removeAll(pers);
dfs(person,dish,setNext,count+1);
}
}
O(k2n)
traverse from col1, col1 to col1, coln
start from col1in temp array, take col2, do OR with it, now sum temp elements, if it sums upto number of users in questions, this is candidate solution, check this with best_solution_so_far,
then do OR with col3, repeat same thing.
then start with col2, repeat same thing.
int minimumDishes(int [][] nk, int n, int k){
int temp[] = new int[n];
int minSoFar = 0;
for(int i=0;i<k;i++){
clearTempArr(temp);
for(int j=i;j<k;j++){
AddColumnToTemp(temp,nk,i,j);
int noOfUsers = noOfUsersInCurrentSelection(temp);
if(noOfUsers < minSoFar)
minSoFar = noOfUsers;
}
}
return minSoFar;
}
import numpy as np
import math
def getMinNumDishes(M):
minNum=np.inf
bestMask=''
numValues=math.pow(2,np.size(M,1))
for mask in range(int(numValues)):
binStr="{0:b}".format(int(mask))
while len(binStr)<np.size(M,1):
binStr='0'+binStr
x = np.matrix(" ".join(binStr))
numDishes = (x==1).sum()
if minNum<numDishes:
continue
b=M*np.transpose(x)
numPersonsServed = (b!=0).sum()
if numPersonsServed < np.size(b,0):
continue
if minNum>numDishes:
minNum=numDishes
bestMask=x
return (minNum, bestMask)
A=np.matrix('1 0 0 0 1 0 0; \
1 0 0 0 0 1 0; \
1 0 0 0 0 0 1; \
0 1 0 0 1 0 0; \
0 0 1 0 0 1 0; \
0 0 0 1 0 0 1')
print(str(getMinNumDishes(A)))
import numpy as np
import math
def getMinNumDishes(M):
minNum=np.inf
bestMask=''
numValues=math.pow(2,np.size(M,1))
for mask in range(int(numValues)):
binStr="{0:b}".format(int(mask))
while len(binStr)<np.size(M,1):
binStr='0'+binStr
x = np.matrix(" ".join(binStr))
numDishes = (x==1).sum()
if minNum<numDishes:
continue
b=M*np.transpose(x)
numPersonsServed = (b!=0).sum()
if numPersonsServed < np.size(b,0):
continue
if minNum>numDishes:
minNum=numDishes
bestMask=x
return (minNum, bestMask)
A=np.matrix('1 0 0 0 1 0 0; \
1 0 0 0 0 1 0; \
1 0 0 0 0 0 1; \
0 1 0 0 1 0 0; \
0 0 1 0 0 1 0; \
0 0 0 1 0 0 1')
print(str(getMinNumDishes(A)))
Greedy approaches dont work here
import numpy as np
import math
def getMinNumDishes(M):
minNum=np.inf
bestMask=''
numValues=math.pow(2,np.size(M,1))
for mask in range(int(numValues)):
binStr="{0:b}".format(int(mask))
while len(binStr)<np.size(M,1):
binStr='0'+binStr
x = np.matrix(" ".join(binStr))
numDishes = (x==1).sum()
if minNum<numDishes:
continue
b=M*np.transpose(x)
numPersonsServed = (b!=0).sum()
if numPersonsServed < np.size(b,0):
continue
if minNum>numDishes:
minNum=numDishes
bestMask=x
return (minNum, bestMask)
A=np.matrix('1 0 0 0 1 0 0; \
1 0 0 0 0 1 0; \
1 0 0 0 0 0 1; \
0 1 0 0 1 0 0; \
0 0 1 0 0 1 0; \
0 0 0 1 0 0 1')
print(str(getMinNumDishes(A)))
-Look at customers if there is a customer who prefers only one dish, take that dish.
-If there is unsatisfied customers
Sort the dishes according to the number of customers who prefer the dish
in decreasing order.
Exclude dishes that has no preferring customers.
While there are still unsatisfied customers
Add dishes one by one to the previously selected dishes,beginning from the top
of the list, check if all customers are satisfied every time, if yes finish.
Then make combinations of two, three, four...., also beginning from the top of the
list, add them and check until all customers are satisfied.
Dynamic programming: recursively check how many dishes needed if not including the current dish, and compare to the option of including the current dish (also done recursively).
def f(M, i):
if i==0:
return 0
cnt_without_dish=f(M, i-1)
M'=mark M to remove persons liking dish i
cnt_with_dish=f(M', i-1)+1
return min(cnt_without_dish, cnt_with_dish)
Yes can be solved using recursion, use DP memoization or tabular to optimize -
int mindishes_util(int **nxm,int n, int nth, int k, bool *isselected);
int mindishes(int **nxm, int n, int k){
int minval=10000000; //keep minval infinite currently
bool *dishselected = new bool[k];
for(int i=0;i<k;i++)
dishselected[i]=false;
for (int i=0;i<k;i++){
if (nxm[0][i]){
//select this dish
int currentval;
dishselected[i]=true;
currentval=1+mindishes_util(nxm,n, 1,k,dishselected);
if (currentval<minval)
minval=currentval;
dishselected[i]=false;
}
}
return minval;
}
int mindishes_util(int **nxm, int n, int nth, int k, bool *isselected){
int minval=10000000;
if (n==nth) {
return 0; //all persons are selected
}
for (int i=0;i<k;i++){
if (nxm[nth][i]){
//common dish is present move to next n
int curr=0;
if (isselected[i])
curr= mindishes_util(nxm,n,nth+1,k,isselected);
else {
isselected[i]=true;
curr= 1 + mindishes_util(nxm,n,nth+1,k,isselected);
isselected[i]=false;
}
if(curr<minval)
minval=curr;
}
}
return minval;
}
int mindishes_util(int **nxm,int n, int nth, int k, bool *isselected);
int mindishes(int **nxm, int n, int k){
int minval=10000000; //keep minval infinite currently
bool *dishselected = new bool[k];
for(int i=0;i<k;i++)
dishselected[i]=false;
for (int i=0;i<k;i++){
if (nxm[0][i]){
//select this dish
int currentval;
dishselected[i]=true;
currentval=1+mindishes_util(nxm,n, 1,k,dishselected);
if (currentval<minval)
minval=currentval;
dishselected[i]=false;
}
}
return minval;
}
int mindishes_util(int **nxm, int n, int nth, int k, bool *isselected){
int minval=10000000;
if (n==nth) {
return 0; //all persons are selected
}
for (int i=0;i<k;i++){
if (nxm[nth][i]){
//common dish is present move to next n
int curr=0;
if (isselected[i])
curr= mindishes_util(nxm,n,nth+1,k,isselected);
else {
isselected[i]=true;
curr= 1 + mindishes_util(nxm,n,nth+1,k,isselected);
isselected[i]=false;
}
if(curr<minval)
minval=curr;
}
}
return minval;
}
int mindishes_util(int **nxm,int n, int nth, int k, bool *isselected);
int mindishes(int **nxm, int n, int k){
int minval=10000000; //keep minval infinite currently
bool *dishselected = new bool[k];
for(int i=0;i<k;i++)
dishselected[i]=false;
for (int i=0;i<k;i++){
if (nxm[0][i]){
//select this dish
int currentval;
dishselected[i]=true;
currentval=1+mindishes_util(nxm,n, 1,k,dishselected);
if (currentval<minval)
minval=currentval;
dishselected[i]=false;
}
}
return minval;
}
int mindishes_util(int **nxm, int n, int nth, int k, bool *isselected){
int minval=10000000;
if (n==nth) {
return 0; //all persons are selected
}
for (int i=0;i<k;i++){
if (nxm[nth][i]){
//common dish is present move to next n
int curr=0;
if (isselected[i])
curr= mindishes_util(nxm,n,nth+1,k,isselected);
else {
isselected[i]=true;
curr= 1 + mindishes_util(nxm,n,nth+1,k,isselected);
isselected[i]=false;
}
if(curr<minval)
minval=curr;
}
}
return minval;
}
public class DishAssignSvc
{
public static int getMinDifferentDishes(int[][] mat)throws NullPointerException
{
if(mat==null)
{
throw new NullPointerException();
}
boolean[] dishes=new boolean[mat[0].length];
for(int i=0;i<mat.length;i++)
{
for(int j=0;j<mat[i].length;j++)
{
if(mat[i][j]==1 && dishes[j])
{
break;
}else if(mat[i][j]==1 && !dishes[j])
{
dishes[j]=true;
}
}
}
int numDiffDishes=0;
for(int i=0;i<dishes.length;i++)
{
numDiffDishes++;
}
return numDiffDishes;
}
}
O(NM) time and O(M) space
Am I correct thinking that is first person likes everything and second likes any of 2 dishes, ie
11
10
then your result would be 2 instead of 1?
Brute force searching for minimum:
static class Program
{
static int MinDishesToOrderBrute(int[][] m)
{
int peopleCount = m.Length, dishCount = m[0].Length;
List<HashSet<int>> dishesPeopleLike = new List<HashSet<int>>(dishCount);
for(int d = 0; d < dishCount; d++)
{
dishesPeopleLike.Add(new HashSet<int>());
}
// Assign people to the dishes they love
for(int p = 0; p < peopleCount; p++)
{
for (int d = 0; d < dishCount; d++)
{
if(m[p][d] == 1)
dishesPeopleLike[d].Add(p);
}
}
// Address any simple cases
//
int maxPeoplePerDish = dishesPeopleLike.Max(c => c.Count);
// if there is a dish that everyone loves, then the count is one
if (maxPeoplePerDish == peopleCount)
return 1;
// if there is no dish in common then the count is N
if (maxPeoplePerDish == 1)
return peopleCount;
// Now perform a brute force search for a combination dish sets that satisfies everyone:
// - first do combinations of two, then three, four, etc. so that the first combination
// found can be returned as the minimum
for(int countOfDishSets = 2; countOfDishSets < peopleCount; countOfDishSets++)
{
foreach (var dishSetCombo in dishesPeopleLike.Combinations(countOfDishSets))
{
var testDishSetCombo = new HashSet<int>();
foreach(var dishSet in dishSetCombo)
{
testDishSetCombo.UnionWith(dishSet);
}
if (testDishSetCombo.Count == peopleCount)
{
Console.Write("Example of dishes that need to be ordered: ");
foreach (var dishSet in dishSetCombo)
{
Console.Write(dishesPeopleLike.IndexOf(dishSet) + " ");
}
Console.WriteLine();
return countOfDishSets;
}
}
}
return 0;
}
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> source, int select, bool repetition = false)
{
return select == 0
? new[] { new T[0] }
: source.SelectMany((element, index) =>
source
.Skip(repetition ? index : index + 1)
.Combinations(select - 1, repetition)
.Select(c => new[] { element }.Concat(c)));
}
static void Main(string[] args)
{
int[][] m = new int[][]{
new int[]{1, 0, 0, 0, 1, 0, 0},
new int[]{1, 0, 0, 0, 0, 1, 0},
new int[]{1, 0, 0, 0, 0, 0, 1},
new int[]{0, 1, 0, 0, 1, 0, 0},
new int[]{0, 0, 1, 0, 0, 1, 0},
new int[]{0, 0, 0, 1, 0, 0, 1}
};
Console.WriteLine("Min dishes to order: {0}", MinDishesToOrderBrute(m));
Console.ReadKey();
}
}
Here is my solution using DP. The idea is to keep the set of all possible dish combinations that satisfy the previous N-1 people. When the Nth person is processed, we check for combinations in the set that do not satisfy either of the Nth person's 2 preferences, and make a copy of that combination and add it to the end of the list of all combinations. The original is combination is modified to add the Nth person's first choice, and the copy at the end is modified to add the Nth persons second choice. If the Nth person's choices are already satisfied by the combinations from the previous N-1 people, then we are done. This is implemented bottom up by making two possible combinations for the first person's 2 choices. I used bitset in C++ to make it easier to hold the possible good dish combinations.
const int N = 6; // number of people
const int K = 7; // number of dishes
void checkAndAddToSets(bitset<K> *sets, bool* personPref, int numDishes, int& totalSets)
{
int choices[2];
int c(0);
// locate the 2 choices for the current person
for(int i=0; i<numDishes; i++)
if(personPref[i]==1)
choices[c++] = i;
int numInitialSets = totalSets;
// check if the choices are satisfied in the existing set.
// Only need to add sets if a combination doesn't contain either of the choices
for(int t=0; t<numInitialSets; t++)
if( sets[t][choices[0]]==0 && sets[t][choices[1]]==0 )
{
sets[totalSets] = sets[t]; // make a copy of the set that does not satisfy the
// person
sets[t][choices[0]] = 1; // add the choice to the set
sets[totalSets++][choices[1]] = 1; // add the second choice to the copy set
// eliminate adding combinations already there. Not totally necessary, saves
// space but costs time
for(int s=0; s<numInitialSets; s++)
if( sets[s]==sets[totalSets-1] )
{
totalSets--;
break;
}
}
}
void minDishesToFeedPeople()
{
// Keep track of all possible dish combinations that satisfy up to N-1 people. If the Nth person
// is satisfied by the existing set, then done. Otherwise, will have to add to the set of
// combinations
bool Pref[N][K] = { {1, 0, 0, 0, 1, 0, 0},
{1, 0, 0, 0, 0, 1, 0},
{1, 0, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 1, 0, 0},
{0, 0, 1, 0, 0, 1, 0},
{0, 0, 0, 1, 0, 0, 1}, };
//bool Pref[N][K] = { {1, 1, 0, 0, 0, 0, 0},
// {0, 1, 1, 0, 0, 0, 0},
// {0, 0, 1, 1, 0, 0, 0},
// {0, 0, 0, 1, 1, 0, 0},
// {0, 0, 0, 0, 1, 1, 0},
// {0, 0, 0, 0, 0, 1, 1}, };
//bool Pref[N][K] = { {1, 0, 0, 0, 0, 0, 1},
// {0, 1, 0, 0, 0, 1, 0},
// {0, 0, 1, 0, 1, 0, 0},
// {0, 0, 0, 1, 1, 0, 0},
// {0, 0, 1, 0, 0, 1, 0},
// {0, 0, 0, 1, 0, 1, 0}, };
int maxSets = 1000*N; // max is really 2^N, but unlikely to need that many
int totalSets(0);
bitset<K>* sets = new bitset<K>[maxSets];
// initialize the first two sets from the first person
for(int i=0; i<K; i++)
if(Pref[0][i]==1)
sets[totalSets++][i] = 1;
// now loop through the remaining N-1 people and build up the possible sets that satisfy
// everyone
for(int n=1; n<N; n++)
checkAndAddToSets(sets, Pref[n], K, totalSets);
// Now find the smallest set
int minSetIndx(0);
int minDishes = sets[0].count();
for(int i=1; i<totalSets; i++)
if(sets[i].count()<minDishes)
{
minDishes = sets[i].count();
minSetIndx = i;
}
for(int j=0; j<K; j++)
cout << sets[minSetIndx][j] << " ";
cout << endl;
delete []sets;
}
Here is my solution using DP. The idea is to keep track of all possible dish combinations that satisfy
the previous N-1 people. Then we process the Nth person. We loop through the existing set of
dish combinations, and if one is found that does not satisfy either of the Nth person's 2 preferences,
we make a copy of that combination and add it to the end of the set. Then the failed combination in
set is modified so that the Nth person's first choice is added to it. Then we modify the copy at the
end of the set so that the Nth person's second choice is added to it. (It may be possible that the
newly added combination at the end of the set already is there, so in this case it is removed to
avoid repeats.) Finally, we go through the set of good dish combinations and find the smallest one.
I used the bitset data type in C++ to make it easier to store the set of good dish combinations and
two other test cases commented out.
Should be O(MN) time and O(N) space.
const int N = 6; // number of people
const int K = 7; // number of dishes
void checkAndAddToSets(bitset<K> *sets, bool* personPref, int numDishes, int& totalSets)
{
int choices[2];
int c(0);
// locate the 2 choices for the current person
for(int i=0; i<numDishes; i++)
if(personPref[i]==1)
choices[c++] = i;
int numInitialSets = totalSets;
// check if the choices are satisfied in the existing set.
// Only need to add sets if a combination doesn't contain either of the choices
for(int t=0; t<numInitialSets; t++)
if( sets[t][choices[0]]==0 && sets[t][choices[1]]==0 )
{
sets[totalSets] = sets[t]; // make a copy of the set that does not satisfy the person
sets[t][choices[0]] = 1; // add the first choice to the set
sets[totalSets++][choices[1]] = 1; // add the second choice to the copy set
// elminate adding combinations already there. Not totally necessary, saves space but costs time
for(int s=0; s<numInitialSets; s++)
if( sets[s]==sets[totalSets-1] )
{
totalSets--;
break;
}
}
}
//
void minDishesToFeedPeople()
{
bool Pref[N][K] = { {1, 0, 0, 0, 1, 0, 0},
{1, 0, 0, 0, 0, 1, 0},
{1, 0, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 1, 0, 0},
{0, 0, 1, 0, 0, 1, 0},
{0, 0, 0, 1, 0, 0, 1}, };
//bool Pref[N][K] = { {1, 1, 0, 0, 0, 0, 0},
//{0, 1, 1, 0, 0, 0, 0},
//{0, 0, 1, 1, 0, 0, 0},
//{0, 0, 0, 1, 1, 0, 0},
//{0, 0, 0, 0, 1, 1, 0},
//{0, 0, 0, 0, 0, 1, 1}, };
//bool Pref[N][K] = { {1, 0, 0, 0, 0, 0, 1},
//{0, 1, 0, 0, 0, 1, 0},
//{0, 0, 1, 0, 1, 0, 0},
//{0, 0, 0, 1, 1, 0, 0},
//{0, 0, 1, 0, 0, 1, 0},
//{0, 0, 0, 1, 0, 1, 0}, };
int maxSets = 1000*N; // max is really 2^N?, but unlikely to need that many
int totalSets(0);
bitset<K>* sets = new bitset<K>[maxSets];
// initialize the first two sets from the first person
for(int i=0; i<K; i++)
if(Pref[0][i]==1)
sets[totalSets++][i] = 1;
// now loop through the remaining N-1 people and build up the possible sets that satisfy everyone
for(int n=1; n<N; n++)
checkAndAddToSets(sets, Pref[n], K, totalSets);
// Now find the smallest set
int minSetIndx(0);
int minDishes = sets[0].count();
for(int i=1; i<totalSets; i++)
if(sets[i].count()<minDishes)
{
minDishes = sets[i].count();
minSetIndx = i;
}
for(int j=0; j<K; j++)
cout << sets[minSetIndx][j] << " ";
cout << endl;
delete []sets;
}
Here is my solution using DP. The idea is to keep track of all possible dish combinations that satisfy the previous N-1 people. Then we process the Nth person. We loop through the existing set of dish combinations, and if one is found that does not satisfy either of the Nth person's 2 preferences, we make a copy of that combination and add it to the end of the set. Then the failed combination in set is modified so that the Nth person's first choice is added to it. Then we modify the copy at the
end of the set so that the Nth person's second choice is added to it. (It may be possible that the newly added combination at the end of the set already is there, so in this case it is removed to avoid repeats.) Finally, we go through the set of good dish combinations and find the smallest one.
I used the bitset data type in C++ to make it easier to store the set of good dish combinations and two other test cases commented out.
Should be O(MN) time and O(N) space.
const int N = 6; // number of people
const int K = 7; // number of dishes
void checkAndAddToSets(bitset<K> *sets, bool* personPref, int numDishes, int& totalSets)
{
int choices[2];
int c(0);
// locate the 2 choices for the current person
for(int i=0; i<numDishes; i++)
if(personPref[i]==1)
choices[c++] = i;
int numInitialSets = totalSets;
// check if the choices are satisfied in the existing set.
// Only need to add sets if a combination doesn't contain either of the choices
for(int t=0; t<numInitialSets; t++)
if( sets[t][choices[0]]==0 && sets[t][choices[1]]==0 )
{
sets[totalSets] = sets[t]; // make a copy of the set that does not satisfy the
//person
sets[t][choices[0]] = 1; // add the first choice to the set
sets[totalSets++][choices[1]] = 1; // add the second choice to the copy set
// elminate adding combinations already there. Not totally necessary, saves
//space but costs time
for(int s=0; s<numInitialSets; s++)
if( sets[s]==sets[totalSets-1] )
{
totalSets--;
break;
}
}
}
//
void minDishesToFeedPeople()
{
bool Pref[N][K] = { {1, 0, 0, 0, 1, 0, 0},
{1, 0, 0, 0, 0, 1, 0},
{1, 0, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 1, 0, 0},
{0, 0, 1, 0, 0, 1, 0},
{0, 0, 0, 1, 0, 0, 1}, };
//bool Pref[N][K] = { {1, 1, 0, 0, 0, 0, 0},
//{0, 1, 1, 0, 0, 0, 0},
//{0, 0, 1, 1, 0, 0, 0},
//{0, 0, 0, 1, 1, 0, 0},
//{0, 0, 0, 0, 1, 1, 0},
//{0, 0, 0, 0, 0, 1, 1}, };
//bool Pref[N][K] = { {1, 0, 0, 0, 0, 0, 1},
//{0, 1, 0, 0, 0, 1, 0},
//{0, 0, 1, 0, 1, 0, 0},
//{0, 0, 0, 1, 1, 0, 0},
//{0, 0, 1, 0, 0, 1, 0},
//{0, 0, 0, 1, 0, 1, 0}, };
int maxSets = 1000*N; // max is really 2^N?, but unlikely to need that many
int totalSets(0);
bitset<K>* sets = new bitset<K>[maxSets]; // stores set of good dish combinations
// initialize the first two sets from the first person
for(int i=0; i<K; i++)
if(Pref[0][i]==1)
sets[totalSets++][i] = 1;
// now loop through the remaining N-1 people and build up the possible sets that
// satisfy everyone
for(int n=1; n<N; n++)
checkAndAddToSets(sets, Pref[n], K, totalSets);
// Now find the smallest set
int minSetIndx(0);
int minDishes = sets[0].count();
for(int i=1; i<totalSets; i++)
if(sets[i].count()<minDishes)
{
minDishes = sets[i].count();
minSetIndx = i;
}
for(int j=0; j<K; j++)
cout << sets[minSetIndx][j] << " ";
cout << endl;
delete []sets;
}
var n = 6;
var k = 7;
var M = [
[1, 0, 0, 0, 1, 0, 0],
[1, 0, 0, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 1, 0, 0],
[0, 0, 1, 0, 0, 1, 0],
[0, 0, 0, 1, 0, 0, 1]
];
console.log("Starting");
function isSufficient(dishes) {
for (var p = 0; p < n; p++) {
var numDishes = 0;
for (var d = 0; d < dishes.length; d++) {
numDishes += M[p][dishes[d]];
}
if (numDishes < 1)
return false;
}
return true;
}
var minD = 99999;
var out = [];
function minDishes() {
combine(0);
return minD;
}
function combine(start) {
if (start == k) return;
for (var i = start; i < k; i++) {
out.push(i);
if (isSufficient(out) && minD > out.length) {
minD = out.length;
console.log(out + " minDishes: "+ minD);
}
combine(i+1);
out.pop();
}
}
console.log("minDishes: "+minDishes());
public class FeedPeople {
static int[][] arr = {{1, 0, 0, 0, 1, 0, 0}, {1, 0, 0, 0, 0, 1, 0}, {1, 0, 0, 0, 0, 0, 1}, {0, 1, 0, 0, 1, 0, 0}, {0, 0, 1, 0, 0, 1, 0}, {0, 0, 0, 1, 0, 0, 1}};
static HashSet dishes = new HashSet();
public static void main(String[] args) {
int numPeopleToFeed = arr.length;
int numDishes = arr[0].length;
HashSet people = new HashSet();
for (int j = 0; j < arr.length; j++)
people.add(j);
int i = feedPeople(numDishes - 1, numPeopleToFeed - 1, people);
System.out.println(i);
System.out.println("Dishes chosen " + dishes);
}
private static int feedPeople(int d, int p, Set people) {
if (d < 0)
return 0;
if (people.size() == 0)
return dishes.size();
return Math.min(1 + feedPeople(d - 1, p - getPeopleFedCount(d), getPeopleLeftToFed(d, people)), feedPeople(d - 1, p, people));
}
private static int getPeopleFedCount(int d) {
int count = 0;
for (int[] a : arr) {
if (a[d] == 1)
count++;
dishes.add(d + 1);
}
return count;
}
private static Set getPeopleLeftToFed(int d, Set inputPeople) {
int count = 0;
HashSet people = new HashSet();
for (int i = 0; i < arr.length; i++) {
if (arr[i][d] == 1)
people.add(i);
}
inputPeople.removeAll(people);
return inputPeople;
}
}
private static int noOfDishes(int [][] a, int dishes, int people){
int req=0;
int [] dis = new int[people];
int j;
for(j=dishes-1; j>=0;j--){
for(int i=0; i<people;i++){
if(((a[i][j]!=0) && (a[i][j]^dis[i]) > 0)){
req++;
dis[i]=1;
}
}
if(req==people){
break;
}
}
if(dishes>1){
return Math.min((req<people)?Integer.MAX_VALUE:dishes-j, noOfDishes(a, dishes-1, people));
} else{
return (req<people)?Integer.MAX_VALUE:dishes-j;
}
}
public static int MinDishes(int[,] pdm)
{
Data count = new Data();
count.count = Int32.MaxValue;
List<int> hungry = new List<int>();
int[] dishes = new int[pdm.GetLength(1)];
for (int i = 0; i < pdm.GetLength(0); i++)
{
hungry.Add(i);
}
for (int i = 0; i < pdm.GetLength(1); i++)
{
dishes[i] = 0;
}
MinDishes(pdm, pdm.GetLength(0), pdm.GetLength(1), 0, hungry, dishes, ref count);
return count.count;
}
private static bool MinDishes(int[,] pdm, int n, int k, int person, List<int> hungry, int[] dishes, ref Data count)
{
if (hungry.Count == 0)
return true;
for (int p = person; p < n; p++)
{
for (int d = 0; d < k; d++)
{
if (pdm[p, d] == 1)
{
if (hungry.Contains(p))
hungry.Remove(p);
dishes[d]++;
if (MinDishes(pdm, n, k, p + 1, hungry, dishes, ref count))
{
if (count.count > dishes.Count(i => i > 0))
count.count = dishes.Count(i => i > 0);
}
if (!hungry.Contains(p))
hungry.Add(p);
dishes[d]--;
}
else
continue;
}
}
return false;
}
any one has a good solution for this ?
- vaibhy1988 July 28, 2015