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:

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

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:

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…

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

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:

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

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:

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:

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:

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:

All test pass when pytest is run:

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

…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