The Problem: Given 3 arrays, write a function that will determine if the 3rd array is comprised of the first 2 arrays on a first-come, first-serve basis.
The pizza place you opened last summer has been running into some problems lately with their orders.
Some customers have been complaining that people who have placed orders after them are getting their food first! 😕
As orders are received for both eat-in and take-away, they should be combined into a single list to be handled first-come first-serve by the cooks.
It’s your job to find out if the orders coming out of the kitchen are indeed being made to order!
The pizza should come out of the kitchen in the same order it was received, and are comprised of 2 lists:
Let’s look at some examples using arbitrary order numbers.
takeAwayOrders = [14, 3, 11] eatInOrders = [7, 2, 9] servedOrders = [14, 7, 2, 3, 9, 11]
In the above example, each served order is first-come first-serve.
takeAwayOrders = [1, 4, 6] eatInOrders = [2, 3, 5] servedOrders = [1, 2, 5, 3, 4, 6]
In this example, order 5 was ordered after order 3, but was served before 3, and therefore did not follow our rule of first-come, first-serve.
Keep in mind: the numbers themselves are not important, but rather the order.
To solve this problem, let’s break it into smaller sub-problems.
First: how do we go about determining that two arrays of equal length have been combined in a first-come-first-serve fashion?
What if we looped over our final array,
If we did that, we could check that each item matched the first item of either of the other arrays. When there is a match, the order is correct, and so we can remove that item from the beginning of the array with
By the end of the loop, the two input arrays should both have a final length of 0. Otherwise the served orders would have missed an order!
Second: we must consider if either
eatInOrders have orders that are not accounted for in
This goes for the opposite as well: what if servedOrders includes orders not accounted for in takeAwayOrders or eatInOrders?
Either way, if this is the case, mistakes have been made by your cooks or your waiting staff, and the servedOrders will be wrong.
Here, we perform an initial disqualification of
servedOrders if it’s length doesn’t match the combined length of
Next, we loop over each item in
servedOrders and compare it with the first values of
A match with either indicates the order is still first-come-first-serve, and so we
shift() the value off the beginning of the matching array. We continue this loop until both
eatInOrders have no values remaining.
In this loop, if at any point there isn’t a match between the values at position 0 in either array and the current item in the
servedOrders loop, the order is incorrect, and we return
Lastly, we do a final check to ensure no extra orders remain.
Often it is best to take a large problem and break it down into smaller problems.
This is usually the case when you think through a problem and realize that there are many possible outcomes you need to account for.
Solve the larger problem by working through each smaller problem one by one.
When you are finished, take another look at your solution and think about ways you might make it more efficient, or ways your code could be implemented in better.