CareerCup

Using a stack to spread the search

public static bool CanReach(char[,] matrix)
{
	if (matrix == null)
		return false;
	
	int m = matrix.GetLength(0);
	int n = matrix.GetLength(1);
	var stack = new Stack<Tuple<int, int>>();
	
	for (int i=0; i < m; i++)
	{
		for (int j=0; j < n; j++)
		{
			if (matrix[i,j] == 'R')
			{
				stack.Push(Tuple.Create(i, j));
				break;
			}
		}
		
		if (stack.Count > 0)
			break;
	}
	
	while (stack.Count > 0)
	{
		var t = stack.Pop();
		if (matrix[t.Item1, t.Item2] == 'T')
			return true;
		
		matrix[t.Item1, t.Item2] = 'V';
		
		if (IsValidCell(t.Item1, t.Item2-1, matrix))
			stack.Push(Tuple.Create(t.Item1,t.Item2-1));
		if (IsValidCell(t.Item1, t.Item2+1, matrix))
			stack.Push(Tuple.Create(t.Item1,t.Item2+1));
		if (IsValidCell(t.Item1-1, t.Item2, matrix))
			stack.Push(Tuple.Create(t.Item1-1, t.Item2));
		if (IsValidCell(t.Item1+1, t.Item2, matrix))
			stack.Push(Tuple.Create(t.Item1+1, t.Item2));
	}
	
	for (int i=0; i < m; i++)
		for (int j=0; j < n; j++)
			if (matrix[i,j] == 'V')
				matrix[i,j] = ' ';
		
	return false;
}

private static bool IsValidCell(int i, int j, char[,] matrix)
{
	if (i < 0 || i >= matrix.GetLength(0) || j < 0 || j >= matrix.GetLength(1))
		return false;
		
	return matrix[i,j] != 'X' && matrix[i,j] != 'V';
}

Using a Math property to check is a number is Fibonacci, O(n)
A number is fibbonaci if (5*n2 + 4) or (5*n2 – 4) is a perfect square

public static List<int> GetFibonacciSequence(int[] a)
{
	var list = new List<int>();
	
	if (a == null)
		return list;
	
	foreach (var n in a)
		if (IsFibonacci(n))
			list.Add(n);
		
	return list;
}

//A number is fibbonaci if (5*n2 + 4) or (5*n2 – 4) is a perfect square
public static bool IsFibonacci(int n)
{
	int f = (5 * n * n);
	int f1 = f + 4;
	
	if (IsPerfectSquare(f1))
		return true;
	
	int f2 = f - 4;
	if (IsPerfectSquare(f2))
		return true;
	
	return false;
}

public static bool IsPerfectSquare(int n)
{
	int sqrt = (int)Math.Sqrt(n);
	return sqrt * sqrt == n;
}

c# implementation using recursion

public static void PrintDiamond(int n)
{
	if (n <= 0 || n % 2 == 0)
		return;
	
	PrintDiamond(5, 1);
}

private static void PrintDiamond(int n, int curr)
{
	
	Console.WriteLine(s);
	
	if (curr == n)
		return;
		
	PrintDiamond(n, curr + 2);
	Console.WriteLine(s);
}

private static string GeneratePattern(int n, int curr)
{
	var sb = new StringBuilder();
	int diff = (n - curr) / 2;
	for (int i=0; i < diff; i++)
		sb.Append(' ');
	for (int i=0; i < curr; i++)
		sb.Append('*');
	for (int i=0; i < diff; i++)
		sb.Append(' ');

	return sb.ToString();
}

Count the number of open/close parenthesis

Index 0 1 2 3 0 1 2 3 4 5 6 0 1
( ( ) ) ( ( ) ) ) ) ( ( (
num Opened 1 2 2 2 1 2 2 2 2 2 3 1 2
num Closed 2 2 2 1 4 4 4 3 2 1 0 0 0
i+1 i i

public static int FindK(char[] a)
{
	if (a == null || a.Length == 0)
		return -1;
	
	int numClose = 0;
	foreach (var c in a)
	{
		if (c == ')')
			numClose++;
	}
	
	if (numClose == 0)
		return 0;
	if (numClose == a.Length)
		return a.Length;
	
	int numOpen = 0;
	for (int i=0; i < a.Length; i++)
	{
		var c = a[i];
		if (c == '(')
			numOpen++;
		
		if (numOpen == numClose)
			return (c == '(')? i+1 : i;
		
		if (c == ')')
			numClose--;
	}
	
	return 0;
}

public class TreeNode
{
	public TreeNode Left;
	public TreeNode Right;
	public int Value;
}

private struct ViewHelper
{
	public int Level;
	public int Value;
}

public static List<int> GetUpperView(TreeNode root)
{
	var list = new List<int>();
	
	if (root == null)
		return list;
	
	int leftCount = 0;
	int rightCount = 0;
	
	GetLimits(root, 0, ref leftCount, ref rightCount);
	
	leftCount = Math.Abs(leftCount);
	int n = leftCount + rightCount + 1; 
	
	var a = new ViewHelper[n];
	a[leftCount].Value = root.Value;
	GetUpperView(root, 0, 0, leftCount, a);
	
	foreach (var item in a)
		list.Add(item.Value);
	
	return list;
}

// Iterates one on the tree to get the limits, left and right count
private static void GetLimits(TreeNode node, int index, ref int leftCount, ref int rightCount)
{
	if (node == null)
		return;
	
	leftCount = Math.Min(leftCount, index);
	rightCount = Math.Max(rightCount, index);
	
	GetLimits(node.Left, index - 1, ref leftCount, ref rightCount);
	GetLimits(node.Right, index + 1, ref leftCount, ref rightCount);
}

private static void GetUpperView(TreeNode node, int row, int level, int leftCount, ViewHelper[] a)
{
	if (node == null)
		return;
	
	int index = leftCount + row;
	if (a[index].Level < level)
	{
		a[index].Level = level;
		a[index].Value = node.Value;
	}
	
	GetUpperView(node.Left, row - 1, level + 1, leftCount, a);
	GetUpperView(node.Right, row + 1, level + 1, leftCount, a);
}

public static int FindFrequency(int[] a, int x)
{
   if (a == null || a.Length == 0)
	   return 0;
	
	int index = BinarySearch(a, x);
	if (index == -1)
		return 0;
	
	int firstIndex = GetFirstOcurrence(a, index);
	int lastIndex = GetLastOccurrence(a, index);
	
	return lastIndex - firstIndex + 1;
}

// Binari Search to find any occurence of item
private static int BinarySearch(int[] a, int x)
{
	int start = 0;
	int end = a.Length - 1;
	
	while (start <= end)
	{
		int midle = (start + end) / 2;
		
		if (a[midle] == x)
			return midle;
		if (a[midle] > x)
			end = midle - 1;
		else
			start = midle + 1;
	}
	
	return -1;
}

private static int GetLastOccurrence(int[] a, int index)
{
	int x = a[index];
	
	int start = index;
	int end = a.Length - 1;
	
	while (start <= end)
	{
		int midle = (start + end) / 2;
		
		if (a[midle] == x)
		{
			index = midle;
			start = midle + 1;
		}
		else
		{
			end = midle - 1;
		}
	}
	
	return index;
}

private static int GetFirstOcurrence(int[] a, int index)
{
	int x = a[index];
	
	int start = 0;
	int end = index;
	
	while (start <= end)
	{
		int midle = (start + end) / 2;
		
		if (a[midle] == x)
		{
			index = midle;
			end = midle - 1;
		}
		else
		{
			start = midle + 1;
		}
	}
	
	return index;
}

Implementation based on first response:

// Returns: Row index and Count
public static IEnumerable<Tuple<int, int>> GetMaximumRows(int[,] a)
{
	
	var result = new List<Tuple<int,int>>();
	int m = a.GetLength(1);
	int j = m - 1;
	
	for (int i=0; i < a.GetLength(0); i++)
	{
		
		if (a[i,j] == 0)
			continue;
		
		if (j > 0 && a[i,j-1] == 1)
		{
			result.Clear();
			while (j > 0 && a[i,j-1] == 1)
				j--;
		}
		
		result.Add(Tuple.Create(i, m-j));
	}
	
	return result;
}

With recursion, First node is parent, First recursion is in all nodes less that or equal that parent; second recursion is on all nodes greather that parent

public static IEnumerable<int> FindNodes(int[] a)
{
	if (a == null || a.Length == 0)
		return Array.Empty<int>();
	
	var nodes = new List<int>();
	FindNodes(a, 0, a.Length -1, nodes);
	return nodes;
}

private static void FindNodes(int[] a, int begin, int end, List<int> nodes)
{
	if (begin == end)
	{
		nodes.Add(a[begin]);
		return;
	}
	
	if (end < begin)
		return;
	
	int parent = a[begin];
	// Skip the parent
	begin++;
	int i = begin;
	while (i <= end && a[i] <= parent)
		i++;
	
	FindNodes(a, begin, i - 1, nodes);
	FindNodes(a, i, end, nodes);
}

public static int GetMaxConsecutiveOnes(int[] a)
{
	if (a == null || a.Length == 0)
		return 0;
	
	int count = 0;
	int max = 0;
	
	for (int i=0; i <a.Length; i++)
	{
		if (a[i] == 1)
		{
			count++;
			max = Math.Max(max, count);
		}
		else
			count = 0;
	}
	
	return max;
}

Not sure if I understood correctly, my implementation using a Sorted List / Max Heap

public static IEnumerable<int> Generate(int[] coins, int n)
{
	var list = new List<int>();
	
	if (coins == null || coins.Length == 0)
		return list;
	
	Array.Sort(coins);
	if (n < coins[0])
		return list;
	
	var set = new SortedSet<int>();
	int m = coins[0];
	
	while (m < n)
	{
		list.Add(m);
		
		foreach (var coin in coins)
			set.Add(m + coin);
		
		m = set.First();
		set.Remove(m);
	}
	
	return list;
}

public static void MoveZeroesBegin(int[] a)
{
	int j = 0;
	for (int i=0; i < a.Length; i++)
	{
		if (a[i] == 0)
		{
			a[i] = a[j];
			a[j] = 0;
			j++;
		}
	}
}

public string RemoveThreeDuplicates(string s)
{
	if (string.IsNullOrEmpty(s))
		return s;
	
	int length = s.Length;
	var arr = s.ToArray();
	int oldLength = 0;
	
	while (length != oldLength)
	{
		int j = 0;
		for (int i=0; i < length; i++)
		{
			if ((i + 2) < length && arr[i] == arr[i+1] && arr[i] == arr[i+2])
				i+=2;  // We need to increment 3, the for-loop add the missing one
			else
			{
				arr[j] = arr[i];
				j++;
			}
		}
		
		oldLength = length;
		length = j;
	}
	
	var sb = new StringBuilder();
	for (int i=0; i < length; i++)
		sb.Append(arr[i]);
	
	return sb.ToString();
}

breadth traversal approach; also can be implemented with Deep traversal like pre-order

public int? FindParent(TreeNode root, int value)
{
	if (root == null || root.Value == value)
		return null;
	
	var queue = new Queue<TreeNode>();
	queue.Enqueue(root);
	
	while (queue.Count > 0)
	{
		var p = queue.Dequeue();
		
		if (p.Left != null)
		{
			if (p.Left.Value == value)
				return p.Value;
			queue.Enqueue(p.Left);
		}
		
		if (p.Right != null)
		{
			if (p.Right.Value == value)
				return p.Value;
			queue.Enqueue(p.Right);
		}   
	}
	
	return null;
}

Is a modification of Binary search

public bool Contains(int[,] matrix, int value)
{
	int m = matrix.GetLength(0);
	int n = matrix.GetLength(1);
	
	int start = 0;
	int end = m * n - 1;
	
	while (start <= end)
	{
		int midle = (start + end) / 2;
		
		int row = midle / n;
		int col = midle % n;
		
		if (matrix[row, col] == value)
			return true;
		if (matrix[row,col] < value)
			start = midle + 1;
		else
			start = midle - 1;
	}
	
	return false;
}

public IEnumerable<string> RestoreText(string s, HashSet<string> words)
{
	var dict = new Dictionary<string, string>();
	int maxLength = 0;
	var lengths = new HashSet<int>();
	var sb = new StringBuilder();
	
	foreach (var word in words)
	{
		var key = GetKey(word);
		dict.Add(key, word);
		maxLength = Math.Max(maxLength, word.Length);
		
		if (!lengths.Contains(word.Length))
			lengths.Add(word.Length);
	}
	
	var result = new List<string>();
	RestoreText(s, dict, 0, maxLength, lengths, sb, result);
	
	return result;
}

private void RestoreText(string s, Dictionary<string, string> dict, int start, int maxLength, HashSet<int> lengths, StringBuilder sb, List<string> result)
{
	if (start == s.Length)
	{
		if (sb.Length > 0)
			sb.Remove(sb.Length - 1, 1);
		result.Add(sb.ToString());
		sb.Append(' ');
		return;
	}
		
	var list = new List<char>();
	for (int i= 0; i < maxLength; i++)
	{
		if (start + i >= s.Length)
			return;
		
		list.Add(s[start + i]);
		
		if (!lengths.Contains(i + 1))
			continue;
		
		var key = GetKey(list);
		
		if (dict.ContainsKey(key))
		{
			var word = dict[key];
			sb.Append(word);
			sb.Append(' ');
			RestoreText(s, dict, start + i + 1, maxLength, lengths, sb, result);
				
				sb.Remove(sb.Length - word.Length - 1, word.Length);
				sb.Remove(sb.Length - 1, 1);
		}
	}
}

private string GetKey(List<char> list)
{
	list.Sort();
	var sb = new StringBuilder();
	foreach (var item in list)
		sb.Append(item);
	return sb.ToString();
}

private string GetKey(string s)
{
	var arr = s.ToArray();
	Array.Sort(arr);
	return new string(arr);
}

public static int[] Multiply(int[] a)
{
	if (a == null || a.Length == 0)
		return new int[0];
	
	int n = 1;
	foreach(var item in a)
		n *= item;
	
	var result = new int[a.Length];
	for(int i=0; i < a.Length; i++)
		result[i] = n / a[i];
	
	return result;
	
}

Use a Dinamic Programming approach; we only need to store the last 2 lists

public static List<string> GeneratePaths(int n)
{
	if (n <= 0)
		return new List<string>();
	
	var list1 = new List<string>();
	list1.Add("");
	
	var list2 = new List<string>();
	list2.Add("1");
	
	if (n == 1)
		return list1;
	
	for (int i=2; i <= n; i++)
	{
		var list = new List<string>();
		foreach (var item in  list2)
			list.Add(item + "1");
		foreach (var item in list1)
			list.Add(item + "2");
		
		list1.Clear();
		list1 = list2;
		list2 = list;
		
	}
	
	return list2;
}

Count Sort

public enum Importance
{
	High,
	Midle,
	Low,
}
        
// Option 1 - Count Sort, use two lista one at the begining and one at the end
public static void Sort(Importance[] patients)
{
	
	int i=0;
	int j=0;
	int k = patients.Length-1;
	
	while (i < k)
	{
		if (patients[i] == Importance.High)
		{
			var tmp = patients[j];
			patients[j] = patients[i];
			patients[i] = tmp;
			j++;
		}
		else if (patients[i] == Importance.Low)
		{
			var tmp = patients[k];
			patients[k] = patients[i];
			patients[i] = tmp;
			k--;
		}
		else
			i++;
	}
}
		

// Option 2 improved
public static void Sort(Importance[] patients)
{
	int highCount = 0;;
	int midleCount = 0;
	int lowCount = 0;
	
	var arr = new int[3];
	foreach (var item in patients)
	{
		arr[(int)item]++;
	}
	
	int index=0;
	for (int i=0; i < patients.Length; i++)
	{
		while (arr[index] == 0)
			index++;
		arr[index]--;
		
		patients[i] = (Importance)index;
	}
}

public static bool CanReachLast(int[] a)
{
	int i = 0;
	int maxRange = a[i];
	while (i <= maxRange && i < a.Length)
	{
		int range = i + a[i];
		maxRange = Math.Max(maxRange, range);
		i++;
	}
	
	return maxRange >= a.Length -1;
}

Calculate the distance and put the result in a Max Heap in the end take K elemets from the Heap.

C# Implementation Use a SortedSet to keep the point sorted according to its Distance
The code complicates a little because C# doesn't have a native Heap

public class Point
{
	public int X { get; private set; }
	public int Y { get; private set; }
	
	public Point(int x, int y)
	{
		this.X = x;
		this.Y = y;
	}
	
	public int Distance(Point p)
	{
		if (p == null)
			throw new Exception();
		
		double diffX = p.X - this.X;
		double diffY = p.Y - this.Y;
		return (int)((diffX * diffX) + (diffY * diffY));
	}
	
	public override string ToString()
	{
		return string.Format("({0}, {1})", this.X, this.Y);
	}
	
}

private class PointSortHelper
{
	public Point Point;
	public int Distance;
	public int Index;
}

private class PointSortComparer : IComparer<PointSortHelper>
{
	public int Compare(PointSortHelper x, PointSortHelper y)
	{
		int n = x.Distance.CompareTo(y.Distance);
		if (n != 0)
			return n;
		
		return x.Index.CompareTo(y.Index);
	}
}

public static IEnumerable<Point> FindClosePoints(List<Point> points, Point p, int k)
{
	var sortedList = new SortedSet<PointSortHelper>(new PointSortComparer());
	
	int index = 0;
	foreach (var point in points)
	{
		int distance = p.Distance(point);
		var helper = new PointSortHelper() { Point = point, Distance = distance, Index = index};
		index ++;
		
		sortedList.Add(helper);
	}
	
	var result = new List<Point>();
	foreach (var item in sortedList)
	{
		result.Add(item.Point);
		k--;
		if (k == 0)
			break;
	}
	
	return result;
}

private class CrossHelper
{
	public int Left;
	public int Right;
	public int Up;
	public int Down;
}

public static int FindMaxCross(int[,] a)
{
	var matrix = new CrossHelper[a.GetLength(0), a.GetLength(1)];
	for (int i=0; i < a.GetLength(0); i++)
		for (int j=0; j < a.GetLength(1); j++)
			matrix[i,j] = new CrossHelper();
		
	// Update values from Left-Up to Right-Bottom
	for (int i=0; i < a.GetLength(0); i++)
		for (int j=0; j < a.GetLength(1); j++)
		{
			if (a[i,j] == 0)
				continue;
		
			// Update Left
			matrix[i,j].Left = (j > 0) ? matrix[i,j-1].Left + 1 : 1;
		
			// Update Right
			matrix[i,j].Up = (i > 0) ? matrix[i-1,j].Up + 1 : 1;
		}
	
	// Update values from Right-Down to Left-Up
	for (int i=a.GetLength(0)-1; i >- 0; i--)
		for (int j=a.GetLength(1)-1; j >= 0; j--)
		{
			if (a[i,j] == 0)
				continue;
		
			// Update Left
			matrix[i,j].Right = (j < a.GetLength(1)-1) ? matrix[i,j+1].Right + 1 : 1;
		
			// Update Right
			matrix[i,j].Down = (i < a.GetLength(0)-1) ? matrix[i+1,j].Down + 1 : 1;
		}
	
	for (int i=0; i < a.GetLength(0); i++)
	{
		for (int j=0; j < a.GetLength(1); j++)
			Console.Write(matrix[i,j].Right + ", ");
		Console.WriteLine();
	}
		
	int maxCross = 0;
	for (int i=1; i < a.GetLength(0)-1; i++)
		for (int j=1; j < a.GetLength(1)-1; j++)
		{
			if (a[i,j] == 0)
				continue;
		
			int minHor = Math.Min(matrix[i,j-1].Left, matrix[i,j+1].Right); 
			int minVer = Math.Min(matrix[i-1,j].Up, matrix[i+1,j].Down);
			int min = Math.Min(minHor, minVer);
			maxCross = Math.Max(maxCross, min);
		}
	
	return maxCross;
}

public string GenerateAbsolutePath(string currentPath, string relativePath)
{
	var stack = new Stack<string>();

	var arr = currentPath.Split('/');
	foreach (var item in arr)
		if (item != null && item.Length > 0)
			stack.Push(item);

	arr = relativePath.Split('/');
	foreach (var item in arr)
	{
		if (item == null || item.Length == 0 || item.Equals("."))
			continue;
		if (item.Equals(".."))
		{
			Debug.Assert(stack.Count > 0);
			if (stack.Count == 0)
				throw new Exception();
			stack.Pop();
		}
		else
			stack.Push(item);
	}

	var sb = new StringBuilder();
	while (stack.Count > 0)
	{
		var item = stack.Pop();
		sb.Insert(0, item);
		sb.Insert(0, '/');
	}

	return sb.Length != 0 ? sb.ToString() : "/";
}

public IEnumerable<string> PrintAllPaths(TreeNode root)
{
	var list = new List<string>();
	if (root == null)
		return list;

	var path = new List<int>();

	return list;
}

private void PrintAllPaths(TreeNode node, List<int> path, List<string> list)
{
	if (node == null)
		return;

	path.Add(node.Value);
	if (node.Left == null && node.Right == null)
	{
		var sb = new StringBuilder();
		foreach (var item in path)
			sb.Append(item).Append(", ");
		list.Add(sb.ToString());
	}

	PrintAllPaths(node.Left, path, list);
	PrintAllPaths(node.Right, path, list);

	path.RemoveAt(path.Count - 1);
}

public IEnumerable<string> GenerateSubsets(int n, int k)
{
	int[] a = new int[k];
	List<string> result = new List<string>();
	GenerateSubsets(n, k, 1, 0, a, result);
	return result;
}

private void GenerateSubsets(int n, int k, int start, int index, int[] a, List<string> result)
{
	if (k == 0)
		return;
	
	int end = n - k + 1;
	
	for (int i=start; i <= end; i++)
	{
		a[index] = i;
		if (k == 1)
		{
			var sb = new StringBuilder();
			foreach (var item in a)
				sb.Append(item);
			result.Add(sb.ToString());
		}
		
		GenerateSubsets(n, k-1, i+1, index+1, a, result);
	}
}

Use a Preorder traversal approach, if both childs have zero means we can not zink any more

public void ZinkZeros(TreeNode root)
{
	if (root == null)
		return;

	ZinkZeros(root.Left);
	ZinkZeros(root.Right);

	// If both childs are Zero we stop the recurzion, all zeros are sink
	if ((root.Left != null || root.Left.Value == 0) && (root.Right != null || root.Right.Value == 0))
		return;

	if (root.Value == 0)
	{
		if (root.Left != null && root.Left.Value != 0)
			SwapValues(root, root.Left);
		else if (root.Right != null && root.Right.Value != 0)
			SwapValues(root, root.Right);
	}
}

my implementation based on more rated post

public void ArrengeByWindow(int[] a, int m)
{
    var set = new HashSet<int>();
            
    for (int i=0; i < a.Length; i++)
    {
        if (set.Contains(a[i]))
        {
            int j = a.Length - 1;
            while (j > i)
            {
                if (set.Contains(a[j]))
                    j--;
                else
                {
                    int tmp = a[i];
                    a[i] = a[j];
                    a[j] = tmp;
                    break;
                }
            }

            if (i == j)
                throw new Exception();
        }

        set.Add(a[i]);
        if (set.Count == m)
            set.Clear();
    }
}

Dinamic Programming, first move be cols calculating the horizontal length,then move by rows calculating the rectangles areas, keep trak of max rectangle. Time O(M) where M is rows * cols

public int FindMaxRectangleArea(int[,] matrix)
{
	var dp = new int[matrix.GetLength(0), matrix.GetLength(1)];
	
	// Calculate/propagate horizontal values
	for (int i=0; i < matrix.GetLength(0); i++)
		for(int j=0; j < matrix.GetLength(1); j++)
			if (matrix[i,j] == 1)
			{
				int prev = (j > 0) ? dp[i,j-1] : 0;
				dp[i,j] = matrix[i,j] + prev;
			}
	
	//Calculate the rectangle areas, propagate vertical and keep track of the maximum area
	int max = 0;
	for (int i=1; i < matrix.GetLength(0); i++)
		for(int j=0; j < matrix.GetLength(1); j++)
			if (matrix[i,j] == 1)
			{
				int prev = (i > 0) ? dp[i-1,j] : 0;
				dp[i,j] += dp[i-1,j];
				max = Math.Max(max, dp[i,j]);
			}
	
	
	return max;
}

public int FindAmazingNumberIndex(int[] a)
{
	int maxLength = 0;
	int maxIndex = -1;
	
	int i=0, j =0;
	while (i < a.Length)
	{
		// j >= i;
		//int index = j - i;   // length - 1
		//if (j < i)
		//    index = a.Length - (i - j);
		
		int index = (j >= i) ? j - i : a.Length - (i - j); 
		if (a[j] <= index)
		{
			j = (j + 1) % a.Length;
			if (j == i)
				return i;
			
			int length = index + 1;
			if (length > maxLength)
			{
				maxLength = length;
				maxIndex = i;
			}
		}
		else
		{
			if (i == j)
				j++;
			i++;
		}
	}
	
	return maxIndex;
}

// Test
//var a = new int[] { 0, 1, 2, 50, 52, 75 };
//var a = new int[] {};
//var a = new int[] { 0 };
var a = new int[] { 3, 5 };
var result = FindMissingRanges(a);

foreach (var item in result)
	if (item.Item1 == item.Item2)
		Console.Write(item.Item1 + ", ");
	else
		Console.Write(item.Item1 + "-" + item.Item2 + ", ");
Console.WriteLine();


public static IEnumerable<Tuple<int, int>> FindMissingRanges(int[] a)
{
	int value = 0;
	var result = new List<Tuple<int,int>>();
	
	for (int i=0; i < a.Length; i++)
	{
		if (a[i] == value)
			value ++;
		else
		{
			result.Add(Tuple.Create(value, a[i] - 1));
			value = a[i] + 1;
		}
	}
	
	if (value < 100)
		result.Add(Tuple.Create(value, 99));
	
	return result;
}

My idea is to create a sign/key for the first string and then move throug the second string in a window of the lenght of the first string, in every step remove the last char (tail of window) and add a new one (head of window) and update the current sign/key.

public List<string> FindPalindromes(string s1, string s2)
{
	var result = new List<string>();
	if (s1.Length > s2.Length)
		return result;
	
	// Initialize the base palindrome array, this hold the base palindrome signature.
	int[] a1 = new int[26];
	foreach (var c in s1)
	{
		int index = c - 'a';
		a1[index]++;
	}
	
	// Create the palindrome signature for the first s1.Length chars
	int[] a2 = new int[26];
	for (int i=0; i < s1.Length; i++)
	{
		int index = s2[i] - 'a';
		a2[index]++;
	}
	
	// See how many chars conform the base palindrome, and calculate how many match with the starting palindrome
	int total = 0;
	int count = 0;
	for (int i=0; i < a1.Length; i++)
	{
		if (a1[i] > 0)
			total++;
		if (a1[i] > 0 && a1[i] == a2[i])
			count++;
	}

	Console.WriteLine("Total = " + total + ", Count = " + count);
	// Start moving for the current palindrome a2 in S2, in each step check if we match the base palindrome,
	// update a2 remove the last char from s2 and add de new one.
	int first = s1.Length - 1;
	int last = 0;

	while (first < s2.Length)
	{
		// check if we match the base palindrome
		if (count == total)
			result.Add(s2.Substring(last, s1.Length));
		
		// Remove the las char and update count
		int index = s2[last] - 'a';
		if (a1[index] > 0 && a1[index] == a2[index])
			count--;
		a2[index]--;
		if (a1[index] > 0 && a1[index] == a2[index])
			count++;
		last++;
		//index = s2[last] - 'a';
		//a2[index]++;
		
		first++;
		
		if (first >= s2.Length)
			break;
		
		// Add First char and update count
		index = s2[first] - 'a';
		if (a1[index] > 0 && a1[index] == a2[index])
			count--;
		a2[index]++;
		if (a1[index] > 0 && a1[index] == a2[index])
			count++;
	}
	
	return result;
}

public void DegenerateTree(TreeNode root)
{
	if (root == null)
		return;
	
	var p = root;
	var stack = new Stack<TreeNode>();
	
	while (p != null)
	{
		if (p.Left == null && p.Right == null)
		{
			if (stack.Count > 0)
			{
				var node = stack.Pop();
				p.Right = node;
			}
		}
		else if (p.Left != null)
		{
			if (p.Right != null)
				stack.Push(p.Right);
			p.Right = p.Left;
			p.Left = null;
		}
		p = p.Right;
	}
}

public int[] Merge(int[] a1, int[] a2)
{
	int[] result = new int[a1.Length + a2.Length];
	int i = 0;
	int j = 0;
	int k = 0;

	while (i < a1.Length || j < a2.Length)
	{
		int n;
		if (i < a1.Length && j < a2.Length)
		{
			if (a1[i] < a2[j])
			{
				n = a1[i];
				i++;
			}
			else
			{
				n = a2[j];
				j++;
			}
		}
		else if (i < a1.Length)
		{
			n = a1[i];
			i++;
		}
		else
		{
			n = a2[j];
			j++;
		}

		result[k] = n;
		k++;

		while (i < a1.Length && a1[i] == n)
			i++;
		while (j < a2.Length && a2[j] == n)
			j++;
	}

	if (k < (a1.Length + a2.Length))
	{
		var tmp = new int[k];
		Array.Copy(result, tmp, k);
		result = tmp;
	}

	return result;
}

Can also be implemented with a Dictionary and a HashSet

public char FindFirstNoRepeating(string s)
{
	int[] arr = new int[26];

	for(int i=0; i < s.Length; i++)
	{
		int index = Math.Abs('a' - s[i]);
		if (arr[index] == -1)
			continue;

		if (arr[index] > 0)
			arr[index] = -1;
		else
			arr[index] = i + 1;
	}

	int min = int.MaxValue;
	for(int i=0; i < arr.Length; i++)
	{
		if (arr[i] > 0)
			min = Math.Min(min, arr[i]);
	}

	return s[min - 1];
}

public class TimeFrame
{
	public int Start;
	public int End;
}

private class TimeFrameComparer : IComparer<TimeFrame>
{
	public int Compare(TimeFrame x, TimeFrame y)
	{
		return x.Start.CompareTo(y.Start);
	}
}

public int GetWorkingTime(TimeFrame[] frames)
{
	if (frames == null || frames.Length == 0)
		return 0;

	var result = new List<TimeFrame>();
	var c = frames[0];

	for (int i=1; i < frames.Length; i++)
	{
		if (frames[i].Start < c.End)
			c = new TimeFrame { Start = c.Start, End = Math.Max(c.End, frames[i].End) };
		else
		{
			result.Add(c);
			c = frames[i];
		}
	}

	result.Add(c);

	int total = 0;
	foreach (var item in result)
		total += item.End - item.Start + 1;

	return total;
}

There are two solutions

Solution 1 is to have a temporary internal matrix and populate it with the lamps queue info (horizontal, vertical and diagonals), we just need to check a given coordinate, for this problem Time O(M) and space O(NxN).

foreach (var coor in coordinates)
	resilt.Add(matrix[coor.X, coor.Y]);

Solution 2 is for a given coordinate compare with the lamps and do some cells Math, if they are located in the same row, column or diagonal the coordinated is iluminated. Time O(NxM) N = num of lamps M num of coordinates.

foreach (var coor in coordinates)
{
	foreach (var lamp in lamps)
	{
		int diffX = Math.Abs(lamp.X - coor.X);
		int diffY = Math.Abs(lamp.Y - coor.Y);
		
		if (diffX == 0 || diffY == 0 || diffX == diffY)
		{
			result.Add(true);
			break;
		}
	}
	
	result.Add(false);
}

public void Flatten(Node head)
{
	var list = new List<>();
 	var p = head;
	while (p != null)
	{
		list.Add(p.A);
		var d = p.Down;
		while (d != null)
		{
			list.Add(d.A);
			d = d.Down;
		}
		
		p = p.Right;
	}
	
	return list;
}

The same as all previus posts

public static int[] GetProducts(int[] a)
{
	if (a == null || a.Length == 0)
		return new int[0];
	
	long product = 1;
	foreach (var numb in a)
		product *= numb;
	
	int[] result = new int[a.Length];
	for (int i=0; i < a.Length; i++)
		result[i] = (int)(product / a[i]);
	
	return result;
}

The trick part is to sort the array, ones sorted becames into the problem of find a continius sequence that sums until max,every time we find a value <= max we update the maximum of words.

public int GetMaxNumberWords(int[] array, int max)
{
	if (array == null || array.Length == 0)
		return 0;
	
	Array.Sort(array);
	
	int i = 0;
	int j = 0;
	int maxWords = int.MinValue;
	int sum = array[0];
	
	while (i < array.Length)
	{
		if (a[i] > max)
			break;
		
		if (sum <= max)
		{
			int numWords = i - j + 1;
			maxWords = Math.Max(maxWords, numWords);
		}
		
		Console.WriteLine("sum = " + sum + ", i = " + i + ", j = " + j + ", maxMords = " + maxWords);
		
		if (i == j || sum < max)
		{
			i++;
			if (i < array.Length)
				sum += array[i];
		}
		else
		{
			sum -= array[j];
			j++;
		}
	}
	
	return maxWords == int.MinValue ? 0 : maxWords;
}

Just count the vowels not need to count the consonants, with the number of vowels we can calculate the rest.

public int GetValue(string s)
{
	var set = new HashSet<char>();
	set.Add('a');
	set.Add('e');
	set.Add('i');
	set.Add('o');
	set.Add('u');
	
	// Count for vowels
	int numVowels = 0;
	foreach (var c in s)
	{
		if (set.Contains(c))
			numVowels++;
	}
	
	int numConsonants = s.Length - numVowels;
	return s.Length + numConsonants;
}

Similar to previous posts, the minimum value is getting from the first and last elements; To find the highest value we use a modification of binary search; We continue advancing/ spliting in the direction where the highst value is.

public static Tuple<int,int> FindMaxMin(int[] a)
{
	int min = Math.Min(a[0], a[a.Length-1]);
	
	int low = 0;
	int high = a.Length - 1;
	int max = int.MinValue;
	
	while (low < high)
	{
		int midle = (low + high) / 2;
		//Console.WriteLine("L = " + low + ", H = " + high + ", M = " +midle);
		if (midle > 0 && a[midle] > a[midle - 1] && midle < a.Length -1 && a[midle] > a[midle + 1])
		{
			max = a[midle];
			break;
		}
		
		if (midle < a.Length -1 && a[midle + 1] > a[midle])
			low = midle + 1;
		else
			high = midle - 1;
	}
	
	if (low == high && max == int.MinValue)
		max = a[low];
	
	return Tuple.Create(min, max);
}

Like mentiones previosly con be solved in O(n) is an example of join two sorted lists

public static int[] GetSortedArrayOfSquares(int[] a)
{
	if (a == null || a.Length == 0)
		return a;
	
	
	// Set I at the begining of positive numbers and J in the last negative number
	int i=0;
	while (a[i] < 0)
		i++;
	int j = i - 1;
	
	int index = 0;
	int[] result = new int[a.Length];
	
	// Join both sorted lists
	while (j >=0 && i < a.Length)
	{
		int n1 = a[i] * a[i];
		int n2 = a[j] * a[j];
		
		if (n1 <= n2)
		{
			result[index] = n1;
			i++;
		}
		else
		{
			result[index] = n2;
			j--;
		}
		
		index++;
	}
	
	// Copy the remainder 
	while (j >=0)
	{
		result[index] = a[j] * a[j];;
		j--;
		index++;
	}
	
	while (i < a.Length)
	{
		result[index] = a[i] * a[i];
		i++;
		index++;
	}
	
	return result;
}

public static string Reverse(string s)
{
	if (string.IsNullOrEmpty(s))
		return s;
	
	var sb = new StringBuilder();
	Reverse(s, sb, 0);
	return sb.ToString();
}

private static void Reverse(string s, StringBuilder sb, int index)
{
	if (index == s.Length)
		return;
	
	Reverse(s, sb, index+1);
	sb.Append(s[index]);
}

C# implementation, O(n) just count the number of characters

public static int GetMaxPalindromeLength(string s)
{
	if (string.IsNullOrEmpty(s))
		return 0;
	
	int length = 0;
	var dict = new Dictionary<char, int>();
	foreach (var ch in s)
	{
		var c = ch;
		if (c >= 'A' && c <= 'Z')
			c = (char)(c - 'A');
		
		if(dict.ContainsKey(c))
			dict[c]++;
		else
			dict.Add(c,1);
		
		if (dict[c] % 2 == 0)
			length += 2;
	}
	
	if (length < s.Length)
		length++;
	
	return length;
}

If the numbers are Sorted we can use a modification of the Binary Search to look for the missing number this will give us a O(logN) time complexity, the idea is to compare the value in the array with the index to determinate witch part of the array is going to be discarded.

public static int FindMissingInSequence(int[] a)
{
	int missing = 0;
	int start = 0; 
	int end = a.Length - 1;
		
	while (start < end)
	{
		int midle = (start + end) / 2;
		
		if (midle + 1 == a[midle])
			start = midle + 1;
		else
			end = midle - 1;
	}
	
	if (start > end)
		return -1;
	
	return (start + 1 == a[start]) ? a[start] + 1 : a[start] - 1;
}

In the case that the sequence doesn't start from 1 a small modification is required.

For the other discussion, to sum the values, an alternative is to use XOR operation, this way is preferred because in the case of a big array with big numbers an overflow can be reached. In this algorithm we have O(N) time complexity so the binary approach is preferred.

public static int FindMissingInSequence(int[] a)
{
	int missing = 0;
	for (int i=0; i < a.Length; i++)
	{
		missing = missing ^ a[i];
	}
	
	
	for (int i=1; i <= a.Length + 1; i++)
	{
		missing = missing ^ i;
	}
	
	return missing;
}

Calculates the new Factorial in every iteration

public int Calculate(int n)
{
	int total = 0;
	int fact = -1;
	
	for (int i=1; i <=n; i++)
	{
		fact *= -i;
		total += fact;
	}
	
	return total;
}

Every time you Add you update a minimum value, so the GetMin method will be O(1) time.

One case for the encoder if the length of the substring to be encoded is less or equals that 3 don't make sense to apply, example
aa => 2xa in this case the info is expanded is counterproductive
aaa => 3xa is the same length so no improve in the compress so no make sense.

There are some considerations about the decoder that are not clarified, for example if we have a string like this: 24xa there are 2 cases
case 1 => aaaaaaaaaaaaaaaaaaaaaaaa
case 2 => 2aaaa

- For the first case we need to handle an input like 5aaaaaa => 56xa after the decoded this would give us a huge expanded string like aaaaaaaaaa...aaaaa so we need to encode something like: 5a5xa; in this case substrings that has length of 4 or less don't make sense to compress
- For the second case we need to manage chunks, example dgeeeeeeeeeeeeeeee => dg9xe7xe

This is my solution for the first case

public string Encode(string s)
{
    var sb = new StringBuilder();

    int j = 0;
    for (int i=0; i < s.Length; i++)
    {
        if (i > 0 && (s[i] == 'x' || s[i] == 'X') && s[i-1] >= '1' && s[i-1] <= '9')
        {
            sb.Append(s[i - 1]);
            sb.AppendFormat("1x{0}", s[i]);
            j = i+1;
            continue;
        }
        if (s[i] == s[j])
            continue;

        AppendChars(s, j, i, sb);
        j = i;
    }

    AppendChars(s, j, s.Length, sb);
              
    return sb.ToString();
}

private void AppendChars(string s, int start, int end, StringBuilder sb)
{
    char c = s[start];
    int lenght = end - start;

    // Handle the case when there is a number befor the sub string.
    bool afterNumber = (start > 0 && s[start - 1] >= '1' && s[start - 1] <= '9');
    int n = afterNumber ? 4 : 3;

    if (afterNumber)
    {
        lenght--;
        sb.Append(c);
    }

    if (lenght <= 3)
        sb.Append(c, lenght);
    else
        sb.AppendFormat("{0}x{1}", lenght, c);
}

Output:
abc => abc
abbccc => abbccc
abbcccdddd => abbccc4xd
p14akkkkkkkkpq => p14a8xkpq
p14xxxxxx1pq => p141xx5xx1pq
p14xxxxxx => p141xx5xx
qp45aaaaaaaaaaaadf => qp45a11xadf

The Start cell can be anywhere or is always located at 0,0; Can you clarify next cell to the start node I mean is right and left or could be any of the 8 cells surrounding it ?

Similar like previous posts

void ReverseBySubset(int[] a, int n)
{
    for (int i=0; i < a.Length; i+=n)
    {
        int start = i;
        int end = i + (n-1);
        if (end >= a.Length)
            break;

        while (start < end)
        {
            int tmp = a[start];
            a[start] = a[end];
            a[end] = tmp;

            start++;
            end--;
        }
    }
}

I store the bulbs in a byte where each bit is a bulb so I can use mask and XOR to toggle the state of a set of bulbs
I did not test the code but is the idea.

public class BulbsManager
{
	private int numBulbs
	private byte[] bulbs;
	
	public BulbManager(int n)
	{
		this.numBulbs = n;
		this.bulbs = new byte[n/8 + 1];
	}
	
	public bool IsOn(int index)
	{
		int n = index / 8;
		int i = index % 8;
		
		byte mask = 1 << i;
		return this.bulbs[n] & mask != 0;
	}
	
	public void Togle(int start, int end)
	{
		if (end < start)
			throw new ArgumentException();
			
		int sb = start / 8;
		int eb = end / 8;
		int i1 = start % 8;
		int i2 = end % 8;
		
		bulbs[sb]= bulbs[sb] >> i1;
		bulbs[sb] = bulbs[sb] << i1;
		
		mask = 0xFF;
		for (int i=sb+1; i < eb; i++)
			bulbs[i] = bulbs[i] ^ mask;
	
		int n2 = 7 - i2;
		bulbs[sb] = bulbs[se] << n2;
		bulbs[sb] = bulbs[se] >> n2;
	}
}