First Come, First Serve (Array Validation)

avatar
Marshal Murphy
June 12, 2020 - 3 MIN READ

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.

In-Place String Reversals

Oh no!

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!


Context

The pizza should come out of the kitchen in the same order it was received, and are comprised of 2 lists:

  1. meals served in the restaurant.
  2. meals ordered for take away.

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.


Approach

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, servedOrders?

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 shift().

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 takeAwayOrders or eatInOrders have orders that are not accounted for in servedOrders.

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.

Alright I think we have enough to go on. Let’s come up with some solutions in JavaScript and Ruby.


Here, we perform an initial disqualification of servedOrders if it’s length doesn’t match the combined length of takeAwayOrders and eatInOrders.

Hint: Easily merge arrays and preserve duplicate values in JavaScript with spread operators.

Next, we loop over each item in servedOrders and compare it with the first values of takeAwayOrders and eatInOrders.

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 takeAwayOrders and 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 false.

Lastly, we do a final check to ensure no extra orders remain.


For posterity, and since I like keeping my Ruby skills up-to-date with my JavaScript, here’s the same solution written in Ruby.

Ruby


Learnings

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.

Marshal Murphy 2020