Categories

## How to solve coding interview questions: The first recurring character in a string

Are you interviewing for job that involves coding or requires coding skills? Then it’s very likely that you’ll be asked to undergo a coding test in the interview.

A long while back, I very badly embarrassed myself in an interview with Google. A Googler friend referred me (referrals are always better than applying yourself) and a handful of days later, I was in the interview, and I did everything wrong. I promised myself that I would never embarrass myself with such a pitiful coding performance at an interview again, and I’d also like to help ensure that it never happens to you either.

The trick, of course, is to practice. In this series, How to solve coding interview questions, I’ll walk you through the sort of questions that you might be asked in a coding interview. Many of the questions you’ll be asked will involve the sort of things that get covered in a “Algorithms and data structures” class and will be designed to test your general problem-solving ability. I’ll show you a solution, and where applicable, I’ll show you some alternate solutions and discuss the pros and cons of each.

You should try coming up with your own answers before looking at mine — after all, it’s the best way to learn!

## The “first recurring character” function

This is a classic coding interview question that is often presented to junior developers.

### The challenge

Write a Python function named `first_recurring_character()` or a JavaScript function named `firstRecurringCharacter()` that takes a string and returns either:

• The first recurring character in the given string, if one exists, or
• A null value like JavaScript’s or Kotlin’s `null`, Python’s `None`, or Swift’s `nil`.

Here are some example inputs for `first_recurring_character()`, along with what their corresponding outputs should be:

### One solution

See if you can code it yourself, then scroll down for my solution.

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

👇🏽

If you had to perform the function’s job yourself, you’d probably go through the given string character by character and use a piece of paper to jot down the keep track of the characters you’ve already seen.

Here’s a solution that takes this approach, in Python:

``````def first_recurring_character(text):
previously_encountered_characters = []

for character in text:
if character in previously_encountered_characters:
return character
else:
previously_encountered_characters.append(character)

return None``````

Here’s the JavaScript version:

``````function firstRecurringCharacter(text) {
let previouslyEncounteredCharacters = []

for (const character of text) {
if (previouslyEncounteredCharacters.includes(character)) {
return character
} else {
previouslyEncounteredCharacters.push(character)
}
}

return null
}``````

Both do the following:

1. They use a built-in data structure to keep track of characters that they have previous encountered as they go through the given string character by character. In the Python version, the data structure is a list named `previously_encountered_characters`; in the JavaScript version, it’s an array named `previouslyEncounteredCharacters`.
2. The use a loop to go through the given string one character at a time.
3. For each character in the given string, the program checks to see if the current character has been encountered before:
• If the current character has been encountered before, it’s the first repeated character. The function returns the current character.
• If the current character has not been encountered before, it is added to the data structure of previously encountered characters.
4. If the function goes through the entire string without encountering a previously encountered character, it returns a null value (`None` in Python, `null` in JavaScript).

## What’s the Big O?

If you’ve made it this far, you might be asked how you can improve the code. This is a different question in disguise: You’re actually being asked if you know the computational complexity or “The Big O” for your solution.

First, there’s the `for` loop. For a given string of length n, the worst-case scenario — either the string doesn’t have any recurring characters or the recurring character is at the very end — the loop will have to execute n times. That task’s complexity of O(n).

Next, let’s look inside the `for` loop. There’s a test to see if the current character is in the collection of previously encountered characters. In Python, this test is performed by the `in` operator; in JavaScript, it’s performed by the `includes()` method.

That’s because they both use the following algorithm to determine if a given item is in a list or array:

``````if we are not yet past the last item in the list/array:
get the next item in the list/array
if this item is the one we’re looking for:
return true

if we are at this point and we have not found the item:
return false``````

So the function is basically an O(n) operation performing an O(n) operation on average, effectively making it an O(n2) operation. As far as computational complexity goes, this is considered “horrible”:

## Can you improve the code?

You’ve probably figured out that the way to improve the code is to try and reduce its time complexity.

You probably can’t reduce the time complexity of the `for` loop. The function has to find the first recurring character, which means that it needs to go through the characters in the given string in order, one at a time. This part of the function will be stuck at O(n).

But you might be able to reduce the time complexity of check to see if the current character in the loop has been encountered before. In the function’s current form, we’re using a Python list or JavaScript array to keep track of characters that we’ve encountered before. Looking up an item in in these structures is an O(n) operation on average.

The solution is to change the data structure that keeps track of previously encountered characters to one where looking for a specific item is faster than O(n). Luckily, both Python and JavaScript provide a data structure for sets, where the time to look up an item is generally O(1).

Let’s rewrite the function to use sets. Here’s the Python version:

``````def first_recurring_character(text):
previously_encountered_characters = set()

for character in text:
if character in previously_encountered_characters:
return character
else:

return None``````

The Python version doesn’t require much changing. We simply changed the initial definition of `previously_encountered_characters` from an empty array literal (`[]`) to a `set` constructor and call on set’s `add()` method instead of the `append()` method for arrays.

Here’s the JavaScript version:

``````function firstRecurringCharacter(text) {
let previouslyEncounteredCharacters = new Set()

for (const character of text) {
if (previouslyEncounteredCharacters.has(character)) {
return character
} else {
}
}

return null
}``````

The JavaScript version requires only a little more changing:

• The initial definition for `previouslyEncounteredCharacters` was changed to a `Set` constructor.
• We changed the array `includes()` method to the set `has()` function.
• We also changed the array `push()` method to the set `add()` method.

Changing the data structure that stores the characters that we’ve encountered before reduces the complexity to O(n), which is much better.

## Coming up next

In the next article in this series, we’ll tackle a slightly different problem: Can you write a function that returns the first non-recurring character in a string?

Categories

## Programmer interview challenge 1, revisited: Revising “Anagram” in Python and implementing it in JavaScript

In the previous article, I wrote about a challenge that’s often given to programmers at a tech interview: Write a program that determines if two words are anagrams. I posted a solution in Python; check it out here. In this article, we’ll refactor the Python code and write a JavaScript implementation.

## Refactoring the Python version

Looking at the code for `anagram()`, it’s quite clear that it isn’t DRY (Don’t Repeat Yourself), but manifestly the opposite: WET (Write Everything Twice)!

Under the time constraints of a technical interview, you might not always have the time or cognitive bandwidth to keep your code DRY, but if you should try to do so if possible. You may find that it helps convey your algorithmic thinking more effectively to the interviewer, and that’s what you want. After all, your goal throughout the process is to prove that you can actually program.

The repeated code is the part that takes a string, sorts its characters into alphabetical order, and removes the leading space if it exists. Let’s turn that code into its own method:

```def sortLetters(word):
# Returns the given word with its letters sorted
# into alphabetical order and with any
word_lowercase = word.lower()
return ''.join(sorted(word_lowercase)).lstrip()```

With this method defined, we can use it in `anagram()`. In fact, we can nest it within `anagram()`. Here’s the revision:

```def anagram(first_word, second_word):
# Returns True if the given words are made of the exact same characters,
# ignoring capitalization and spaces.

def sortLetters(word):
# Returns the given word with its letters sorted
# into alphabetical order and with any
word_lowercase = word.lower()
return ''.join(sorted(word_lowercase)).lstrip()

return sortLetters(first_word) == sortLetters(second_word)```

Creating the `sortLetters()` method doesn’t just DRY up the code, but helps the method better convey what it does. Now, what `anagram()` does is very clearly conveyed by its return statement: it tells you if the first word with its letters sorted is the same as the second word with its letters sorted.

I confirmed that this refactored code works by running the tests, which show just how useful having tests is.

## Implementing `anagram()` in JavaScript

Here’s `anagram()` in JavaScript:

```function anagram(firstWord, secondWord) {

function sortLetters(word) {
return word
.toLowerCase()
.split('')
.sort()
.join('')
.trim()
}

return sortLetters(firstWord) === sortLetters(secondWord)
}```

Note that the JavaScript version of `sortLetters()` is structured slightly differently from the Python version. That’s because JavaScript’s `sort()` is an array method rather than a general function like Python’s `sorted()`.

In the JavaScript version of sortLetters(), I use method chaining to spell out what happens to the given word step by step:

1. Convert the word to lower case
2. Convert that into an array of characters
3. Sort that array
4. Convert that array into a string
5. Remove any trailing or leading whitespace

I could’ve written `sortLetters()` this way…

```function sortLetters(word) {
return word.toLowerCase().split('').sort().join('').trim()
}```

…but I find that “put each method in the chain on its own line” approach more clearly conveys what I’m trying to do:

```function sortLetters(word) {
return word
.toLowerCase()
.split('')
.sort()
.join('')
.trim()
}```

Next: The Swift version!

Categories

## Programmer interview challenge 1: Anagram

An anagram is a word, phrase, or name that can be formed by rearranging the letters in another word, phrase, or name. For example, iceman is an anagram of cinema, and vice versa. Ignoring spaces and capitalizations, “Florida” is an anagram of “rod fail”.

“Anagram” is a common programming challenge that I’ve seen issued to prospective developers in technical interviews: Write a program or function that can tell if two given words are anagrams of each other. Here’s how you solve it.

## The general idea

One solution to the problem is hinted at in the definition of “anagram”. Let’s look at it again:

An anagram is a word, phrase, or name that can be formed by rearranging the letters in another word, phrase, or name.

The word rearranging should be your hint. Somehow, the solution should involve rearranging the letters of both words so that you can compare them. Another word for rearranging is reordering, and when you encounter that word in programming, you should think of sorting. That’s where the solution lies:

If two words are anagrams of each other, sorting each word’s letters into alphabetical order should create two identical words. For example, if you sort the letters in cinema and iceman into alphabetical order, both will be turned into aceimn.

With that in mind, let’s try writing an anagram-detecting function. Given two strings, it should return `true` if they’re anagrams of each other, and `false` otherwise.

## The Python version

This assumes that you’ve got Python and pytest installed on your system. I recommend installing the Individual Edition of the Anaconda Python distribution, followed by entering `pip install pytest` at the commend line.

Let’s do this the test-first way. We’ll write the test first, and then write the code. This means that we’ll want to create two files:

• anagram.py, which will contain the actual code of the solution, and
• test_anagram.py, which will contain test for that code.

Here’s the code for the test:

```import pytest
from anagram import anagram

def test_simple_anagram():
assert anagram('iceman', 'cinema'), "'cinema' is an anagram of 'iceman'."```

…and here’s the code for the initial iteration of the anagram function:

```def anagram(first_word, second_word):
return False```

To run the test, enter `pytest` at the command line. You should see output that looks like this:

Now that we have a failing test, let’s write code to make it pass.

Sorting the letters in a string is Python can be done by using a couple of methods:

• `sorted()`, which when given a string, returns an array containing that string’s letters in ascending order. For example, `sorted('cinema')` returns `['a', 'c', 'e', 'i', 'm', 'n']`.
• `join()`, which when given a string and an array, returns a string where the elements of the array are joined by the given string. For example, `'*'.join(['a', 'b', 'c'])` returns `'a*b*c'`.

Here’s my code:

```def anagram(first_word, second_word):
first_word_sorted = ''.join(sorted(first_word))
second_word_sorted = ''.join(sorted(second_word))
return first_word_sorted == second_word_sorted```

Running `pytest` now gives a passing test:

Let’s now deal with cases with capitalization and spaces. Ideally, the `anagram()` method should treat “Florida” and “rod fail” as anagrams. We’ll specify this in the test:

```import pytest
from anagram import anagram

def test_simple_anagram():
assert anagram('iceman', 'cinema'), "'cinema' is an anagram of 'iceman'."

def test_complex_anagram():
assert anagram('Florida', 'rod fail'), "'rod fail', if you ignore spaces and capitalization, is an anagram of 'Florida'."```

Running `pytest` yields these results: 1 failed test and 1 passed test…

We can fix this through the use of another two methods:

• `lower()`, which when applied to a string, converts all its letters to lowercase. For example, `'RADAR'.lower()` returns `'radar'`.
• `lstrip()`, which when applied to a string, removes any whitespace characters from the left side. Since the space character has a lower value than any letter in the alphabet, it will always be the leftmost character in a string whose characters have been sorted into ascending order.

Here’s my revised code:

```def anagram(first_word, second_word):
first_word_lowercase = first_word.lower()
first_word_sorted = ''.join(sorted(first_word_lowercase)).lstrip()
second_word_lowercase = second_word.lower()
second_word_sorted = ''.join(sorted(second_word_lowercase)).lstrip()
return first_word_sorted == second_word_sorted```

Running `pytest` now shows that all the tests pass:

Just to be safe, let’s add a test to make sure than `anagram()` returns `False` when given two strings that are not anagrams of each other:

```import pytest
from anagram import anagram

def test_simple_anagram():
assert anagram('iceman', 'cinema'), "'cinema' is an anagram of 'iceman'."

def test_complex_anagram():
assert anagram('Florida', 'rod fail'), "'rod fail', if you ignore spaces and capitalization, is an anagram of 'Florida'."

def test_non_anagram():
assert anagram('ABC', 'xyz') == False, "'ABC' and 'xyz' are not anagrams."```

All test pass when `pytest` is run:

And trying all sorts of pairs of strings confirms what the test tells us: `anagram()` works!

```# All of these return True
anagram('Oregon', 'no ogre')
anagram('North Dakota', 'drank a tooth')
anagram('Wisconsin', 'cows in sin')

# All of these return False
anagram('Florida', 'i oil sauna') # Try Louisiana
anagram('New York', 'on my wig') # Try Wyoming
anagram('Georgia', 'navy sin panel') # Try Pennsylvania
```

…and there you have it!

Next: Implementing `anagram()` in JavaScript, Swift, and possibly other languages.

Categories

## Jeff Atwood: A Very Brief Interview

Over at Canadian Developer Connection, we’ve got one more video from PDC in which Yours Truly conducted the interview: it’s with Jeff Atwood, the guy behind the blog Coding Horror and co-creator of Stack Overflow. It’s a brief interview; there were many people who wanted a slice of Jeff’s time, and we were lucky to even be able to buttonhole for as long as we did.

We’ll catch up for beers and Rock Band soon, Jeff!