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




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: