Amazon Interview Question for SDE1s


Country: India
Interview Type: Phone Interview




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

any one has a good solution for this ?

- vaibhy1988 July 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- S O U N D W A V E August 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- geekyjaks August 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The results of known recursion can be cached to reduce the complexity in my approach.

- geekyjaks August 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

If the problem is too hard => go greedy
i.e. choose at every step that dish which will feed the largest number of peoplez
(among those that are hungry of course)

- anonus October 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

This problem called "set coverage" and it's NP complete, so could be solved using approximation or brute force (if small enough).

- m@}{ July 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Arun August 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Mr. Lazy August 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous March 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This problem called "set coverage". Can be solved using approximation greedy algorithm or brute force (if small enough).

- max July 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This problem called "set coverage". Can be solved using approximation greedy algorithm or brute force (if small enough).

- max July 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- meh July 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

We can sort the dishes according to number of the customers who prefer the dish in decreasing order, exclude the dishes which has no customers, then brute force beginning from the top of the list.

- Atom July 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)))

- Anonymous July 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)))

- drdoom July 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)))

- drdoom July 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

-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.

- Atom July 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

While there are still dishes not taken.
I'm sorry, but a small correction doesn't hurt

- Atom July 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

solve it bottom up. its a dp problem.

- Anonymous July 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

stop posting this in so many threads

explain the recursion/recurrence of the DP

- stop August 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This can be formulated as a binary linear integer program for which very optimized solvers exist

- Anonymous July 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)

- gen-y-s July 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Mudit July 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Mudit July 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Mudit July 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- divm01986 July 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- t July 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will just mark every dish as true in dishes[] and return 7 in the example case.

- Anonymous July 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is completely wrong - it just counts all the meals (instances of dished with a 1), returning 7 for the above example.

- Anon July 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Greenskid August 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- PT August 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- PT August 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- pthiyana August 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Why does this forum fail to post a reply my first 2 times, then after I sign in and try again, it posts all 3 attempts?

- pthiyana August 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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());

- brazilcoder August 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Is it not similar to job matching problem solved using Graph ??

- ram.prasad.prabu August 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous August 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

}

- saddham August 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- codealtecdown August 23, 2015 | 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