1
00:00:00,410 --> 00:00:08,090
‫Now let's talk about a very common interview question that uses a hash table as the solution.

2
00:00:08,450 --> 00:00:13,070
‫And the question will take a few different forms, but it will look something like this.

3
00:00:13,070 --> 00:00:15,710
‫They'll give you two arrays.

4
00:00:15,950 --> 00:00:21,800
‫I'm going to use vectors here because it will make it where we can write a little bit cleaner code,

5
00:00:21,800 --> 00:00:24,620
‫but the concepts will be exactly the same.

6
00:00:24,950 --> 00:00:31,790
‫So what we're going to do here is check to see if these two vectors have an item in common.

7
00:00:31,790 --> 00:00:36,770
‫And you can look at this and see that they do they have that five in common.

8
00:00:37,040 --> 00:00:44,750
‫So I'm going to start out with the primitive way of solving this where we do not use a hash table and

9
00:00:44,750 --> 00:00:51,230
‫we'll do this by using a for loop to go through the first vector and then a nested for loop that will

10
00:00:51,230 --> 00:00:56,420
‫compare each of the items in the second vector to the item and the first vector.

11
00:00:56,420 --> 00:01:03,080
‫So we'll check to see if any of these are the number one and then we'll have that first for loop moved

12
00:01:03,080 --> 00:01:03,950
‫to the next item.

13
00:01:03,950 --> 00:01:08,150
‫And then we loop through this second vector again.

14
00:01:08,420 --> 00:01:15,140
‫And then finally we move to this last item and do the comparisons again and we find a match.

15
00:01:15,680 --> 00:01:20,450
‫So in this case, N is three and we had nine operations.

16
00:01:20,450 --> 00:01:28,550
‫So this is O of N squared and this big o result should be obvious since we have a loop within a loop.

17
00:01:28,880 --> 00:01:33,770
‫So now let's shrink this down and write the code with a loop within a loop.

18
00:01:34,070 --> 00:01:40,460
‫We'll call our function item and common will pass it the two vectors and this for loop will loop through

19
00:01:40,460 --> 00:01:41,810
‫the first vector.

20
00:01:41,840 --> 00:01:45,830
‫This nested for loop will loop through the other vector.

21
00:01:45,950 --> 00:01:51,170
‫If there's ever a match if I ever equals j we return true.

22
00:01:51,380 --> 00:01:55,910
‫And if we go through the four loops and we don't find a match, we'll return false.

23
00:01:56,150 --> 00:01:59,480
‫So just to be clear, this code will work.

24
00:01:59,480 --> 00:02:03,530
‫But this is not the solution they'll be looking for in the interview.

25
00:02:03,770 --> 00:02:07,520
‫But let's flip over and look at this and vs code.

26
00:02:08,220 --> 00:02:12,860
‫And remember, you do need this include statement because we're using vectors.

27
00:02:12,870 --> 00:02:15,540
‫This is the code that we just wrote here.

28
00:02:15,810 --> 00:02:21,600
‫I'm going to scroll up and in our main function this creates those two vectors.

29
00:02:21,810 --> 00:02:28,890
‫And with this line here, we'll run the item in common function and output the result and remember this

30
00:02:28,890 --> 00:02:30,380
‫returns a boolean.

31
00:02:30,390 --> 00:02:32,970
‫If it's true, it's going to return one.

32
00:02:32,970 --> 00:02:35,820
‫And if it's false, it's going to return zero.

33
00:02:36,120 --> 00:02:37,590
‫So I'll run this.

34
00:02:38,280 --> 00:02:44,100
‫And you can see that this is returned one, because we do have an item in common that number five.

35
00:02:44,460 --> 00:02:49,140
‫So I'm going to come up here and replace this five with a six.

36
00:02:49,620 --> 00:02:51,480
‫And now I'll run this again.

37
00:02:52,080 --> 00:02:55,140
‫And you can see that this has returned zero.

38
00:02:55,500 --> 00:02:58,140
‫So this is working the way we would expect.

39
00:02:58,620 --> 00:03:01,020
‫So now let's flip back.

40
00:03:01,470 --> 00:03:06,360
‫So now let's look at how we would solve this with a hash table.

41
00:03:06,630 --> 00:03:12,990
‫So what we're going to do first is have a four loop that copies each of the values from the first vector

42
00:03:12,990 --> 00:03:14,370
‫into this hash table.

43
00:03:14,730 --> 00:03:19,260
‫So we'll take that, number one and make it a key and a key value pair.

44
00:03:19,500 --> 00:03:22,020
‫I'll just make the value true.

45
00:03:22,320 --> 00:03:25,210
‫And the value is something that we're not going to use here.

46
00:03:25,230 --> 00:03:27,620
‫We're just going to be using the keys.

47
00:03:27,630 --> 00:03:33,810
‫So as we loop through, we'll add the three and we'll just make that true and then we'll add the five

48
00:03:33,810 --> 00:03:37,710
‫will make that the key and the value true on that one as well.

49
00:03:38,100 --> 00:03:42,870
‫And then we'll have another four loop that loops through the other vector.

50
00:03:43,080 --> 00:03:49,680
‫And what that four loop is going to do is C, is this number to a key in the hash table.

51
00:03:49,710 --> 00:03:55,650
‫And remember, when you're looking for a key in a hash table that is o of one and that we'll do the

52
00:03:55,650 --> 00:04:00,510
‫same thing with the four and the five, and then we find our match.

53
00:04:00,870 --> 00:04:04,590
‫So in this case, we just ran through each of the vectors.

54
00:04:04,590 --> 00:04:10,020
‫Once in was three, we did two in operations.

55
00:04:10,020 --> 00:04:18,780
‫We drop the constant and this is o of n and o of n is much more efficient than o of in squared.

56
00:04:18,780 --> 00:04:23,760
‫So this is going to be the solution they're really looking for in an interview.

57
00:04:24,270 --> 00:04:27,270
‫So now let's start writing this code.

58
00:04:27,300 --> 00:04:35,220
‫Notice that this line is exactly the same, which means anyone that is interacting with this function

59
00:04:35,490 --> 00:04:38,910
‫will pass vectors to it exactly the same way.

60
00:04:39,300 --> 00:04:42,090
‫So we're going to need to create a hash table.

61
00:04:42,510 --> 00:04:48,930
‫The built in hash table that we're going to use is going to be an unordered map and it will have an

62
00:04:48,930 --> 00:04:52,260
‫integer for the key and a boolean for the value.

63
00:04:52,260 --> 00:04:54,330
‫And we'll call it my map.

64
00:04:54,780 --> 00:04:59,550
‫And that first for loop starts out the same way as it did last time.

65
00:04:59,970 --> 00:05:06,630
‫But inside of the for loop, we're just copying everything into the my map unordered map that we just

66
00:05:06,630 --> 00:05:07,440
‫created.

67
00:05:07,830 --> 00:05:15,120
‫So as we are moving through that vector, we're inserting the value I from that vector and that will

68
00:05:15,120 --> 00:05:16,650
‫have a second for loop.

69
00:05:16,650 --> 00:05:19,790
‫But the key here is this is not a nested for loop.

70
00:05:19,800 --> 00:05:22,500
‫These four loops are one after the other.

71
00:05:22,800 --> 00:05:29,610
‫And as we are looping through that second vector with a second for loop, we're just checking to see

72
00:05:29,610 --> 00:05:33,480
‫is each item in that unordered map.

73
00:05:33,810 --> 00:05:37,080
‫If there is ever a match, we return true.

74
00:05:37,500 --> 00:05:44,910
‫And if we run all the way through this for loop and we don't find any matches, we will return false.

75
00:05:45,420 --> 00:05:50,160
‫So now let's flip over and take a look at this code in vs code.

76
00:05:51,060 --> 00:05:57,930
‫So make sure that you have both of these include statements because we're using unordered maps and vectors

77
00:05:57,930 --> 00:05:58,440
‫here.

78
00:05:58,830 --> 00:06:06,030
‫And I'll scroll up and this is our new item in common function that we just created and I'll scroll

79
00:06:06,030 --> 00:06:07,020
‫up again.

80
00:06:07,620 --> 00:06:12,150
‫And in our main function we have the two vectors that we created last time.

81
00:06:12,360 --> 00:06:17,910
‫And the way that we're passing the vectors to the item in common function is exactly the same.

82
00:06:18,450 --> 00:06:21,990
‫So you can see here that we have an item in common this number five.

83
00:06:21,990 --> 00:06:23,700
‫So we'll expect this to return.

84
00:06:23,700 --> 00:06:25,800
‫True and I'll run this.

85
00:06:26,160 --> 00:06:29,790
‫And you can see up here that this has returned true.

86
00:06:30,360 --> 00:06:34,140
‫And I'm going to come up here and change this five to a six.

87
00:06:34,950 --> 00:06:36,570
‫And I'll run this again.

88
00:06:37,080 --> 00:06:39,540
‫And you can see that this has returned.

89
00:06:39,540 --> 00:06:40,470
‫False.

90
00:06:41,030 --> 00:06:46,310
‫So the key thing to remember here is that both ways of doing this will work.

91
00:06:46,310 --> 00:06:48,710
‫It will give you the correct answer.

92
00:06:48,980 --> 00:06:54,890
‫The difference is how efficiently your code works one way versus the other.

93
00:06:55,220 --> 00:07:00,290
‫So in an interview, they're not really asking, can you make it work?

94
00:07:00,620 --> 00:07:02,510
‫Can you make this work?

95
00:07:02,510 --> 00:07:08,090
‫As an o of n function is the real interview question.