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

Find the first recurring character in the given string!

(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.

[johannesvahlkvist]

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

[ilustrado]

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

[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.

[firefoxmetzger]

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

[jeremyingraham]

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

[lvlichaelly]

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

[marcom]

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

[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...

[Michael-btfn]

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

[dotanoob]

This is too easy for a google question i feel

[GoHomeAndGetYourShinebox]

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

[ovndfbs]

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.

[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

[tigerrx]

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

[ridiculoustoysss]

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

[arpanm]

I got the exact same question in my college exams.. and I wrote the first solution.

Guess what - I got the FULL marks😐😂😂😋😋

[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).

[TheRahul]

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.