Google Interview Question Software Engineer / Developers
Team: Bing
Country: United States
Interview Type: In-Person
This returns just one bundle. You can extend this to return all bundles.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class BestBundle {
public List<Bundle> bestBundle(List<Bundle> bundles,
List<String> itemsToBuy, List<Bundle> bundlesBought) {
if (itemsToBuy.isEmpty()) {
return bundlesBought;
}
String firstItem = itemsToBuy.get(0);
List<Bundle> bundlesWithItem0 = getBundleWithItem(bundles, firstItem);
double minPrice = Double.MAX_VALUE;
List<Bundle> bestBundles = null;
for (Bundle b : bundlesWithItem0) {
List<String> itemsToBuyCopy = new ArrayList<String>(itemsToBuy);
for (String s : b.items) {
itemsToBuyCopy.remove(s);
}
List<Bundle> bundlesBoughtCopy = new ArrayList<Bundle>(
bundlesBought);
bundlesBoughtCopy.add(b);
List<Bundle> bundlesBoughtR = bestBundle(bundles, itemsToBuyCopy,
bundlesBoughtCopy);
double price = getPrice(bundlesBoughtR);
if (price < minPrice) {
minPrice = price;
bestBundles = bundlesBoughtR;
}
}
return bestBundles;
}
private double getPrice(List<Bundle> bundlesBoughtCopy) {
double price = 0;
for (Bundle bundle : bundlesBoughtCopy) {
price += bundle.price;
}
return price;
}
private List<Bundle> getBundleWithItem(List<Bundle> bundles,
String firstItem) {
List<Bundle> bundlesWithItems = new ArrayList<BestBundle.Bundle>();
for (Bundle bundle : bundles) {
if (bundle.items.contains(firstItem)) {
bundlesWithItems.add(bundle);
}
}
return bundlesWithItems;
}
private static final class Bundle {
private List<String> items;
private int sNo;
private double price;
@Override
public String toString() {
return "Bundle [items=" + items + ", sNo=" + sNo + ", price="
+ price + "]";
}
}
public static void main(String[] args) {
BestBundle bestBundle = new BestBundle();
// 1. 5 | Burger
// 2. 4 | French_Frice
// 3. 8 | Coldrink
// 4. 12 | Burger, French_Frice, Coldrink
// 5. 14 | Burger, Coldrink
Bundle bundle1 = getBundle(1, 5, Arrays.asList("B"));
Bundle bundle2 = getBundle(2, 4, Arrays.asList("FF"));
Bundle bundle3 = getBundle(3, 8, Arrays.asList("C"));
Bundle bundle4 = getBundle(4, 12, Arrays.asList("B", "FF", "C"));
Bundle bundle5 = getBundle(5, 14, Arrays.asList("B", "C"));
List<Bundle> bundles = Arrays.asList(bundle1, bundle2, bundle3,
bundle4, bundle5);
List<String> itemsToBuy = Arrays.asList("C");
System.out.println(bestBundle.bestBundle(bundles, itemsToBuy,
new ArrayList<BestBundle.Bundle>()));
}
private static Bundle getBundle(int sNo, int price, List<String> asList) {
Bundle bundle = new Bundle();
bundle.sNo = sNo;
bundle.price = price;
bundle.items = asList;
return bundle;
}
}
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
/**
*
*/
public class BestBundle {
private Map<String, Item> items = new HashMap<>();
private Set<Bundle> bundles = new HashSet<>();
private class Bundle {
private int[] id;
private Set<String> items;
private Double price;
@Override
public String toString() {
return "Bundle [id=" + Arrays.toString(id) + ", items=" + items + ", price=" + price + "]";
}
}
private class Item {
private String desc;
private Double price;
private int id;
@Override
public String toString() {
return "Item [desc=" + desc + ", price=" + price + ", id=" + id + "]";
}
}
public int[] bestOne(String[] inventory, String toBuy) {
// build data
for (String itemOrBundle : inventory) {
if (isBundle(itemOrBundle)) {
bundles.add(toBundle(itemOrBundle));
} else {
Item newItem = toItem(itemOrBundle);
items.put(newItem.desc, newItem);
}
}
// build virtual bundle
Bundle virtualBundle = new Bundle();
String[] itemsToBuy = toBuy.split(",");
virtualBundle.id = new int[itemsToBuy.length];
virtualBundle.items = new HashSet<>();
double price = 0;
int i = 0;
for (String itemToBuy : itemsToBuy) {
Item itb = items.get(itemToBuy);
virtualBundle.id[i++] = itb.id;
price += itb.price;
virtualBundle.items.add(itemToBuy);
}
virtualBundle.price = price;
bundles.add(virtualBundle);
Bundle bestBundle = null;
double minPrice = Double.MAX_VALUE;
outer: for (Bundle bundle : bundles) {
for (String itemToBuy : itemsToBuy) {
if (!bundle.items.contains(itemToBuy)) {
break outer;
}
}
if (bundle.price < minPrice) {
minPrice = bundle.price;
bestBundle = bundle;
}
}
// System.out.println(bundles);
// System.out.println(items);
return bestBundle.id;
}
/**
* parses "1 5 Burger"
*/
private Item toItem(String item) {
Item newItem = new Item();
Scanner s = new Scanner(item);
newItem.id = s.nextInt();
newItem.price = s.nextDouble();
newItem.desc = s.next();
s.close();
return newItem;
}
/**
* parses "4 12 Burger,French_Frice,Coldrink"
*/
private Bundle toBundle(String bundle) {
Bundle newBundle = new Bundle();
Scanner s = new Scanner(bundle);
newBundle.id = new int[] { s.nextInt() };
newBundle.price = s.nextDouble();
String[] items = s.next().split(",");
s.close();
newBundle.items = new HashSet<>();
for (String item : items) {
newBundle.items.add(item);
}
return newBundle;
}
private boolean isBundle(String item) {
return item.indexOf(',') >= 0;
}
public static void main(String[] args) {
BestBundle bb = new BestBundle();
int[] bestOnes = bb.bestOne(new String[] { "1 5 Burger", "2 4 French_Frice", "3 8 Coldrink", "4 12 Burger,French_Frice,Coldrink",
"5 14 Burger,Coldrink" }, "Burger,French_Frice");
System.out.println(Arrays.toString(bestOnes));
}
}
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
/**
*
*/
public class BestBundle {
private Map<String, Item> items = new HashMap<>();
private Set<Bundle> bundles = new HashSet<>();
private class Bundle {
private int[] id;
private Set<String> items;
private Double price;
@Override
public String toString() {
return "Bundle [id=" + Arrays.toString(id) + ", items=" + items + ", price=" + price + "]";
}
}
private class Item {
private String desc;
private Double price;
private int id;
@Override
public String toString() {
return "Item [desc=" + desc + ", price=" + price + ", id=" + id + "]";
}
}
public int[] bestOne(String[] inventory, String toBuy) {
// build data
for (String itemOrBundle : inventory) {
if (isBundle(itemOrBundle)) {
bundles.add(toBundle(itemOrBundle));
} else {
Item newItem = toItem(itemOrBundle);
items.put(newItem.desc, newItem);
}
}
// build virtual bundle
Bundle virtualBundle = new Bundle();
String[] itemsToBuy = toBuy.split(",");
virtualBundle.id = new int[itemsToBuy.length];
virtualBundle.items = new HashSet<>();
double price = 0;
int i = 0;
for (String itemToBuy : itemsToBuy) {
Item itb = items.get(itemToBuy);
virtualBundle.id[i++] = itb.id;
price += itb.price;
virtualBundle.items.add(itemToBuy);
}
virtualBundle.price = price;
bundles.add(virtualBundle);
Bundle bestBundle = null;
double minPrice = Double.MAX_VALUE;
outer: for (Bundle bundle : bundles) {
for (String itemToBuy : itemsToBuy) {
if (!bundle.items.contains(itemToBuy)) {
break outer;
}
}
if (bundle.price < minPrice) {
minPrice = bundle.price;
bestBundle = bundle;
}
}
// System.out.println(bundles);
// System.out.println(items);
return bestBundle.id;
}
/**
* parses "1 5 Burger"
*/
private Item toItem(String item) {
Item newItem = new Item();
Scanner s = new Scanner(item);
newItem.id = s.nextInt();
newItem.price = s.nextDouble();
newItem.desc = s.next();
s.close();
return newItem;
}
/**
* parses "4 12 Burger,French_Frice,Coldrink"
*/
private Bundle toBundle(String bundle) {
Bundle newBundle = new Bundle();
Scanner s = new Scanner(bundle);
newBundle.id = new int[] { s.nextInt() };
newBundle.price = s.nextDouble();
String[] items = s.next().split(",");
s.close();
newBundle.items = new HashSet<>();
for (String item : items) {
newBundle.items.add(item);
}
return newBundle;
}
private boolean isBundle(String item) {
return item.indexOf(',') >= 0;
}
public static void main(String[] args) {
BestBundle bb = new BestBundle();
int[] bestOnes = bb.bestOne(new String[] { "1 5 Burger", "2 4 French_Frice", "3 8 Coldrink", "4 12 Burger,French_Frice,Coldrink",
"5 14 Burger,Coldrink" }, "Burger,French_Frice");
System.out.println(Arrays.toString(bestOnes));
}
}
Just a random thought, not yet tried to code:
If we consider this as bitwise numbers for the given example, the problem reduces to the following table:
Price : 5 4 8 12 14
Combo : 4 2 1 7 5
where Combo is of bits [BFC]
For example, if combo value is 5, meaning the price corresponds to B+C
Now suppose we are looking to minimize BF - that means we are looking for all the subsets with sum is atleast 6 and the answer would be minimum of the elements of all the subsets whose sum >= 6.
public class CheapShopping {
public static void main(String[] args) {
Map<String, Integer> prices = new HashMap<String, Integer>();
prices.put("1.Burger", 5);
prices.put("2.French_Frice", 4);
prices.put("3.Coldrink", 8);
prices.put("4.Burger, French_Frice, Coldrink", 12);
prices.put("5.Burger, Coldrink", 14);
System.out.println(calculateCheapest(prices,
new String[] { "Burger", "Coldrink" }));
System.out.println(calculateCheapest(prices,
new String[] { "Burger", "French_Frice" }));
System.out.println(calculateCheapest(prices,
new String[] { "Coldrink" }));
}
private static String calculateCheapest(Map<String, Integer> prices,
String[] toBuy) {
String pack = "";
int minPrice = Integer.MAX_VALUE;
int cartPrice = 0, itemsInCart = 0;
String tempCart = "";
for (String label : prices.keySet()) {
for (String labelToBuy : toBuy) {
if (label.contains(labelToBuy)) {
if (!tempCart.contains(label)) {
tempCart += label.concat(" ");
cartPrice += prices.get(label);
}
itemsInCart++;
}
}
if (itemsInCart == toBuy.length && minPrice > cartPrice) {
minPrice = cartPrice;
pack = tempCart;
itemsInCart = 0;
cartPrice = 0;
tempCart = "";
}
}
return pack.trim();
}
}
struct Bundle{
int SrNo;
int price;
vector<string> items;
};
vector<Bundle> bundles;
// Auxiliary table maps name to indexes of bundels:
// Burger | 1,4,5
// French_Frice | 2,4
// Coldrink | 3, 4, 5
map<string, vector<int>> item_name_to_bundle_indexes;
int GetBundles(const set<string>& items_to_buy,
vector<int>& best_bundles) {
if (items_to_buy.empty())
return 0;
int best_price = INT_MAX;
string item_name = *items_to_buy.begin();
for (int bundle_index : item_name_to_bundle_indexes[item_name]) {
auto items_to_buy_copy = items_to_buy;
for (string item : bundles[bundle_index].items) {
items_to_buy_copy.erase(item);
}
vector<int> curr_best_bundles;
int price = bundles[bundle_index].price +
GetBundles(items_to_buy_copy, curr_best_bundles);
if (price < best_price) {
curr_best_bundles.push_back(bundle_index);
best_bundles = curr_best_bundles;
best_price = price;
}
}
return best_price;
}
Create a Graph where nodes are the price list items.
Direct edges with the following rule:
Connect node that has ith item of buy list with node that has (i+1)th.
For each node that has 0th item in buy list find lowest cost path to the node that has last item. Can visit one node more than once but need to add cost on first visit only.
Optimization: BFS. Cut all those path that exceed current best as soon as they exceed.
Just one more detail:
Many nodes can be in multiple categories therefore search only paths that visit nodes in buy list sequence.
What's a french frice?
Anyway, it's easy to express this problem in natural language, and easy to resolve using common sense (thank to the small data set), but more complex to express in programmatic notation.
I'm curious as to what type of computer language or paradigm would be most suitable to express the solution: functional programming, etc. Assuming it makes any difference, of course.
public class CoverSet {
private String[] buyList;
private Map<String,List<PriceItem>> item2priceList = new HashMap<String,List<PriceItem>>();
public CoverSet(String[] bl) {
buyList = bl;
}
public class PriceItem {
private double m_price;
public PriceItem(double price, String[] items) {
for ( String item : items ) {
List<PriceItem> priceList = item2priceList.get(item);
if (priceList == null) {
priceList = new ArrayList<PriceItem>();
item2priceList.put(item, priceList);
}
priceList.add(this);
}
m_price = price;
}
}
private double nextItem(int buyIndx, Set<PriceItem> resultPriceItems, double price) {
if (buyIndx == buyList.length) return price;
List<PriceItem> nextList = item2priceList.get(buyList[buyIndx]);
double minPrice = Long.MAX_VALUE;
for (PriceItem item : nextList) {
double bestCost;
if (!resultPriceItems.contains(item)) {
resultPriceItems.add(item);
bestCost = price + nextItem(buyIndx+1, resultPriceItems, item.m_price);
resultPriceItems.remove(item);
}
else {
bestCost = price + nextItem(buyIndx+1, resultPriceItems, 0);
}
if (bestCost < minPrice) minPrice = bestCost ;
}
return minPrice;
}
public double getBestCost() {
return nextItem(0, new HashSet<PriceItem>(), 0);
}
public static void main(String[] args) {
CoverSet cs = new CoverSet(new String[]{"Burger", "French_Frice"});
cs.new PriceItem(5, new String[]{"Burger"});
cs.new PriceItem(4, new String[]{"French_Frice"});
cs.new PriceItem(8, new String[]{"Coldrink"});
cs.new PriceItem(12, new String[]{"Burger", "French_Frice", "Coldrink"});
cs.new PriceItem(14, new String[]{"Burger", "Coldrink"});
System.out.println(cs.getBestCost());
}
}
class Combo{
int id;
int price;
Set<String> list;
Combo(int id, int price, Set<String> list){
this.id=id;
this.price=price;
this.list=list;
}
}
public class Solution{
public List<Integer> getBestCombo(List<Combo> combos, List<String> items){
int n=combos.size();
int m=items.size();
int S=(int)Math.pow(2,m);
int[] w=new int[S];
int[] track=new int[S];
Arrays.fill(w,Integer.MAX_VALUE);
Arrays.fill(track,-1);
w[0]=0;
for(int mask=1;mask<S;++mask){
for(int j=0;j<n;++j){
int p=mask;
for(int k=0;k<m;++k){
if(((1<<k) & p)!=0 && combos.get(j).list.contains(items.get(k)))
p^=(1<<k);
}
if(p!=mask && combos.get(j).price+w[p]<w[mask]){
w[mask]=w[p]+combos.get(j).price;
track[mask]=j;
}
}
}
int p=S-1;
List<Integer> rs=new ArrayList<Integer>();
while(p>0 && track[p]!=-1){
rs.add(combos.get(track[p]).id);
int q=p;
for(int k=0;k<m;++k){
if(((1<<k) & q)!=0 && combos.get(track[p]).list.contains(items.get(k)))
q^=(1<<k);
}
p=q;
}
return rs;
}
import java.util.*;
public class Restaurant {
public enum Item {
DRINK("drink"),
FRIES("fries"),
BURGER("burger");
private String m_name;
private Item(String name) {
m_name = name;
}
};
private Collection<MenuNode> m_menuNodes = null;
public Restaurant() {
initMenu();
}
private void initMenu() {
m_menuNodes = new ArrayList<MenuNode>();
m_menuNodes.add(new MenuNode(5, Item.BURGER));
m_menuNodes.add(new MenuNode(4, Item.FRIES));
m_menuNodes.add(new MenuNode(8, Item.DRINK));
m_menuNodes.add(new MenuNode(12, Item.BURGER, Item.FRIES, Item.DRINK));
m_menuNodes.add(new MenuNode(11, Item.BURGER, Item.DRINK));
}
/**
* Does a BFS on m_menuNodes
*/
public Collection<MenuNode> buy(Item...items) {
logWantToBuy(items);
// Make start and end pseudo-Nodes, each with $0 cost, and make a DAG
MenuNode start = new MenuNode(0);
start.setPriorCost(0);
MenuNode end = new MenuNode(0);
setUpDag(start, end, items);
// Now do the BFS
Collection<MenuNode> bought = new ArrayList<>();
Deque<MenuNode> queue = new ArrayDeque<>();
queue.addLast(start);
BFS(queue);
try {
for (MenuNode n=end.getBestPreceder(); start!=n; n=n.getBestPreceder()) {
bought.add(n);
}
} catch (Exception e) {
e.printStackTrace();
}
return bought;
}
private void setUpDag(MenuNode start, MenuNode end, Item... items) {
for (MenuNode s : m_menuNodes) {
s.reset();
if (s.contains(items[0])) {
start.addEdge(s);
}
if (s.contains(items[items.length-1])) {
s.addEdge(end);
}
for (int i=0; i<items.length-1; ++i) {
for (MenuNode t : m_menuNodes) {
if (s != t && s.contains(items[i]) && t.contains(items[i+1])) {
s.addEdge(t);
}
}
}
}
}
private void BFS(Deque<MenuNode> queue) {
while (!queue.isEmpty()) {
MenuNode n = queue.removeFirst();
for (MenuNode c : n.getEdges()) {
if (!c.getVisited()) {
int priorCostViaN = n.getPriorCost() + n.getCost();
if (priorCostViaN < c.getPriorCost()) {
c.setPriorCost(priorCostViaN);
c.setBestPreceder(n);
}
if (!c.getDiscovered()) {
c.setDiscovered();
queue.addLast(c);
}
}
}
n.setVisited();
}
}
public static void main(String args[]) {
Restaurant r = new Restaurant();
logBought(r.buy(Item.BURGER));
logBought(r.buy(Item.BURGER, Item.FRIES));
logBought(r.buy(Item.DRINK, Item.BURGER));
logBought(r.buy(Item.FRIES, Item.BURGER, Item.DRINK));
}
public static void logWantToBuy(Item... items) {
System.out.println("I want to buy: ");
for (Item i : items) {
System.out.println(i.name());
}
}
public static void logBought(Collection<MenuNode> bought) {
System.out.println("I bought: ");
for (MenuNode n : bought) {
System.out.println(n.toString());
}
System.out.println("---------------------------------");
}
private class MenuNode {
private boolean m_visited;
private boolean m_discovered;
private int m_cost;
private int m_priorCost;
private Collection<Item> m_items;
private Collection<MenuNode> m_edges; // Directed
private MenuNode m_bestPreceder;
public MenuNode(int cost, Item... items) {
m_visited = m_discovered = false;
m_cost = cost;
m_priorCost = Integer.MAX_VALUE;
m_items = Arrays.asList(items);
m_edges = new ArrayList<MenuNode>();
m_bestPreceder = null;
}
public int getCost() {
return m_cost;
}
public int getPriorCost() {
return m_priorCost;
}
public void setPriorCost(int priorCost) {
m_priorCost = priorCost;
}
public boolean contains(Item i) {
return m_items.contains(i);
}
public void addEdge(MenuNode n) {
m_edges.add(n);
}
public Collection<MenuNode> getEdges() {
return new ArrayList<MenuNode>(m_edges);
}
public void setBestPreceder(MenuNode n) {
m_bestPreceder = n;
}
public MenuNode getBestPreceder() {
return m_bestPreceder;
}
public void reset() {
m_edges.clear();
m_discovered = false;
m_visited = false;
m_priorCost = Integer.MAX_VALUE;
}
public void setDiscovered() {
m_discovered = true;
}
public boolean getDiscovered() {
return m_discovered;
}
public void setVisited() {
m_visited = true;
}
public boolean getVisited() {
return m_visited;
}
public String toString() {
StringBuffer buf = new StringBuffer();
buf.append(m_cost);
for (Item i : m_items) {
buf.append(" ");
buf.append(i.name());
}
return buf.toString();
}
}
}
#include<iostream>
#define MAXQUANTITY 5
using namespace std;
struct Bundle{
int SrNo;
int price;
int numItems;
string *items;
};
int main(){
struct Bundle *head = new Bundle[MAXQUANTITY];
string itemsSeq[3] ={"Burger", "French_Frice", "Coldrink"};
//for(int i=0; i<3; i++)
//cout<<itemsSeq[i]<<endl;
int quantity;
int itemnum;
for(int i=0; i<MAXQUANTITY; i++){
head[i].SrNo = i;
//entering items in the list
cout<<"Enter Number of Items in " << i+1<<" the list"<<endl;
cin>>quantity;
if(quantity<=0 || quantity>3){
cout<<"No. of items are zero or more than 3"<<endl;
break;
}
else{
head[i].numItems = quantity;
head[i].items = new string[head[i].numItems];
cout<<"Enter item to select: 1:Burger 2:French_Fries 3:Coldrink";
for(int j=0; j<quantity; j++){
cout<<"Enter "<<j+1<<" item"<<endl;
cin>>itemnum;
if(itemnum <1 || itemnum>3){
cout<<"Invalid Items"<<endl;
break;
}
head[i].items[j] = itemsSeq[itemnum-1];
}
}
//price
cout<<"Enter price"<<endl;
cin>>head[i].price;
}
for(int i=0; i<MAXQUANTITY; i++){
cout<<head[i].SrNo+1<<" "<<head[i].price<<" "<<head[i].numItems<<endl;
for(int j=0; j<head[i].numItems; j++)
cout<<head[i].items[j];
cout<<endl;
}
struct Bundle *buy = new Bundle;
buy->SrNo = 1;
cout<<"Enter Number of Items in the list to buy"<<endl;
cin>>quantity;
if(quantity<=0 || quantity>3){
cout<<"No. of items are zero or more than 3"<<endl;
exit(-1);
}
buy->numItems = quantity;
cout<<"Enter item to select: 1:Burger 2:French_Fries 3:Coldrink";
for(int j=0; j<quantity; j++){
cout<<"Enter "<<j+1<<" item"<<endl;
cin>>itemnum;
if(itemnum <1 || itemnum>3){
cout<<"Invalid Items"<<endl;
break;
}
buy->items[j] = itemsSeq[itemnum-1];
}
int min_cost = 0;
int index=-1;
for(int i=0; i<MAXQUANTITY; i++){
int cost = 0;
for(int j=0; j<head[i].numItems; j++){
if(buy->items[j] == head[i].items[j])
cost = head[i].price;
}
if(min_cost<cost){
min_cost = cost;
index = i;
}
}
cout<<"Output List is"<<endl;
for(int j=0; j<head[index].numItems; j++)
cout<<head[index].items[j]<<" ";
cout<<endl;
return 0;
}
{
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.TreeMap;
import java.util.regex.Pattern;
/*Sr.No Price | Items/Combo_Items
1. 5 | Burger
2. 4 | French_Frice
3. 8 | Coldrink
4. 12 | Burger, French_Frice, Coldrink
5. 14 | Burger, Coldrink
*/
public class FoodItem {
public static void main(String args[])
{
String input[] = {"1:5:Burger","2:4:French_Frice","3:8:Coldrink","4:12:Burger,French_Frice,Coldrink","5:14:Burger,Coldrink"};
cheapDeal(input,"Burger");
cheapDeal(input,"Coldrink");
cheapDeal(input,"Burger Coldrink");
cheapDeal(input,"Burger French_Frice");
}
private static void cheapDeal(String[] input, String items) {
// TODO Auto-generated method stub
HashMap<String,Integer> srCombo = new HashMap<String,Integer>();
HashMap<Integer,Integer> srPrice = new HashMap<Integer,Integer>();
TreeMap<String,Integer> result = new TreeMap<String,Integer>();
String inputItems[] = items.split(" ");
String itemCombo = items.replace(" ", "(.*)");
for(int i=0;i<inputItems.length;i++){
for(int j=0;j<input.length;j++){
String readLine[] = input[j].split(":");
int srno = Integer.parseInt(readLine[0]);
int price = Integer.parseInt(readLine[1]);
String item = readLine[2];
if(input[j].matches("(.*)"+itemCombo+"(.*)")){
putValues(srCombo,srPrice,srno,price,item);
}
else if(input[j].contains(inputItems[i])){
putValues(srCombo,srPrice,srno,price,item);
}
}
}
String output="";
int minPrice=Integer.MAX_VALUE;
int p1=0;
for(String keys: srCombo.keySet()){
int p2=srPrice.get(srCombo.get(keys));
if(!keys.matches("(.*)"+itemCombo+"(.*)") && keys.split(",").length==1){
p1 = p1+p2;
output = output + " "+srCombo.get(keys);
}
else{
result.put(srCombo.get(keys).toString(), p2);
if(p2<minPrice)
minPrice = p2;
}
}
if(!output.isEmpty()){
result.put(output.trim(), p1);
if(p1<minPrice){
minPrice = p1;
}
}
for(String keys:result.keySet()){
if(result.get(keys)==minPrice)
System.out.println(keys);
}
}
private static void putValues(
HashMap<String, Integer> srCombo, HashMap<Integer, Integer> srPrice, int srno,int price, String item) {
// TODO Auto-generated method stub
if(srCombo.containsKey(item)){
int getSr = srCombo.get(item);
int getPr = srPrice.get(getSr);
if(price<getPr){
srCombo.put(item, srno);
srPrice.put(srno, price);
}
}
else{
srCombo.put(item, srno);
srPrice.put(srno, price);
}
}
}
}
{
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.TreeMap;
import java.util.regex.Pattern;
/*Sr.No Price | Items/Combo_Items
1. 5 | Burger
2. 4 | French_Frice
3. 8 | Coldrink
4. 12 | Burger, French_Frice, Coldrink
5. 14 | Burger, Coldrink
*/
public class FoodItem {
public static void main(String args[])
{
String input[] = {"1:5:Burger","2:4:French_Frice","3:8:Coldrink","4:12:Burger,French_Frice,Coldrink","5:14:Burger,Coldrink"};
cheapDeal(input,"Burger");
cheapDeal(input,"Coldrink");
cheapDeal(input,"Burger Coldrink");
cheapDeal(input,"Burger French_Frice");
}
private static void cheapDeal(String[] input, String items) {
// TODO Auto-generated method stub
HashMap<String,Integer> srCombo = new HashMap<String,Integer>();
HashMap<Integer,Integer> srPrice = new HashMap<Integer,Integer>();
TreeMap<String,Integer> result = new TreeMap<String,Integer>();
String inputItems[] = items.split(" ");
String itemCombo = items.replace(" ", "(.*)");
for(int i=0;i<inputItems.length;i++){
for(int j=0;j<input.length;j++){
String readLine[] = input[j].split(":");
int srno = Integer.parseInt(readLine[0]);
int price = Integer.parseInt(readLine[1]);
String item = readLine[2];
if(input[j].matches("(.*)"+itemCombo+"(.*)")){
putValues(srCombo,srPrice,srno,price,item);
}
else if(input[j].contains(inputItems[i])){
putValues(srCombo,srPrice,srno,price,item);
}
}
}
String output="";
int minPrice=Integer.MAX_VALUE;
int p1=0;
for(String keys: srCombo.keySet()){
int p2=srPrice.get(srCombo.get(keys));
if(!keys.matches("(.*)"+itemCombo+"(.*)") && keys.split(",").length==1){
p1 = p1+p2;
output = output + " "+srCombo.get(keys);
}
else{
result.put(srCombo.get(keys).toString(), p2);
if(p2<minPrice)
minPrice = p2;
}
}
if(!output.isEmpty()){
result.put(output.trim(), p1);
if(p1<minPrice){
minPrice = p1;
}
}
for(String keys:result.keySet()){
if(result.get(keys)==minPrice)
System.out.println(keys);
}
}
private static void putValues(
HashMap<String, Integer> srCombo, HashMap<Integer, Integer> srPrice, int srno,int price, String item) {
// TODO Auto-generated method stub
if(srCombo.containsKey(item)){
int getSr = srCombo.get(item);
int getPr = srPrice.get(getSr);
if(price<getPr){
srCombo.put(item, srno);
srPrice.put(srno, price);
}
}
else{
srCombo.put(item, srno);
srPrice.put(srno, price);
}
}
}
}
- m@}{ August 23, 2014