Conexiom Interview Test

conexiom.cs

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

namespace ConexiomInterviewTest
{
	class Program
	{
		static void Main(string[] args)
		{

			Console.WriteLine("AvoidRepeatedSlidingWindow...");
			Console.WriteLine(AvoidRepeatedSlidingWindow("substrings"));
			Console.WriteLine(AvoidRepeatedSlidingWindow("abba"));
			Console.WriteLine(AvoidRepeatedSlidingWindow("abbac"));

			Console.WriteLine("");
			Console.Write("SlidingWindowEx1: ");
			Console.WriteLine(SlidingWindowEx1(new int[] { -1, 2, 3, 1, -3, 2 }, 2));

			Console.WriteLine("");
			Console.WriteLine("SlidingWindowEx2: ");
			var desiredResult = 7;
			var arrays = SlidingWindowEx2(new int[] { 1, 7, 4, 3, 1, 2, 1, 5, 1 }, desiredResult);
			foreach (var a in arrays) {
				Console.WriteLine($"[{string.Join(", ", a)}] = {desiredResult}");
			}

			Console.WriteLine("");
			Console.Write("SlidingWindowEx4: ");
			Console.WriteLine(SlidingWindowEx4("fa4chba4c", "abc"));
		}

		// sample: substrings | result: ubstring
		// sample: abba | result: ab
		// sample: abbac | result: bac
		static string AvoidRepeated(string text)
		{
			// longest substring without repeated chars
			var largeOutput = "";
			for (int i = 0; i < text.Length - 1; i++)
			{
				var c = text[i];
				string output = c.ToString();
				for (int j = i + 1; j < text.Length; j++)
				{
					var ic = text[j];
					if (c == ic && !string.IsNullOrEmpty(output) && output.Length > largeOutput.Length)
						largeOutput = output;

					output += ic;
				}
			}

			return largeOutput;
		}

		static string AvoidRepeatedSlidingWindow(string text)
		{
			// longest substring without repeated chars
			int i = 0, j = 0;
			var finished = false;
			var output = "";

			while (!finished)
			{
				var temp = text.Substring(i, j - i);

				if (HasRepeatedChars(temp))
				{
					if (temp.Length > output.Length)
						output = text.Substring(i, j - i - 1);

					i++;
				}
				else
				{
					finished = (j == text.Length);
					j++;
				}

				if (finished && temp.Length > output.Length)
					output = text.Substring(i, j - i - 1);
			}

			return output;
		}

		private static bool HasRepeatedChars(string charList)
		{
			var dict = new Dictionary<char, int>();

			for (var i = 0; i < charList.Length; i++)
			{
				var c = charList[i];
				if (!dict.ContainsKey(c))
					dict.Add(c, 1); // add first time
				else
					return true; // already found, so something is repeated
			}
			return false;
		}

		/// <summary>
		/// SlidingWindowEx1
		/// </summary>
		/// <param name="array"></param>
		/// <param name="subSize"></param>
		/// <returns>Biggest sum found giving the subset size</returns>
		static int SlidingWindowEx1(int[] array, int subSize)
		{
			var currentWindow = new int[subSize];

			var biggestSum = 0;
			for (int i = 0; i < array.Length - 1; i++)
			{
				var firstNumber = array[i];
				var secondNumber = array[i + subSize - 1]; // needs a validation so it doesn't return IndexOutOfRange
				if (firstNumber + secondNumber > biggestSum)
				{
					biggestSum = firstNumber + secondNumber;
					currentWindow[0] = firstNumber;
					currentWindow[1] = secondNumber;
				}
			}

			return biggestSum;
		}

		/// <summary>
		/// SlidingWindowEx2
		/// </summary>
		/// <param name="array"></param>
		/// <param name="desiredSum"></param>
		/// <returns>List of arrays found that matches the desiredSum</returns>
		static List<int[]> SlidingWindowEx2(int[] array, int desiredSum)
		{
			int i = 0, j = 0;
			var outputs = new List<int[]>();
			var itemsUsed = new List<int>();
			var finished = false;

			while (!finished)
			{
				var currentSum = 0;
				itemsUsed.Clear();
				for (int k = i; k <= j; k++)
				{
					currentSum += array[k];
					itemsUsed.Add(array[k]);
				}

				if (currentSum < desiredSum && j < array.Length - 1)
					j++; // move second pointer
				if (currentSum > desiredSum)
					i++; // move first pointer
				if (currentSum == desiredSum)
				{
					outputs.Add(itemsUsed.ToArray());

					if (j < array.Length - 1)
					{
						j++;
					}
					else if (j == array.Length - 1)
					{
						i++;
						continue;
					}
				}

				finished = (i == array.Length - 2);
			}

			return outputs;
		}

		/// <summary>
		/// SlidingWindowEx4
		/// * ignored a couple of rules stated by the videos just for the sake of time
		/// </summary>
		/// <param name="input"></param>
		/// <param name="desired"></param>
		/// <returns>Shortest string</returns>
		static string SlidingWindowEx4(string input, string desired)
		{
			int i = 0, j = 0;
			var finished = false;
			var output = input;

			while (!finished)
			{
				var temp = new List<char>();
				for (int k = i; k <= j; k++)
				{
					temp.Add(input[k]); // f | fa | fa4 | fa4c | fa4ch | *fa4chb
				}

				if (temp.Intersect(desired).Count() == desired.Length) // prone to errors
				{
					if (output.Length > temp.Count()) // check if its shorter
						output = new string(temp.ToArray());
					i++;
				}
				else
				{
					finished = (j + 1 == input.Length);
					j++;
				}
			}

			return output;
		}
	}
}