Welcome back to How to solve coding interview questions! In this series of articles, I’ll walk you through the sort of questions that you might be asked in a coding interview and provide solutions in a couple of programming languages.
In the previous article in this series, I presented you with a challenge to write a function that took a string as an argument and returned either:
- The first recurring character in the given string, if one exists, or
- A null value like JavaScript’s or Kotlin’s
null, Python’sNone, or Swift’snil.
I also provided solutions in Python, JavaScript, and Swift.
The follow-up challenge
Usually in a coding interview, if you succeed at the initial challenge, there’s usually a follow-up that is a more challenging variation on the theme. The “find the first recurring character” challenge is often followed up by looking for its opposite:
Write a Python function named first_nonrecurring_character() or a JavaScript function named firstNonRecurringCharacter() that takes a string and returns either:
- The first NON-recurring character in the given string, if one exists, or
- A null value like JavaScript’s or Kotlin’s
null, Python’sNone, or Swift’snil.
Here are some example inputs for the function, along with what their corresponding outputs should be:
| If you give the function this input… | …it should produce this output: |
'aabbbXccdd' | 'X' |
'a🤣abbbXcc3dd' | '🤣' |
‘aabbccdd' | null / None / nil |
One solution
See if you can code it yourself, then scroll down for my solution.
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
👇🏽
Let’s consider the following example string:
"a🤣abbbXcc3dd"The string is short, and I purposely made the first non-recurring character an emoji so that it would be easy to spot, so a glance is all you need to spot it.
One programmatic approach is to go through the string one character at a time and keep track of the number of times you’d encountered each character. For this example string, you’d end up with this:
| Character | Number of times it appeared in the string |
a | 2 |
🤣 | 1 |
b | 3 |
X | 1 |
c | 2 |
3 | 1 |
d | 2 |
If you maintain the order in which the characters were encountered, the solution becomes either:
- The first character that appears 1 time in the string, if one exists, or
- A null value like JavaScript’s or Kotlin’s
null, Python’sNone, or Swift’snil.
This was my first pass at a solution in Python:
# Python
def first_non_recurring_character(text):
character_record = {}
# Go through the text one character at a time
# keeping track of the number of times
# each character appears.
# In Python 3.7 and later, the order of items
# in a dictionary is the order in which they were added.
for character in text:
if character in character_record:
character_record[character] += 1
else:
character_record[character] = 1
# Now that we have a record of the number of times each character appears,
# create a list containing only those characters that have appeared once.
non_recurring_character_record = {k:v for (k, v) in character_record.items() if v == 1}
non_recurring_characters = list(non_recurring_character_record.keys())
# The first non-recurring character, if there is one,
# is the first item in the list of non-recurring characters.
if len(non_recurring_characters) == 0:
return None
else:
return non_recurring_characters[0]What’s the Big O?
In the code above, there are 2 O(n) operations:
- The
forloop that builds a record of the number of times each character appears in the text, and - This list comprehension:
# Python
{k:v for (k, v) in character_record.items() if v == 1}These operations take place one at a time, so the complexity of the code is O(2n). As far as computational complexity is concerned, constants don’t really matter; O(2n) is effectively the same as O(n). So its computational complexity is O(n).
An (unsuccessful) attempt to make the solution a little more time- and space-efficient
In its current form, the code builds a record of the number of times each character appears in the text — even those that appear more than once. Then, in the next step, it goes through that record to create a new record of the characters that appear only once.
I thought: “What if we eliminated that second step by building a record of only characters that appeared once?”
Here’s pseudocode that explains what I mean:
For each character in the text:
If the current character is already in the record:
Remove that character from the record
Otherwise:
Add that character to the recordAt the end of the for loop, the character record contains only the characters that have appeared once.
Here’s my revised implementation:
# Python
def first_non_recurring_character(text):
character_record = {}
# Go through the text one character at a time
# but record ONLY those characters that appear once.
# In Python 3.7 and later, the order of items
# in a dictionary is the order in which they were added.
for character in text:
if character in character_record:
# We've seen this character before,
# so remove it from the record.
del character_record[character]
else:
# # We've never seen this character before,
# so add it to the record.
character_record[character] = 1
# character_record contains only those characters
# that appear ONCE in the string
non_recurring_characters = list(character_record.keys())
if len(non_recurring_characters) == 0:
return None
else:
return non_recurring_characters[0]This solution seems like a good idea, but it has a big flaw! As one reader, Hans, astutely pointed out in a comment:
basically it tests if characters appear an odd number of times in a string. For example if a character appears a third time, it was removed the second time and consequently added again to
character_recordthat third time.
This is true — by removing a character from character_record, it’s as if the character was never encountered. I’m going to treat this as a reminder to:
- Not prematurely discard information, and
- Write better tests!
So in the end, I should stick with my first solution. Good catch, Hans, and thanks for pointing out my mistake!
