Function to Find Anagrams

Reading time ~3 minutes

For a technical interview over video chat for an API Developer position, I was asked to write a function while sharing my screen that would compare two strings and determine whether or not they formed an anagram. This article outlines my approach to solving the problem.

This solution has O(n) runtime complexity. Since you must iterate over the strings to get the characters, O(n) is the best possible runtime average that can be achieved for this problem. (Yes, the interviewers did ask me wht the big-O complexity of my solution was.)

Here is my solution in C# with some additional cleanup after the interview:

using System.Collections.Generic;
using System.Linq;

namespace Interview.Main
{
    public class Interview
    {
        /// <summary>
        /// Compares two strings for an anagram
        /// </summary>
        /// <param name="str1">First string for comparison</param>
        /// <param name="str2">Second string for comparison</param>
        /// <returns>True if the two strings form an anagram, otherwise false</returns>
        public bool IsAnagram(string str1, string str2)
        {
            // **Assumption** Leading/trailing whitespace is acceptable input, but not considered for comparison.
            str1 = str1.Trim();
            str2 = str2.Trim();

            // internal whitespace breaks the definition of an anagram
            if (str1.Any(char.IsWhiteSpace) || str2.Any(char.IsWhiteSpace))
            {
                return false;
            }

            // null strings break the definition of an anagram
            if (string.IsNullOrWhiteSpace(str1) || string.IsNullOrWhiteSpace(str2))
            {
                return false;
            }

            var str1CharCounts = TallyChars(str1);
            var str2CharCounts = TallyChars(str2);

            // check for differring keys and key counts
            if (str1CharCounts.Count != str2CharCounts.Count ||
                !str1CharCounts.Keys.All(x => str2CharCounts.ContainsKey(x)))
            {
                return false;
            }

            foreach (var (key, value) in str1CharCounts)
            {
                if (str2CharCounts[key] != value)
                {
                    return false;
                }
            }

            return true;
        }

        /// <summary>
        /// Counts the occurrence of each letter in a given string
        /// </summary>
        /// <param name="str">The string containing characters to tally</param>
        /// <returns>A Dictionary mapping the letters that occurred in the string to the total number of times that they occurred in the string</returns>
        public Dictionary<char, int> TallyChars(string str)
        {
            var chars = str.ToCharArray(0, str.Length);
            var map = new Dictionary<char, int>();
            foreach (var c in chars)
            {
                if (map.TryGetValue(c, out var currentCount))
                {
                    map[c] = currentCount + 1;
                }
                else
                {
                    map.Add(c, 1);
                }
            }

            return map;
        }
    }
}

Additionally, I wrote some quick tests. These are very unpolished, but they ensured that I my code worked as intended.

using FluentAssertions;
using PowerDMS.Main;
using Xunit;

namespace Interview.Tests
{
    public class InterviewTests
    {
        private Interview Interview { get; }

        public InterviewTests()
        {
            Interview = new Interview();
        }

        [Fact]
        public void Returns_True_If_Anagram()
        {
            var str1 = "cinema";
            var str2 = "iceman";
            Interview.IsAnagram(str1, str2).Should().BeTrue();
        }

        [Fact]
        public void Returns_False_If_Two_Strings_Have_Same_Length_Different_Letters()
        {
            var str1 = "ars";
            var str2 = "set";

            Interview.IsAnagram(str1, str2).Should().BeFalse();
        }

        [Fact]
        public void Returns_False_If_Two_Strings_Have_Differring_Lengths()
        {
            var str1 = "arst";
            var str2 = "qw";

            Interview.IsAnagram(str1, str2).Should().BeFalse();
        }

        [Fact]
        public void Returns_False_If_Strings_Have_Same_Letters_Different_Count()
        {
            var str1 = "aarr";
            var str2 = "arrr";

            Interview.IsAnagram(str1, str2).Should().BeFalse();
        }

        [Fact]
        public void Returns_False_If_Strings_Contain_Whitespace()
        {
            var str1 = "aa rr";
            var str2 = "aa rr";

            Interview.IsAnagram(str1, str2).Should().BeFalse();
        }

        [Fact]
        public void Returns_False_If_String_Is_Whitespace()
        {
            var str1 = "";
            var str2 = "aarr";

            Interview.IsAnagram(str1, str2).Should().BeFalse();
        }

        [Fact]
        public void Leading_And_Trailing_Whitespace_Are_Acceptable()
        {
            var str1 = " arst";
            var str2 = "sart    ";

            Interview.IsAnagram(str1, str2).Should().BeTrue();
        }
    }
}

Software Interfaces in the Wild

Interfaces are a powerful tool when used properly. This article explores a real-world example. Continue reading

Microservices are not Micro; They are Vertical

Published on October 16, 2018

Giving Life to Legacy Apps with Docker

Published on October 07, 2018