Solving Coding Interview Problems

One of the reasons I got into programming was that I loved solving problems. Brain teasers, crosswords, Encyclopedia Brown mysteries, sudoku, those weird word problems with all those statements where you have to figure out who lives in the blue house - bring them on!  Programming gave me that same rush as when I solved one of those puzzles. However, one thing I hear continuously from my peers is that they hate coding interviews.  This is surprising as I find them comparable to solving a puzzle.

I get that coding interviews are artificial, that they bear little resemblance to real programming, and that they can be stress inducing especially when they prevent you from coding in the IDE of your choice (forcing you to code on a whiteboard or in CodePad).  But they can also be fun (in a non-masochistic way).

First, make your peace that you are going to be happy regardless of the result of the interview.  Second, treat the coding problems presented like the puzzles and exercises you do for fun.  If you can remove the stresses and instead have fun, you are far more likely not to suffer brain-freeze and to be more successful.

Let's take a simple common coding problem.  How do you check if two strings are anagrams of each other?  Anagrams have all the same letters, just in a different order.  That reminds me, make sure you understand the problem before you start trying to solve it.  As far as I know, no interviewer subtracts points from you for asking for clarification.

So let's give this one a whirl, solving it using Swift:

extension String {

    func isAnagram(str: String) -> Bool {

        var str = str

        for char in self {

            let index = str.firstIndex(of: char)

            guard index != nil else { return false }

            str.remove(at: index!)

        }

        return str.isEmpty

    }

}

Nicely done. You even made it an extension of String and followed the naming convention for functions returning Bool. This is a straightforward implementation that solves the problem in a clear, understandable way. We have a copy of the comparison string and we just keep removing letters that we have in the source string.  If we wind up with an empty string, we matched each letter of the source string, regardless of the order.  However, this solution has a computational complexity of O(2N-squared) where N is the number of characters in the string.  Can we do better?  

Is there a way we could organize each string such that they could be compared directly?  Since the two strings may be anagrams, they would have the same number of occurrences of each letter, that sounds like a counted set.  A counted set, is a set of unique items (in this case letters) and the number of times they occur.  We can implement it with a Dictionary.  

func isAnagram(str: String) -> Bool {

        var dictSelf = [Character : Int]()

        var dictStr = [Character : Int]()

        for char in self {

            let sum = dictSelf[char, default: 0]

            dictSelf[char] = sum + 1

        }

        for char in str {

            let sum = dictStr[char, default: 0]

            dictStr[char] = sum + 1

        }

        return dictSelf == dictStr

    }

We just created a dictionary with the letter as the key and the number of occurrences as the value.  The computational complexity of this solution is O(3N).  Creating each dictionary is O(N) as is the comparison.

Swift doesn't't directly implement CountedSet in its standard library, but Objective-C/Foundation does.  Using NSCountedSet, the above solution becomes a single line:

func isAnagram(str: String) -> Bool {

        return NSCountedSet(array: Array(self)) == NSCountedSet(array: Array(str))

    }

One other common solution to this problem which is not quite as efficient ( O(N㏒(N)) ) as the above but uses the same reasoning of arranging the strings in such a way that they can be compared directly is:

func isAnagram(str: String) -> Bool {

        return self.sorted() == str.sorted()

    }

This solution has the tentative advantage that it is directly supported in Swift and will be more easily understood by Swift developers.

There are usually many right answers to any programming problem or interview question.  Look for a way to represent the data in a way that helps you more easily solve the problem.  Remember to relax, have fun, and you will do your best.  Thank you to Kevin Tarr for suggesting this problem.  You can find videos by Kevin here on a variety of programming problems.