It seems simple, but in fact it is one of the standard phone-interview questions at google. Designed to weed out the smart engineers who understand complexity over the rest.
From my friends at google I heard 70% of people answer it wrong. Which is kind of shocking.
Here is the question :
Given an arbitrary string of character eg. ‘aabcdef’;
Return the first recurring character.
Most peoples immediate thought would be a for loop looking something like this
Wrong, naive solution
for all characters in string
for all other characters in the string
compare character
if its the same
return character
Yes this solution does work. But don’t expect google to call you back after.
There are two nested for loops inside this solution. This should tip you off this solution has a time complexity of O(n²) with n being number of characters in the string - we can do much better.
Because of the discussion in the comments. The explanation of this O(n²) time complexity goes as follows - if there is no double characters, you have to loop through each character and then loop through the string again with the rest of the characters. There is no checks for letters of the alphabet or similar stops.
The correct solution is simple
Use a hashtable or one of its data-structure siblings.
You can learn more in-depth about hashtables in our other article.
Create a hashtable/object/lookup table of structure { character }
For all characters in string
If character is in the hashtable
Return character
Else
Add character to hashtable
This solution has time complexity of O(n) !
This means is a square root of n faster than the previous one!
Want interview questions delivered to your inbox?

We also just launched a free Slack channel to chat about programming, computer science questions, and interview prep. Join us on Slack!