[No Audio]
Hello and welcome back again. Let us first
understand the scenario. There is an online
shopping business who recently held a lucky
draw contest, where 1000s of people
participated. The ones who were successful
have been given a $50 shopping gift card,
which can be used to buy items from the
online store. There is however, a restriction
from the business that the customers can only
buy two products at most. Now we want to help
the customers by suggesting a list of
triplets that contains products worth $50
exactly, so that they are not worried from
paying the extra from their own pockets.
In other words, we want to suggest package deals
containing two products that sum up to $50,
and we want to suggest as many such
possibilities as there may exist. To
implement this feature, we will have access
to a list of products that the customer is
likely to buy. These products will include
products from the person wish list, and other
products based on the previous purchases.
Our job is to return the possible pairs of
products whose sum is equal to $50.
Let us start implementing this problem.
[No Audio]
In the main, I will first declare a vector which will
contain the prices of products.
[No Audio]
We will next pass this vector to a function,
which will return to us the possible
suggestions. We will use the HashSet to
implement this function. So let us first
bring that into scope.
[No Audio]
Let us declare a function called
product_suggestion for this purpose.
[No Audio]
The input to the function will be vector
containing the prices and the amount of the
gift card. The output will be a nested vector
of two dimensional vector, where each entry
will contain the pair of products.
[No Audio]
We will first declare an empty HashSet, which
we will use for efficient searching through the vector.
[No Audio]
This specific use of the HashSet will be
explained in a while. To capture the final
output, which we will return from this
function, I will declare a two dimensional
vector called offers.
[No Audio]
Now before going further, let us look at the
vector of values again. To implement the
problem, we will first pick up the first
value, and then iterating through all the
values to check if the first value can be
paired up with any other element. In the same
way, we will process the second element, and
we'll keep on checking it with all the
remaining elements in the list. One way of
implementing this problem would be, to pick up
the first value, and then iterating through
all the values to check if the first value
can be paired up with any of the other
elements. In the same way, we will
process the second element that will
keep on checking it with all the remaining
elements in the list. This is however an
inefficient solution, because it will require us
to use two nested loops. The outer loop will
be used to pick up the values one at a time,
and then the inner loop will be used to check
it against the list of values for possible
pairing. We will use a more efficient
solution using the HashSet and using a single loop.
The loop will be used to iterate
through all the values, and if the value can
be paired up with any value that is already
in the HashSet, then we will add it to the
list of possible pairs. In any other case, we
will add it to the HashSet. This may look a
bit hard to comprehend right now, but it will
start to make sense once we implement this.
Let's start with the implementation.
I will first use a loop for iterating
through all the elements in the vector.
[No Audio]
Next, I will define a variable called
difference, which will subtract the value of
the currently processed word from the list.
[No Audio]
Next, we will inspect the HashSet which
initially does not contain any value. We will
see if any value in the HashSet has a value
equal to the difference or not. If we are
unable to find a value equal to the
difference, then we will add it to the HashSet.
[No Audio]
The get function needs a reference to
the value, and the is_none will return true, if
there is no value found in the HashSet after
calling the get function. In any other case,
we will add the value to the offers along
with the difference, because the difference
value do exist in the HashSet.
[No Audio]
This means that, we will only add a value to
the HashSet, when we are unable to find the
difference value in the HashSet.
Let us cargo run this.
[No Audio]
That is great. Let us now see
how this will work. For the first time we have
a value of 11, the difference will be 39.
Since there is nothing in the HashSet, therefore,
therefore the get function will return a
true, and therefore, we will add the value to
the HashSet. The next value is 34, which the
difference will be 20. And since 20 also does
not exist, exist in the HashSet, therefore,
it will also be inserted.
Similarly, the value of 55, 34, 45, 10, and 19 will
also be inserted. When we reach at a value of
20, the difference will be 30, and the value 30
exist in the HashSet, therefore, the value
20 will not be inserted in the HashSet, but
it will be rather added to the offers list
along with the value of 30. This means that,
we will only add a value to the HashSet, when
it cannot be currently paired with any other
existing value in the HashSet.
You may also note that since
each value can only be paired
up with a single value, that is the value 30
can only be paired up with a value 20, and
cannot be paired up with any other value, so
having 30 in the HashSet is sufficient for
us, and we do not need to store the value 20.
As pointed out before, searching in HashSet
is very fast and takes constant amount of
time, therefore, it does not involve any
significant overhead in terms of time.
Moreover, since we are using only a single
loop, therefore, our solution is more
efficient compared to using nested loops for
searching out items in the list.
Finally, also please note that, our solution is based
on the assumption that the values will not
repeat, for repeating values the solution may
be a bit different. That is it for this
particular tutorial. See you again with
another interesting real life problem.
Do come back again and
until then happy Rust programming.
[No Audio]