In this post we will try to define some requirements and then solve the problem. I briefly saw this problem and was not able to get all the details. If it does not make much sense you could specify a variant and go on and solve it.
In this problem we are given a list of offer items and cart items. The cart items are provided in the order the customer put them in the shopping cart. The offer items are a list of list of items that must be put into the cart in the order specified. I guess there could be different versions of the requirements, but in our case, we need to make sure that all items in all the item lists are placed in the cart in the specified order. Perhaps it would be more reasonable to get an additional discount if a set of items are placed in a specified order in the shopping cart, or better yet, if each set of items ends in the shopping cart the customer could receive additional offers. We need to return true if all items are placed in the shopping cart in the specified order; otherwise we return false. Constraints: o 1 <= number of items <= 100 o 0 <= number of offers <= 100 o The string `anything` in the offers indicates that the correspoinding item in the shopping cart should be ignored.
The requirements call for having two lists available. In one is a set of offers that require all the specified items to be placed (not just be found) into the cart in the order specified by the offer item. Not only that, but all items must be placed in the cart in the order specified by all offers. That is how we will proceed.
As I am writing this post I think that if I would be starting with the code I would have specified it differently. Given a set of offers, verify that none, one, or more offers apply for the items in the shopping cart regardless of the order they were put in. The function of interest would return the number of offers (discounts) applicable. We are not here designing problems so let’s move on and go with the requirements as stated earlier in this post.
I will be solving the problem using the Java programming language and the VSCode IDE on a Windows computer.
/**
* Determine if customer should receive an offer.
*/
public boolean receiveOffer(List<List<String>> offerItems, List<String> cartItems) {
}
The signature for the problem indicates that we are provided a list of offers and a list of items in the cart. The items should be checked in the provided order. The more that I think about this the less realistic the requirements sound. It seems that we should be looking for one or more offers in the shopping cart.
4 orange apple apple banana orange apple banana 7 orange apple apple banana orange apple banana main <<< n: 4 main <<< offerList: [[orange], [apple, apple], [banana, orange, apple], [banana]] main <<< m: 7 main <<< cart: [orange, apple, apple, banana, orange, apple, banana] main <<< receiveOffer0: true main <<< receiveOffer: true 4 orange apple apple banana anything apple banana 7 orange apple apple banana mango apple banana main <<< n: 4 main <<< offerList: [[orange], [apple, apple], [banana, anything, apple], [banana]] main <<< m: 7 main <<< cart: [orange, apple, apple, banana, mango, apple, banana] main <<< receiveOffer0: true main <<< receiveOffer: true 4 orange apple apple banana orange apple banana 7 orange apple apple banana guava apple banana main <<< n: 4 main <<< offerList: [[orange], [apple, apple], [banana, orange, apple], [banana]] main <<< m: 7 main <<< cart: [orange, apple, apple, banana, guava, apple, banana] main <<< receiveOffer0: false main <<< receiveOffer: false
Each test case is separated from others by two blank lines.
The first input line specifies the number of offers. Each offer contains a set of items (not only fruits) that need to be placed into the shopping cart in the specified order.
The next set of items is started by a number. It contains the number of items and the order in which they were added to the shopping cart.
Our function of interest needs to return `true` if all items in the shopping cart were added in the order specified by the first list.
We have two different implementations. Both appear to return the same results.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// *** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** number of offer elements ****
int n = Integer.parseInt(br.readLine().trim());
// **** read ofer elements into List<List<String>> ****
List<List<String>> offerItems = new ArrayList<List<String>>();
for (int i = 0; i < n; i++) {
// **** read and populate list ****
List<String> lst = Arrays.stream(br.readLine().trim().split(" "))
.collect(Collectors.toList());
// **** add list to List<List<String>> ****
offerItems.add(lst);
}
// **** number of products in cart ****
int m = Integer.parseInt(br.readLine().trim());
// **** read products into cart ****
List<String> cart = new ArrayList<>();
for (int i = 0; i < m; i++)
cart.add(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< n: " + n);
System.out.println("main <<< offerList: " + offerItems.toString());
System.out.println("main <<< m: " + m);
System.out.println("main <<< cart: " + cart.toString());
// **** call function of interest and display tesult ****
System.out.println("main <<< receiveOffer0: " + receiveOffer0(offerItems, cart));
// **** call function of interest and display tesult ****
System.out.println("main <<< receiveOffer: " + receiveOffer(offerItems, cart));
}
The test scaffold reads the input lines, creates and populates the two arguments that will be passed to the function of interest. The function of interest is then called and the result displayed. A second implementation is then called.
/**
* Determine if customer should receive an offer.
*/
static public boolean receiveOffer0(List<List<String>> offerItems, List<String> cartItems) {
// **** sanity checks ****
if (offerItems.size() == 0) return false;
// **** convert offerList to string ****
String offerStr = OffersToStr(offerItems);
// **** convert cart to string ****
String cartStr = CartToStr(cartItems);
// **** array of offers ****
String[] offers = offerStr.split(" ");
// **** array or cart items ****
String[] items = cartStr.split(" ");
// **** compare contents in arrays ****
return GetOffer(offers, items);
}
In this implementation we perform a sanity check.
We then convert the list of `offerItems` into a string.
We then take the `cartItems` and convert them to a string.
We use the individual strings to generate and populate two String[] arrays.
The final step is to determine if the strings match. If they do, our function returns `true`; otherwise it returns `false`.
/**
* Return a string of offers blank separated.
*/
static private String OffersToStr(List<List<String>> offerItems) {
// **** initialization ****
StringBuilder sb = new StringBuilder();
// **** build string ****
for (List<String> lst : offerItems) {
for (String s : lst)
sb.append(s + ' ');
}
// **** delete last ' ' ****
sb.delete(sb.length() - 1, sb.length());
// **** return offer string blank separated ****
return sb.toString();
}
This auxiliary function converts the `offerItems` into a single string separated by ` ` blank characters.
/**
* Return string with cart items.
*/
static private String CartToStr(List<String> cartItems) {
// **** initialization ****
StringBuilder sb = new StringBuilder();
// **** build string with cart contents ****
for (String item : cartItems)
sb.append(item + ' ');
// **** delete last ' ' ****
sb.delete(sb.length() - 1, sb.length());
// **** return cart string blank separated ****
return sb.toString();
}
This auxiliary function generates a string in which the items are separated by a single ` ` blank character.
/**
* Compare array contents.
*/
static private boolean GetOffer(String[] offers, String[] items) {
// **** sanity checks ****
if (offers.length != offers.length) return false;
// **** check offers and items ****
for (int i = 0; i < offers.length; i++) {
// **** skip checking this item ****
if (offers[i].equals("anything")) continue;
// **** ****
if (!offers[i].equals(items[i])) return false;
}
// **** all items match the offers in the same order ****
return true;
}
This function compares the order and contents of the `offers` and `items` String[] arrays.
If the items match the function returns `true`; otherwise it returns `false`.
/**
* Determine if customer should receive an offer.
*/
static public boolean receiveOffer(List<List<String>> offerItems, List<String> cartItems) {
// **** sanity checks ****
if (offerItems.size() == 0) return false;
// **** count number of items in offerItems ****
int m = 0;
for (List<String> lst : offerItems)
for (String s : lst)
m++;
// **** declare offers array ****
String[] offers = new String[m];
// **** populate offers array ****
int j = 0;
for (List<String> lst : offerItems)
for (String s : lst)
offers[j++] = s;
// **** get number of items ****
int n = cartItems.size();
// **** cart items array ****
String[] items = new String[n];
// **** populate array ****
for (int i = 0; i < n; i++)
items[i] = cartItems.get(i);
// **** check offers and items ****
for (int i = 0; i < offers.length; i++) {
// **** skip checking this item ****
if (offers[i].equals("anything")) continue;
// **** item does not match ****
if (!offers[i].equals(items[i])) return false;
}
// **** offers match items in cart ****
return true;
}
This is the second implementation of the function of interest.
The steps are similar in order to achieve the same goal as before but using a single function.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named FruitOrderInCart.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John