Question: Take an input string and output the "encoded" string by using the following rules:

 [1] vowels are replaced with number: a->1, e->2, etc
 [2] consonants are replaced with previous letter b->a, c->b, etc
 [3] y goes to space
 [4] space goes to y
 [5] numbers are reversed
 [6] other characters remain unchanged(punctuation, etc.)
 [7] all output should be lower case
 E.g.: Hello World! => g2kk4yv4qkc!

My Solution:

  /// pre processed conversions for letters
  private static Dictionary<char, char> Convert;

  public static string encode(string stringToEncode) {

     // approach: pre process a mapping (dictionary) for letter conversions
     // use a Dict for fastest look ups.  The first run, will take a little
     // extra time, subsequent usage will perform even better
     if (Convert == null || Convert.Count == 0) BuildConversionMappings();

     // our return val (efficient Appends)
     StringBuilder sb = new StringBuilder(); 

     // used for reversing the numbers
     Stack<char> nums = new Stack<char>(); 

     // iterate the input string
     for(int i = 0; i < stringToEncode.Length; i++) {

        char c = stringToEncode[i]; 

        // we have 3 cases:
        // 1) is alpha ==> convert using mapping
        // 2) is number ==> peek ahead to complete the number
        // 3) is special char / punctunation ==> ignore

        if(Convert.ContainsKey(c)) {
           sb.Append(Convert[c]);
           continue;
        }

        if(Char.IsDigit(c)) {
           nums.Push(c);

           // we've reached the end of the input string OR
           // we've reached the end of the number
           if (i == stringToEncode.Length - 1
              || !Char.IsDigit(stringToEncode[i + 1])) {
              while (nums.Count > 0) {
                 sb.Append(nums.Pop());
              }
           }

           continue;
        }

        // not letter, not digit
        sb.Append(c);
     }
     return sb.ToString();
  }

  // create our mappings for letters
  private static void BuildConversionMappings() {

     Convert = new Dictionary<char, char>();

     // only loop once for both
     for(char c = 'B'; c<='Z'; c++) {
        // add capitals version
        char val = (char)(c - 1);
        val = Char.ToLower(val);
        Convert.Add(c, val);
        // add lower case version
        Convert.Add(Char.ToLower(c),val);
     }

     // special cases
     Convert['y'] = ' ';
     Convert['Y'] = ' ';
     Convert.Add(' ', 'y');

     // vowels
     char[] vowels = new char[] { 'a', 'e', 'i', 'o', 'u' };
     for(int i = 0;i < vowels.Length;i++) {
        var letter = vowels[i];
        var value = (i+1).ToString()[0];
        Convert[letter] = value;
        Convert[Char.ToUpper(letter)] = value;
     }
  }

I was asked this question for an interview and the only feedback I received was building a dictionary was a very poor choice and they were no longer interested in continuing the application process. I was surprised and disappointed, but I want to improve for the next time. What should I do better?

  • 5
    Odd. Dictionary would be exactly what I would choose for this task and hardly consider it "poor". – Jesse C. Slicer Nov 16 at 17:05
  • 1
    @JesseC.Slicer mhmm... if you'd like to be really strict about it then you don't actually need a dictionary, you could calculate everything on the fly... but why? I'm also wondering about the comment although I don't think using the dictionary itself was wrong but rather the way it's being constructed when you call encode and then all rules inside a single method... if a senior dev wrote this code I would send him home ;-] It's neither extendable nor maintainable. – t3chb0t Nov 16 at 17:15
  • 2
    @t3chb0t Yeah, I spoke too generically there. I was thinking of a similar thing I did for a ROT-13 coder. So what really needs to happen here is an enterprise rules engine that gets the codings from a cloud-based data store... – Jesse C. Slicer Nov 16 at 17:24
  • 4
    I should think a thoughful 2-way code review would be the most valuable part of the task. I want to know how you think, plumb your knowledge, the why of your code, get your thoughts on our "right" answer, etc. I'd say they blew the interview, not you. – radarbob Nov 16 at 19:09
  • 3
    Sounds like you dodged a bullet in that job. – Nic Hartley Nov 17 at 0:16
up vote 13 down vote accepted

There are couple of things that might have been done better...

  • Initilize the dictionary form a static constructor or call the method to initialize the field. The method should not access it internally but return a dictionary as a result. The field itself should be readonly.
  • foreach could be used to iterate the stringToEncode.
  • Names of internal variables could be better:
    • Convert sounds like a method name. The dictionary should be named Conversions.
    • nums should be digits
    • sb should be called encoded
  • TryGetValue could have been used instead of ContainsKey
  • The dictionary is case-insensitive only because you put all letters there. Instead you should use the StringComparer.OrdinalIgnoreCase and make the dictionary <string, char> but this would be inconvenient. You could create your own IEqualityComparer<char>. This will cut in half its size .
  • I wish more var (optional)
  • I wish more LINQ

Things that are already good:

  • I find using a dictionary was a good choice.
  • The use of a Stack to reverse the order is very clever.
  • Using StringBuilder for efficiency is definitely a good choice either.

When we apply all suggestions the code could look like this:

Creating the IReadOnlyDictionary which returns a result and uses a couple of additional helper variables. No for loops.

// pre processed conversions for letters
private static readonly IReadOnlyDictionary<char, char> Conversions = BuildConversionDictionary();

private static IReadOnlyDictionary<char, char> BuildConversionDictionary()
{
    var conversions = new Dictionary<char, char>(CaseInsensitiveCharComparer);

    var alphabet = Enumerable.Range('a', 'z' - 'a' + 1).Select(x => (char)x);
    var vowels = new char[] { 'a', 'e', 'i', 'o', 'u' };
    var consonants = alphabet.Except(vowels);

    // consonants are replaced with previous letter b->a, c->b, etc
    foreach (var c in consonants)
    {
        conversions.Add(c, (char)(c - 1));
    }

    // y goes to space
    // space goes to y
    conversions['y'] = ' ';
    conversions[' '] = 'y';

    // vowels are replaced with number: a->1, e->2, etc
    foreach (var (c, i) in vowels.Select((c, i) => (c, i + 1)))
    {
        conversions.Add(c, (char)('0' + i));
    }

    return conversions;
}

The alternative equality comparer (here I'm using a helper-factory from my libraries):

private static IEqualityComparer<char> CaseInsensitiveCharComparer =
    EqualityComparerFactory<char>.Create
    (
        (x, y) => StringComparer.OrdinalIgnoreCase.Equals(x.ToString(), y.ToString()),
        obj => StringComparer.OrdinalIgnoreCase.GetHashCode(obj.ToString())
    );

The refactored encode (which should be Encode). What has changed here is that I first check for digits. If it's not one and we have some then dump the stack to the builder and clear it, othewise do the rest. Below the loop we have to dump it once again in case there are some digits left at the end.

public static string Encode(string stringToEncode)
{
    if (string.IsNullOrEmpty(stringToEncode)) throw new ArgumentException(nameof(stringToEncode));

    // our return val (efficient Appends)
    var encoded = new StringBuilder();

    // used for reversing the numbers
    var digits = new Stack<char>();

    // iterate the input string
    foreach (var c in stringToEncode)
    {
        if (char.IsDigit(c))
        {
            digits.Push(c);
            continue;
        }

        if (digits.Any())
        {
            encoded.Append(digits.ToArray());
            digits.Clear();
        }

        if (Conversions.TryGetValue(c, out var converted))
        {
            encoded.Append(converted);
            continue;
        }

        // something else, undefined
        encoded.Append(c);
    }

    // "dump" what's left
    encoded.Append(digits.ToArray());

    return encoded.ToString();
}

I think you cannot do anything else having only 60 minutes.

  • 3
    I cannot begin to tell you how grateful I am you took the time to write such a beautiful, optimized, and improved solution. It reminds me that in my journey to becoming an excellent software engineer, there will always be much room for improvement. Thank you for taking the time to help me grow. – whiteshooz Nov 16 at 19:07
  • I'm honestly not sure that using a more complex comparer to save a few bytes of RAM is worth it, especially if you need to implement one yourself. What would be the speed implications of the more complex comparer? Seems like an optimization problem either way, where the right choice would depend on context. – jpmc26 Nov 16 at 23:03
  • @jpmc26 this time it's not because I want to save RAM. I just didn't want to have ToString all over the place. The comparer encapsulates this very nicely, and come on, a comparer is not rocket science, especially when you have helpers for their creation. I find it's one of the most natural things to use in c# saving tons of typing and errors. – t3chb0t Nov 17 at 5:42

Additional to @t3chb0t real code review, I would like to provide an alternative more object oriented implementaion.

Not sure if that solution is really better / more readable / appropriate for such a small problem - but at least it follows the SOLID principles:

public class InputProcessor
{
    private static readonly ICharStreamProcessor[] CharStreamProcessors;

    static  InputProcessor()
    {
        CharStreamProcessors = new ICharStreamProcessor[]
        {
            new VowelCharStreamProcessor(),
            new YCharStreamProcessor(),
            new WhiteSpaceCharStreamProcessor(),
            new ConsonantCharStreamProcessor(),
            new NumberCharStreamProcessor(),
            new DefaultCharStreamProcessor(),
        };
    }

    public string Process(string input)
    {
        var preprocessedInput = (input ?? string.Empty).ToLower();
        var resultBuilder = new StringBuilder();

        using (var enumerator = preprocessedInput.GetEnumerator())
        {
            var continueProcessing = enumerator.MoveNext();
            while (continueProcessing)
            {
                var processor = CharStreamProcessors.FirstOrDefault(p => p.CanProcess(enumerator.Current));

                if (processor == null)
                {
                    throw new InvalidOperationException($"Unable to find appropriate processor for character '{enumerator.Current}'.");
                }

                bool continueProcessingWithCurrentProcessor;
                ProcessResult result = null;
                do
                {
                    var accumulated = result?.Result ?? string.Empty;
                    result = processor.Process(enumerator.Current, accumulated);
                    continueProcessing = enumerator.MoveNext();

                    continueProcessingWithCurrentProcessor =
                        continueProcessing
                        && result.ContinueConsuming
                        && processor.CanProcess(enumerator.Current);
                } while (continueProcessingWithCurrentProcessor);

                resultBuilder.Append(result.Result);
            }
        }

        return resultBuilder.ToString();
    }
}

public class VowelCharStreamProcessor : ICharStreamProcessor
{
    private static readonly string vowels = "aeiou";
    private const int AsciiNumberFor1 = 49;

    public bool CanProcess(char c) => vowels.Contains(c);
    public ProcessResult Process(char c, string accumulate) => ProcessResult.Finished((char)(vowels.IndexOf(c) + AsciiNumberFor1));
}

public class ConsonantCharStreamProcessor : ICharStreamProcessor
{
    private static readonly string consonants = "bcdefghjklmnpqrstvwxyz";

    public bool CanProcess(char c) => consonants.Contains(c);
    public ProcessResult Process(char c, string accumulate) => ProcessResult.Finished((char)(c - 1));
}

public class YCharStreamProcessor : ICharStreamProcessor
{
    public bool CanProcess(char c) => c == 'y';
    public ProcessResult Process(char c, string accumulate) => ProcessResult.Finished(' ');
}

public class WhiteSpaceCharStreamProcessor : ICharStreamProcessor
{
    public bool CanProcess(char c) => c == ' ';
    public ProcessResult Process(char c, string accumulate) => ProcessResult.Finished('y');
}

public class NumberCharStreamProcessor : ICharStreamProcessor
{
    public bool CanProcess(char c) => char.IsDigit(c);
    public ProcessResult Process(char c, string accumulate) => ProcessResult.Continue(c + accumulate);
}

public class DefaultCharStreamProcessor : ICharStreamProcessor
{
    public bool CanProcess(char c) => true;
    public ProcessResult Process(char c, string accumulate) => ProcessResult.Finished(c);
}

public interface ICharStreamProcessor
{
    ProcessResult Process(Char c, string accumulate);
    bool CanProcess(Char c);
}

public class ProcessResult
{
    private ProcessResult(string result, bool continueConsuming = false)
    {
        this.ContinueConsuming = continueConsuming;
        this.Result = result;
    }

    public bool ContinueConsuming { get; }
    public string Result { get; }

    public static ProcessResult Continue(string result) => new ProcessResult(result, true);
    public static ProcessResult Finished(string result) => new ProcessResult(result);
    public static ProcessResult Finished(char result) => new ProcessResult(result.ToString());
}
  • I love the OO approach! Maybe in the future, I should flex this type of answer. I have the ability, but I've always feared it would send a signal that I create over engineered solutions to simple problems. Next time, I will make sure to ask the technical stakeholders these sort of questions. Thank you immensely for taking the time to provide such a cool solution. – whiteshooz Nov 16 at 19:40
  • 3
    I think it is OK to ask the interviewer what exactly she intends with the question. Should the solution be optimized for performance, development speed, following clean code principles... what ever. That shows also, that you are able to clarify unclear requirements in advance - a very importent ability for software developers ;) – JanDotNet Nov 16 at 19:55
  • I like this edition and usually this kind of approach pays off. Especially in large projects where you already can anticipate changes that will come. This could be the second part of the interview for a senior position where you could ask them about the design. It might however be very difficult to come up with somethig like this and make it work during a 60 minutes interview ;-) – t3chb0t Nov 16 at 20:45
  • 2
    @jpmc26 I have to maintain a piece of $%&§ software that has been build procedurally and implement changes that the business requires every couple of weeks or months... you have to spend hours making sure you're doing the right thing in the right place and then another couple of hours making sure you did it right because every change can break everything else... and it already happened multiple times. Nobody understands that this needs to be rewritten to a more OO solution where we just could put the modules together or create new ones easily. [..] – t3chb0t Nov 17 at 7:09
  • 2
    @jpmc26: the good thing of that solution is: you dont have to understand the complex part (Process method) if you need to modify / extend the business logic. :) – JanDotNet Nov 17 at 8:45

You should check the input for a valid string:

  if (string.IsNullOrWhiteSpace(stringToEncode))
    return stringToEncode;

The check for Convert.Count == 0 is a little strange in that Convert is a private field and only set in one method where we can assume it will be constructed equally every time it is called:

if (Convert == null || Convert.Count == 0) BuildConversionMappings();

But no real harm done, without that check you could just simplify the call like this:

Convert = Convert ?? BuildConversionMappings();

You can set the capacity of the StringBuilder which is a performance improvement:

  StringBuilder sb = new StringBuilder(stringToEncode.Length);

You use continue a couple of times in your loop:

    if (Convert.ContainsKey(c))
    {
      sb.Append(Convert[c]);
      continue;
    }

    if (char.IsDigit(c))
    {
      ...

If you replace continue with else if statements it will IMO give a more readable code:

  for (int i = 0; i < stringToEncode.Length; i++)
  {

    char c = stringToEncode[i];
    if (Convert.ContainsKey(c))
    {
      sb.Append(Convert[c]);
    }
    else if (char.IsDigit(c))
    {
      nums.Push(c);
      if (i == stringToEncode.Length - 1
         || !char.IsDigit(stringToEncode[i + 1]))
      {
        while (nums.Count > 0)
        {
          sb.Append(nums.Pop());
        }
      }
    }
    else
    {
      sb.Append(c);
    }
  }

That said, I think you main method and main loop are quite good and easy to read and understand, and the Dictionary idea is just the way to go. But the way you build the dictionary is maybe a little cumbersome.

To the bone you just map between two sets of chars (except for the numbers):

  const string keys =    "abcdefghijklmnopqrstuvwxyz ";
  const string values =  "1abc2efg3ijklm4opqrs5uvw yy";

You could look up by finding the index of chars from the input string in keys and fetch the corresponding value from values (lower case). But that would require two look ups per char, and therefore the Dictionary is much better. A Dictionary<char, char> can be build from the above keys and values in the following way:

private static Dictionary<char, char> ConstructMap()
{
  const string keys =    "abcdefghijklmnopqrstuvwxyz ";
  const string values =  "1abc2efg3ijklm4opqrs5uvw yy";

  IEnumerable<(char c, char cm)> map = keys.Zip(values, (c, cm) => (c, cm));
  return map.ToDictionary(ccm => ccm.c, ccm => ccm.cm);
}

because string implements IEnumerable<char>


Just for the exercise I implemented a quite old school indexed for-loop like this:

private static readonly Dictionary<char, char> charMap = ConstructMap();

public static string HHEncode(string data)
{
  char[] result = new char[data.Length];

  for (int i = 0; i < data.Length; i++)
  {
    if (charMap.TryGetValue(char.ToLower(data[i]), out char value))
    {
      result[i] = value;
    }
    else if (char.IsDigit(data[i]))
    {
      int j = i + 1;
      while (j < data.Length && char.IsDigit(data[j])) j++;

      j--;
      for (int k = 0; k <= (j - i) / 2; k++)
      {
        result[i + k] = data[j - k];
        result[j - k] = data[i + k];
      }
      i = j;
    }
    else
    {
      result[i] = data[i];
    }
  }

  return new string(result);
}

The main difference to yours is how I handle numbers

  • Personally, I can't stand the else if - I treat it like goto ;-P – t3chb0t Nov 16 at 20:48
  • @t3chb0t: I've never heard that comparison before - but it's your world, I'm only living in it :-). As long as the chain isn't too long (as in the above) I think it's OK. On the other hand: what about five or even ten if-else statements vs the same number of continues? I would prefer the first. – Henrik Hansen Nov 16 at 21:04
  • nah, ifs only have a nice and pretty alignment and are easier to read, you can better use helper variables for their conditions and even better comment them if necessary. This is not possible with else if because they are glued to the previous block. This is my theory behind it ;-) – t3chb0t Nov 16 at 21:10
  • Thank you for the feedback! I like many of your suggestions and your usage of LINQ zip is sexy! To explain my choice of using continue. I have a profound dislike for nested if statements. I've found that if there is no reason to stay in the if block, I'd rather skip to the next for loop iteration. At the end of the day it's more of a preference like you stated and other people have echoed. – whiteshooz Nov 16 at 21:53
  • 1
    @whiteshooz: I do not disagree with you. But on the other hand, never hesitate to use a consistent, easy maintainable and intuitive solution. An interview question is also about creativity and productivity as well as "real" coding skills. – Henrik Hansen Nov 17 at 7:12

Just FYI, here's what the pre-built (no need for the BuildConversionMappings method any more) dictionary would look like:

/// pre processed conversions for letters
private static readonly IDictionary<char, char> Convert = new Dictionary<char, char>
{
    { 'A', '1' }, { 'E', '2' }, { 'I', '3' }, { 'O', '4' }, { 'U', '5' },
    { 'a', '1' }, { 'e', '2' }, { 'i', '3' }, { 'o', '4' }, { 'u', '5' },
    { 'Y', ' ' },
    { 'y', ' ' },
    { ' ', 'y' },
    { 'B', 'a' }, { 'C', 'b' }, { 'D', 'c' }, { 'F', 'e' }, { 'G', 'f' }, { 'H', 'g' },
    { 'J', 'h' }, { 'K', 'j' }, { 'L', 'k' }, { 'M', 'l' }, { 'N', 'm' }, { 'P', 'o' },
    { 'Q', 'p' }, { 'R', 'q' }, { 'S', 'r' }, { 'T', 's' }, { 'V', 'u' }, { 'W', 'v' },
    { 'X', 'w' }, { 'Z', 'y' },
    { 'b', 'a' }, { 'c', 'b' }, { 'd', 'c' }, { 'f', 'e' }, { 'g', 'f' }, { 'h', 'g' },
    { 'j', 'h' }, { 'k', 'j' }, { 'l', 'k' }, { 'm', 'l' }, { 'n', 'm' }, { 'p', 'o' },
    { 'q', 'p' }, { 'r', 'q' }, { 's', 'r' }, { 't', 's' }, { 'v', 'u' }, { 'w', 'v' },
    { 'x', 'w' }, { 'z', 'y' }
};

Things slightly of note:

  • Pascal-case the method name encode to Encode.
  • Simplify the dictionary from the .ContainsKey.[] combo to a single call to .TryGetValue
  • 2
    I could have manually entered all the mappings, but that didn't seem like the best way to demonstrate my ability to problematically populate the cache. This was a coding interview after all. =) I agree the method Encode was not Pascal-case, but it was required to be this way because this problem was verified by Hackerrank. They had thier skeleton of the method improperly named. Lastly, I like your suggestion of using .TryGetValue() so I only have to look up the hash once! – whiteshooz Nov 16 at 18:03

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.