Let’s Talk About TDD

One should be prepared to receive ninety-nine percent of an enemy’s attack and stare death right in the face in order to illumine the Path.” – Morihei Ueshiba

The first white-board question from the horrible interview that I had recently was a question that a great number of computer science students are familiar with. The question was stated as follows:

Devise an algorithm for detecting whether a given string is a palindrome (spelled the same way forwards and backwards). For example, “kayak”

After the interview I decided that I wanted to explore the idea in more depth using TDD as a development tool to ensure that as new code was added none of the previous editions were broken without my knowledge. I decided that since I was using C# and the methods would only affect strings that the IsPalindrome() methods should be extension methods. The entire solution, including the unit tests, can be found in my PalindromeExtension repository on BitBucket.

To begin with, I decided that I would implement IsPalindrome() the classical way. I started with a single static class set up as follows:

namespace PalindromeExtension
{
    public static class PalindromeExtensionMethod
    {
    }
}

The easiest place to start, in my opinion, is the most common case; therefore, my first unit test tested the case where the given string is not a palindrome, and was written as follows:

public class When_using_the_palindrome_extension_method
     {
         [TestMethod]
        public void And_the_given_string_is_not_a_palindrome_then_the_extension_returns_false()
         {
            //arrange
            
            const string notApalindrome = "This is not a palindrome";

            //act

            var observedResult = notApalindrome.IsPalindrome();

            //assert

            Assert.IsFalse(observedResult);
         }
     }

This test is easy enough to get passing and will pass with the following implementation of IsPalindrome():

public static class PalindromeExtensionMethod
     {
        public static bool IsPalindrome(this string value)
        {
            return false;
        }
     }

That implementation may seem like a “cop-out” to those of you not familiar with test driven development, but writing the minimum amount of code to make the test pass is a key concept in test driven development. This does two very important things to the development process. First, and most importantly, it keeps the development cycle on any piece of code short and keeps iterations fast. Second it keeps things that are extra and unnecessary out of the code base, because YAGNI. When it all comes down to it, the method should return false if the given string is not a palindrome. Don’t worry about when the string is a palindrome yet. That is not what this test is testing.

The next unit test should test the minimal positive case. That is to say, my next test case was, “if the string was a palindrome with a length of 2 then the extension should return true”. My test was written like this:

        const string twoLetterPalindrome = "oo";

        [TestMethod]
        public void And_the_given_string_is_a_palindrome_with_2_letters_then_the_extension_returns_true()
        {
            //act

            var observedResult = twoLetterPalindrome.IsPalindrome();

            //assert

            Assert.IsTrue(observedResult);
        }

The next step was to get this test to pass. This iteration is where most of the functionality in all three implementations came about. That can be expected in fairly simple problems like this one. Larger problems, however, grow slower with each unit test, but there is always exponentially more and more implementation per iteration until a certain point is reached in the implementation. The classical solution uses a pair of stacks. The string is pushed onto one stack and, character by character, popped of the first stack and then pushed onto the second stack. The stacks are then check to see if their elements are equivalent and if they are, then the string is a palindrome, otherwise loop until the first stack is empty. Here is the code to get the most recent test passing:

public static class PalindromeExtensionMethod
     {
         public static bool IsPalindrome(this string value)
         {
            var startingStack = StringToStack(value);
            var stackToCompareTo = new Stack<char>();

            while (startingStack.Count > 0)
            {
                stackToCompareTo.Push(startingStack.Pop());

                if (startingStack.ToString() == stackToCompareTo.ToString()) return true;
            }

             return false;
         }

        private static Stack<char>; StringToStack(string theStringToConvert)
        {
            var backwardStringAsArray = theStringToConvert.Reverse().ToArray();
            var stackToReturn = new Stack<char>();

            foreach (var charater in backwardStringAsArray)
            {
                stackToReturn.Push(charater);   
            }

            return stackToReturn;
        }

This gets the code to pass, but surprisingly for the wrong reason. Using the ToString() method on a stack in C# does not change the stack’s elements back into a string, it gives a little bit of information on what type of data structure it is and how many elements it contains. I didn’t think of this and didn’t realize that there was a problem until I wrote the next test, but that is how test driven development works at times. On to the next test which tests the case where the beginning of the palindrome is upper-case and the end is lower-case. Here is the test:

        [TestMethod]
        public void And_the_given_string_is_a_palindrome_with_2_letters_with_one_capital_then_the_extension_returns_true()
        {
            var testString = twoLetterPalindrome.First().ToString(CultureInfo.InvariantCulture).ToUpper() +
                             String.Join("", twoLetterPalindrome.Skip(1));
            //act

            var observedResult = testString.IsPalindrome();

            //assert

            Assert.IsTrue(observedResult);
        }

The LINQ expression is some magic so that I could change my two letter palindrome into a palindrome with the beginning upper-case and the ending lower-case. This unit test passed out of the gate. This befuddled me and after realizing the mistake that I had made earlier, I changed the previous implementation to read as follows:

         public static bool IsPalindrome(this string value)
         {
            var startingStack = StringToStack(value);
            var stackToCompareTo = new Stack<char>();

            while (startingStack.Count > 0)
            {
                stackToCompareTo.Push(startingStack.Pop());
                
                var first = new String(startingStack.ToArray());
                var second = new String(stackToCompareTo.ToArray());
                
                if (first == second) return true;
            }

             return false;
         }

With these changes, my most recent test is now failing for the reason I expected it to fail. Getting this test to pass is as easy as making sure that the input is all lower-case before doing any operations on it:

         public static bool IsPalindrome(this string value)
         {
            var startingStack = StringToStack(value.ToLower());
            var stackToCompareTo = new Stack<char>();

            while (startingStack.Count > 0)
            {
                stackToCompareTo.Push(startingStack.Pop());
                
                var first = new String(startingStack.ToArray());
                var second = new String(stackToCompareTo.ToArray());
                
                if (first == second) return true;
            }

             return false;
         }

The next case to test is when the string is 3 letters long an is a palindrome. Here is the test for that case:

        private const string threeLetterPalindrome = "mom";
        [TestMethod]
        public void And_the_given_string_is_a_palindrome_with_3_letters_then_the_extension_returns_true()
        {
            //act

            var observedResult = threeLetterPalindrome.IsPalindrome();

            //assert

            Assert.IsTrue(observedResult);
        }

To get this test to pass, it is sufficient to pop an extra character off the stack so that the the middle character is not being compared when the comparison is being done. However, doing this breaks all the unit tests for the 2 character palindromes. In order to test for the even cases and still return true when the palindrome is even. here are the changes that I made:

         public static bool IsPalindrome(this string value)
         {
            var startingStack = StringToStack(value.ToLower());
            var stackToCompareTo = new Stack<char>();

            while (startingStack.Count > 0)
            {
                stackToCompareTo.Push(startingStack.Pop());

                var middleCharacter = startingStack.Pop();                

                var first = new String(startingStack.ToArray());
                var second = new String(stackToCompareTo.ToArray());
                
                if (first == second || (middleCharacter + first == second)) return true;
            }

             return false;
         }

All the unit tests are green again and we can move on to the next test. This tests for an even length palindrome of size 4. I thought that this test was going to pass out the gate, but strictly following the principle of only writing enough code to get the tests passing has yielded an anomaly. Here is the test:

        private const string fourLetterPalindrome = "noon";
        [TestMethod]
        public void And_the_given_string_is_a_palindrome_with_4_letters_then_the_extension_returns_true()
        {
            //act

            var observedResult = fourLetterPalindrome.IsPalindrome();

            //assert

            Assert.IsTrue(observedResult);
        }

After a bit of searching, I realized that the reason that this case wasn’t passing, even though the other cases with palindromes of even length were passing, is because I had forgotten to put the middle character back on the beginning stack before proceeding to the next step. To fix this I added the following code right before the closing bracket for the loop:

     startingStack.Push(middleCharacter);

Expecting this to work, I ran all the tests, but the last test was still failing because an InvalidOperationException was being thrown. This was because there was a point at which I was trying to pop the starting stack and there was nothing to pop. To fix this I changed the test in the loop to read as follows:

     while (startingStack.Count > 1)

This completed the functionality of the classical approach to deciding if a string is a palindrome and all the unit tests passed. Before I go on to talk about the other two implementations I got out of this exercise, I want to talk a little about my testing setup. I use the Visual Studio Unit Testing Framework for my testing framework. This is mainly because I get it for free with Visual Studio and it is what I am familiar with. For my mocking framework I use RhinoMocks using Arange-Act-Assert style test writing instead of Record-Replay. In my opinion, Record-Replay unit testing is better suited for larger more complex objects and it is also a more difficult concept to teach in a text based forum.

With the more classical general solution completed, I began to think of ways to implement IsPalindrome() using some of the nice libraries that are provided by the .NET framework. LINQ came to mind and after writing a few unit tests that looked similar to the ones written above, I came up with this implementation:

public static bool LinqOnlyIsPalindrome(this string value)
        {
            return value.IsEvenLength() ? value.ToLower().Substring(0, (value.Count()/2)) == new string(value.ToLower().Substring((value.Count()/2)).Reverse().ToArray())
                : value.ToLower().Substring(0, (value.Count()/2)) == new string(value.ToLower().Substring((value.Count()/2) + 1).Reverse().ToArray());
        }

private static bool IsEvenLength(this string value)
        {
            return ((value.Count() & 1)==0);
        }

This is an impressively ugly solution to the problem, but it works and all unit tests pass. After some time it dawned on me that this is ugly because I had become hampered by the notion that the string needed to be split in half and the two halves to be check for equality. Splitting the word in half is not necessary per the definition of a palindrome “A palindrome is a word, phrase, number, or other sequence of symbols or elements that reads the same forward or reversed …” LINQ helps with this implementation as well and reduces the code to an elegant on line of code:

public static bool RidiculouslyEasyLinqOnlyIsPalindrome(this string value)
        {
           return value.ToLower().Equals(new string(value.ToLower().Reverse().ToArray()));
        }

That is all for palindromes and TDD for now.

Advertisements

The Tipping Point

Be grateful even for hardship, setbacks, and bad people. Dealing with such obstacles is an essential part of training in the Art of Peace.” – Morihei Ueshiba

When the venture down this road into the public world of blogging began, I am afraid I boxed myself in by saying, “The purpose of this blog is to take known coding interview questions, analyze them, formulate requirements, find a complete solution, and present one or more solutions for the question. The question will be the kata; the nameless interviewer will be the tori; and I will be the uke.” I have grown quite a bit in the past several months of silence. Reading, studying, learning and practicing have helped me to understand that my subject is restrictive and misleading. I don’t know if anyone should ever apologize for naivety, but it will help me by way of taking a first step forward into a new way of thinking. I am sorry for my restricted view that technical interview questions, whiteboard questions, and the ability to code on the fly in front of interviewers was the key to the golden opportunity in software development and also about the implication that this blog made that these were the most important things to consider. There is so much more to this software development thing than I could imagine. I vow to break free of this restricted mindset and state a new purpose, but let me tell you about my journey first.

I work for a small company. A company still struggling to find its foothold in the world. A company in its adolescence. A company kind enough to take a chance on a budding software developer, sans any training in actual software development. The leaders of this company, while extremely knowledgeable in their fields of expertise, are not business men, and are still learning how to be business men. Earlier this year, after months of subtle suggestion and coaxing from my product manager, my team members, and most notably myself, the Chief Executive Officer announced that it had come to his realization that the company website must be updated, and that, being the most vocal of the proponents, I would be the lead of this project. I was energized by this validation and poured my soul into the project, admittedly unbeknownst the the CEO.

In 3 weeks I had learned enough about .NET MVC3 to become extremely dangerous. In 3 months I had the current static website translated into MVC3 so that it worked exactly as the current static pages did; however, notably faster, and without the cruft that built up after many years of various developers adjusting and tweaking the site, without source control and the other tools common to the trade today. The goal was to learn MVC in the real world, and get the site into source control where it would be safe for posterity. Both goals were achieved.

In addition to the translation of the website, I helped build the front end UX for a web application that was going to be part of the updated site. It had been announced with great fanfare by the board of directors in a press release in which a deadline of 120 days was given to complete the web application. Despite the development team’s opinion that the cart had been put before the horse, this news had already been reported through all the news outlets that would listen to the story. And so we completed it in less than 120 days, knowing that it would go live before the updated website. Since our shop develops desktop applications, it was the most beautiful thing that I could create with the internet being the only mentor I could find to help me learn web development. Aside from my loving pets, I consider it my most cherished child, and I keep it safe in my BitBucket account to show to anyone who delights in these things.

As the go live date for the web application neared, without definitive plans on the future of the website project as a whole, my product manager and I secretively made plans to point the domain alias at the MVC version of the website with the web application placed neatly where it should be and made plans to move forward with the redesign of the company website on our own. The day before our secret plans were to come to fruition, the members of the board called and announced that they had contracted to have a WordPress site built to replace the antiquated company site. My product manager was relieved. I died inside. For the next 2 months I clutched at everything for motivation, and then one of my co-workers, one third of our development team, announced he was moving on to greener pastures. I was lost. The ship was sinking and I had forgotten how to swim. I realized that if I was going to survive and stay sane I had to learn what I didn’t know how to do. I had to learn how to search for a job, even though the one I had was still OK.

Little did I know that searching for a new job was going to be as difficult now as it was when I was green with no experience at all. After updating my LinkedIn page, polishing my resume, and making it public on Monster, the calls from recruiters poured in like an unstoppable deluge. Offers for this and that came in, sometimes as many as 6 a day. It was exciting and fatiguing at the same time.

Nothing incredibly interesting came for several weeks, and then, it came. A large, well known company wanted to vet me for a web development position. This was exciting because I had just found I was passionate about web development and was excited to see where that career could take me. I decided to move forward with the interview process although I was ambivalent about the company culture and working in a large corporate environment.

The interview process moved forward as follows:

  1. 4 technical assessments were administered in order to gauge my aptitude for items in the web development arena.
  2. A technical phone interview was conducted in which we discussed the points on my resume and went through several technical scenarios which were formulated as, “what would you do if …” questions.
  3. 6 personality assessments were administered.
  4. And finally a personal onsite interview with a panel of interviewers was conducted which included 3 white-board questions.

It took 3 weeks and was exhausting. The most exhausting part about it was that, by the time I had reached the personal interview, my research on the company had convinced me that the company culture fit was not right for me and that I was most likely going to decline any offers for employment from this company. I went to the personal interview anyhow hoping that they may change my mind about what I had read from others about the company culture on Glassdoor. Unfortunately, I realized that the reports of horrible culture were factual when, during the white board questions, the interviewers decided to multitask by having a business meeting while I answered the first question. During the second question, half the interviewers left the room to do something with no excuse or apology.

Unfortunately, I did not get the great pleasure of declining their offer, because there was no offer. The reason given to the recruiter for not proceeding with an offer was that they were considering me for a desktop application development position and I wouldn’t talk about anything except how much I wanted to do web development. If you recall, the job requisition was for a web developer. Emotionally drained, completely demoralized, and utterly exhausted, I realized that all the pomp and ceremony of a traditional technical interview for a development position could have been summed up in 2 questions:

  1. “I see from your resume that you have been doing desktop application development for 2 years, is this true?”
  2. “We are in need of someone who would like to do desktop application development, if given the opportunity, would you enjoy being the one to fill that position?”

All the important questions about culture and team fit would have been answered during the 6 month contract period that is standard with all positions in their software development division. In fact, Eric Dietrich outlines just this proposed process at the end of his blog post entitled, “What’s Your Greatest Weakness: The Employer-Candidate Impedance Mismatch”. So why did this company insist on making me dance like a monkey and perform under ridiculous amounts of stress just to answer two simple questions? I’d like to think that it was to see how well I can execute daily duties under high levels of stress, but the more realistic answer is that they don’t know what is really important to demonstrate success in a position, which is team fit.

Two benefits have come out of this experience for me. The first is that I am extremely satisfied with my current position. My current employer treats me like what I am, a human being. The other is the realization that my former purpose behind this blog was narrow and that the subject matter of this blog needs to be about practicing in all arenas of the software development field, of which coding is only one. To paraphrase myself in order to restate my purpose, “The purpose of this blog is to talk about items pertaining to the field of software engineering. The blog will be the kata; the subject matter will be the tori; and I will be the uke.”