Google Coding Interview Question and Answer #1: First Recurring Character

Key Takeaways

here's a coding interview question from Google this is a fairly simple problem so it's probably a sort of question that's often asked on the phone interview and here's the problem you're given a string and you're supposed to write a function that takes the string and returns the first recurring character in that string so for example if you're given this string as the input ABC a there's only one recurring character in the string a so your function should return a if you're given this string BC ABA you see that there are two recurring characters B and a and the first recurrent character is B so you sort of return be from your function if you're given this string ABC there is no recurring character in this string so your function should return either now or none depending on the language that you're using now for practice I do recommend that you pause the video right here think about it for a second and then come back to the video now when you're given this problem initially you may come up with a naive solution like this one in our naive solution we're going to first check the first character in the given string for example this string on the screen the first character in the string is d and we're going to ask ourselves is there another occurrence of the same character D in the subsequent characters we can check this character by character and the answer is no there's no other occurrence of D so we can move on to the next character B and then we can go through the same process ask ourselves is there another occurrence of B in the subsequent characters check that character by character and once we get to this other occurrence of B we'll know that B is the first recurring character in the string so we can just return B from our function and we're done with this naive solution we're essentially checking every potential pair of characters in the string to see if there is any recurring character and so the number of pears we need to check with this naive solution would be and choose two or n times n minus 1/2 which is equal to Big O of N squared and so the time complexity or the run time for this algorithm would be Big O of N squared let's see if we can do any better than that and here's a more efficient solution to this problem instead of checking every potential pair of characters we're going to go through this string only once from left to right character by character and as we see a character we're going to store it in a data structure such as a set a dictionary or hash table to show that we've seen this character already so for example when we're examining the first character D we're going to store it let's say in a hash table and in a hash table we need a key value pair so we're going to use the character as the key and the value could be anything but let's just use one here to show that we've seen this character once and when we go to the next character in this case B right here we need to first ask ourselves have we seen this character already before this character and we can do that with this hash table and the answer is no because B is not in this hash table yet so we're going to put B in this hash table as the key and the value will be 1 again to show that we've seen this character once we'll keep going like that until we get to a character that we've seen already which is the second occurrence of B right here in this case and we'll know that we've seen this character already because it's already in the hash table of course and at that point we can return B in this particular case from our function and we're done with this solution because we only go through this string once from left to right the time complexity or the runtime for this algorithm is Big O of n where and is the number of characters in the string now let's see what this solution by look like in code we're going to define our function first recurring which takes the given string of course for example this one and we turns the first recurring character in that string we're going to use suit code to explain this code the first step in our function is to define counts which is the dictionary or the hash table we're going to use to keep track of each character that we've seen and then we're going to run a for loop for each character in the given string or fork our in given string and then if this character char is already in the dictionary or the hash table then that means this is the first recurring character so we turn that character and if not for example if we're examining this first character in this particular example D put that character as a key in this dictionary or hash table and the value corresponding to that will be 1 and again this value could be anything but I'm just using one to show that we've seen this character once and here you might notice that I'm not using an else statement here but that's just a style issue so you could use it if you'd like to now after this for loop if we haven't returned yet that means that there is no recurring character in the string so in that case either return none or no depending on the language and that's my solution alright guys thanks so much for watching this video one interesting variation to this problem is to find the first non recurring character in the string instead of finding the first recurring character I covered that problem and many other problems in my brand new udemy course 11 essential coding interview questions in which I cover 11 of the most essential coding interview questions to master for your next coding interview there's a discount code below in case you're interested in taking the course ok thanks so much and I'll see you soon