CareerCup

public enum PointsState
    {
        None,
        Row,
        Column,
        Diagonal
    }
    public class Point
    {
        public int X { get; set; }
        public int Y { get; set; }
    }

    public class PointChecker
    {
        public static PointsState GetPointsState (IList <Point> points)
        {
            if (points.Count < 2)
                return PointsState.None;

            var firstPoint = points[0];

            bool sameX = true;
            bool sameY = true;
            bool sameDiagonal = true;

            for (var i = 1; i < points.Count; i++)
            {
                if (points [i].X != firstPoint.X)
                    sameX = false;

                if (points [i].Y != firstPoint.Y)
                    sameY = false;

                // check if diagonal!

                if (firstPoint.X * points [i].Y != firstPoint.Y * points [i].X)
                    sameDiagonal = false;
            }

            if (sameX)
                return PointsState.Row;
            if (sameY)
                return PointsState.Column;
            if (sameDiagonal)
                return PointsState.Diagonal;
            return PointsState.None;
        }
    }

So the Binary tree is not a sorted binary tree. In this case we have to perform a full scan:

public class Node
    {
        public Node Left { get; set; }
        public Node Right { get; set; }
        public int Value { get; set; }

        public override string ToString()
        {
            return Value.ToString(CultureInfo.InvariantCulture);
        }
    }

    public class TreeSearcher
    {
        public static Node Search(Node parent, int valueToSearch)
        {
            return SearchInternal(parent, valueToSearch, null);
        }

        private static Node SearchInternal(Node n, int valueToSearch, Node parentNode)
        {
            if (n == null)
                return null;

            if (n.Value == valueToSearch)
                return parentNode;

            var val = SearchInternal(n.Left, valueToSearch, n);
            return val ?? SearchInternal(n.Right, valueToSearch, n);
        }
    }

There are two approaches possible: The first one is: Perform a binary search vertically (Which takes O ( N )) and then perform a binary search inside the row found (which takes O (M)). Since O (N) + O(M) takes O (N*M) then we can say that it's like performing a binary search over a huge array that is composed of segments made of rows. So that

BigArray[i] = matrix[i / M, i % M]. So it's simpler to peform a binary search over the BigArray.

public static int? FindFirstPartition(int[] arr)
        {
            if (arr == null)
                return null;
            if (arr.Length == 0)
                return arr[0]; // the single ellement is in fact a "partition"

            var minValues = new Stack<int>();

            for (var i = arr.Length - 1; i > 0; i--)
            {
                if (minValues.Count == 0)
                    minValues.Push(arr[i]);
                else
                {
                    var min = minValues.Peek();
                    if (arr[i] <= min)
                        minValues.Push(arr[i]);
                }
            }

            var leftMax = int.MinValue;

            foreach (var current in arr)
            {
                if (current >= leftMax && (minValues.Count == 0 || current <= minValues.Peek()))
                    return current; // found it!
                // Otherwise, advance!
                if (leftMax <= current)
                    leftMax = current;

                if (minValues.Peek() == current)
                    minValues.Pop();
            }

            return null;
        }

public static class Merger
{
public static IEnumerable<int> Merge(IEnumerable<int> a, IEnumerable<int> b)
{
if (a == null && b == null)
yield break;

if (a == null)
{
foreach (var item in b)
yield return item;
yield break;
}

if (b == null)
{
foreach (var item in a)
yield return item;

yield break;
}

using (var leftEnumerator = a.GetEnumerator())
using (var rightEnumerator = b.GetEnumerator())
{
var leftHasValue = leftEnumerator.MoveNext();
var rightHasValue = rightEnumerator.MoveNext();

while (leftHasValue || rightHasValue)
{
if (!leftHasValue)
{
var val = rightEnumerator.Current;
rightHasValue = rightEnumerator.MoveNext();
yield return val;
continue;
}

if (!rightHasValue)
{
var val = leftEnumerator.Current;
leftHasValue = leftEnumerator.MoveNext();
yield return val;
continue;
}

var leftValue = leftEnumerator.Current;
var rightValue = rightEnumerator.Current;

if (leftValue <= rightValue)
{
leftHasValue = leftEnumerator.MoveNext();
yield return leftValue;
}
else
{
rightHasValue = rightEnumerator.MoveNext();
yield return rightValue;
}
}
}
}
}

public static class Merger
    {
        public static IEnumerable<int> Merge(IEnumerable<int> a, IEnumerable<int> b)
        {
            if (a == null && b == null)
                yield break;

            if (a == null)
            {
                foreach (var item in b)
                    yield return item;
                yield break;
            }
                
            if (b == null)
            {
                foreach (var item in a)
                    yield return item;

                yield break;
            }

            using (var leftEnumerator = a.GetEnumerator())
            using (var rightEnumerator = b.GetEnumerator())
            {
                var leftHasValue = leftEnumerator.MoveNext();
                var rightHasValue = rightEnumerator.MoveNext();

                while (leftHasValue || rightHasValue)
                {
                    if (!leftHasValue)
                    {
                        var val = rightEnumerator.Current;
                        rightHasValue = rightEnumerator.MoveNext();
                        yield return val;
                        continue;
                    }

                    if (!rightHasValue)
                    {
                        var val = leftEnumerator.Current;
                        leftHasValue = leftEnumerator.MoveNext();
                        yield return val;
                        continue;
                    }

                    var leftValue = leftEnumerator.Current;
                    var rightValue = rightEnumerator.Current;

                    if (leftValue <= rightValue)
                    {
                        leftHasValue = leftEnumerator.MoveNext();
                        yield return leftValue;
                    }
                    else
                    {
                        rightHasValue = rightEnumerator.MoveNext();
                        yield return rightValue;
                    }
                }
            }
        }
    }

public class Resolver {
        public static IEnumerable <Tuple<int, int>> GetPairs(IEnumerable<int> numbers) {
            var array = numbers.ToArray ();
            if (array.Length < 2) // we don't have pairs!!
                yield break;

            Array.Sort (array);

            if (array.Length == 3) {
                if (array [0] + array [1] == array [2])
                   yield return new Tuple <int, int> (array [0], array [1]);
                // There are no other possibilities due to the fact that the array is sorted!
                yield break;
            }
            
            var hSet = new HashSet <int> (array);

            var lastPosition = array.Length - 1;

            for (var i = 0; i < lastPosition; ++i) {
                // break condition!
                if ((array [i] < 2 ? 2 : array [i] << 1) > array [lastPosition]) {
                    yield break; // we found a situation where we would not find the sum in our array anylonger!
                }

                for (var j = i + 1; j < array.Length; ++j) {
                    var sum = array [i] + array [j];

                    if (hSet.Contains (sum)) {
                        yield return new Tuple <int, int> (array [i], array [j]);
                    }
                }
            }
        }
    }

C# implementation, it runs in big O (N). More exactly, o (n + k) space and in o(n+k) time where k is the count of even numbers.

public static int GetFirstWithEvenAppearance(int[] numbers)
        {
            Dictionary<int, int> firstIndexes = new Dictionary<int, int>();
            HashSet<int> evenNumbers = new HashSet<int>();

            for (var i = 0; i < numbers.Length; ++i)
            {
                var number = numbers[i];

                if (false == firstIndexes.ContainsKey(number))
                    firstIndexes[number] = i; // the first apparition is not even
                else if (false == evenNumbers.Add (number)) // if we failed to add, then that means that it's not even
                    evenNumbers.Remove(number);
            }
            
            if (evenNumbers.Count > 0)
            {
                int minIndex = int.MaxValue;
                foreach (var even in evenNumbers)
                {
                    // getting the index!
                    var idx = firstIndexes[even];
                    if (idx < minIndex)
                        minIndex = idx;
                }

                return numbers[minIndex];
            }
            
            return -1;
        }

O(N) time and O(N) space. Solution written in C#:

public static void Reverse (ref Node root, int number)
        {
            if (number < 0)
                throw new ArgumentOutOfRangeException("number");

            Stack<Node> reversedNodes = new Stack<Node>();

            Node iteratingNode = root;
            for (int cnt = 0; cnt < number && iteratingNode != null; iteratingNode = iteratingNode.Next, cnt++ ) {
                reversedNodes.Push(iteratingNode);
            }

            var linkWith = iteratingNode;

            Node previous = null;
            
            for (; reversedNodes.Count > 0;)
            {
                var node = reversedNodes.Pop();
                if (previous == null)
                    root = node;
                else
                    previous.Next = node;

                previous = node;
            }

            if (previous != null)
                previous.Next = linkWith;

}

I think the best option is to have a balanced tree for storing elements in sorted order. In this maneer you will have quaranteed O (LogN) time for inserting / removing elements.

O (Log N) it's NOT the best case, it's the average case. The best case is O (1) if the tree is plat (all nodes has a single root, the root of the tree) and I have to perform only two steps to find out the left most node.

C# simple implementation that runs in O (N) time

public static string Serialize (IEnumerable<string> strings)
        {
            StringBuilder sb = new StringBuilder();
            
            foreach (var str in strings)
            {
                sb.Append(str.Length); // how many characters
                sb.Append("|");
                sb.Append(str);
            }

            return sb.ToString();
        }

        public static IEnumerable<string> Deserialize (string s)
        {
            if (String.IsNullOrEmpty(s))
                yield break;

            var readingData = false;

            int fwd =0;
            for (var i = 0; i < s.Length; i++)
            {
                
                if (readingData == false )
                {
                    fwd = ReadNumber(ref i, s);
                    readingData = true;
                    continue;
                }
                else
                {
                    yield return ReadString(ref i, s, fwd);
                    readingData = false;
                }
            }
        }

        private static int ReadNumber (ref int index, string s)
        {
            StringBuilder sb = new StringBuilder(10); // maximum 10 digits can have an int32 in C#
            while (s[index] != '|')
                sb.Append(s[index++]);
                
            return int.Parse(sb.ToString());
        }

        private static string ReadString (ref int index, string s, int howMany)
        {
            StringBuilder sb = new StringBuilder(howMany);
            var cnt = 0;
            while (cnt < howMany)
            {
                sb.Append(s[index++]);
                cnt++;
            }
            index--;
            
            return sb.ToString();
        }

It depends what means for them to actually "read". If you want to provide an interface let's name it "IPossibleToRead" that exposes a single read method: Read (int row, int column) and maybe two additional properties: ColumnLength, RowLength and you could return an implementation of this interface in O (1) time. Next, if he REALLY want to read he could just call our Read method.

Assuming that the total number of elements is N, we must avoid trying to go to the left because we will achieve O (N) running time. Instead, first i would find the root and in the same time i would count my depth level. Then i would try to traverse down by trying to peek on each step the most left node. This down traversal i would do until my depth is reached. Total running time would be O (log N)

// C# implementation

    public class StringSearcher
    {
        public static string GetMax(string s1, string s2)
        {
            if (string.IsNullOrEmpty(s2))
                return string.Empty;

            var charSet = new HashSet<char>(s2);

            StringBuilder sb = null;
            string current = string.Empty;

            foreach (char c in s1)
                if (false == charSet.Contains(c))
                {
                    if (sb != null)
                    {
                        if (sb.Length > current.Length)
                            current = sb.ToString();
                        sb = null;
                    }
                }
                else
                {
                    if (sb == null)
                        sb = new StringBuilder(s1.Length); // give length of s1 to avoid reallocations

                    sb.Append(c);    
                }

            // the case when there's a last stringbuilder and after it no character was skipped.
            if (sb != null && sb.Length > current.Length)
                current = sb.ToString();

            return current;
        }
    }