Tag: Interviews

Categories
Career Programming

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:

If you give the function this input……it will produce this output:
'abcdeefg''e'
'abccddee''c'
'abcde'null / None / nil

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”:

“Big O” complexity chart
Tap to view at full size.

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:
            previously_encountered_characters.add(character)
            
    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 {
            previouslyEncounteredCharacters.add(character)
        }
    }
    
    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
Career Programming

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
  # leading space removed.
  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
    # leading space removed.
    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!

Previously, in the “Programmer interview challenge” series

Categories
Career Programming

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
Uncategorized

Jeff Atwood: A Very Brief Interview

joey_devilla_jeff_atwood

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!

Links