Most common phone interview question at google.

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!