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

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

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

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

For Rubyists:

``````# The method to find the least number of drinks

def least_drinks_serve_all(drink_schedule, drinks, customers)
array_for_elimination = Array.new(drinks){Array.new(customers + 1, 0)}
# Now making the array for elimination process
array_for_elimination.each_with_index do |row, i|
row.each_with_index do |col, j|
next unless drink_schedule[i] && drink_schedule[i][j]
index_of_drink = drink_schedule[i][j]
array_for_elimination[index_of_drink][i] = 1
end
end
# adding the total preference of each drink as last column
array_for_elimination.each_with_index do |row, i|
sum = 0
row.each_with_index do |col, j|
sum += array_for_elimination[i][j]
end
array_for_elimination[i][customers] = sum
end
customers_left = customers # counter for tracking the number of customers left to be served
least_drink_count = 0 # counter for least number of drinks to be served by the lazy tenderer
while customers_left > 0
index_to_eliminate = 0
row_max_val = 0
# loop through to find the row index with maximum sum
array_for_elimination.each_with_index do |row, i|
if array_for_elimination[i][customers] > row_max_val
row_max_val = array_for_elimination[i][customers]
index_to_eliminate = i
end
end
least_drink_count += 1 # we found one drink that serves maximum customers at the end of 1 iteration
customers_left -= row_max_val # we have served to row_max_val customers
# for to eliminate the counted drink with its customers
for i in 0..customers
if array_for_elimination[index_to_eliminate][i] == 1
array_for_elimination.each_with_index do |row, j|
if array_for_elimination[j][i] == 1
array_for_elimination[j][i] = 0
array_for_elimination[j][customers] -= 1
end
end
end
end
end
return least_drink_count
end``````

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

//			If topLevelCustomerSet does NOT have all the counted customers
if(!topLevelCustomerSet.containsAll(loopLevelCustomerSet)){
}
}

System.out.println(topLevelDrinksSet);
}``````

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;

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

}
}
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))
{
stat = true;
}
}
if (stat)
}
}

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

}
}
}``````

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

Time complexity of your solution is O(n3).

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

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

}``````

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.

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

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;
/*
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)
{
Dictionary<string, int> dict = PrepareSortedDrinkDictionary(customerList);
ServeCustomer(customerList, dict);
}

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

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

return dict;
}

{
List<Customer> list = new List<Customer>();
string input = null;
do
{
if (string.IsNullOrEmpty(input) == false)
{
var v = input.Split(',').ToList();
Customer c = new Customer { CustomerId = v[0] };

}

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

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;
/*
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)
{
Dictionary<string, int> dict = PrepareSortedDrinkDictionary(customerList);
ServeCustomer(customerList, dict);
}

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

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

return dict;
}

{
List<Customer> list = new List<Customer>();
string input = null;
do
{
if (string.IsNullOrEmpty(input) == false)
{
var v = input.Split(',').ToList();
Customer c = new Customer { CustomerId = v[0] };

}

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

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>();
}
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>();
ArrayList<Integer> choice2 = new ArrayList<Integer>();
ArrayList<Integer> choice3 = new ArrayList<Integer>();
ArrayList<Integer> choice4 = new ArrayList<Integer>();
ArrayList<Integer> choice5 = new ArrayList<Integer>();
map.put('a', choice1);
map.put('b', choice2);
map.put('c', choice3);
map.put('d', choice4);
map.put('e', choice5);

findLeastDrinksToBeSold(map);
}

}

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>();
}
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>();
ArrayList<Integer> choice2 = new ArrayList<Integer>();
ArrayList<Integer> choice3 = new ArrayList<Integer>();
ArrayList<Integer> choice4 = new ArrayList<Integer>();
ArrayList<Integer> choice5 = new ArrayList<Integer>();
map.put('a', choice1);
map.put('b', choice2);
map.put('c', choice3);
map.put('d', choice4);
map.put('e', choice5);

findLeastDrinksToBeSold(map);
}

}``````

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>();
}
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>();
ArrayList<Integer> choice2 = new ArrayList<Integer>();
ArrayList<Integer> choice3 = new ArrayList<Integer>();
ArrayList<Integer> choice4 = new ArrayList<Integer>();
ArrayList<Integer> choice5 = new ArrayList<Integer>();
map.put('a', choice1);
map.put('b', choice2);
map.put('c', choice3);
map.put('d', choice4);
map.put('e', choice5);

findLeastDrinksToBeSold(map);
}

}``````

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;
for (String d:drinks) {
DrinkCustomerBase dc = drinksCustomerBase.get(d);
if (dc == null){
dc = new DrinkCustomerBase(d);
drinksCustomerBase.put(d, dc);
}
}
}
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[]) {
for (Customer c: customers) {
for (String d:drinks){
if (c.hasDrink(d)){
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() {
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)) {
}
}
}
System.out.println(drinks.toString());
}

public static void main(String[] arg) {
findGoodDrinkSet();
findDrinksBf();
}

}``````

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)
{
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))
{
}
if (isUnique && !Unique.Contains(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))
{
}
if ((isUnique && !mandatory.ContainsValue(cust.CustomerId)) && !allDrinks.Contains(drink) || (isCommon && !mandatory.ContainsKey(drink)))
{
validDrinks = validDrinks + drink + ",";
}
}

}

}
Console.Write(string.Format("{0}({1})", mandatory.Count, validDrinks.TrimEnd(',')));
}``````

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.

*/

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

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.

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

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

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)){
}else{
Set<String> custs = new HashSet<String>();
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{
}
}
drinksvscustcount.remove(drink);
}
System.out.println("finalDrinks"+finalDrinks);
return finalDrinks.size();
}

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

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

``````# The method to find the least number of drinks

def least_drinks_serve_all(drink_schedule, drinks, customers)
array_for_elimination = Array.new(drinks){Array.new(customers + 1, 0)}
# Now making the array for elimination process
array_for_elimination.each_with_index do |row, i|
row.each_with_index do |col, j|
next unless drink_schedule[i] && drink_schedule[i][j]
index_of_drink = drink_schedule[i][j]
array_for_elimination[index_of_drink][i] = 1
end
end
# adding the total preference of each drink as last column
array_for_elimination.each_with_index do |row, i|
sum = 0
row.each_with_index do |col, j|
sum += array_for_elimination[i][j]
end
array_for_elimination[i][customers] = sum
end
customers_left = customers # counter for tracking the number of customers left to be served
least_drink_count = 0 # counter for least number of drinks to be served by the lazy tenderer
while customers_left > 0
index_to_eliminate = 0
row_max_val = 0
# loop through to find the row index with maximum sum
array_for_elimination.each_with_index do |row, i|
if array_for_elimination[i][customers] > row_max_val
row_max_val = array_for_elimination[i][customers]
index_to_eliminate = i
end
end
least_drink_count += 1 # we found one drink that serves maximum customers at the end of 1 iteration
customers_left -= row_max_val # we have served to row_max_val customers
# for to eliminate the counted drink with its customers
for i in 0..customers
if array_for_elimination[index_to_eliminate][i] == 1
array_for_elimination.each_with_index do |row, j|
if array_for_elimination[j][i] == 1
array_for_elimination[j][i] = 0
array_for_elimination[j][customers] -= 1
end
end
end
end
end
return least_drink_count
end``````

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

# The method to find the least number of drinks

def least_drinks_serve_all(drink_schedule, drinks, customers)
array_for_elimination = Array.new(drinks){Array.new(customers + 1, 0)}
# Now making the array for elimination process
array_for_elimination.each_with_index do |row, i|
row.each_with_index do |col, j|
next unless drink_schedule[i] && drink_schedule[i][j]
index_of_drink = drink_schedule[i][j]
array_for_elimination[index_of_drink][i] = 1
end
end
# adding the total preference of each drink as last column
array_for_elimination.each_with_index do |row, i|
sum = 0
row.each_with_index do |col, j|
sum += array_for_elimination[i][j]
end
array_for_elimination[i][customers] = sum
end
customers_left = customers # counter for tracking the number of customers left to be served
least_drink_count = 0 # counter for least number of drinks to be served by the lazy tenderer
while customers_left > 0
index_to_eliminate = 0
row_max_val = 0
# loop through to find the row index with maximum sum
array_for_elimination.each_with_index do |row, i|
if array_for_elimination[i][customers] > row_max_val
row_max_val = array_for_elimination[i][customers]
index_to_eliminate = i
end
end
least_drink_count += 1 # we found one drink that serves maximum customers at the end of 1 iteration
customers_left -= row_max_val # we have served to row_max_val customers
# for to eliminate the counted drink with its customers
for i in 0..customers
if array_for_elimination[index_to_eliminate][i] == 1
array_for_elimination.each_with_index do |row, j|
if array_for_elimination[j][i] == 1
array_for_elimination[j][i] = 0
array_for_elimination[j][customers] -= 1
end
end
end
end
end
return least_drink_count
end

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

```
# Lazy Bar tenderer code
# A bar has m type of drinks and has n customers having
# their personal preference of drinks known
# This is represented by a 2D array represented
# as the rows represent each customer and columns as their preferred drinks type
# We have a lazy bar tenderer who would like to make(or even learn) the least number of
# drinks so as to serve the customers their choice of drinks
# we have the array, m the number of drink types, and n the number of customers as the input
# we as supposed to give the least count of drinks the bar tenderer needs to make as 'count'
#
# Sample input

array = [
[0, 1, 3, 6],
[1, 4, 7],
[2, 4, 7, 5],
[3, 2, 5],
[5, 8]
]

n = 5
m = 9

# Sample output should be count = 2 (the drink number 5 and 1)
#

# We will make an array of m rows each representing the drink type number
# and n+1 columns where n columns are for customers with preference represented as
# binary value either 0 or 1
# and the +1 column for the sum of preferences for each drink row
#
# The arr for sample input is
#
# 0 1 2 3 4 Sum
#
# 0 1 0 0 0 0 1
# 1 1 1 0 0 0 2
# 2 0 0 1 1 0 2
# 3 1 0 0 1 0 2
# 4 0 1 1 0 0 2
# 5 0 0 1 1 1 3
# 6 1 0 0 0 0 1
# 7 0 1 1 0 0 2
# 8 0 0 0 0 1 1
#
# We will find the max value of sum ie the most preferred drink, so naturally the bar tenderer
# needs to know how to make it
# So we can eliminate the drink with the customers whom we can serve with the drink
# Now just increment the count variable count++
# and shortlist the array as below
#
# 0 1 Sum
#
# 0 1 0 1
# 1 1 1 2
# 2 0 0 0
# 3 1 0 1
# 4 0 1 1
# 6 1 0 1
# 7 0 1 1
# 8 0 0 0
#
# Now you may need to select the drink with maxim preference and
# go on...until all of the customers are served
# ie, till the array is empty or customers left is zero
# For the example thats it ... all are served with the two drinks, drinks 5 and 1
# Now lets go to the codes for that....
#
# The method to find the least number of drinks

def least_drinks_serve_all(drink_schedule, drinks, customers)
array_for_elimination = Array.new(drinks){Array.new(customers + 1, 0)}
# Now making the array for elimination process
array_for_elimination.each_with_index do |row, i|
row.each_with_index do |col, j|
next unless drink_schedule[i] && drink_schedule[i][j]
index_of_drink = drink_schedule[i][j]
array_for_elimination[index_of_drink][i] = 1
end
end
# adding the total preference of each drink as last column
array_for_elimination.each_with_index do |row, i|
sum = 0
row.each_with_index do |col, j|
sum += array_for_elimination[i][j]
end
array_for_elimination[i][customers] = sum
end
customers_left = customers # counter for tracking the number of customers left to be served
least_drink_count = 0 # counter for least number of drinks to be served by the lazy tenderer
while customers_left > 0
index_to_eliminate = 0
row_max_val = 0
# loop through to find the row index with maximum sum
array_for_elimination.each_with_index do |row, i|
if array_for_elimination[i][customers] > row_max_val
row_max_val = array_for_elimination[i][customers]
index_to_eliminate = i
end
end
least_drink_count += 1 # we found one drink that serves maximum customers at the end of 1 iteration
customers_left -= row_max_val # we have served to row_max_val customers
# for to eliminate the counted drink with its customers
for i in 0..customers
if array_for_elimination[index_to_eliminate][i] == 1
array_for_elimination.each_with_index do |row, j|
if array_for_elimination[j][i] == 1
array_for_elimination[j][i] = 0
array_for_elimination[j][customers] -= 1
end
end
end
end
end
return least_drink_count
end
```

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

``````# Lazy Bar tenderer code
# A bar has m type of drinks and has n customers having
# their personal preference of drinks known
# This is represented by a 2D array represented
# as the rows represent each customer and columns as their preferred drinks type
# We have a lazy bar tenderer who would like to make(or even learn) the least number of
# drinks so as to serve the customers their choice of drinks
# we have the array, m the number of drink types, and n the number of customers as the input
# we as supposed to give the least count of drinks the bar tenderer needs to make as 'count'
#
# Sample input

array = [
[0, 1, 3, 6],
[1, 4, 7],
[2, 4, 7, 5],
[3, 2, 5],
[5, 8]
]

n = 5
m = 9

# Sample output should be count = 2 (the drink number 5 and 1)
#

# We will make an array of m rows each representing the drink type number
# and n+1 columns where n columns are for customers with preference represented as
# binary value either 0 or 1
# and the +1 column for the sum of preferences for each drink row
#
# The arr for sample input is
#
# 		0	1	2	3	4	Sum
#
# 0		1	0	0	0	0	1
# 1		1	1	0	0	0	2
# 2		0	0	1	1	0	2
# 3		1	0	0	1	0	2
# 4		0	1	1	0	0	2
# 5		0	0	1	1	1	3
# 6		1	0	0	0	0	1
# 7		0	1	1	0	0	2
# 8		0	0	0	0	1	1
#
# We will find the max value of sum ie the most preferred drink, so naturally the bar tenderer
# needs to know how to make it
# So we can eliminate the drink with the customers whom we can serve with the drink
# Now just increment the count variable count++
# and shortlist the array as below
#
# 		0	1	Sum
#
# 0		1	0	1
# 1		1	1	2
# 2		0	0	0
# 3		1	0	1
# 4		0	1	1
# 6		1	0	1
# 7		0	1	1
# 8		0	0	0
#
# Now you may need to select the drink with maxim preference and
# go on...until all of the customers are served
# ie, till the array is empty or customers left is zero
# For the example thats it ... all are served with the two drinks, drinks 5 and 1
# Now lets go to the codes for that....
#
# The method to find the least number of drinks

def least_drinks_serve_all(drink_schedule, drinks, customers)
array_for_elimination = Array.new(drinks){Array.new(customers + 1, 0)}
# Now making the array for elimination process
array_for_elimination.each_with_index do |row, i|
row.each_with_index do |col, j|
next unless drink_schedule[i] && drink_schedule[i][j]
index_of_drink = drink_schedule[i][j]
array_for_elimination[index_of_drink][i] = 1
end
end
# adding the total preference of each drink as last column
array_for_elimination.each_with_index do |row, i|
sum = 0
row.each_with_index do |col, j|
sum += array_for_elimination[i][j]
end
array_for_elimination[i][customers] = sum
end
customers_left = customers # counter for tracking the number of customers left to be served
least_drink_count = 0 # counter for least number of drinks to be served by the lazy tenderer
while customers_left > 0
index_to_eliminate = 0
row_max_val = 0
# loop through to find the row index with maximum sum
array_for_elimination.each_with_index do |row, i|
if array_for_elimination[i][customers] > row_max_val
row_max_val = array_for_elimination[i][customers]
index_to_eliminate = i
end
end
least_drink_count += 1 # we found one drink that serves maximum customers at the end of 1 iteration
customers_left -= row_max_val # we have served to row_max_val customers
# for to eliminate the counted drink with its customers
for i in 0..customers
if array_for_elimination[index_to_eliminate][i] == 1
array_for_elimination.each_with_index do |row, j|
if array_for_elimination[j][i] == 1
array_for_elimination[j][i] = 0
array_for_elimination[j][customers] -= 1
end
end
end
end
end
return least_drink_count
end``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.