Amazon Coding Interview Question - firstNonRepeatingCharacter

yeah coders today we are going to be answering a Amazon coding interview question this is called first non-repeating character and this is according to code signal if you I'm checked out all in the description if you're new here please like and subscribe helping you grow my channel well yeah let's get into it this is could be asked by Amazon this question I actually am familiar with and I was asked this during my google screening interview for the internship position but still very interesting let's get into it all right so instead of reading the confusing problem descriptions I do like to just explain this to you guys so we don't have to read and get confused basically what we're gonna do is solve a function called first non-repeating character our input is going to be one string so we're gonna get one string maybe it's like this or this or this only characters in the string are gonna be lowercase English letters so there's no numbers there's no special characters it's you know letter A through Z all lowercase it's gonna be at least one character and it could be up to like 100,000 characters so it give you a really long string really short but we're not worrying about empty strings here now our objective is to find the first non repeating character in the string that we're given right so that means that a character is non repeating if there's not if there's only one right so if you see there's three A's that's what repeating character a is a repeating character three sees three E's but you know you can see that B right here is clearly not in the string again so that is non repeating d is not repeating and F is not repeating as well we want to find the first of these so let's just go through this example or all these examples for that matter so a is repeating B is not repeating C's repeating DS not repeating so we see E's repeating and F is a non repeating so we see that we have three options here B D and F those are all non repeating right but we want the first one right so the first one we come across is B so the answer is going to be B just a character B in our next string we're looking at we have ABC there's so let's look at a first a is repeating BB is repeating C C is not repeating neither is D but C is you know the first not repeating one so the answer here is just gonna be the character C now depending on your interviewer usually when you have a situation like this where there is no repeating characters or you can't solve the function you know sometimes you'll return negative one for an answer in this case we're returning characters so in this case we don't have any non repeating characters you can see a has there's more than one a there's more than one B C is also repeating so there's no other characters that are in here so in that case we're just gonna return an underscore that's what we're gonna do to solve this problem so we understand the objective right we understand we are given a string length one to 100,000 lowercase English letters and we need to somehow you know whether we loop through or whatever method we're gonna choose to figure this out find the first non repeating character meaning that characters only in there once and the first occurrence of that in the string we're given and we have to return that otherwise we just return that underscore so how do we do this how do we accomplish our objective how do we find the first non repeating character I always just think right off the bat when I try and solve a problem like oh I have a string or I have an array let's loop through it right you loop through it and check each element or each character but I mean hey how do I know if it's repeating I see another a here and then how do I do I check with the index before I do it like it doesn't you need there's no way to reference other parts of the string okay how do I know if it's I've seen a duplicate you know there's no way with just a for loop I'm gonna need like a data structure I guess I could do a two pointer like brute force right I always start with brute force and I mean if we did this we could have you know our outer loop is an A and then we just loop through the rest of the string and we could see up there's duplicates so maybe we you know go up and now we go back up duplicate so up up duplicates up so we go up and then we get to B and then we're like boom boom boom and we don't count the comparison at the same index right that's this there's only one letter so the same index we don't compare is this would be okay so we don't see a be another B in the string so if you use two pointers you could do that but unfortunately that solution is o of N squared which is gonna be way too slow for Amazon way too slow for any of these big tech companies all right so here's the implementation of our oven squared solution where we you know most cases it's a double for loop right we're for outer for loop here and then we have our inner for loop what we're doing is this is the red arrow and it's going slower and then the yellow arrow goes and looks for those duplicates if it sees a duplicate it will modify this boolean value and say hey we saw a duplicate and then once we're finished looking with all the yellow arrows we're gonna say okay did we see no duplicates if so then we returned that character right and it works out perfectly because the outer loops going in a linear fashion so the inner loop just goes looks for those duplicates if there are none then the first character that we saw that doesn't have duplicates that's we return otherwise if we don't find any of them that don't have duplicates then we're going to just we're just gonna return this under underscore so how can we improve this how can we not do ov N squared well let's think about this if it's non repeating that means it's only in there once and if we want to know how many times the character is in the string we could use a data structure that keeps track of you know the number of times something occurs right and what would be good for that one thing that can help us keep track of the number of times the character occurs is a hash map and a hash map is good because it has key value pairs so the keys could be the characters and the values could be the number of times they occur so the idea here is we have this hash map the key is the character the value is the num times we see it in the string so we're gonna loop in the first character we see is an a so we increment the count of it okay so now we've seen one a now we go to the next day and now the count will be two next day count is three then we go on to Abby we haven't seen Abby yet let's increment the count see another see another c d e another e and all right so that is the idea we loop through our string only once one linear loop oh then and we fill their hash map up and we now know how many times each character occurs but like a hash set these hash maps aren't sorted so we can't get the first non-repeating character by kind of just at referencing it from this hash map there's no way to do that you know there's no ordering in a hash map so what we actually have to do is loop through again in the lookups luckily in a hash map our constant time meaning they don't require any time so it's not extra time to look up you know the count of a or the count of how many times B occurs in the string so what we can do is we can look at a as we loop through again we could say how many times does a occur three okay how many times they occur three how many times they occur three in the first time we see a character and our second loop through that has a count of one when we look this up it's constant time it takes no time to look this up hey how many bees are in this string 1 then we know we found the first non repeating character so altogether it was a linear loop oh of n where n is the size of the string we had to go boom boom boom boom boom boom fill up the entire hash map with that one loop from beginning to end and then there's no extra time to reference from the hash map so we just do one extra loop below and we go boom boom boom up to here now the worst case time complexity of this solution is o of 2n and in programming 2n is nothing to 1 is an exponential or anything crazy so in these coding interviews we drop the constant so really it's just oh then still and that is an optimal solution that's going to be accepted at all these companies oh then linear is what we strive for with most of these problems so be proud that we accomplished this goal and so here's the code for our hashmap version of the solution or we have a hash map with character as the key integer is the val to count the number of times the characters in the string we loop through the string the first time if it's already in the hash map we'll increment the count of it and if it's not we'll just put it in there we saw for the first time this is the loop where we filled up the hash map with the count of each character in the string so the last thing we have to do is just one extra linear loop through that string and if the the first character we find that has a count or frequency of 1 within that string we just return it if you don't find any then you get that underscore again so the hash map in this case is probably the way to go another way you can actually create this hash map instead of like the built in hash map data structure that's in most languages is you can create an integer array of size 26 where each index of the array represents the count of that character of the alphabet so right this is how many a's are in the string this is how many bees sees all the way down to Z and you could access them by index so the 0th index it's like the indexes of the alphabet as an array and there's a really nice thing you can do with string problems when you're dealing with the characters of the string it's really convenient and yeah it comes in handy so what would happen is we would see this a and then we increment the value in the first index of the alphabet then we'd see another a and we didn't comment it again and so on right you move through the whole string and then there's a result it's three A's one B three C's one D threes and one half right so now you can access the count of each character just by referencing the correct index in the array right so you loop through it once and you fill that up just like the hash map it's basically the same thing then you go through it again and you loop and then you check the index of this letter in the array which is 0 and keep going 0 0 it's 3 until you find a character where the count of it is 1 right so we find that if B same exact thing as the hashmap thing so here's what that would look like in code you basically just have this array you know for every letter in the alphabet int array with the count for count of each letter you do that one for loop o oven where you fill it up with the count of each character you reference the index by doing ASCII subtraction so the current character was a a minus a would be zero and then it would reference index zero into that array and it would increment the value by one so all its 26 zeros at first and then as you go through you do the letter - the letter and it gets the correct map to the correct index in this array and increments the count then once you're done you have all the counts of each character the frequency of each character you just loop through one more time in the first character you find where the the frequency of it is 1 then you just return that otherwise you return that underscore this once again is just this is a linear time o then because it loops through the whole string once this is linear time ova and loops to the whole string once and then we do have this space but it's only size 26 so it's not it's an int array of size 26 not a big deal really and one of the very last solutions I would cover is there are sometimes built-in methods and programming languages that can find the first index of in the last index of explicit a character in a string so for example we could check if the first index of by calling this method which would give us a value of 0 for a is equal to the last index of which is not because the last index of a is 0 1 2 index 2 then that would be the first that would be that wouldn't have any duplicates right the if the first index of the first occurrence of that character is equal to the last occurrence that means there's only one occurrence of that character means there's no duplicate so we can kind of go through check this condition on each of these characters until we find one where the first occurrence which is at index 0 1 2 3 is equal to the last index of which is also at index 3 and once we find that we can just return that value so in code that would just look something like this you're looping through that string and you're just checking it each character if the first index of it this index of method will look up the first index of that character is equal to the last index of it that means there's only one of those in the string we find one of those you know it's not repeating clearly and it was the first one we saw because we're checking every character as we go through so we return it otherwise we return the underscore so that is it for first non repeating character once again this is an Amazon coding interview question so hopefully you are prepared now and you understand this and if you interview at Amazon you can solve it please leave a like and subscribe I got my study guide for technical interviews on my patreon if you want to support me please everything is in the description and yeah we got the time flexi down to linear which is pretty much the goal on most of these some of them you can't really achieve that but a lot of problems you really want to get down to linear run time so we got down there pick there's a variety of those solutions if you want to pick from them but of course you're gonna want that linear solution you're not gonna want to choose the double for loop n squared solution so thank you guys for watching this video I think yeah that's it I guess and the next time we'll do another one I guess alright that was a bad outro but it's okay I'll see you guys in the next video peace

Channel: Nick White

Views: 526,054

Rating: 4.8537021 out of 5

Keywords: coding, programming, computer science, software engineering, google, tech, technology, algorithms, data structures, developers, software development, google coding interview, coding interview, technical interview, coding interview questions, firstNonRepeatingCharacter, code signal, arrays, fang, time complexity, hash map

Id: 5co5Gvp_-S0

Length: 14min 29sec (869 seconds)

Published: Fri Jan 31 2020