CareerCup

I assume that making use of regular expressions, Socket API and system parse methods is a bit of overhead. At least, it's not what interviewers usually expect. Here's the code that gets the job done with one simple linear scan.

namespace CareerCup
{
    public class ValidIpAddress
    {
        public bool IsValidIpAddress(string input)
        {
            if (string.IsNullOrEmpty(input) || input.Length > 15)
            {
                return false;
            }

            int lastOctet = 0;
            bool hasLeadingZeros = false;
            int octetsCount = 0;
            for (int i = 0; i < input.Length; ++i)
            {
                bool checkLastOctet = false;
                char current = input[i];
                if (char.IsDigit(current))
                {
                    lastOctet = lastOctet * 10 + (input[i] - '0');
                    if (lastOctet == 0)
                    {
                        hasLeadingZeros = true;
                    }
                    if (i == input.Length - 1)
                    {
                        checkLastOctet = true;
                    }
                }
                else if (current == '.')
                {
                    checkLastOctet = true;
                }
                else
                {
                    return false;
                }

                if (checkLastOctet)
                {
                    if (lastOctet > 255 || (lastOctet != 0 && hasLeadingZeros))
                    {
                        return false;
                    }
                    lastOctet = 0;
                    hasLeadingZeros = false;
                    octetsCount++;
                }
            }

            return octetsCount == 4;
        }
    }
}

Here's the simple C# code for both recursive and iterative in-order traversals. The maximum stack size is equal to the tree height. For an arbitrary tree it is equal to O(n) in the worst case. For a perfectly balanced BST it is equal to O(lgN).

using System;
using System.Collections.Generic;

namespace CareerCup
{
    public class TreeNode
    {
        private readonly int _key;
        private readonly int _value;

        public TreeNode(int key, int value)
        {
            _key = key;
            _value = value;
        }

        public int Key
        {
            get
            {
                return _key;
            }
        }

        public int Value
        {
            get
            {
                return _value;
            }
        }

        public TreeNode Left { get; set; }

        public TreeNode Right { get; set; }
    }

    public class InorderTraversal
    {
        public void TraverseRecursively(TreeNode node, Action<TreeNode> callback)
        {
            if (node == null)
            {
                return;
            }

            TraverseRecursively(node.Left, callback);
            callback(node);
            TraverseRecursively(node.Right, callback);
        }

        public void TraverseIteratively(TreeNode node, Action<TreeNode> callback)
        {
            if (node == null)
            {
                return;
            }

            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (stack.Count > 0 || node != null)
            {
                if (node == null)
                {
                    TreeNode parent = stack.Pop();
                    callback(parent);
                    node = parent.Right;
                }
                else
                {
                    stack.Push(node);
                    node = node.Left;
                }
            }
        }
    }
}

using System;
using System.Collections.Generic;

namespace CareerCup
{
    public class BuildOrder
    {
        private const int Undiscovered = 1;
        private const int Discovered = 2;
        private const int Processing = 4;

        public void ResolveBuildOrder(string input)
        {
            var adjLists = Parse(input);
            var buildQueue = TopologicalSort(adjLists);

            foreach (var item in buildQueue)
            {
                Console.WriteLine(item);
            }
        }

        private Dictionary<char, LinkedList<char>> Parse(string input)
        {
            var result = new Dictionary<char, LinkedList<char>>();
            var tokens = input.Split(' ');

            foreach (var token in tokens)
            {
                char from = token[0], to = token[3];
                if (!result.ContainsKey(from))
                {
                    result[from] = new LinkedList<char>();
                }
                if (!result.ContainsKey(to))
                {
                    result[to] = new LinkedList<char>();
                }
                result[from].AddLast(to);
            }

            return result;
        }

        private Queue<char> TopologicalSort(Dictionary<char, LinkedList<char>> adjLists)
        {
            var states = new Dictionary<char, int>();
            foreach (var vertice in adjLists.Keys)
            {
                states[vertice] = Undiscovered;
            }
            var queue = new Queue<char>();

            foreach (var vertice in adjLists.Keys)
            {
                if ((states[vertice] & Discovered) != Discovered)
                {
                    DfsVisit(vertice, adjLists, states, queue);
                }
            }

            return queue;
        }

        private void DfsVisit(
            char root, 
            Dictionary<char, LinkedList<char>> adjLists, 
            Dictionary<char, int> states,
            Queue<char> postorderQueue)
        {
            states[root] |= Processing;
            states[root] |= Discovered;

            foreach (var child in adjLists[root])
            {
                if ((states[child] & Processing) == Processing)
                {
                    throw new Exception("Cycle found!");
                }

                if ((states[child] & Discovered) != Discovered)
                {
                    DfsVisit(child, adjLists, states, postorderQueue);
                }
            }

            states[root] ^= Processing;
            postorderQueue.Enqueue(root);
        }
    }
}

Naive approach is used to find a substring (which is OK if both words are short). If I had more time, I would something more advanced (e.g. Rabin–Karp algorithm).

using System;

namespace InterviewTasks
{
    internal static class MinLengthBetweenWords
    {
        public static int FindMinLength(string input, string x, string y)
        {
            if (string.IsNullOrEmpty(input))
            {
                throw new ArgumentException("input");
            }

            if (string.IsNullOrEmpty(x))
            {
                throw new ArgumentException("x");
            }

            if (string.IsNullOrEmpty(y))
            {
                throw new ArgumentException("y");
            }

            int whitespacesCount = 0;
            int lastXOccurence = -1;
            for (int i = 0; i < input.Length - x.Length + 1; ++i)
            {
                bool isSubstring = true;
                for (int j = 0; j < x.Length; ++j)
                {
                    if (input[i + j] != x[j])
                    {
                        isSubstring = false;
                        break;
                    }
                }

                if (isSubstring)
                {
                    lastXOccurence = i;
                }
            }

            if (lastXOccurence == -1)
            {
                return -1;
            }

            for (int i = lastXOccurence + x.Length; i < input.Length - y.Length + 1; ++i)
            {
                if (input[i] == ' ')
                {
                    whitespacesCount++;
                    continue;
                }

                bool isSubstring = true;
                for (int j = 0; j < y.Length; ++j)
                {
                    if (input[i + j] != y[j])
                    {
                        isSubstring = false;
                        break;
                    }
                }

                if (isSubstring)
                {
                    return whitespacesCount;
                }
            }

            return -1;
        }
    }
}

using System;

namespace CareerCup
{
    public class ShortestPalindrome
    {
        public int GetShortestPalindromeLength(string input)
        {
            if (string.IsNullOrEmpty(input))
            {
                throw new ArgumentNullException("input");
            }

            int leadingCharsNumber = 0;
            while (leadingCharsNumber < input.Length)
            {
                bool flag = true;
                for (int i = 0, j = input.Length - 1 - leadingCharsNumber;
                    i < j;
                    i++, j--)
                {
                    if (input[i] != input[j])
                    {
                        flag = false;
                        break;
                    }
                }

                if (flag)
                {
                    break;
                }

                leadingCharsNumber++;
            }

            return leadingCharsNumber + input.Length;
        }
    }
}

using System;
using System.Collections.Generic;

namespace InterviewTasks
{
    internal static class QuotationMarks
    {
        public static string[] GetAllStrings(string pattern)
        {
            if (string.IsNullOrEmpty(pattern))
            {
                throw new ArgumentException("Pattern should be a non-empty string");
            }

            List<int> quotationMarks = new List<int>();
            for (int i = 0; i < pattern.Length; ++i)
            {
                if (pattern[i] == '?')
                {
                    quotationMarks.Add(i);
                }
            }

            string[] result = new string[1 << quotationMarks.Count];
            for (int i = 0; i < result.Length; ++i)
            {
                char[] chars = pattern.ToCharArray();
                for (int j = 0; j < quotationMarks.Count; ++j)
                {
                    var quotationMarkPosition = quotationMarks[j];
                    chars[quotationMarkPosition] = ((i >> j) & 1) == 1 ? '1' : '0';
                }
                result[i] = new string(chars);
            }

            return result;
        }
    }
}