1
00:00:00,000 --> 00:00:07,300
[No Audio]

2
00:00:07,301 --> 00:00:09,600
Hello and welcome back again. Let us first

3
00:00:09,601 --> 00:00:12,300
understand the scenario. There is an online

4
00:00:12,301 --> 00:00:14,633
shopping business who recently held a lucky

5
00:00:14,634 --> 00:00:16,966
draw contest, where 1000s of people

6
00:00:16,967 --> 00:00:20,200
participated. The ones who were successful

7
00:00:20,201 --> 00:00:23,533
have been given a $50 shopping gift card,

8
00:00:23,833 --> 00:00:25,833
which can be used to buy items from the

9
00:00:25,834 --> 00:00:28,500
online store. There is however, a restriction

10
00:00:28,501 --> 00:00:30,733
from the business that the customers can only

11
00:00:30,734 --> 00:00:33,866
buy two products at most. Now we want to help

12
00:00:33,867 --> 00:00:35,900
the customers by suggesting a list of

13
00:00:35,901 --> 00:00:38,866
triplets that contains products worth $50

14
00:00:38,867 --> 00:00:41,133
exactly, so that they are not worried from

15
00:00:41,134 --> 00:00:43,300
paying the extra from their own pockets.

16
00:00:44,500 --> 00:00:47,300
In other words, we want to suggest package deals

17
00:00:47,301 --> 00:00:50,600
containing two products that sum up to $50,

18
00:00:51,133 --> 00:00:53,400
and we want to suggest as many such

19
00:00:53,401 --> 00:00:56,100
possibilities as there may exist. To

20
00:00:56,101 --> 00:00:58,600
implement this feature, we will have access

21
00:00:58,601 --> 00:01:01,200
to a list of products that the customer is

22
00:01:01,201 --> 00:01:04,266
likely to buy. These products will include

23
00:01:04,267 --> 00:01:06,966
products from the person wish list, and other

24
00:01:06,967 --> 00:01:09,300
products based on the previous purchases.

25
00:01:09,933 --> 00:01:12,733
Our job is to return the possible pairs of

26
00:01:12,734 --> 00:01:15,133
products whose sum is equal to $50.

27
00:01:15,600 --> 00:01:17,933
Let us start implementing this problem.

28
00:01:17,934 --> 00:01:20,033
[No Audio]

29
00:01:20,034 --> 00:01:22,800
In the main, I will first declare a vector which will

30
00:01:22,801 --> 00:01:24,600
contain the prices of products.

31
00:01:24,601 --> 00:01:34,166
[No Audio]

32
00:01:34,167 --> 00:01:36,433
We will next pass this vector to a function,

33
00:01:36,434 --> 00:01:38,100
which will return to us the possible

34
00:01:38,101 --> 00:01:41,066
suggestions. We will use the HashSet to

35
00:01:41,067 --> 00:01:43,700
implement this function. So let us first

36
00:01:43,701 --> 00:01:45,233
bring that into scope.

37
00:01:45,234 --> 00:01:50,333
[No Audio]

38
00:01:50,334 --> 00:01:52,000
Let us declare a function called

39
00:01:52,001 --> 00:01:54,398
product_suggestion for this purpose.

40
00:01:54,399 --> 00:01:59,766
[No Audio]

41
00:01:59,767 --> 00:02:01,600
The input to the function will be vector

42
00:02:01,601 --> 00:02:03,733
containing the prices and the amount of the

43
00:02:03,734 --> 00:02:07,200
gift card. The output will be a nested vector

44
00:02:07,201 --> 00:02:09,633
of two dimensional vector, where each entry

45
00:02:09,634 --> 00:02:11,500
will contain the pair of products.

46
00:02:11,501 --> 00:02:16,966
[No Audio]

47
00:02:16,967 --> 00:02:19,966
We will first declare an empty HashSet, which

48
00:02:19,967 --> 00:02:22,566
we will use for efficient searching through the vector.

49
00:02:22,567 --> 00:02:28,466
[No Audio]

50
00:02:28,467 --> 00:02:30,500
This specific use of the HashSet will be

51
00:02:30,501 --> 00:02:33,700
explained in a while. To capture the final

52
00:02:33,701 --> 00:02:36,000
output, which we will return from this

53
00:02:36,001 --> 00:02:38,000
function, I will declare a two dimensional

54
00:02:38,001 --> 00:02:39,500
vector called offers.

55
00:02:39,501 --> 00:02:47,466
[No Audio]

56
00:02:47,467 --> 00:02:49,666
Now before going further, let us look at the

57
00:02:49,667 --> 00:02:52,566
vector of values again. To implement the

58
00:02:52,567 --> 00:02:54,966
problem, we will first pick up the first

59
00:02:54,967 --> 00:02:57,066
value, and then iterating through all the

60
00:02:57,067 --> 00:02:59,666
values to check if the first value can be

61
00:02:59,667 --> 00:03:02,700
paired up with any other element. In the same

62
00:03:02,701 --> 00:03:05,066
way, we will process the second element, and

63
00:03:05,067 --> 00:03:06,900
we'll keep on checking it with all the

64
00:03:06,901 --> 00:03:09,400
remaining elements in the list. One way of

65
00:03:09,401 --> 00:03:11,700
implementing this problem would be, to pick up

66
00:03:11,701 --> 00:03:13,700
the first value, and then iterating through

67
00:03:13,701 --> 00:03:15,666
all the values to check if the first value

68
00:03:15,667 --> 00:03:17,700
can be paired up with any of the other

69
00:03:17,701 --> 00:03:21,133
elements. In the same way, we will

70
00:03:21,134 --> 00:03:23,100
process the second element that will

71
00:03:23,101 --> 00:03:25,033
keep on checking it with all the remaining

72
00:03:25,066 --> 00:03:27,766
elements in the list. This is however an

73
00:03:27,767 --> 00:03:30,300
inefficient solution, because it will require us

74
00:03:30,301 --> 00:03:33,533
to use two nested loops. The outer loop will

75
00:03:33,534 --> 00:03:35,866
be used to pick up the values one at a time,

76
00:03:36,100 --> 00:03:38,066
and then the inner loop will be used to check

77
00:03:38,100 --> 00:03:40,466
it against the list of values for possible

78
00:03:40,467 --> 00:03:43,500
pairing. We will use a more efficient

79
00:03:43,501 --> 00:03:46,700
solution using the HashSet and using a single loop.

80
00:03:47,000 --> 00:03:48,733
The loop will be used to iterate

81
00:03:48,734 --> 00:03:51,133
through all the values, and if the value can

82
00:03:51,134 --> 00:03:53,833
be paired up with any value that is already

83
00:03:53,834 --> 00:03:56,500
in the HashSet, then we will add it to the

84
00:03:56,501 --> 00:03:59,400
list of possible pairs. In any other case, we

85
00:03:59,401 --> 00:04:02,066
will add it to the HashSet. This may look a

86
00:04:02,067 --> 00:04:04,800
bit hard to comprehend right now, but it will

87
00:04:04,801 --> 00:04:07,233
start to make sense once we implement this.

88
00:04:07,733 --> 00:04:09,633
Let's start with the implementation.

89
00:04:11,000 --> 00:04:14,366
I will first use a loop for iterating

90
00:04:14,367 --> 00:04:16,033
through all the elements in the vector.

91
00:04:16,034 --> 00:04:22,550
[No Audio]

92
00:04:22,551 --> 00:04:24,966
Next, I will define a variable called

93
00:04:24,967 --> 00:04:27,866
difference, which will subtract the value of

94
00:04:27,867 --> 00:04:30,000
the currently processed word from the list.

95
00:04:30,001 --> 00:04:37,466
[No Audio]

96
00:04:37,467 --> 00:04:39,500
Next, we will inspect the HashSet which

97
00:04:39,501 --> 00:04:42,600
initially does not contain any value. We will

98
00:04:42,601 --> 00:04:45,600
see if any value in the HashSet has a value

99
00:04:45,601 --> 00:04:48,166
equal to the difference or not. If we are

100
00:04:48,167 --> 00:04:50,000
unable to find a value equal to the

101
00:04:50,001 --> 00:04:53,289
difference, then we will add it to the HashSet.

102
00:04:53,290 --> 00:04:59,333
[No Audio]

103
00:04:59,334 --> 00:05:01,600
The get function needs a reference to

104
00:05:01,601 --> 00:05:05,366
the value, and the is_none will return true, if

105
00:05:05,367 --> 00:05:07,900
there is no value found in the HashSet after

106
00:05:07,901 --> 00:05:10,733
calling the get function. In any other case,

107
00:05:10,734 --> 00:05:12,866
we will add the value to the offers along

108
00:05:12,867 --> 00:05:14,466
with the difference, because the difference

109
00:05:14,467 --> 00:05:16,900
value do exist in the HashSet.

110
00:05:16,901 --> 00:05:23,400
[No Audio]

111
00:05:23,401 --> 00:05:25,700
This means that, we will only add a value to

112
00:05:25,701 --> 00:05:28,166
the HashSet, when we are unable to find the

113
00:05:28,167 --> 00:05:30,033
difference value in the HashSet.

114
00:05:31,000 --> 00:05:32,800
Let us cargo run this.

115
00:05:32,801 --> 00:05:37,866
[No Audio]

116
00:05:37,867 --> 00:05:40,000
That is great. Let us now see

117
00:05:40,001 --> 00:05:42,900
how this will work. For the first time we have

118
00:05:42,901 --> 00:05:46,366
a value of 11, the difference will be 39.

119
00:05:46,800 --> 00:05:49,166
Since there is nothing in the HashSet, therefore,

120
00:05:49,900 --> 00:05:51,800
therefore the get function will return a

121
00:05:51,801 --> 00:05:54,700
true, and therefore, we will add the value to

122
00:05:54,701 --> 00:05:57,433
the HashSet. The next value is 34, which the

123
00:05:57,434 --> 00:06:00,866
difference will be 20. And since 20 also does

124
00:06:00,867 --> 00:06:03,400
not exist, exist in the HashSet, therefore,

125
00:06:03,766 --> 00:06:06,466
it will also be inserted.

126
00:06:06,600 --> 00:06:11,866
Similarly, the value of 55, 34, 45, 10, and 19 will

127
00:06:11,867 --> 00:06:15,300
also be inserted. When we reach at a value of

128
00:06:15,301 --> 00:06:18,500
20, the difference will be 30, and the value 30

129
00:06:18,501 --> 00:06:20,733
exist in the HashSet, therefore, the value

130
00:06:20,734 --> 00:06:23,833
20 will not be inserted in the HashSet, but

131
00:06:23,834 --> 00:06:25,966
it will be rather added to the offers list

132
00:06:26,000 --> 00:06:28,900
along with the value of 30. This means that,

133
00:06:28,901 --> 00:06:31,500
we will only add a value to the HashSet, when

134
00:06:31,501 --> 00:06:34,366
it cannot be currently paired with any other

135
00:06:34,367 --> 00:06:36,433
existing value in the HashSet.

136
00:06:38,000 --> 00:06:39,633
You may also note that since

137
00:06:39,634 --> 00:06:41,266
each value can only be paired

138
00:06:41,267 --> 00:06:43,833
up with a single value, that is the value 30

139
00:06:43,834 --> 00:06:46,633
can only be paired up with a value 20, and

140
00:06:46,634 --> 00:06:49,600
cannot be paired up with any other value, so

141
00:06:49,666 --> 00:06:52,833
having 30 in the HashSet is sufficient for

142
00:06:52,834 --> 00:06:55,800
us, and we do not need to store the value 20.

143
00:06:56,633 --> 00:06:58,966
As pointed out before, searching in HashSet

144
00:06:58,967 --> 00:07:01,133
is very fast and takes constant amount of

145
00:07:01,134 --> 00:07:03,566
time, therefore, it does not involve any

146
00:07:03,567 --> 00:07:05,966
significant overhead in terms of time.

147
00:07:06,233 --> 00:07:08,933
Moreover, since we are using only a single

148
00:07:08,934 --> 00:07:10,833
loop, therefore, our solution is more

149
00:07:10,834 --> 00:07:13,500
efficient compared to using nested loops for

150
00:07:13,501 --> 00:07:15,233
searching out items in the list.

151
00:07:16,233 --> 00:07:18,933
Finally, also please note that, our solution is based

152
00:07:18,934 --> 00:07:21,233
on the assumption that the values will not

153
00:07:21,234 --> 00:07:23,800
repeat, for repeating values the solution may

154
00:07:23,801 --> 00:07:26,066
be a bit different. That is it for this

155
00:07:26,067 --> 00:07:28,300
particular tutorial. See you again with

156
00:07:28,333 --> 00:07:30,166
another interesting real life problem.

157
00:07:30,167 --> 00:07:31,233
Do come back again and

158
00:07:31,234 --> 00:07:33,400
until then happy Rust programming.

159
00:07:33,401 --> 00:07:42,833
[No Audio]