‫Now let's talk about a very common interview question that uses a hash table as the solution.
‫And the question will take a few different forms, but it will look something like this.
‫They'll give you two arrays.
‫I'm going to use vectors here because it will make it where we can write a little bit cleaner code,
‫but the concepts will be exactly the same.
‫So what we're going to do here is check to see if these two vectors have an item in common.
‫And you can look at this and see that they do they have that five in common.
‫So I'm going to start out with the primitive way of solving this where we do not use a hash table and
‫we'll do this by using a for loop to go through the first vector and then a nested for loop that will
‫compare each of the items in the second vector to the item and the first vector.
‫So we'll check to see if any of these are the number one and then we'll have that first for loop moved
‫to the next item.
‫And then we loop through this second vector again.
‫And then finally we move to this last item and do the comparisons again and we find a match.
‫So in this case, N is three and we had nine operations.
‫So this is O of N squared and this big o result should be obvious since we have a loop within a loop.
‫So now let's shrink this down and write the code with a loop within a loop.
‫We'll call our function item and common will pass it the two vectors and this for loop will loop through
‫the first vector.
‫This nested for loop will loop through the other vector.
‫If there's ever a match if I ever equals j we return true.
‫And if we go through the four loops and we don't find a match, we'll return false.
‫So just to be clear, this code will work.
‫But this is not the solution they'll be looking for in the interview.
‫But let's flip over and look at this and vs code.
‫And remember, you do need this include statement because we're using vectors.
‫This is the code that we just wrote here.
‫I'm going to scroll up and in our main function this creates those two vectors.
‫And with this line here, we'll run the item in common function and output the result and remember this
‫returns a boolean.
‫If it's true, it's going to return one.
‫And if it's false, it's going to return zero.
‫So I'll run this.
‫And you can see that this is returned one, because we do have an item in common that number five.
‫So I'm going to come up here and replace this five with a six.
‫And now I'll run this again.
‫And you can see that this has returned zero.
‫So this is working the way we would expect.
‫So now let's flip back.
‫So now let's look at how we would solve this with a hash table.
‫So what we're going to do first is have a four loop that copies each of the values from the first vector
‫into this hash table.
‫So we'll take that, number one and make it a key and a key value pair.
‫I'll just make the value true.
‫And the value is something that we're not going to use here.
‫We're just going to be using the keys.
‫So as we loop through, we'll add the three and we'll just make that true and then we'll add the five
‫will make that the key and the value true on that one as well.
‫And then we'll have another four loop that loops through the other vector.
‫And what that four loop is going to do is C, is this number to a key in the hash table.
‫And remember, when you're looking for a key in a hash table that is o of one and that we'll do the
‫same thing with the four and the five, and then we find our match.
‫So in this case, we just ran through each of the vectors.
‫Once in was three, we did two in operations.
‫We drop the constant and this is o of n and o of n is much more efficient than o of in squared.
‫So this is going to be the solution they're really looking for in an interview.
‫So now let's start writing this code.
‫Notice that this line is exactly the same, which means anyone that is interacting with this function
‫will pass vectors to it exactly the same way.
‫So we're going to need to create a hash table.
‫The built in hash table that we're going to use is going to be an unordered map and it will have an
‫integer for the key and a boolean for the value.
‫And we'll call it my map.
‫And that first for loop starts out the same way as it did last time.
‫But inside of the for loop, we're just copying everything into the my map unordered map that we just
‫created.
‫So as we are moving through that vector, we're inserting the value I from that vector and that will
‫have a second for loop.
‫But the key here is this is not a nested for loop.
‫These four loops are one after the other.
‫And as we are looping through that second vector with a second for loop, we're just checking to see
‫is each item in that unordered map.
‫If there is ever a match, we return true.
‫And if we run all the way through this for loop and we don't find any matches, we will return false.
‫So now let's flip over and take a look at this code in vs code.
‫So make sure that you have both of these include statements because we're using unordered maps and vectors
‫here.
‫And I'll scroll up and this is our new item in common function that we just created and I'll scroll
‫up again.
‫And in our main function we have the two vectors that we created last time.
‫And the way that we're passing the vectors to the item in common function is exactly the same.
‫So you can see here that we have an item in common this number five.
‫So we'll expect this to return.
‫True and I'll run this.
‫And you can see up here that this has returned true.
‫And I'm going to come up here and change this five to a six.
‫And I'll run this again.
‫And you can see that this has returned.
‫False.
‫So the key thing to remember here is that both ways of doing this will work.
‫It will give you the correct answer.
‫The difference is how efficiently your code works one way versus the other.
‫So in an interview, they're not really asking, can you make it work?
‫Can you make this work?
‫As an o of n function is the real interview question.