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

Find the first recurring character in the given string!
A variation of this problem: find the first NON-recurring character. This variation problem and many others are covered in my Udemy course, 11 Essential Coding Interview Questions: www.udemy.com/11-essential-co...
(You'll get a discount through the above link.)

[@CSDojo]

Hi guys! I actually made a mistake in my first solution.. sorry. The first recurring character in ABBA should be B, and not A. Also, I should've used a set in my second solution. The time complexity is the same either way, though.

[@ACarbonellBeceiro]

You don't loop, but query it directly with a given key, in this case the char itself. Example: hashTable.has('A') // true or false if the table has that key or: hashTable.get('A') != null // true or false if the table has that key I did show 2 variations because it can vary from one language to another. The .has() method is just a helper that some implementations offer. The second example can cause problems if we actually want to store null values, but for this case works fine. A hashtable has a constant access time, O(1), so the overall time complexity does not increment.

[@kumakun3861]

too late over half a million ppl watched lmaooo

[@IceQub3]

Lol I just thought about that before resuming the video, my solution tho is using a int with size of n bits. Then I check if the bit in the place of the character is on or off. If it on return the number. If it off turn it on. As that more efficient in memory (the hash can be stored in a register). If I want to redefine the problem to result A in a ABBA case my solution is failing because I can't know the order of the characters in the input string. In such case using a table won't help ether because hash table don't keep order of inserion ether. I don't have a real good simple solution for that problem right now. As the efficient way I am thinking about is creating the hash in a way that every recurring characters are marked with a on bit. Then looking for the first 'on' character in the string. I find my solution not simple because it has those 2 steps that I need to repeat...

[@cyhlau]

For "first solution" he is referring to the O(n^2) solution that scan each character and try to find a match in the remaining characters. Using that solution, the input "ABBA" would return 'A', but the correct answer should be 'B', according to the question definition.

[@fahadjaved9855]

CS Dojo Assuming the characters can only be ASCII (or any character encoding with a constant number of characters), your second solution has an O(1) runtime complexity. Not O(n) because your string can be 256000 characters long but you will see a repeated character after 256.

[@johannesvahlkvist]

"we're going to use pseudo code to explain this code" > uses python LOL

[@asthamalhotra2345]

I was thinking the same😁

[@algoseekee]

Probably it was a subtle trolling 😉

[@HandledToaster2]

LOL

[@play005517]

isn't Python just a runnable pseudo code?

[@HandledToaster2]

@@play005517 no its real code, Reddit works on Python. It's just weird

[@ilustrado7291]

What if I just wanna sweep the floor and clean the toilets?

[@LouisNgatale]

lmao

[@SanthoshKaitheri]

For that, u dont need to fuck around a Coding Video.

[@WakeUpSmellTheCoffee]

Plot twist: floor sweepers and toilet cleaners at Google are robots programmed by these coders. Our job prospects just got lowered! 🤪

[@YoungOrbital]

Classic miss direction and you fell for it, the only purpose for this video is to asses their future janitor if he can work out if he has cleaned a toilet twice during his shift.

[@adarshinginshetty484]

Watch a toilet cleaning tutorial.that will help u more than a coding video.

[@sompamalakar]

Instead of using a HashMap, you could use a bit vector as the hash map. Set the bit of the character in the bit vector while you encounter it and if the bit is already set, thats the first recurring character.

[@firefoxmetzger9063]

Actually the run time for the hashing variant is O(const) (and O(n) for small lists). We will find a double character within the first k+1 elements of the list where k is the number of valid characters. If the string is encoded in say UTF-8 our charset has 8 bit, thus we will inevitably find a repeating character after 256 elements and can ignore the remaining list. If our charset is even shorter (say only A-Z [note the capital]) as in this case, we only consider the first 27 characters. This number is independent of the lists actual size, thus it will work in constant time for long lists. The same goes for the first variant which is O(n^2), we can prune comparing against characters that are more then charset+1 away from the start and will find one within the first charset + 1 characters. This will result in a runtime of O( [charset + 1]^2 ) which is lower then O(n^2) for big lists. Which variant is faster then becomes interesting, because we might be able to further optimize via multicore processing or SIMD ...

[@MoRasheed]

I'm an IT graduate (computer networks) but this comment section makes me reconsider my life decisions

[@alibaba8266]

why ?

[@rodrigoogirdor774]

Modi Rasheed why?😂

[@WakeUpSmellTheCoffee]

Cuz coding is more fun than IT. I’ve done both. Just my opinion :p.

[@justinjohn93]

Same here

[@deecoder4497]

Same here bro

[@marcom2092]

Came into the comments section not knowing anything about this subject and now I feel dumb

[@sanketsony8143]

Marco M lol! then why this video came into your feeds in the first place?

[@Loser-ow6ye]

Marco M sameeee

[@Dalendrion]

Why? Obviously you're not going to know anything about a subject you haven't studied. :D If you've studied it extensively and you still don't understand it, _then_ you may feel dumb about it. And even then, so what? Feeling dumb simply means you just found out that you have something to learn. Feeling dumb has nothing to do with being dumb. :)

[@vaishnavi5070]

Dalendrion u know the last line of ur cmnt is like inception ending scene for me. what i mean is i didnt get it

[@Dalendrion]

vaishnavi Our feelings are often illusions. They are emotions. And emotions aren't logical. So these feelings often give us an incorrect idea about reality. You may feel dumb even if you aren't. You may feel smart even if you aren't.

[@lvlichaelly]

I have gone through google phone interview twice before and to be honest it's never as easy of this.

[@tigerrx7]

Fundamentally, if you understand Data Structures and Algorithms you can solve this one. This is why those two classes are ALWAYS recommended (required even) before any elaborate code building. Great vid to reinforce the fundamentals

[@jeremyingraham9344]

Wouldn't just a set work better? It's O(1) lookup and requires less space.

[@WendyWangMusic]

Would hash set be better? In hash table you are storing another column count, which uses more space... In hash set, you only need to check whether the element is in the set. If it is already in the set, then you return this element right away...

[@CSDojo]

Yeah using hash set would be another option. Same space complexity though.

[@asphix]

CS Dojo its the same space complexity but hashset in this case is certainly a better option. I guess you can use the hash table and if interviewer asks for space optimization you can suggest a hashset with minimal code change

[@_sudosu]

It hardly depends on the language. For instance, in Java HashMap is used internally in the HashSet collection thus it does not bring any memory optimization.

[@khaledsaleh4238]

Agree , HashSet is better in my opinion too!. Thanks for your suggestion , Wendy!

[@dafemartdafemart4020]

what's the complexity of a look up in your hash table?

[@JannisAdmek]

after seeing your video I made a short python script with two functions, the first using the good, the second the poor algorithm. I made a list with 10000 random, not repeating characters and at the end AA. Here are the results: good: (using a set and going through ones) 0.0789 sec bad: 9.46 seconds! Nice video, thanks for enlightening

[@Michael-bt8fn]

A rather simple operation with Time O(length of string) and space O (1) is using bit operations. Just define a mask 0, loop through the characters get bit of mask at location char-'A'. If 0 is gotten, set to 1. And continue looping, if 1, return char

[@GoHomeAndGetYourShinebox]

Interviewer asks question: *Me* : Ummm can I go to the toilet and does it have wifi?

[@agnesmortey7266]

Go home and get your shine boxes jumped poor village training Lord37899 Henry

[@mistermomo2904]

@@agnesmortey7266 Agnes Morty has issued an insult Lord Vyron 12937 Mark ii; the shoes are shined and feet are in the boxes

[@dotanoob466]

This is too easy for a google question i feel

[@dkarbaev]

dota noob probably a warm-up question. I was told that their interviewer might ask a couple of simple questions before getting for a hard one.

[@kharinskiyalexey7409]

If I were a google interviewer, I would ask after that: "Can you solve it with O(1) space?". Not so easy anymore?))

[@Abdulmajeed-sy1us]

@@kharinskiyalexey7409 Without checking n characters we can't conclude so they can't ask like that

[@kharinskiyalexey7409]

@@Abdulmajeed-sy1usof course you have to check you, go on :) but with O(1) space

[@calmsh0t]

Mhhh not necessarily. I don't think that the problems itself are unsolvable at these companies, I believe that they are more looking for how you solve it and if you can get to the uber-smart approach they are expecting (tough for me, since I mostly work after the pattern "make it work, optimize it later")

[@user-ov5nd1fb7s]

In your assessment of the time complexity, you should add the time that it takes to actually create a hashtable and insert the values. That would have increased memory usage as well. Depending on your time and memory constraints, you have to use different approaches.

[@NeverCodeAlone]

I love this explaining style and videos - now you are on our inspiration channel!!

[@Zir0KZN]

Thank you! It was pretty simple to solve. Wait for the harder ones :)

[@mathewdempsey16]

Well that was easy, using a hash table was literally the first thing that popped into my mind

[@Thatguy-ru3hw]

So thorough unlike most channels. Thank you very much earned a subscribe!

[@TNTsundar]

You could use a bitmap to mark the seen characters and when the same character is seen the next time, you could return that character simply. This way you save space as well by not tracking the character and the count in a dictionary/hash table. For example, for 96 printable ASCII characters including special characters, you would need only 12 bytes to mark different characters that are seen as we pass each character. Since we are interested only in the first reoccurring character we don’t need more than 12 bytes. We mark each character from the string using a lookup table and set the corresponding bit in the bitmap. We can have different ranges for special characters and normal characters in the bitmap and mark appropriately. The first reoccurring character can be found when we try to set the bit which is already set. This way we don’t use a lot of space as well as the time complexity is at minimum (which is similar to the solution presented in the video).

[@codybarscott6280]

It's actually a very good exercise. Thank you. I think it would be something like this in Java (though my first approach was the naive solution, I agree with using a Map instead) import java.util.HashMap; import java.util.Iterator; import java.util.Map; public class MainApp { public static void main(String[] args) { //the subject String String someString = "ABCDEFGAD"; //split subject String to an array String[] someStringCharArray = someString.split(""); //the Map to fill in with individual character and count per character Map map = new HashMap(); //start looping through comparing and counting for(int i=0; i 1){ System.out.println(o); } } } }

[@arpanm9652]

I got the exact same question in my college exams.. and I wrote the first solution. Guess what - I got the FULL marks😐😂😂😋😋

[@JPNSynster]

I love your channel I hope you return again soon. I really love the python series, you have such a great way of teaching.

[@bennydcunha1514]

the idea of an array is perfect

[@jatinlalwani9459]

The two solutions that you mentioned (O(n^2) and O(n)) produce different results for the string ABBA. Now I am confused which one is first recurring char in ABBA, A or B. If it is B then your second solution would work properly (Set would be better though). But if it is A then we can use dictionary like you did with chars as keys and respective counts as values. We need to traverse the complete string to complete the dictionary then we could start traversing the string again and for every char we would refer dictionary for its count. Once we reach a char for which count is >1, return. Time complexity - O(n). Space - O(1). Any better solution?

[@avinashkhare1341]

I think the second solution is wrong.

[@wwxk123]

his brute solution is wrong; like you suggested ABBA will return A when in fact ABBA should return B. For second method, I don't think it matters whether you use hashset/map or even an array. What does matter is that the space is not O(n) but rather O(1) since there are limited number of alphabets (52 if case sensitive, 26 otherwise).

[@pepajimenez8376]

Exactly what I was going to comment! The problem is not properly defined, is the first recurring character the first one to appear twice or the first one in the sequence that repeats? His solution only works in the first case.

[@pedant9134]

exactly what I was confused about

[@TheAuxLux]

I agree that 2nd solution gives correct result, since in ABBA, A recuring in 4th spot, and B is recurring in 3rd. However I not quite agree we have O(n) in second solution. Sure we go only forward the string, but we iterate each table row every char. Sure, most languages are making this for us in lower level, yet still are doing.

[@Jorde]

You could also create an array of length 26 in which you insert the ascii code to int and increment the position and then when the index is equal to 2 stop and convert the index to the position getting the character

[@vigneshviggu8417]

Became your subscriber. Your sessions are awesome dude

[@ridiculoustoysss]

in real work environment, it will be like: 1. google 'find first recurring character' 2. click into stackoverflow, copy, done

[@Francefire]

🤣🤣🤣

[@engineergirl6869]

accurate!!!! lol

[@vaishaligupta1360]

We can actually terminate it just when the count of any of the characters become 2 since we are concerned about only the first recurring character.

[@ryuaan]

The hash table is def more elegant and better time complexity. My first attempt in c++ was of a double for loop O(n^2), 2 array chars, & 1 basic char. One array char to hold the letters, another array char to assign & store duplicates found by a third plain char holding current indexed letter.

[@AlokKumar-jh8wp]

Thankyou csdojo for explaining it in a great way you are doing a great job for us.

[@g_455]

The counts of the character is of no use, so why not use a Set (like hashset) instead.

[@kkppccdd]

Ganesh _ the complexity of hashset and hashtable is equivalent. Here it supposed the time complexity of ‘ if e in counts ‘ is 1. If the size of counts may grow large, it needs to optimize ‘if e in counts’.

[@rajeshdansena]

Agree. Better optimized memory.

[@x-yl]

Some performance numbers in python (running the method on string.printable 10000 times): List - 1.8005362025424931 seconds Dictionary - 0.4816858277563984 seconds Set - 0.2586124478794257 seconds Looks like a set would have been the best choice.

[@wozhendeaa]

Using hashset is still the same memory complexity. They are the same. You can use an array instead if you worry about the nonexistent memory overhead

[@kalebbruwer]

It is useful for the problem he mentioned at the end.

[@TheRahul9191]

Another approch is to use Set data structures. Start adding char in set through iteration. Check lenght after each value appended in set, if length does not change then return that char. This is in O(n) time complexity and good space complexity over HashTable.

[@AvinashSharma-fr5lh]

set element insertion takes logN time so the complexity will be NlogN and not N

[@denysivanov3364]

@@AvinashSharma-fr5lh set is slower than dict?

[@AvinashSharma-fr5lh]

@@denysivanov3364 I think it is.

[@princedavidbuduru4242]

very helpful and great teaching thank you so much for impacting my life! and i cant wait to start learning code with you!!

[@radhekrishanrathod9001]

Hi I am in last year of my CS graduation.Videos are really helpful.😀

[@ironrose6]

My thought was simply to iterate through the array and for each element, check the length of a set before and after adding the element to that set. If the length increases, that's the first time the element has occurred in the array. If the length stays the same, the element was already in the set and therefore it's the first recurring element.

[@grantmartin2002]

most add functions actually return a boolean value for if the set was changed or not (at least in java). So all you would really have to do is if(!set.add(char)){ return char}

[@ironrose6]

@@grantmartin2002 Interesting! Unfortunately, it doesn't work that way in python- it just returns "None". But I didn't know that about java!

[@mrankushtechnical]

What were the questions asked to u ??

[@hitzcritz]

I don't think you are allowed to reveal the questions a company asks you for an interview.

[@nimisidiv9244]

You are just being known as a whistle blower is career ending in tech

[@aakash9475]

I think they are pretty basic questions. And you always can share interview questions.

[@invictuz4803]

lmao interview questions are not some trade secret. Say you don't even get the job, how can they enforce that you don't talk about your interview. Also, it's not like there's a public database of whistle blowers.

[@allisonosullivan6095]

mrankushtechnical dog shall ask would he pick up phone bring washing over babe babe yes or no

[@ajr_almeida]

Bro, you're awesome. You explanation is very easy to understand. Thank you!

[@techtitbits]

You make coding simple. Thanks

[@tariqganem1109]

him : asking him a very simple ques me: apply dfs on array of trees

[@adamgomaev6968]

I just started to learn programming at university and I think it`s too early for this kind of videos for me. lol

[@sunrise8263]

Congratulations, You took clear water and muddied it.

[@shree203]

Dude. Ur videos are so freaking clean and simple... I like it...😍

[@prabhur764]

hey ,its very easy man.

[@lokakshabm2612]

Even if we don't have any recurring characters in the first 26 characters of the string, the 27th character will be recurring, since we have only 26 alphabets (assuming the string contains only alphabets). So time complexity is O(26), which can also be written as O(1). Even if the string can contain all ASCII characters, it can still be considered O(1) according to me.

[@tornes]

That's a deeper understanding of the problem, nice

[@sangramjitchakraborty7845]

But you still have to traverse the whole thing to find the element that is recurring. And if the input is smaller than 26 you can't use the pigeonhole principle.

[@lokakshabm2612]

@@sangramjitchakraborty7845 As soon as you find the first recurring character you can exit the for loop. The first recurring character can't come after 27th position, because for it to do so all the positions before it must contain different characters, which is not possible since only 26 characters are possible. Hence 27th position or lower positions must contain at least one recurring character which will be the first recurring character.

[@lokakshabm2612]

@@tornes Thank you

[@sangramjitchakraborty7845]

Ahh. I see what you mean. Thats a great approach.

[@KGcodes]

Pretty simple but good to nail this down as it could be a building block to harder problems.

[@MsThekiller02]

I just started uni and got the answer right, didn't think about the naive way at all. I come up with a good enough solution and then I optimize it. If you shoot for the stars right away, you'll struggle a lot because you're gonna get stuck on the details and you won't get anything from that. My high school computer science teacher used to say "you can't build a skyscraper all at once, start with the foundations, then build your way up"

[@Luckpart1]

A simple hashing to 26 bits should work to avoid using extra space as well.

[@KirinDave]

I like this and I was reaching for it in my head too, but I think to properly answer strings like "ADDA" with an 'A' you wouldn't be able to reduce this to a range/popcount problem.

[@jorgeromero3422]

I'm so proud I solved it by my own

[@agnieszkarutkowska8244]

Me too :)

[@lajti4376]

xd

[@pantagry]

you could also use hashset and check only for length after adding to it, so if count of elements unchanged - you have duplicate

[@rahulsethione]

I’d use a Set. Over the loop if set.has(str[i]) then return it. Else set.add(str[i]).

[@akshadk7]

I guess it would not be much harder for me to crack their interview if they ask such questions

[@GacemAyoub]

for (i from 0 to n - 1) { character = input_string[ i ] counts[character] = 1 if (counts.size() < i + 1) return character } return none This variation take advantage of the unicity of Hash keys

[@akarshy]

Ayoub Gacem this is a great solution that is actually O(n)

[@vanessahayes6471]

Thank god I found this channel better late than never, I guess

[@prasannalakshmi1081]

Ur videos are so impressive and interesting and make everyone enjoy the fruit of programming

[@pranavbhat29]

I thought the first recurring character is the one which has a frequency greater than one in the string and it has the least index among all such possible characters. Like in this particular algorithm, a string "bcaabd" would return "a" since "a" repeats for the first time, but I thought asked me to return "b" instead ( since among the characters which repeat in the string, b occurs for the first time in the string. )

[@jrajesh11]

Yes, that is what I think is more accurate as it takes the whole word into account, and not just an incomplete word.

[@hdwe1756]

I was just thinking about adding them to an array and checking if they were in it....

[@louiswouters71]

I don't get it. They are already in a string, so you could just start at the 2nd level and see if its in the first position. Then continue to take the n-th letter and check it with the first n-1 letters. It uses the same amount of comparisons as his 'correct' solution.

[@yashsoni501]

Louis, both the solutions are correct but the second one is better than the first one as it takes much lesser comparisons. Your method uses same number of comparisons as his first method which is n(n-1)/2...

[@LoveWillB4U]

Checking if something exists in an array takes at best O(1), on average O(n/2) -> O(n), and at worst O(n) comparison. Checking something if it is in a hashmap/hashset takes at best O(1), on average O(1), at worst O(n). So adding an item into an array and then checking if it is in an array is O(n^2), which is what we want to avoid. Use a hashmap/hashset when you don't care about the order it gets added into the hashmap/hashset.

[@hdwe1756]

Leighton Lee Thanks, I get it now.

[@RomanSteiner_xD]

Leighton Lee, assuming there are only uppercase English letters (it seems so), you could use an array of 26 booleans and use the current char as index (its ASCII value minus that of 'A'). That way it's always O(1) for the lookup because you don't actually have to search for anything. If you're short on memory you could even use a 4byte bitmask in the same way :3

[@BetoEats]

Great video, I enjoy refreshing my knowledge with some sample problem 👍

[@ManishGupta-wb2wc]

Good job . Need more videos like this

[@saadakhtar2000]

I am student of First Semester of B.S(CS). I literally pused it and thought a rough algorithm and I made it on my FIRST try C++ ! :) Really really happy to realize my hidden skills :-D

[@sagan666]

UNIX solved all of this over 40 years ago. You can man sort, sed, awk, grep et al.

[@DotSimLtd]

A quicker way is to simply use a list where the letter is stored at an index in the list or array lookup. If the string was large you could even speed up using heuristics such as a coarse sort.

[@holonaut]

Storing the letter as an index in a list/array/dictionary (call it whatever) is exactly what he does in the second solution, isn't it?

[@DotSimLtd]

Except an array is much quicker access than a dictionary.

[@dhruvsingh3066]

bro pls keep on uploading such questions from Google , i wanna learn more

[@jydk37]

I would design a neural network to figure it out while I ate a snack

[@azztereris]

jydk37 wtf? hahaha

[@vedant6633]

Lol

[@fikkitchen]

xD

[@vedant6633]

You're selected ~google interviewer

[@SanderMFC872]

Trying random solutions until you get the answer is bad. But if you do it fast enough it's called machine learning.

[@MarcusAseth]

Hey I've answered that right, so I'm now I Google employee? Nice! :D

[@JakubSK]

This is insanely simple. I'm kind of surprised this was a Google question. Wow.

[@vivilee7290]

I like your video so much. It's clear and easy to learn.

[@VLS-Why]

If you can use JavaScript couldn't you run through your array once and compare indexOf with lastIndexOf and return the first value where they are not the same?

[@LoubrielJayneberg]

It would have to parse the array every time you use indexOf and lastindexOf. Not the most efficient solution.

[@mikheilchkheidze1629]

It is not very efficient to make people read long names either

[@blasttrash]

And it is also not very efficient to make people read unpronounceable names either. ...Lets start the bashing. :P Juz kiddin though. Happy coding. :)

[@TheFreakinProgrammer]

Will that work for string "ABBA"? No

[@zuko655]

@@TheFreakinProgrammer with this it does: function findRecurrence(str) { for(let i = 0; i < str.length - 1; i++) { let char = str.charAt(i); if(str.indexOf(char) !== str.lastIndexOf(char)) return char; } return null; }

[@marcushines4172]

Just use a set, bro. HashMap is the wrong tool for this job but the idea behind your solution is correct. We just don't care how many times we've seen a char, only that we've seen it before. Good job though!

[@marcushines4172]

...A Set has constant time lookup, and yes it has a hashing function which gives us the O(1) time complexity. I understand the task is about the underlying algorithms, I was simply pointing out that there is a better tool to accomplish this task . But....I guess when all you have is a hammer, everything looks like a nail.

[@marcushines4172]

...also you should delete your comment about the quadratic time complexity, since you are in fact wrong. That way, people in the future will not be confused by your incorrect reasoning.

[@henriksundt7148]

I guess this is a general coding interview, not python specific. In that case the candidate does the right thing (like in the video), to explain what actually happens, independent of what the language provides.

[@cipherxen2]

Marcus Hines In java hashset internally uses hashmap. And hashset don't always give constant time lookup, it depends upon hashing function.

[@marcushines4172]

The developers at Oracle seem to be pretty smart. I'm sure their implementation of a hash function for the HashMap/HashSet is fine, so the comment about "depends upon the hashing function" is really meaningless. You all are making a big deal about nothing, lol. I simply stated that he can accomplish the same result, without having to count the occurrences of the characters.

[@nikitafulzele6099]

Keep going your explanation is understandable

[@koushikn3016]

Simple and Soothing

[@SreeragNairisawesome]

why not use a simple bit vector of size 26 (total no. of characters) , keep marking the corresponding rows '1' as you find unique characters and when you try to mark an already marked row, return the corresponding character.

[@illiap3628]

It does not say anywhere that the string only contains uppercase English alphabet letters, so your algorithm might not work.

[@SreeragNairisawesome]

Illia Potapchuk if that's the case ,then a 52 bit vector will suffice..... I don't see any problems now.

[@illiap3628]

What about other symbols or numbers?

[@SreeragNairisawesome]

Illia Potapchuk well ,I originally assumed characters as only letters.... and the video also mentions only alphabets.

[@hisjojo6312]

Or maybe 256 size for ASCII code

[@CutTheRope1]

In the second method, wouldn't the O-notation not be O(n) since in addition to checking the String you are also checking the created set for every character?

[@MoJo01]

Less processing but more memory. Guess it depends on what hardware you want to utilize. But usually small if the string is anticipate to be small, then processing is valued over memory I assume. But the instruction won't be repeated, I think that's what the O is about, not overall complexity, but instruction repetition. Oh, just noticed your comment is 3 years ago. Well, cheers.

[@jacobmiller7175]

@@MoJo01 well im glad you mentioned that, i had that thought as well so I am glad you left a reply. Ill have to look into it more, but now i no where to start so cheers to you!

[@nikitafulzele6099]

I understand all what you have explained thank you

[@maxfan6035]

This *simple* problem can be a foundation to solve some appearingly complex problems. Thanks

[@Bazoozehindizzle88]

Don't these two solutions do different things? Given the string "ABCBDA", solution 1 would return "A", whereas solution 2 would return "B", right?

[@pk062]

Rowan Hatherley You are right

[@sukeshkumard6064]

Rowan Hatherley, you absolutely right. I was so much confused doing this many times and came to know that this twp solutions gives two different answers.

[@jatinlalwani9459]

Correct! I think he needs to clarify what is first recurring char. In a string ABBA, the first recurring char is A or B?

[@nealpatel7696]

It's B. Basically, just look for the character you see twice first. Since you return after the first recurring character (B), the second, third, ..., recurring characters don't matter. ABCA returns A because A is the only recurring character, therefore, the first recurring character. BCABA returns B because B is the first recurring character. Given ABCBDA, it would return B since it's the first recurring character.

[@shanugarg8428]

Hey guys Checkout this Google interview problem that's solved with 4 different approaches from scratch to code really quick at : kzbin.info/www/bejne/q5SwdXuLr8Z7bJI

[@Seanbo88]

Me before 2:19 "Oh, hey, maybe I can understand coding. Me after 2:19 "Nope"

[@PsyfirX]

Seanbo88 I wouldn't worry, the guy in the video doesn't understand coding either.

[@Mikt25]

Watch some of his or other people's videos on Big O notation. It's not as hard and intimidating as it looks. CS Dojo's explanation of it is one of the better ones.

[@swaraj8769]

I think a linear solution is possible by using map in c++. I extract each character from the string and increment the count. If I get a count greater than 1, I print that character. Then in a visited array, I set the attribute to true so that I don't print the same character again.

[@jamaajair393]

Yes your code is more clearly and simple to get it. Thank you

[@TonyThomas01]

From what I see, most interview questions (specially on phone and online) are a coversion from a O(n^2) to O(n). And when you have it, hashmaps - there you go! :) Saved my ass last Friday (before I saw this video though).

[@juarezsotelo]

This is my solution in java 8: private static Character findFirstRecurring(String letter){ char[] l = letter.toCharArray(); Set list = new HashSet(); for (char c: l) { if (!list.add(c)) { return c; } } return null; }

[@tsetsenmendsaikhan252]

Congrats, We're hiring you as Security Guard.

[@rodrigoogirdor774]

Tsetsen Mendsaikhan omg i am dying 😂😂

[@darellarocho5729]

Lmao!

[@Unbreak00]

very nice bro

[@bubba6755]

Very helpful,thanks!

[@ezequielcervantes3925]

It should be mentioned that the linear time solution also incurred a linear space complexity.

[@sefkannnn2085]

This guy looks from macdanuru drive thru.

[@zuko655]

A JavaScript solution: function findRecurrence(str) { //convert string to array const arr = str.split(""); //construct new set from array and check if the size is the same if(new Set(arr).size === arr.length) return null; //loop through array and use slice method to extract elements starting at current index +1 so that the current index is not on the new array //check if this new array contains the current element, return it if so for(let i = 0; i < arr.length - 1; i++) { if(arr.slice(i+1).indexOf(arr[i]) !== -1) return arr[i]; } }

[@Thiago-jm7gr]

Good job. By performance purpose you can replace arr.slice() with arr.indexOf(arr[i], i + 1). Slice function creates a useless array, which turns the algorithm a bit slow I created this gist to demonstrate my tests! Check this out: gist.github.com/thiago-tallison/36b3e826a856f9ffaa1cdd09dcf95265

[@GrandpappyLuke]

IndexOf makes this solution n^2 which is just as bad as checking every pair.

[@nguyenhoanglong420]

Wow this coding interview question is really awsome :3

[@sophiaatn5339]

Thanks so much for this

[@BarksApp]

First question I ask on an interview... What sound does an owl make?

[@AaronBrand]

If you've heard one in flight, they're actually pretty quiet. Like a gentle "whoosh" sound.

[@kablouserful]

"write some pseudo code" *writes python* XD classic

[@milew81]

Thanks! Great video

[@chinmayhundekari]

In your code, you need to add the elements to a hash table. You have to include the time taken for that.

[@bobsanchez6646]

Your naïve solution returns a different answer than your final solution for the case "abba." Therefore one of your solutions isn't a solution at all.

[@ningdi6545]

idk for abba we should return a or b?

[@hjdeheer]

b . Its the first recurring character

[@RandomGuy-df1oy]

public String findFirstRecurring(char[] array) { String answer = null; for(int i=array.length - 1; i>0; i--) { for(int j=i-1; j>0; j--) { if(array[i] == array[j]) { answer = "" + array[j]; } } } return answer; } Thats the naïve solution I guess.

[@thewayofbeauty5731]

So there is no naive solution for this problem, basically.

[@shanugarg8428]

Hey guys Checkout this Google interview problem that's solved with 4 different approaches from scratch to code really quick at : kzbin.info/www/bejne/q5SwdXuLr8Z7bJI

[@MrGamingPigeon]

Console.writeline("pls hire me senpai");

[@LukaCekovic]

Great video, subbed immediately!

[@pankajarmo129]

The answer would be different in "naive" and hash table method if the string is DBCAAB. In naive method it would return B while in other it will return A.

[@GuyMichaely]

Aren't both solutions O(n^2)? For the second solution, the programming language will have to compare char against each item in the list, won't it? That would make it O(n^2) if i'm not mistaken. Can anyone confirm/deny?

[@manfredzalud7914]

I thought so as well. But the comparison of the chars will only take a constant amount of time, because there is a finite number of possible characters

[@peterhayman]

the 'key' is that unlike arrays hash tables have O(1) lookup time

[@yixunnnn]

The naive solution does not account for when the there may be an earlier recurrence of another character after the current searched character

[@ArnavBarbaad]

It does. Since you are starting from the first element, there can't be an earlier recurrence. What you're calling an "earlier recurrence" would actually be the 1st occurrence at some point ealier in the algorithm, and the 2nd occurrence would therefore be caught.

[@ArnavBarbaad]

Damn didnt think of that. You’re right, however then it depends on the definition of ‘first recurring character’. Does it mean the first character in the string that is repeated or a character in the string to first have two occurrences.

[@samwhaleIV]

But when you start from the first character (and the input doesn't change) that doesn't matter. It would work from back to front as well, just so long as you iterate all characters.

[@samwhaleIV]

Zuy It means the first, the examples in the video show so.

[@Kr2025]

The first recurring character is still C in B C C B. Since B didnt recurr before C.

[@chanchalsinghal5973]

You r great buddy. U r my inspiration , 👍👍👍

[@mayankpant1596]

There is also this other approach where you first use merge or quicksort to sort the string character wise, and the ln simply iterate through the array and compare arr[I] and arr[I+1] , if they are equal just return it . Complexity is O(nlogn), but dosent take any extra memory..