To solve this problem, I proccessed the json file of products into a Hash Map where the keys are possible input combinations, and the values are themselves Hash Maps whose keys are the remaining options that point to Sets that hold the corresponding option values.
e.g
{
"tshirt" => {
"gender"=> <Set: {"male", "female"}>,
"color"=> <Set: {"red", "green", "navy", "white", "black"}>,
"size"=> <Set: {"small", "medium", "large", "extra-large", "2x-large"}>
},
"tshirt+male" => {
"color"=> <Set: {"red", "green", "navy", "white", "black"}>,
"size"=> <Set: {"small", "medium", "large", "extra-large", "2x-large"}>
}, ...
}
Obtaining the remaining options for a given input is then just an O(1) Hash Map lookup.
The program output can be viewed in the terminal
The cmd app can be run in the terminal from the root directory using:
- ruby lib/product_parser.rb product_type option1 option2 ... OR
- lib/product_parser.rb product_type option1 option2
I used Rspec for testing. I've inlcuded several example inputs and a few edges cases, as well as printing out the actual output of each test case.
Tests can be run by navigating to the root directory and typing:
- bundle exec rspec spec/product_parser_spec.rb
Making sure to run bundle install first
Proccessing the json file is a one time operation after which extracting the remaining options for a given input combination is O(1)
If 'n' is the number of products in the list, and 'O' is the product type with the maximum number of option categories, the processing takes O(n * 2^O) time.
The 2^O comes from the possible combinations of option inputs for a given product type. For each product, the number of combinations is:
which has an upper bound of 2^O
Depending on the real-world constraints, the number of option categories could be considered constant. For example, in the data set given, O = 3.
Adding a product to the Hash Map is O(2^O)
If the number of product option categories for a single product type exceeds ~ 20 (which seems unlikely), the processing could begin to take a while, and a better solution may be required. Even so, the processing of the JSON file is a one time operation after which the Hash Map is free to be accessed in O(1) time to return the remaining options.