Amazon Interview Question for SDE-2s


Country: India




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

mix = { 'Cust1' : [ 'n3', 'n7', 'n5', 'n2' , 'n9' ],
        'Cust2' : [ 'n5' ],
        'Cust3' : [ 'n2' , 'n3' ],
        'Cust4' : [ 'n4' ],
        'Cust5' : [ 'n3' , 'n4' , 'n3' , 'n5' , 'n7' , 'n4' ] }
// what drinks serves who?
serving = fold( mix.keys , dict() ) as {
   values = mix[$.o]
   for ( v : values ){
     if ( v @ $.p ){
       $.p[v] += $.o 
     } else {
       $.p[v] = set($.o)
     }
   }
   $.p // return     
} 
// next, sort by no of customer a drink serves, and union off, 
// go with greedy mode. if adding a drink does not increase customer base
// no need to add it.. thus...
l = list ( serving ) as { [ $.key , $.value ] }
sortd(l) where { size($.left[1]) < size($.right[1])  }
drinks = set( l[0][0] )
catered = set( l[0][1] )
n = size(catered)
i = 1 
while ( n != size( mix ) ){ 
   catered |= l[i][1]
   if ( size(catered) > n ){
      n = size(catered) 
      drinks += l[i][0]
   }
   i += 1
}
println(drinks)
// caution, the problem is bin packing. Greedy is NOT a gurantee.
// en.wikipedia.org/wiki/Bin_packing_problem#Exact_algorithm
// A gurantee is, of course NP Hard.

- NoOne July 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If a customer adds his two choice at a time then according to which possiblity bartender will make the list of choices first.... 🙃

- Kishan March 28, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void lazyBartender(){
		
		Set<Character> topLevelDrinksSet;
		Set<Character> topLevelCustomerSet;
		
//		Loop on drinks
		while(true){
			
			Set<Character> loopLevelCustomerSet;
			
//			Loop on customers
			while(true){
				
//				Does current customer have the current drink as a fav.
//				Yes -> loopLevelCustomerSet.add(Customer)
			}
			
//			If topLevelCustomerSet does NOT have all the counted customers
			if(!topLevelCustomerSet.containsAll(loopLevelCustomerSet)){
				topLevelCustomerSet.addAll(loopLevelCustomerSet);
				topLevelDrinksSet.add(currentDrink);
			}
		}
		
		System.out.println(topLevelDrinksSet);
	}

- deep.kulshreshtha July 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace test_aws
{
    class Bartender_drinks_distribution
    {
        public Bartender_drinks_distribution()
        {
            List<string> dr;
            Dictionary<string, List<string>> drinks = new Dictionary<string, List<string>>();
            Dictionary<string, List<string>> nlist = new Dictionary<string, List<string>>();
            nlist.Add("Cust1", new List<string>() { "n3", "n7", "n5", "n2", "n9" });
            nlist.Add("Cust2", new List<string>() { "n5" });
            nlist.Add("Cust3", new List<string>() { "n2", "n3" });
            nlist.Add("Cust4", new List<string>() { "n4" });
            nlist.Add("Cust5", new List<string>() { "n3", "n4", "n3", "n5", "n7", "n4" });

            foreach (KeyValuePair<string, List<string>> s in nlist)
            {
                foreach (string st in s.Value)
                {
                    if (!drinks.ContainsKey(st))
                    {
                        drinks.Add(st, new List<string>() { s.Key });
                    }
                    else
                    {
                        dr = drinks[st];
                        if (!dr.Contains(s.Key))
                            dr.Add(s.Key);
                    }

                }
            }
           IOrderedEnumerable< KeyValuePair < string,List<string>>> str =  drinks.OrderByDescending(t => t.Value.Count);
            int lencust = drinks.Count;
            List<string> finaldrinks = new List<string>();
            List<string> finalcust = new List<string>();

            foreach (KeyValuePair<string, List<string>> tt in str)
            {
                if (finalcust.Count >= lencust)
                    break;
                else
                {
                    if (!finaldrinks.Contains(tt.Key))
                    {
                        bool stat = false;
                        foreach(string tts in tt.Value)
                        {
                            if (!finalcust.Contains(tts))
                            {
                                finalcust.Add(tts);
                                stat = true;
                            }
                        }
                        if (stat)
                            finaldrinks.Add(tt.Key);
                    }
                }

            }
            Console.WriteLine(String.Join(",", finaldrinks.ToArray()));
            Console.WriteLine(String.Join(",",finalcust.ToArray()));

        }
    }
}

- KD July 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time complexity of your solution is O(n3).

- gvc July 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my Algorithm,
1. Pick a customer
2. Iterate its drinks
3. check if any customer has this drinks if it has update cust with that drinks.
4. check which drinks have the most customer, and delete them from the set.
5. now for the rest customer go to point 1.

import java.util.*;

public class LazyBartender {

	public static void main(String[] args) {

		HashMap<String, Set<String>> custMap = new HashMap<String, Set<String>>();

		custMap.put("cust1", new HashSet<String>(Arrays.asList("n3", "n7", "n5", "n2", "n9")));
		custMap.put("cust2", new HashSet<String>(Arrays.asList("n5")));
		custMap.put("cust3", new HashSet<String>(Arrays.asList("n2", "n3")));
		custMap.put("cust4", new HashSet<String>(Arrays.asList("n4")));
		custMap.put("cust5", new HashSet<String>(Arrays.asList("n3", "n4", "n5", "n7")));

		System.out.println("total number of drinks required: " + countDrinks(custMap));
	}

	private static int countDrinks(HashMap custMap) {

		int count = 0;
		HashMap<String, ArrayList<String>> cutomerDrinksMap;
		Iterator custItr = custMap.entrySet().iterator();

		while (custItr.hasNext()) {
			Map.Entry pairs = (Map.Entry) custItr.next();

			String customer = (String) pairs.getKey();
			Set<String> drinksSet = (Set<String>) pairs.getValue();

			String maxDrinks = new String();
			int maxDrinksCount = 0;

			cutomerDrinksMap = new HashMap<String, ArrayList<String>>(); // temporaryMap

			for (String set : drinksSet) {

				
				cutomerDrinksMap.put(set, new ArrayList<>(Arrays.asList(customer)));
				
				if (cutomerDrinksMap.get(set).size() > maxDrinksCount) {
					maxDrinksCount = cutomerDrinksMap.get(set).size();
					maxDrinks = set;
				}
				
				
				Iterator internalCustItr = custMap.entrySet().iterator();
				while (internalCustItr.hasNext()) {

					Map.Entry internalPairs = (Map.Entry) internalCustItr.next();
					String internalCustomer = (String) internalPairs.getKey();

					if (!internalCustomer.equals(customer)) {

						Set<String> internalDrinksSet = (Set<String>) internalPairs.getValue();

						if (internalDrinksSet.contains(set)) {
							cutomerDrinksMap.get(set).add(internalCustomer);

							if (cutomerDrinksMap.get(set).size() > maxDrinksCount) {
								maxDrinksCount = cutomerDrinksMap.get(set).size();
								maxDrinks = set;
							}

						}

					}

				}

			}

			ArrayList customerList = cutomerDrinksMap.get(maxDrinks);
			
			if (customerList != null && customerList.size() > 0) {
				count++;
				for (int index = 0; index < customerList.size(); index++) {
					custMap.remove(customerList.get(index));
				}
			}
			custItr = custMap.entrySet().iterator();
		
		}

		return count;
	}

}

- abc.xyz July 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@NoOne hey, what programming language is that? I'm trying to understand the algorithm and what you're saying. If your solution is greedy then it might not be optimal, right? i.e. it might not yield the smallest set of drinks needed, but it gives a good enough solution.

Also how did you realize it was an instance of the Bin packing problem? I spent so long trying to think of a solution before realizing that I could only come up with inefficient or non-optimal algorithms; good thing you pointed it out.

- funk July 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

create a node for all customers and drinks and then do a dfs starting from each customer...minimize the path having least drinks and all customers

- ak47 July 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;
/*
 PROBLEM STATEMENT - Lazy Bartender :

There are N number of possible drinks.(n1,n2..)
Has C number of fixed customers.
Every customer has fixed favourite set of drinks.
Bartender has to create least possible number of drinks
to suffice need of all the customers. A customer is satisfied if he gets atleast once of his favourite drink.
Example:
Cust1,n3,n7,n5,n2,n9
Cust2,n5
Cust3,n2,n3
Cust4,n4
Cust5,n3,n4,n6,n5,n7,n4

Output: 3(n3,n4,n5)
*/

namespace LazyBartender
{
    class Program
    {
        static void Main(string[] args)
        {
            List<Customer> customerList = ReadInput();
            Dictionary<string, int> dict = PrepareSortedDrinkDictionary(customerList);
            ServeCustomer(customerList, dict);
            Console.ReadKey();
        }

        private static void ServeCustomer(List<Customer> customerList, Dictionary<string, int> dict)
        {
            var minimumDrinkHashSet = new HashSet<string>();
            foreach (var element in dict)
            {
                foreach (var c in customerList)
                {
                    if (c.IsSatified == false && c.DrinkList.Contains(element.Key))
                    {
                        c.IsSatified = true;
                        minimumDrinkHashSet.Add(element.Key);
                        Console.WriteLine("Answer: " + c.CustomerId + " Drinks " + element.Key);
                    }

                    if (customerList.Any(x => x.IsSatified == false) == false)
                        break;
                }

                if (customerList.Any(x => x.IsSatified == false) == false)
                    break;
            }

            Console.WriteLine("Minimum drinks needed to serve all customers = " + minimumDrinkHashSet.Count);
        }

        private static Dictionary<string, int> PrepareSortedDrinkDictionary(List<Customer> customerList)
        {
            Dictionary<string, int> dict = new Dictionary<string, int>();
            foreach (var c in customerList)
            {
                foreach (var drink in c.DrinkList)
                {
                    if (dict.ContainsKey(drink))
                    {
                        dict[drink]++;
                    }
                    else dict.Add(drink, 1);
                }
            }

            dict = dict.OrderByDescending(x => x.Value).ToDictionary(x => x.Key, x => x.Value);

            return dict;
        }

        private static List<Customer> ReadInput()
        {
            List<Customer> list = new List<Customer>();
            string input = null;
            do
            {
                input = Console.ReadLine();
                if (string.IsNullOrEmpty(input) == false)
                {
                    var v = input.Split(',').ToList();
                    Customer c = new Customer { CustomerId = v[0] };
                    c.DrinkList.AddRange(v.GetRange(1, v.Count - 1));

                    list.Add(c);
                }

            } while (!string.IsNullOrEmpty(input));

            return list;
        }
    }

    class Customer
    {
        public string CustomerId { get; set; }
        public List<string> DrinkList = new List<string>();
        public bool IsSatified { get; set; }
    }
}

- Anonymous July 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;
/*
 PROBLEM STATEMENT - Lazy Bartender :

There are N number of possible drinks.(n1,n2..)
Has C number of fixed customers.
Every customer has fixed favourite set of drinks.
Bartender has to create least possible number of drinks
to suffice need of all the customers. A customer is satisfied if he gets atleast once of his favourite drink.
Example:
Cust1,n3,n7,n5,n2,n9
Cust2,n5
Cust3,n2,n3
Cust4,n4
Cust5,n3,n4,n6,n5,n7,n4

Output: 3(n3,n4,n5)
*/

namespace LazyBartender
{
    class Program
    {
        static void Main(string[] args)
        {
            List<Customer> customerList = ReadInput();
            Dictionary<string, int> dict = PrepareSortedDrinkDictionary(customerList);
            ServeCustomer(customerList, dict);
            Console.ReadKey();
        }

        private static void ServeCustomer(List<Customer> customerList, Dictionary<string, int> dict)
        {
            var minimumDrinkHashSet = new HashSet<string>();
            foreach (var element in dict)
            {
                foreach (var c in customerList)
                {
                    if (c.IsSatified == false && c.DrinkList.Contains(element.Key))
                    {
                        c.IsSatified = true;
                        minimumDrinkHashSet.Add(element.Key);
                        Console.WriteLine("Answer: " + c.CustomerId + " Drinks " + element.Key);
                    }

                    if (customerList.Any(x => x.IsSatified == false) == false)
                        break;
                }

                if (customerList.Any(x => x.IsSatified == false) == false)
                    break;
            }

            Console.WriteLine("Minimum drinks needed to serve all customers = " + minimumDrinkHashSet.Count);
        }

        private static Dictionary<string, int> PrepareSortedDrinkDictionary(List<Customer> customerList)
        {
            Dictionary<string, int> dict = new Dictionary<string, int>();
            foreach (var c in customerList)
            {
                foreach (var drink in c.DrinkList)
                {
                    if (dict.ContainsKey(drink))
                    {
                        dict[drink]++;
                    }
                    else dict.Add(drink, 1);
                }
            }

            dict = dict.OrderByDescending(x => x.Value).ToDictionary(x => x.Key, x => x.Value);

            return dict;
        }

        private static List<Customer> ReadInput()
        {
            List<Customer> list = new List<Customer>();
            string input = null;
            do
            {
                input = Console.ReadLine();
                if (string.IsNullOrEmpty(input) == false)
                {
                    var v = input.Split(',').ToList();
                    Customer c = new Customer { CustomerId = v[0] };
                    c.DrinkList.AddRange(v.GetRange(1, v.Count - 1));

                    list.Add(c);
                }

            } while (!string.IsNullOrEmpty(input));

            return list;
        }
    }

    class Customer
    {
        public string CustomerId { get; set; }
        public List<string> DrinkList = new List<string>();
        public bool IsSatified { get; set; }
    }
}

- Rajdeep July 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package awesome;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;

public class LazyBarTenderProblem {
static ArrayList<Integer> leastDrinksArray = new ArrayList<Integer>();
static HashMap<Integer, ArrayList<Character>> map2 = new HashMap<Integer, ArrayList<Character>>();
static HashMap<Integer, ArrayList<Character>> resultMap = new HashMap<Integer, ArrayList<Character>>();

private static void findLeastDrinksToBeSold(HashMap<Character, ArrayList<Integer>> map) {

HashMap<Integer, ArrayList<Character>> map1 = new HashMap<Integer, ArrayList<Character>>();

Set<Entry<Character, ArrayList<Integer>>> entrySet = map.entrySet();
for (Entry<Character, ArrayList<Integer>> entry : entrySet)
{
ArrayList<Integer> value = entry.getValue();
for (Integer integer : value)
{
ArrayList<Character> arrayList = map1.get(integer);
if (arrayList == null)
{
arrayList = new ArrayList<Character>();
}
arrayList.add(entry.getKey());
map1.put(integer, arrayList);
}
}
System.out.println(map1);
getMaxLenValues(map1);

System.out.println("The Least required number of Drinks required are:");
Set<Entry<Integer, ArrayList<Character>>> entrySet1 = resultMap.entrySet();
for (Entry<Integer, ArrayList<Character>> entry : entrySet1) // removal
{
if (!entry.getValue().isEmpty())
System.out.println(entry.getKey()+"="+entry.getValue());
}
}

private static HashMap<Integer, ArrayList<Character>> getMaxLenValues(HashMap<Integer, ArrayList<Character>> map1) {

while (!map1.isEmpty()) {
Integer drink = getMaxCustomer(map1);

ArrayList<Character> customers = map1.get(drink);
resultMap.put(drink, customers);
map1.remove(drink);

Set<Entry<Integer, ArrayList<Character>>> entrySet2 = map1.entrySet();

for (Entry<Integer, ArrayList<Character>> entry : entrySet2) // removal
{
ArrayList<Character> temCustomers = entry.getValue();
for (Character character : customers) {
if (temCustomers.contains(character)) {
temCustomers.remove(character);
}
}
}
}
return resultMap;
}

private static Integer getMaxCustomer(HashMap<Integer, ArrayList<Character>> map1) {
Integer drinkMax = 0;
Set<Entry<Integer, ArrayList<Character>>> entrySet = map1.entrySet();
for (Entry<Integer, ArrayList<Character>> entry : entrySet) {
if (drinkMax == 0) {
drinkMax = entry.getKey();
}
if (entry.getValue().size() > drinkMax) {
drinkMax = entry.getKey();
}
}
return drinkMax;
}

public static void main(String[] args) {
HashMap<Character, ArrayList<Integer>> map = new HashMap<Character, ArrayList<Integer>>();
ArrayList<Integer> choice1 = new ArrayList<Integer>();
choice1.add(1);
choice1.add(2);
choice1.add(3);
ArrayList<Integer> choice2 = new ArrayList<Integer>();
choice2.add(2);
choice2.add(4);
ArrayList<Integer> choice3 = new ArrayList<Integer>();
choice3.add(3);
// choice3.add(2);
choice3.add(4);
ArrayList<Integer> choice4 = new ArrayList<Integer>();
choice4.add(4);
choice4.add(5);
// choice4.add(5);
ArrayList<Integer> choice5 = new ArrayList<Integer>();
choice5.add(5);
choice5.add(6);
// choice5.add(4);
map.put('a', choice1);
map.put('b', choice2);
map.put('c', choice3);
map.put('d', choice4);
map.put('e', choice5);

findLeastDrinksToBeSold(map);
}

}

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

package awesome;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;

public class LazyBarTenderProblem {
	static ArrayList<Integer> leastDrinksArray = new ArrayList<Integer>();
	static HashMap<Integer, ArrayList<Character>> map2 = new HashMap<Integer, ArrayList<Character>>();
	static HashMap<Integer, ArrayList<Character>> resultMap = new HashMap<Integer, ArrayList<Character>>();

	private static void findLeastDrinksToBeSold(HashMap<Character, ArrayList<Integer>> map) {

		HashMap<Integer, ArrayList<Character>> map1 = new HashMap<Integer, ArrayList<Character>>();

		Set<Entry<Character, ArrayList<Integer>>> entrySet = map.entrySet();
		for (Entry<Character, ArrayList<Integer>> entry : entrySet)
		{
			ArrayList<Integer> value = entry.getValue();
			for (Integer integer : value) 
			{
				ArrayList<Character> arrayList = map1.get(integer);
				if (arrayList == null) 
				{
					arrayList = new ArrayList<Character>();
				}
				arrayList.add(entry.getKey());
				map1.put(integer, arrayList);
			}
		}
		System.out.println(map1);
		getMaxLenValues(map1);

		System.out.println("The Least required number of Drinks required are:");
		Set<Entry<Integer, ArrayList<Character>>> entrySet1 = resultMap.entrySet();
		for (Entry<Integer, ArrayList<Character>> entry : entrySet1) // removal
		{
			if (!entry.getValue().isEmpty())
				System.out.println(entry.getKey()+"="+entry.getValue());
		}
	}

	private static HashMap<Integer, ArrayList<Character>> getMaxLenValues(HashMap<Integer, ArrayList<Character>> map1) {

		while (!map1.isEmpty()) {
			Integer drink = getMaxCustomer(map1);

			ArrayList<Character> customers = map1.get(drink);
			resultMap.put(drink, customers);
			map1.remove(drink);

			Set<Entry<Integer, ArrayList<Character>>> entrySet2 = map1.entrySet();

			for (Entry<Integer, ArrayList<Character>> entry : entrySet2) // removal
			{
				ArrayList<Character> temCustomers = entry.getValue();
				for (Character character : customers) {
					if (temCustomers.contains(character)) {
						temCustomers.remove(character);
					}
				}
			}
		}
		return resultMap;
	}

	private static Integer getMaxCustomer(HashMap<Integer, ArrayList<Character>> map1) {
		Integer drinkMax = 0;
		Set<Entry<Integer, ArrayList<Character>>> entrySet = map1.entrySet();
		for (Entry<Integer, ArrayList<Character>> entry : entrySet) {
			if (drinkMax == 0) {
				drinkMax = entry.getKey();
			}
			if (entry.getValue().size() > drinkMax) {
				drinkMax = entry.getKey();
			}
		}
		return drinkMax;
	}

	public static void main(String[] args) {
		HashMap<Character, ArrayList<Integer>> map = new HashMap<Character, ArrayList<Integer>>();
		ArrayList<Integer> choice1 = new ArrayList<Integer>();
		choice1.add(1);
		choice1.add(2);
		choice1.add(3);
		ArrayList<Integer> choice2 = new ArrayList<Integer>();
		choice2.add(2);
		choice2.add(4);
		ArrayList<Integer> choice3 = new ArrayList<Integer>();
		choice3.add(3);
		// choice3.add(2);
		choice3.add(4);
		ArrayList<Integer> choice4 = new ArrayList<Integer>();
		choice4.add(4);
		choice4.add(5);
		// choice4.add(5);
		ArrayList<Integer> choice5 = new ArrayList<Integer>();
		choice5.add(5);
		choice5.add(6);
		// choice5.add(4);
		map.put('a', choice1);
		map.put('b', choice2);
		map.put('c', choice3);
		map.put('d', choice4);
		map.put('e', choice5);

		findLeastDrinksToBeSold(map);
	}

}

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

package awesome;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;

public class LazyBarTenderProblem{
	static ArrayList<Integer> leastDrinksArray = new ArrayList<Integer>();
	static HashMap<Integer, ArrayList<Character>> map2 = new HashMap<Integer, ArrayList<Character>>();
	static HashMap<Integer, ArrayList<Character>> resultMap = new HashMap<Integer, ArrayList<Character>>();

	private static void findLeastDrinksToBeSold(HashMap<Character, ArrayList<Integer>> map) {

		HashMap<Integer, ArrayList<Character>> map1 = new HashMap<Integer, ArrayList<Character>>();

		Set<Entry<Character, ArrayList<Integer>>> entrySet = map.entrySet();
		for (Entry<Character, ArrayList<Integer>> entry : entrySet)
		{
			ArrayList<Integer> value = entry.getValue();
			for (Integer integer : value) 
			{
				ArrayList<Character> arrayList = map1.get(integer);
				if (arrayList == null) 
				{
					arrayList = new ArrayList<Character>();
				}
				arrayList.add(entry.getKey());
				map1.put(integer, arrayList);
			}
		}
		System.out.println(map1);
		getMaxLenValues(map1);

		System.out.println("The Least required number of Drinks required are:");
		Set<Entry<Integer, ArrayList<Character>>> entrySet1 = resultMap.entrySet();
		for (Entry<Integer, ArrayList<Character>> entry : entrySet1) // removal
		{
			if (!entry.getValue().isEmpty())
				System.out.println(entry.getKey()+"="+entry.getValue());
		}
	}

	private static HashMap<Integer, ArrayList<Character>> getMaxLenValues(HashMap<Integer, ArrayList<Character>> map1) {

		while (!map1.isEmpty()) {
			Integer drink = getMaxCustomer(map1);

			ArrayList<Character> customers = map1.get(drink);
			resultMap.put(drink, customers);
			map1.remove(drink);

			Set<Entry<Integer, ArrayList<Character>>> entrySet2 = map1.entrySet();

			for (Entry<Integer, ArrayList<Character>> entry : entrySet2) // removal
			{
				ArrayList<Character> temCustomers = entry.getValue();
				for (Character character : customers) {
					if (temCustomers.contains(character)) {
						temCustomers.remove(character);
					}
				}
			}
		}
		return resultMap;
	}

	private static Integer getMaxCustomer(HashMap<Integer, ArrayList<Character>> map1) {
		Integer drinkMax = 0;
		Set<Entry<Integer, ArrayList<Character>>> entrySet = map1.entrySet();
		for (Entry<Integer, ArrayList<Character>> entry : entrySet) {
			if (drinkMax == 0) {
				drinkMax = entry.getKey();
			}
			if (entry.getValue().size() > drinkMax) {
				drinkMax = entry.getKey();
			}
		}
		return drinkMax;
	}

	public static void main(String[] args) {
		HashMap<Character, ArrayList<Integer>> map = new HashMap<Character, ArrayList<Integer>>();
		ArrayList<Integer> choice1 = new ArrayList<Integer>();
		choice1.add(1);
		choice1.add(2);
		choice1.add(3);
		ArrayList<Integer> choice2 = new ArrayList<Integer>();
		choice2.add(2);
		choice2.add(4);
		ArrayList<Integer> choice3 = new ArrayList<Integer>();
		choice3.add(3);
		// choice3.add(2);
		choice3.add(4);
		ArrayList<Integer> choice4 = new ArrayList<Integer>();
		choice4.add(4);
		choice4.add(5);
		// choice4.add(5);
		ArrayList<Integer> choice5 = new ArrayList<Integer>();
		choice5.add(5);
		choice5.add(6);
		// choice5.add(4);
		map.put('a', choice1);
		map.put('b', choice2);
		map.put('c', choice3);
		map.put('d', choice4);
		map.put('e', choice5);

		findLeastDrinksToBeSold(map);
	}

}

- Chinmay Joshi July 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class LazyBartender {

	static private final java.util.HashMap<String, DrinkCustomerBase> drinksCustomerBase =new java.util.HashMap<>();
	
	static private final Customer customers[] = { 
			new Customer("C1", new String[] { "n3", "n7", "n5", "n2", "n9" }),
			new Customer("C2", new String[] { "n5" }), 
			new Customer("C3", new String[] { "n2", "n3" }),
			new Customer("C4", new String[] { "n4" }),
			new Customer("C5", new String[] { "n3", "n4", "n5", "n7" }) };


	/*
	 * Helper class Customer
	 */
	public static class Customer {
		public final String name;
		public final java.util.HashSet<String> drinks = new java.util.HashSet<String>();

		Customer(String name, String[] drinks) {
			this.name = name;
			this.drinks.addAll(java.util.Arrays.asList(drinks) );
			for (String d:drinks) {
				DrinkCustomerBase dc = drinksCustomerBase.get(d);
				if (dc == null){
					dc = new DrinkCustomerBase(d);
					drinksCustomerBase.put(d, dc);
				}
				dc.customers.add(this);
			}
		}
		boolean hasDrink(String d) {
			return drinks.contains(d);
		}
	}

	/*
	 * Helper class DrinkCustomerBase: drink to customers relation
	 */
	public static class DrinkCustomerBase implements Comparable<DrinkCustomerBase> {
		public final String drink;
		public final java.util.HashSet<Customer> customers;

		public DrinkCustomerBase(String drink) {
			this.drink = drink;
			this.customers = new java.util.HashSet<Customer> ();
		}

		// compare by customer base, greater base first 
		@Override
		public int compareTo(DrinkCustomerBase dc) {
			return dc.customers.size() - this.customers.size();
		}
	}

	/*
	 * Brute-force combination n Choose k, k: 1..n, n: total number of unique drinks    
	 */
	static boolean checkCustomers(String drinks[]) {
		java.util.HashSet<Customer> customersSet = new java.util.HashSet<Customer>();
		for (Customer c: customers) {
			for (String d:drinks){
				if (c.hasDrink(d)){
					customersSet.add(c);
					if (customersSet.size() == customers.length)
						return true;
				}
			}			
		}
		return false;
	}

	/*
	 * n choose k
	 */
	static boolean drinksFound = false;
	static <T> void combinations(T arr[], T data[], int start, int end, int index, int r) {
		if (index == r) {
			if (!drinksFound && checkCustomers ((String[])data) ){				
				System.out.println(java.util.Arrays.asList(data));
				drinksFound = true;
			}
			return;
		}

		for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
			data[index] = arr[i];
			combinations(arr, data, i + 1, end, index + 1, r);
		}
	}
	
	/*
	 * BF. find first smallest set
	 */
	static void findDrinksBf () {
		
		String[] uniquedrinks = drinksCustomerBase.keySet().toArray(new String[0]);
		/*
		 * check combinations n:i
		 */
		for (int i = 1; i <= uniquedrinks.length; ++i){
	        String data[]=new String[i];
	        combinations(uniquedrinks, data, 0, uniquedrinks.length -1, 0, i);
	        if (drinksFound)
	        	break;
		}			
	}

	/*
	 * Find good enough for the lazy
	 */
	static void findGoodDrinkSet() {
		java.util.LinkedList<DrinkCustomerBase> drinkList = new java.util.LinkedList<>(drinksCustomerBase.values());
		drinkList.sort(null); // sort using DrinkCustomerBase.compareTo 
		
		java.util.HashSet<Customer> customerBase = new java.util.HashSet<>();
		java.util.HashSet<String> drinks = new java.util.HashSet<>();

		for (DrinkCustomerBase dc : drinkList) {
			for (Customer c : dc.customers) {
				if (!customerBase.contains(c)) {
					drinks.add(dc.drink);
					customerBase.add(c);
				}
			}
		}
		System.out.println(drinks.toString());		
	}
	
	public static void main(String[] arg) {
		findGoodDrinkSet();
		findDrinksBf();
	}

}

- vzyarko July 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Customer
		{
			public string CustomerId { get; set; }
			public List<string> DrinkList = new List<string>();
		}
		 
		static void Main(string[] args)
		{
			List<Customer> customers = new List<Customer>
			{
				new Customer() {CustomerId = "Cust1", DrinkList = {"n3", "n7", "n5", "n2", "n9"}},
				new Customer() {CustomerId = "Cust2", DrinkList = {"n5"}},
				new Customer() {CustomerId = "Cust3", DrinkList = {"n2", "n3"}},
				new Customer() {CustomerId = "Cust4", DrinkList = {"n4"}},
				new Customer() {CustomerId = "Cust5", DrinkList = {"n3", "n4", "n3", "n5", "n7", "n4"}},
			};
			Dictionary<string, string> mandatory = new Dictionary<string, string>();
			string validDrinks=String.Empty;
			List<string> allDrinks = new List<string>();
			for (int i =0; i < customers.Count; i++)
			{
				var cust = customers[i];
				if (cust.DrinkList.Count == 1)
				{
					mandatory.Add(cust.DrinkList[0],cust.CustomerId);
					validDrinks = validDrinks + cust.DrinkList[0] + ",";
				}
				else
				{
					foreach (var drink in cust.DrinkList)
					{
						if (mandatory.ContainsKey(drink))
						{
							continue;
						}
						bool isUnique = false;
						bool isCommon = false;
						List<string> common = new List<string>();
						List<string> Unique = new List<string>();
						for (int j = i + 1; j < customers.Count; j++)
						{
							var next = customers[j];
							if (next.DrinkList.Count > 1)
							{
								isUnique = !next.DrinkList.Contains(drink);
								isCommon = (next.DrinkList.Contains(drink));
								if (isCommon && !common.Contains(drink))
								{
									common.Add(drink);
								}
								if (isUnique && !Unique.Contains(drink))
								{
									Unique.Add(drink);
								}
								if (isUnique && common.Contains(drink))
								{
									common.Remove(drink);
									isUnique = false;
									isCommon = false;
								}
								if(isCommon && Unique.Contains(drink))
								{
									Unique.Remove(drink);
									isCommon = false;
									isUnique = false;
								}
							}
						}
						if (!allDrinks.Contains(drink))
						{
							allDrinks.Add(drink);
						}
						if ((isUnique && !mandatory.ContainsValue(cust.CustomerId)) && !allDrinks.Contains(drink) || (isCommon && !mandatory.ContainsKey(drink)))
						{
							mandatory.Add(drink, cust.CustomerId);
							validDrinks = validDrinks + drink + ",";
						}
					}
					
				}
				
			}
			Console.Write(string.Format("{0}({1})", mandatory.Count, validDrinks.TrimEnd(',')));
			Console.ReadKey();
		}

- Rashid Malik August 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**

Algorithm:
C -> NumberOfCustomers
N -> Max Number of Drinks
1. Create a Sort Order Matrix based on the frequencies O(C * N)
2. Sort each customer's favorites based on the Sort order matrix O(C * NlogN)
3. Add first elements of each to the set. O(C)
4. return the max of 1, size of set. O(1)

Also, handles a case where no customer/ some customers has any favorites.

All Values should start with 0.

*/


import java.util.*;
public class Solution {
	public int minDrinksToPrepare(int numberOfDrinks, int numberOfCustomers, ArrayList<Integer>[] favorites) {
		if(numberOfDrinks <= 1) {
			return Math.max(numberOfDrinks, 0);
		}

		HashSet<Integer> result = new HashSet<Integer>();
		int[] sortOrder = getSortOrder(favorites, numberOfDrinks);

		sortBasedOnOrder(favorites, sortOrder);

		getFirstElementsOfAll(favorites, result);

		return Math.max(1, result.size());
	}
	
	private void sortBasedOnOrder(ArrayList<Integer>[] favorites, int[] sortOrder) {
		for(int i = 0; i < favorites.length; i++) {
			Collections.sort(favorites[i], new OrderedSortComparator(sortOrder));
		}
	}
	
	class OrderedSortComparator implements Comparator<Integer> {
		int[] order;
		// We can also bring make this map as outer class variable and use the same instance,
		// instead of creating a new one everytime
		HashMap<Integer, Integer> map;
	
		OrderedSortComparator(int[] order) {
			this.order = order;
			map = new HashMap<Integer, Integer>();
			for(int i = 0; i < order.length; i++) {
				if(!map.containsKey(order[i])) {
					map.put(order[i], i);
				}
			}
		}
	
		public int compare(Integer a, Integer b) {
			if(!map.containsKey(a) && !map.containsKey(b)) {
				return (a > b) ? b : a;
			} else if(!map.containsKey(a)) {
				return b;
			} else if(!map.containsKey(b)) {
				return a;
			} else {
				return (map.get(a) <= map.get(b)) ? a : b;
			}
		}
	}
	
	private void getFirstElementsOfAll(ArrayList<Integer>[] favorites, HashSet<Integer> result) {
		for(int i = 0; i < favorites.length; i++) {
			for(int fav : favorites[i]) {
				result.add(fav);
				break;
			}
		}
	}
	
	private int[] getSortOrder(ArrayList<Integer>[] favorites, int numberOfDrinks) {
		int[] sortOrder = new int[numberOfDrinks];
		for(int i = 0; i < favorites.length; i++) {
			sortOrder[i] = 0;
		}
		
		for(int i = 0; i < favorites.length; i++) {
			for(int j : favorites[i]) {
				sortOrder[j]++;
			}
		}
		return sortOrder;
	}
}

Overall Time Complexity : O(C * NlogN)

- Harish September 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The problem above is an instance of Hitting Set (Derivation of Set Cover) Problem which is an NP-Complete problem.

- Experienced Coder October 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey. What's the difference with the Set cover problem ? Am I missing something ?

- kozv October 22, 2017 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class LazyBartender {

	public static void main(String[] args) {

		HashMap<String, Set<String>> custMap = new HashMap<String, Set<String>>();

		custMap.put("cust1", new HashSet<String>(Arrays.asList("n3", "n7", "n5", "n2", "n9")));
		custMap.put("cust2", new HashSet<String>(Arrays.asList("n5")));
		custMap.put("cust3", new HashSet<String>(Arrays.asList("n2", "n3")));
		custMap.put("cust4", new HashSet<String>(Arrays.asList("n4")));
		custMap.put("cust5", new HashSet<String>(Arrays.asList("n3", "n4", "n5", "n7")));

		System.out.println("total number of drinks required: " + countDrinks(custMap));
	}

	private static int countDrinks(HashMap custMap) {
		int count =0;
		HashMap<String, Set<String>> drinksMap = new HashMap<String, Set<String>>();
		HashMap<String,Integer> drinksvscustcount = new HashMap<String, Integer>();
		Iterator custvsdrinksIt = custMap.keySet().iterator();
		//Prepare drink map
		while(custvsdrinksIt.hasNext()){
			String customer = (String) custvsdrinksIt.next();
			Set<String> drinks = (Set<String>) custMap.get(customer);
			for (String drink : drinks) {
				if(drinksMap.containsKey(drink)){
					drinksMap.get(drink).add(customer);
				}else{
					Set<String> custs = new HashSet<String>();
					custs.add(customer);
					drinksMap.put(drink, custs);
				}
				drinksvscustcount.put(drink, drinksMap.get(drink).size());
			}
		}	
		Set<String> finalDrinks = new HashSet<String>();
		Set<String> finalCusts = new HashSet<String>();
		while(finalCusts.size() < custMap.size()){
			String drink = getDrinkWithMaxCustomers(drinksvscustcount);
			Set<String> custs = drinksMap.get(drink);
			for(String cust : custs){
				if(finalCusts.contains(cust)){
					continue;
				}else{
					finalDrinks.add(drink);
					finalCusts.add(cust);
				}
			}
			drinksvscustcount.remove(drink);
		}
		System.out.println("finalDrinks"+finalDrinks);
		return finalDrinks.size();
	}

	public static String getDrinkWithMaxCustomers(HashMap<String, Integer> drinksvscustcount){
		int maxCustomersForADrink = 0;
		String maxDrink = "";
		Set<String> drinks = drinksvscustcount.keySet();
		for(String drink : drinks){
			if(drinksvscustcount.get(drink) > maxCustomersForADrink){
				maxCustomersForADrink = drinksvscustcount.get(drink);
				maxDrink = drink;
			}
		}
		return maxDrink;
	}
}

- Nithin Reddy Gujjula February 01, 2018 | 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