Mapping the donut orders

Problem [reviewed on 2022/03/27]

You are given the two array of strings:
dountType: the first one is donut name and the second one is donut type
[
[ "crullar", "vegan"],
[ "beignet", "coffee"]
]
order: the first one is the name of the people and the second one is donut type.
[
[ "jose" , "vegan"],
[ "john", "coffee"]
]

You need to write the program listing the following output.
[
  ["john", "beignet"], ["jose", "cruller"]
]

Each person can like either one donut for all donuts. If a person like all donuts, the input will be like below:
["Adam", "*"]

In that case, the output should be
[ "Adam", "beignet"], ["Adam", "crulller"]

Note the output is sorted primarily by the name and secondarily by the donut name.

You need to implement the following method:

# c++

vector < vector < string > > matchDonuts(vector < vector < string > >
 donutConstraintPairs, vector < vector < string > > candidateConstraintPairs){

}

#python

def matchDonuts( donutConstraintPairs, candidateConstraintPairs):

donutConstraintPairs is the list of list containing pair of donut name and donut type

candidateConstraintPairs is the list of list containing pair of name and donut type

I had this question for my interview recently and I thought it would be a good idea to post it before forgetting the question.

Basically, this question asks us to do the two main tasks.

1) Map the donut types to corresponding donut names in a hashtable

2) sort the output by the person's name primarily and donut name secondarily.

Once we understand the subproblems, let's find out how we can solve each problem.

1) Map the donut types to corresponding donut names in a hashtable

Given the list of pairs, we can construct the Hash Table having a donut type as a key and a donut name as a value in $O(M)$ time, where M is the number of existing donuts types.

For each order in the test, we can access the donuts name with the donuts type from the order in $O(1)$.

In order to save time to handle the "*" type and to sort the orders by the donut name, we can keep all donut names in an array and sort them in $O(M \log M)$ time.

Therefore, the overall running time of this step will be $$O(M \log M)$$ , with M for # of donut types.

2) sort the output by the person's name primarily and donut name secondarily.

Now, we have the list of orders mapped to the donut names. Sorting this done through the following steps:

Given that we already shorted the donut's name, the only thing we need to do is to short the orders by name in $O(N \log N)$ where N is the number of orders.

For each order, we handle two cases:

Case 1: donut type is "*"

We can just create a list of pairs of names and a donut type from the sorted donut name array in $O(M)$

Case 2: donut type is a single type

We can search the donut name from the hash table in $O(1)$


Therefore, the overall running time will be $$O(N \log N)$$ , assuming that $N \gt M$.

Here is the complete code running in $O(N \log N)$.

	#include<iostream>
	#include<string>
	#include<list>
	#include<vector>
	#include<set>
	#include<map>
	#include<algorithm>
	#include<math.h>
	using namespace std;
	bool compareString(string p, string n)
	{
	int a=0, b=0;
	while(a< p.length() && b <n.length())
	{
	if (p[a] != n[b])
	return p[a]<n[b];
	a++;
	b++;
	}
	if (a<p.length())
	{
	return p[a] < n[n.length()-1];
	}
	else if (b <n.length())
	return p[p.length()-1] < n[b];
	return true;
	}
	bool compare(vector<string> p, vector<string> n)
	{
	//check if name is the same, if so, compare tye donut name instead
	if (p[0] == n[0])
	return compareString(p[1], n[1]); // compare donut name
	else
	{
	cout<< "prev = "<< p[0] << ", next =" << n[0]<<endl;
	bool result = compareString(p[0], n[0]); //compare name
	cout<< "result = "<< result <<endl;
	return result;
	}
	}
	vector < vector < string > > matchDonuts(vector < vector < string > > donutConstraintPairs, vector < vector < string > > candidateConstraintPairs) {
	vector<vector<string>> result;
	map<string, string>::iterator iter;
	map<string, string> typeMap;
	set<string> donutNames;
	set<string> names;
	//check if the donut information is empty
	if (donutConstraintPairs.size() == 0)
	return result;
	//build the type map
	for(int i = 0; i< donutConstraintPairs.size(); i++)
	{
	//return empty if invalid input was passed.
	if (donutConstraintPairs[i].size() !=2)
	{
	cout<<"invalid donut"<<endl;
	return result;
	}
	if (typeMap.find(donutConstraintPairs[i][1])!= typeMap.end())
	{
	cout<<"duplicate donut type"<<endl;
	return result;
	}
	if (donutNames.find(donutConstraintPairs[i][0])!= donutNames.end())
	{
	cout<<"duplicate donut name"<<endl;
	return result;
	}
	typeMap[donutConstraintPairs[i][1]] = donutConstraintPairs[i][0];
	donutNames.insert(donutConstraintPairs[i][0]);
	}
	for(int i = 0; i < candidateConstraintPairs.size(); i++)
	{
	string donutname;
	vector<string> row;
	//return empty if invalid input was passed.
	if (candidateConstraintPairs[i].size() !=2)
	{
	cout<<"invalid order"<<endl;
	return result;
	}
	string name = candidateConstraintPairs[i][0];
	//check if there is any duplicate order
	if (names.find(name) != names.end())
	{
	cout<<"duplicate order"<<endl;
	return result;
	}
	//add the order to the set for duplicate check.
	names.insert(name);
	if (candidateConstraintPairs[i][1] == "*")
	{
	//add all existing donut names
	for (iter = typeMap.begin() ; iter != typeMap.end(); iter++)
	{
	vector<string> row1;
	row1.push_back(name);
	row1.push_back(iter->second);
	result.push_back(row1);
	}
	continue;
	}
	//return empty if non existing type is passed.
	if (typeMap.find(candidateConstraintPairs[i][1])== typeMap.end())
	return result;
	donutname = typeMap[candidateConstraintPairs[i][1]];
	row.push_back(name);
	row.push_back(donutname);
	result.push_back(row);
	}
	sort(result.begin(), result.end(), compare);
	return result;
	}
	int main () {
	vector<vector<string>>donuts;
	vector<string> d1;
	d1.push_back("cruller");
	d1.push_back("vegan");
	vector<string> d2;
	d2.push_back("beignet");
	d2.push_back("coffee");
	donuts.push_back(d1);
	donuts.push_back(d2);
	vector<vector<string>>order;
	vector<string> r1;
	r1.push_back("jose");
	r1.push_back("vegan");
	vector<string> r2;
	r2.push_back("johe");
	r2.push_back("*");
	order.push_back(r1);
	order.push_back(r2);
	vector<vector<string>> result = matchDonuts(donuts, order);
	cout<<"[ " <<endl;
	for(int i = 0; i< result.size(); i++)
	{
	cout<<"[ " <<endl;
	for(int j = 0; j < result[i].size(); j++)
	{
	cout<< result[i][j]<<", ";
	}
	cout<<"] " <<endl;
	}
	cout<<"] " <<endl;
	cout<<"test is done"<<endl;
	return 1;
	};

view raw donut_mapper.cpp hosted with ❤ by GitHub

Practice Statistics:

1hr 30 mins: to write up the code (stupidly, could not find the simple logical flaws. needs more practice)

Prior one had the flaw in that the compare algorithm was wrong. We should've compare like below:

For two pairs of names and donut names, a and b:

if the donut name is the same, compare the donut types:

else if

    compare the names

return 1 when a $\gt$ b, 0 when a = b, -1 when a $\lt$ b
 
2022-03-27:

Here is the python code:

	def matchDonuts(donutConstraintPairs, orders):
	# build the type map and all donut name array
	donut_map = {}
	all_donuts = []
	for pos in range(len(donutConstraintPairs)):
	donut_info = donutConstraintPairs[pos]
	if len(donut_info) == 2 and donut_info[1] not in donut_map:
	donut_map[donut_info[1]] = donut_info[0]
	all_donuts.append(donut_info[0])
	# sort all donuts
	all_donuts.sort()
	# sort order by name
	orders.sort(key = lambda o:o[0])
	output = []
	# now find the all matchin donuts
	for pos in range(len(orders)):
	order = orders[pos]
	name = order[0]
	if order[1] == '*':
	#add all of them
	for i in range(len(all_donuts)):
	donut = all_donuts[i]
	output.append([name, donut])
	elif order[1] in donut_map:
	output.append([name, donut_map[order[1]]])
	return output
	# example input 1
	orders = [[ "jose" , "vegan"], [ "john", "coffee"]]
	donuts = [[ "crullar", "vegan"], [ "beignet", "coffee"]]
	# expected output:
	expected = [["john", "beignet"], ["jose", "cruller"]]
	actual = matchDonuts(donuts, orders)
	print(actual)
	# example input 2
	orders = [["Adam", "*"]]
	donuts = [[ "crullar", "vegan"], [ "beignet", "coffee"]]
	actual = matchDonuts(donuts, orders)
	# expected output:
	expected = [[ "Adam", "beignet"], ["Adam", "crulller"]]
	print(actual)

view raw amazon_donut_match.py hosted with ❤ by GitHub