---
tags: algorithms
---
<style>.markdown-body { max-width: 1200px; }</style>
[AlgoExpert Cert](https://certificate.algoexpert.io/AE-3dece3260e)

# Algorithms

## Levinstein Distance

public static int GetLevinsteinDistanceBase(string source, string target){
	
	var costMatrix = Enumerable.Range(0, source.Length+1)
	.Select(line => new int[target.Length+1])
	.ToArray();
	
	for(var row = 1; row <= source.Length; row++){
		costMatrix[row][0] = row;
	}
	
	for(var col = 1; col <= target.Length; col++){
		costMatrix[0][col] = col;
	}

	for (var row = 1; row <= source.Length; row++)
	{
		for (var col = 1; col <= target.Length; col++) { 
			var insertion = costMatrix[row][col-1] + 1;
			var deletion = costMatrix[row-1][col] + 1;
			var substitution = costMatrix[row-1][col-1] + (source[row-1] == target[col-1] ? 0 : 1);
			
			costMatrix[row][col] = Math.Min(Math.Min(insertion, deletion), substitution);
		}
	}
		
	
	return costMatrix[source.Length][target.Length];
}

public static int GetLevinsteinDistance2(string source, string target){

	// trim all mathing caracters to avoid extra calculation
	
	var startIndex = 0;
	var sourceEnd = source.Length;
	var targetEnd = target.Length;

	while (startIndex < sourceEnd && startIndex < targetEnd && source[startIndex] == target[startIndex])
	{
		startIndex++;
	}

	while (startIndex < sourceEnd && startIndex < targetEnd && source[sourceEnd - 1] == target[targetEnd - 1])
	{
		sourceEnd--;
		targetEnd--;
	}
	
	var sourceLength = sourceEnd - startIndex;
	var targetLength = targetEnd - startIndex;

	if(sourceLength == 0)
		return targetLength;
		
	if(targetLength == 0)
		return sourceLength;
		
	var sourceSpan = source.AsSpan().Slice(startIndex, sourceLength);
	var targetSpan = target.AsSpan().Slice(startIndex, targetLength);

	// calculate cost

	var previousRow = ArrayPool<int>.Shared.Rent(targetSpan.Length);
	
	for(var col = 0; col < targetSpan.Length; col++){
		previousRow[col] = col+1;
	}

	for (var row = 0; row < sourceSpan.Length; row++)
	{
		var lastSubstitutionCOst = row;
		var lastInsertionCOst = row+1;
		
		for (var col = 0; col < targetSpan.Length; col++) { 
			
			var deletion = previousRow[col];
			var substitution = lastSubstitutionCOst + (sourceSpan[row] == targetSpan[col] ? 0 : 1);
			lastInsertionCOst = Math.Min(Math.Min(lastInsertionCOst, deletion)+1, substitution);
			lastSubstitutionCOst = deletion;
			previousRow[col] = lastInsertionCOst;
		}
	}
		
	
	var result = previousRow[targetSpan.Length-1];
	ArrayPool<int>.Shared.Return(previousRow);
	return result;
}


public static int GetLevinsteinDistance3(string source, string target){

	// trim all mathing caracters to avoid extra calculation
	
	var startIndex = 0;
	var sourceEnd = source.Length;
	var targetEnd = target.Length;

	while (startIndex < sourceEnd && startIndex < targetEnd && source[startIndex] == target[startIndex])
	{
		startIndex++;
	}

	while (startIndex < sourceEnd && startIndex < targetEnd && source[sourceEnd - 1] == target[targetEnd - 1])
	{
		sourceEnd--;
		targetEnd--;
	}
	
	var sourceLength = sourceEnd - startIndex;
	var targetLength = targetEnd - startIndex;

	if(sourceLength == 0)
		return targetLength;
		
	if(targetLength == 0)
		return sourceLength;
		
	var sourceSpan = source.AsSpan().Slice(startIndex, sourceLength);
	var targetSpan = target.AsSpan().Slice(startIndex, targetLength);

	// calculate cost
	var previousRow = ArrayPool<int>.Shared.Rent(targetSpan.Length);
	for(var col = 0; col < targetSpan.Length; col++){
		previousRow[col] = col+1;
	}

	for (var row = 0; row < sourceSpan.Length; row++)
	{
		var lastSubstitutionCost = row;
		var lastInsertionCost = row + 1;
		
		for (var col = 0; col < targetSpan.Length; col++) 
		{ 
			var localCost = lastSubstitutionCost;
			var deletionCost = previousRow[col];

			if (sourceSpan[row] != targetSpan[col]) 
			{
				localCost = Math.Min(lastInsertionCost, localCost);
				localCost = Math.Min(deletionCost, localCost);
				localCost++;
			}

			lastInsertionCost = localCost;
			previousRow[col] = localCost;
			lastSubstitutionCost = deletionCost;
		}
	}
		
	
	var result = previousRow[targetSpan.Length-1];
	ArrayPool<int>.Shared.Return(previousRow);
	return result;
}

## Deserialize binary tree from a string

void Main()
{
	var s = "4(-21(3(7)(-8))(1))(6(5)(4))";
	int i = 0;
	Build(s, ref i).D();	
}


TreeNode Build(string s, ref int i){
	int val = 0;
	bool negative = false;

	while (i < s.Length && s[i] != '(' && s[i] != ')')
	{
		if (s[i] == '-')
		{
			negative = true;
		}
		else
		{
			val = 10 * val + (s[i] - '0');
		}
		i++;
	}
	
	if (negative)
		val = -val;

	var root = new TreeNode(val);
	if (i < s.Length && s[i] == '(')
	{
		i++;
		root.left = Build(s, ref i);
		i++;

		if (i < s.Length && s[i] == '(')
		{
			i++;
			root.right = Build(s, ref i);
			i++;
		}	
	}
	
	return root;
}


public class TreeNode
{
	public int val;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
	{
		this.val = val;
		this.left = left;
		this.right = right;

	}
}

## Minimum sum

public int MinSumOfLengths(int[] arr, int target) {
       int n = arr.Length;
       int [] best = new int[n];
       Array.Fill(best, Int32.MaxValue);
	   
       int sum = 0, start = 0, ans = Int32.MaxValue, bestSoFar = Int32.MaxValue;
       
	   for(int i = 0; i < n; i++){
           
		   sum += arr[i];
           while(sum > target){
               sum -= arr[start];
               start++;
           }
           
		   if(sum == target){
		   		$"sum [{start}:{i}] = {target}".D();	
               int currentLength = i + 1 - start ;
			   if(start > 0 && best[start - 1] != Int32.MaxValue){
                   ans = Math.Min(ans, best[start - 1] + currentLength);
               }
               bestSoFar = Math.Min(bestSoFar, currentLength);
           }
		   
           best[i] = bestSoFar;
		   
		   best.Print();
		   i.D("--");
       }
       return ans == Int32.MaxValue ? -1 : ans;
   }

## Regex matching

void Main()
{
	string s = "aab";
	string p = "c*a*b";
	
	matches(s,p).D();
}

bool matches(string s, string p){
	if(string.IsNullOrEmpty(p)) return string.IsNullOrEmpty(s);
	
	bool firstMatches = !string.IsNullOrEmpty(s) && (s[0] == p[0] || p[0] == '.');
	
	// a*bc aaabc => a*bc, aabc => a*bc, abc => a*bc, bc => bc, bc => c,c = > true
	// c*a*b, aab => a*b, aab => a*b, ab => a*b, b => b => b;
	
	if(p.Length > 1 && p[1] == '*'){
		return matches(s, p.Substring(2)) || firstMatches && matches(s.Substring(1), p);
	}else{
		return firstMatches && matches(s.Substring(1), p.Substring(1));
	}
}

## Optimal Account Balancing

public class Solution {
    public int MinTransfers(int[][] transactions) {
        var debt = new Dictionary<int,int>();
        
        foreach(var t in transactions){
            debt[t[0]] = GetOrDefault(debt, t[0], 0) - t[2];
            debt[t[1]] = GetOrDefault(debt, t[1], 0) + t[2];
        }
        
        return helper(0, debt.Values.ToArray());
    }
    
    int helper(int start, int[] debt){
        while(start < debt.Length && debt[start] == 0) start++;
        if(start >= debt.Length) return 0;
        
        int min = Int32.MaxValue;
        for(int i = start + 1; i < debt.Length; i++){
            if(debt[start] * debt[i] < 0){
                debt[i] += debt[start];
                min = Math.Min(min, 1 + helper(start+1, debt));
                debt[i] -= debt[start];
            }
        }
        
        return min;
    }
    
    int GetOrDefault(Dictionary<int,int> map, int key, int def){
        if(!map.ContainsKey(key)){
            return def;
        }
        return map[key];
    }
}

## Remove comments

void Main()
{
	var source = new[]{"/*Test program */", 
		"int main()", "{ ", 
		"  // variable declaration ", 
		"int a, b, c;", 
		"/* This is a test", "   multiline  ", "   comment for ", "   testing */", 
		"a = b + c;", 
		"}"};
	
		f(source).D();
	
}

List<string> f(string[] source){
	bool isInBlock = false;
	var result = new List<string>();
	var buffer = new StringBuilder();
	foreach(var s in source){
		int i=0;
		while(i < s.Length){
			if(i < s.Length-1 && s[i] == '/' && s[i+1] == '/' && !isInBlock){
				i = s.Length;
			}else if(i < s.Length-1 && s[i] == '/' && s[i+1] == '*' && !isInBlock){
				isInBlock = true;
				i++;
			}else if(i < s.Length-1 && s[i] == '*' && s[i+1] == '/' && isInBlock){
				isInBlock = false;
				i++;
			}else if(!isInBlock){
				buffer.Append(s[i]);
			}
			i++;
		}
		
		if(!isInBlock){
			result.Add(buffer.ToString());
			buffer.Clear();
		}
		
	}
	
	return result;
}

## Fenwick Tree

void Main()
{
	int[] array = new[]{2,1,1,3,2,3,4,5,6,7,8,9};	
	var ft = new FenwickTree(array);
	ft.BinaryTree.Print();
	
	for(int i = 0; i < array.Length; i++){
		$"i: [{i}], sum: [{ft.Query(i)}]".D();
	}
}


public class FenwickTree{

	int[] binaryTree;
	
	public FenwickTree(int[] array){
		binaryTree = new int[array.Length+1];
		for(int i = 1; i < binaryTree.Length; i++){
			UpdateBinaryTree(binaryTree, i, array[i-1]);
		}
	}
	
	public void UpdateBinaryTree(int[] binaryTree, int index, int value){
		while(index < binaryTree.Length){
			binaryTree[index] += value;
			index += index & (-index);
		}
	}
	
    public int Query(int from, int to){
		return Query(to) - Query(from-1);
	}
    
	public int Query(int index){
		int sum = 0;
		index = index+1;
		while(index > 0){
			sum += binaryTree[index];
			index -= index & (-index);
		}
		
		return sum;
	}
	
	public int[] BinaryTree => binaryTree;
}

## Minimum Swaps To Make Sequences Increasing

public class Solution {
    public int MinSwap(int[] A, int[] B) {
        int n1 = 0;
	    int s1 = 1;
	
        for(int i = 1; i < A.Length; i++){
            int n2 = Int32.MaxValue;
            int s2 = Int32.MaxValue;

            if(A[i] > A[i-1] && B[i] > B[i-1]){
                n2 = n1;
                s2 = s1 + 1;
            }

            if(A[i-1] < B[i] && B[i-1] < A[i]){
                n2 = Math.Min(n2, s1);
                s2 = Math.Min(s2, n1 + 1);
            }
            //$"i: [{i}],  n1: {n1}, s1: {s1}, n2: {n2}, s2: {s2}".D();
            n1 = n2;
            s1 = s2;
        }
        
        return Math.Min(n1,s1);
    }
}

## Min coin change

void Main()
{
	int n = 35;
	var denoms = new[]{1,5,10,25,100};
	
	var mins = new int[n+1];
	Array.Fill(mins, Int32.MaxValue);
	mins[0] = 0;
		
	int toCompare = 0;
	
	foreach(var denom in denoms){
		for(int amount = 1; amount <= n; amount++){
			
			if(amount >= denom){
				if(mins[amount-denom] == Int32.MaxValue){
					toCompare = mins[amount-denom];
				}else{
					toCompare = mins[amount-denom] + 1;  
				}
				
				mins[amount] = Math.Min(toCompare, mins[amount]);
			}
		}
	}
	
	mins[n].Dump();
	mins.Print();
}

## Find missing numbers in array (1..n)

void Main()
{
	var nums = new[]{1,2,2,3,3,4,6,5,7};	
	
	for(int i = 0; i < nums.Length; i++){
		int index = Math.Abs(nums[i]) - 1;
		
		if(nums[index] > 0){
			nums[index] *= -1;
		}
	}
	
	nums.Dump();
	var result = new List<int>();
	for(int i = 0; i < nums.Length; i++){
		if(nums[i] > 0) result.Add(i+1);
	}
	
	result.Dump();
}

## Min Palindromic Cuts

void Main()
{
	string s = "noonabbad";
	var lengths = BuildPalindromeTable(s);
	lengths.Dump();
	
	int[] cuts = new int[s.Length];
	
	for(int i = 0; i < s.Length; i++)
	{
		if(lengths[0,i]){
			cuts[i] = 0;	
		}else{
			int min = 1 + cuts[i-1];
			for(int j = 1; j < i; j++){
				if(lengths[j,i]) {		  
					s.Substring(0,i).Dump();
					min = Math.Min(min, cuts[j-1] + 1);
				}
			}
			cuts[i] = min;
		}
	}
	cuts.Print();
}


public static bool[,] BuildPalindromeTable(string s){
	int n = s .Length;
	bool[,] palindromeLengths = new bool[n, n];
	
	for(int i = 0; i < n; i++){
	for(int j = i; j < n; j++){
			palindromeLengths[i,j] = isPalindrome(i,j,s);
		}
	}
	
	return palindromeLengths;
}

static bool isPalindrome(int startIndex, int endIndex, string s){
	while(startIndex <= endIndex){
		if(s[startIndex++] != s[endIndex--]) return false;
	}
	return true;
}

// palindrome

## Decode Ways

void Main()
{
	var s = "120212";
	var dp = new int[s.Length + 1];
	dp[0] = 1;
	dp[1] = s[0] == '0' ? 0 : 1; 
	
	for(int i = 2; i <= s.Length; i++){
		
		Int32.TryParse(s.Substring(i-1, 1), out var oneDigit);
		Int32.TryParse(s.Substring(i-2, 2), out var twoDigit);

		$"{oneDigit}, {twoDigit}".Dump();
		
		if(oneDigit != 0) dp[i] += dp[i-1];
		
		if(twoDigit >= 10 && twoDigit <=26) dp[i] += dp[i-2];
	}
	
	dp.Dump();
}

## Longest Word

/*
	Given a list of words, find the longest word made from other words in the list.
*/
void Main()
{
	var words = new []{"big", "testing", "tester", 
	"bad", "test", "testingtesterbigbadmouse", 
	"bigbad", "mouse", "bigbadmouse", "testmouse", "testerbigmouse"};
	
	var map = new Dictionary<string, bool>();
	
	foreach(var word in words){
		map.Add(word, true);
	}
	
	foreach(var word in words.OrderByDescending(s => s.Length)){
		if(CanBuildWord(word, map, true)){
			word.Dump();
		}
	}
	
	map.Dump();
	
}

bool CanBuildWord(string word, Dictionary<string, bool> map, bool isOriginal){
	if(map.ContainsKey(word) && !isOriginal){
		return map[word];
	}
	
	for(int i = 1; i < word.Length; i++){
		string left = word.Substring(0, i);
		string right = word.Substring(i);
		
		//$"{left}, {right}".Dump();
		
		if(map.ContainsKey(left) && map[left] 
			&& CanBuildWord(right, map, false)){
			return true;
		}
	}
	
	//$"Putting {word} into map with false value".Dump();
	map[word] = false;
	return false;
}

## Largest Area in Histogram

void Main()
{
	var hist = new int[]{1,2,3,5,4,4,3,2,5};
	MaxAreaHist(hist).Dump();
}


int MaxAreaHist(int[] hist){
	int i = 0;
	int maxArea = 0;
	
	Stack<int> stack = new Stack<int>();
	while(i < hist.Length){
		if(stack.Count == 0 || hist[stack.Peek()] <= hist[i]){
			stack.Push(i++);
		}else{
			int top = stack.Pop();
			int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
			int area = hist[top] * width;
			
			maxArea = Math.Max(maxArea, area);
		}
	}
	
	while(stack.Count != 0){
		int top = stack.Pop();
		int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
		
		int area = hist[top] * width;
		maxArea = Math.Max(maxArea, area);
	}
	
	return maxArea;
}

## Four Number Sum

using System.Collections.Generic;
using System;

public class Program {
	public static List<int[]> FourNumberSum(int[] array, int targetSum) {
		
		var map = new Dictionary<int, List<Pair>>();
		var result = new List<int[]>();
		
		for(int i = 0; i < array.Length - 1; i++){
			for(int j = i + 1; j < array.Length; j++){
				int sum = array[i] + array[j];
				int compliment = targetSum - sum;
				if(map.ContainsKey(compliment)){
					foreach(var complimentPair in map[compliment]){
						result.Add(new int[]{array[i], array[j], array[complimentPair.i], array[complimentPair.j]});
						Console.WriteLine($"{i}, {j}, {complimentPair.i}, {complimentPair.j}");
					}
				}	
			}
			
			for(int k = 0; k < i; k++){
				int sum = array[k] + array[i];
				if(!map.ContainsKey(sum)){
					map.Add(sum, new List<Pair>(){new Pair(k, i)});
				}else{
					map[sum].Add(new Pair(k, i));
				}
			}
			
		}
		return result;
	}
	
	public class Pair
	{
		public int i;
		public int j;
		public Pair(int i, int j){
			this.i = i;
			this.j = j;
		} 
	}
}

## Sum (without addition)

/*
	Write a function that adds two numbers without using + or any arithmetic operators.
*/
void Main()
{
	Sum2(2,3).Dump();	
}


// Recursive

int Sum(int a, int b){
	if(b == 0) return a;
	
	int sum = a ^ b; // XOR is equivalent to adding without carry
	int carry = (a & b) << 1; // carry is equivalent to AND and left shift.
	
	$"a: {Convert.ToString(a,2)}, \nb:{Convert.ToString(b,2)}, \nsum: {Convert.ToString(sum,2)}, \ncarry: {Convert.ToString(carry,2)}".Dump("--");
	
	
	return Sum(sum, carry);
}

// Iterative

int Sum2(int a, int b){
	while(b != 0){
		int sum = a ^ b;
		int carry = (a & b) << 1;
		a = sum;
		b = carry;
	}
	return a;
}

## Shuffle

/*
	Write a method to shuffle a deck of cards. It must be a perfect shuffle, 
	i.e. each of the 52! permutations of the deck has to be equally likely.
*/
void Main()
{
		var nums = new[]{1,2,3,4,5,6,7,8,9,10,11,12,13};
		Shuffle(nums).Print();
}


int[] Shuffle(int[] nums){
	Random rand = new Random();
	for(int i = 0; i< nums.Length; i++){
		int k = rand.Next(i+1);
		
		Swap(i, k, nums);		
	}
	return nums;
}

int[] Shuffle1(int[] nums){
	return ShuffleRecursively(nums, nums.Length -1 );
}

int[] ShuffleRecursively(int[] nums, int i){
	if(i == 0) return nums;
	
	ShuffleRecursively(nums, i-1);
	Random rand = new Random();
	int k = rand.Next(i+1);
	
	Swap(k, i, nums);
	return nums;
}

static void Swap(int i, int j, int[] a){
	int tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
}

## Simple Calculator ( with parenthesis)

void Main()
{
	string input = "7 + 3*2/6 + (3+4)*5";
	Calculate(input).Dump();
	
}

int Calculate(string s){
	var listInput = s.ToCharArray().ToList();
	listInput.RemoveAll(c => c == ' ');
	return Calculate(listInput);
}

int Calculate(List<char> s){
	if(s.Count == 0) return 0;
	
	var stack = new Stack<int>();
	int num = 0;
	var sign = '+';
	
	while(s.Count > 0){
		char c = s[0];
		s.RemoveAt(0);
		
		if(Char.IsDigit(c)){
			num = num * 10 + (c - '0');
		}
		
		if(c == '(')
			num = Calculate(s);
		
		if(s.Count == 0 || c == '+' || c == '-' || c == '*' || c == '/' || c == ')'){
			if(sign == '+'){
				stack.Push(num);
			}
			if(sign == '-'){
				stack.Push(-num);
			}
			if(sign == '*'){
				int top = stack.Pop();
				stack.Push(top * num);
			}
			if(sign == '/'){
				int top = stack.Pop();
				stack.Push(top / num);
			}
			
			sign = c;
			num = 0;
			
			if(sign == ')') break;
			
		}
	}
	
	stack.Dump();
	
	return stack.Sum();
}

## Phone Digit Words

void Main()
{
	var path = "C:\\temp\\words_alpha.txt";
	var words = File.ReadAllLines(path);
	
	var trie = new Trie();
	foreach(var word in words){
		trie.Insert(word);
	}
	
	var input = Console.ReadLine();
	while(input != ""){
		GetSequence(input, trie).Dump();
		input = Console.ReadLine();	
	}
	
}


List<string> GetSequence(string number, Trie trie){
	var words = new List<string>();
	GetSequence(number, 0, trie.Root, words);
	return words;
}

private void GetSequence(string number, int index, TrieNode currentNode, List<string> words){
	if(index == number.Length){
		if(Trie.IsTerminating(currentNode)){ 
			words.Add(currentNode.Word); 
		}
		return;
	}
	
	char digit = number[index];
	var letters = GetT9Letters(digit);
	
	if(letters != null){
		foreach(var letter in letters){
			if(currentNode.Children.ContainsKey(letter)){
				GetSequence(number, index + 1, currentNode.Children[letter], words);
			}
		}
	}
}

public char[] GetT9Letters(char digit){
	var t9Letters = new char[][]{
		null,null, 
		new []{'a','b','c'}, new []{'d','e','f'}, new []{'g','h','i'},
		new []{'j','k','l'}, new []{'m','n','o'}, new []{'p','q','r', 's'},
		new []{'t','u','v'}, new []{'w','x','y','z'}};
		
	if(!Char.IsDigit(digit)) return null;
	int index = digit - '0';
	
	return t9Letters[index];
}


public HashSet<string> walk(string word, Trie trie){
	var currentNode = trie.Root;
	var result = new HashSet<string>();
	
	char letter = word[0];
	for(int i=0; i < word.Length; i++){
		letter = word[i];
		if(!currentNode.Children.ContainsKey(letter)){
			return result;
		}
		currentNode = currentNode.Children[letter];
	}
	
	Walk(currentNode, result);
	
	return result;
}

public void Walk(TrieNode currentNode, HashSet<string> result){
	if(currentNode == null) return;
	if(Trie.IsTerminating(currentNode)){
		result.Add(currentNode.Word);
	}
	
	foreach(var node in currentNode.Children.Values){
		Walk( node, result);
	}
}


public class Trie{
	public TrieNode Root = new TrieNode();
	const char EndChar = '*';
	public int Count;
	
	public static bool IsTerminating(TrieNode node){
		return node.Children.ContainsKey(EndChar);
	}
	
	public bool Contains(string word){
		TrieNode currentNode  = Root;
		for(int i=0; i < word.Length; i++){
			var letter = word[i];
			if(!currentNode.Children.ContainsKey(letter)){
				return false;
			}
			currentNode = currentNode.Children[letter];
		}
		return IsTerminating(currentNode); 
	}
	
	public void Insert(string word){
		TrieNode currentNode  = Root;
		for(int i=0; i < word.Length; i++){
			var letter = word[i];
			if(!currentNode.Children.ContainsKey(letter)){
				currentNode.Children.Add(letter, new TrieNode());
			}
			currentNode = currentNode.Children[letter];
		}
		currentNode.Children[EndChar] = null;
		currentNode.Word = word;
		Count++;
	}
	
}

public class TrieNode{
	public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
	public string Word;
}

## LCS

using System.Collections.Generic;
using System;

public class Program {
	public static List<char> LongestCommonSubsequence(string str1, string str2) {
		List<char> result = new List<char>();
		int rows = str1.Length + 1;
		int columns = str2.Length + 1;
		
		int[,] dp = new int[rows, columns];
		for(int row=0; row<rows; row++){
			dp[row, 0] = 0;
		}
		for(int column = 0; column < columns; column++){
			dp[0, column] = 0;
		}
		
		for(int row = 1; row < rows; row++){
			for(int column = 1; column < columns; column++){
				if(str1[row-1] == str2[column-1]){
					dp[row,column] = 1 + dp[row-1, column-1];
				}else{
					dp[row,column] = Math.Max(dp[row-1, column], dp[row, column-1]);
				}		
			}
		}
		
		
		int r = rows - 1;
		int c = columns - 1;
		
		while(r != 0 && c != 0){
			if(dp[r,c] == dp[r, c-1]) {
				c--;
			}else if(dp[r,c] == dp[r-1, c]){
				r--;
			}else{
				result.Insert(0, str1[r-1]);
				r--;
				c--;
			}
		}
		
		return result;
	}
}

## Weaving Lists

void Main()
{
	var nums = new[]{50,20,60,10,25,70,5,15,65,80};
	BstNode root = new BstNode(nums[0]);
	for(int i = 1; i<nums.Length; i++){
		root.Insert(nums[i]);
	}
	
	var sequences = AllSequences(root);
	sequences.ToList().ForEach(s => s.Print());
}

public List<List<int>> AllSequences(BstNode node){

	List<List<int>> result = new List<List<int>>();
	if(node == null){
		result.Add(new List<int>());
		return result;
	}
	var prefix = new List<int>(){node.value};
	
	var leftSequences = AllSequences(node.left);
	var rightSequences = AllSequences(node.right);
	
	foreach(var left in leftSequences){
	foreach(var right in rightSequences){
			var woven = new List<List<int>>();
			WeaveLists(left, right, prefix, woven);
			result.AddRange(woven);
		}
	}
	
	return result;
}


public void WeaveLists(List<int> first, List<int> second, List<int> prefix, List<List<int>> result){
	if(first.Count == 0  || second.Count == 0){
		var merged = new List<int>(prefix);
		merged.AddRange(first);
		merged.AddRange(second);
		result.Add(merged);
		//merged.Print();
		return;
	}
	
	var firstHead = first.ElementAt(0);
	first.RemoveAt(0);
	prefix.Add(firstHead);
	WeaveLists(first, second, prefix, result);
	prefix.RemoveAt(prefix.Count-1);
	first.Insert(0, firstHead);
	
	var secondHead = second.ElementAt(0);
	second.RemoveAt(0);
	prefix.Add(secondHead);
	WeaveLists(first, second, prefix, result);
	prefix.RemoveAt(prefix.Count-1);
	second.Insert(0, secondHead);
	
}



public class BstNode
{
	public readonly int value;
	public BstNode left;
	public BstNode right;
	
	public BstNode(int value)
	{
		this.value = value;
	}
	
	public void Insert(int val){
		if(val < this.value){
			if(this.left == null){
				this.left = new BstNode(val);
			}else{
				this.left.Insert(val);
			}
		}else{
			if(this.right == null){
				this.right = new BstNode(val);
			}else{
				this.right.Insert(val);
			}
		}
	}
}

## Rotate Matrix

static void rotate(int [,] matrix){
	int n = matrix.GetLength(0);
	for(int layer = 0; layer < n; layer++)
	{
		int first = layer;
		int last = n - layer - 1;
		for(int i = first; i < last; i++)
		{	
		    int offset = i - first;
			int tmp = matrix[first, i];
			
			matrix[first, i] = matrix[last-offset, first];
			matrix[last-offset, first] = matrix[last, last-offset];
			matrix[last, last-offset] = matrix[i, last];
			matrix[i, last] = tmp;
						
		}
	}
}

## Binary Search (Insertion Point) - equivalent of Array.BinarySearch

static int BinarySearch(int[] array, int target)
{
	return bs(0, array.Length - 1, array, target); 
}

static int bs(int start, int end, int[] array, int target){
	int lastMid = start + (end - start) / 2;
	
	while(start <= end){
		int mid = start + (end - start) / 2;
		lastMid = mid;
		
		if(array[mid] == target){
			return mid;
		}else if(array[mid] > target){
			end = mid - 1;
		}else{
			start = mid + 1;
			lastMid++;
		}
	}
	
	
	return -1 * lastMid - 1;
}

## Sum of 2 linked lists

/*
	Write a function to add 2 linked lists, where each linked list node represents a single digit.
	
	Example:
		Input: 	List 1: ( 1 -> 2 -> 5 ) 
				List 2: ( 2 -> 4 -> 3 )
		Output: 		( 3 -> 6 -> 8 )		
				
*/
void Main()
{
	var l1 = new LinkedListNode(9);
	l1.next = new LinkedListNode(9);
	l1.next.next = new LinkedListNode(9);
	
	
	var l2 = new LinkedListNode(9);
	l2.next = new LinkedListNode(9);
	l2.next.next = new LinkedListNode(9);

	Print(AddLists(l1,l2));
}


public LinkedListNode AddLists(LinkedListNode l1, LinkedListNode l2){
	var partial = AddListsUtil(l1, l2);
	if(partial.carry > 0){
		return InsertBefore(partial.sum, partial.carry);
	}
	
	return partial.sum;
}

public PartialSum AddListsUtil(LinkedListNode l1, LinkedListNode l2){
	if(l1 == null && l2 == null){
		return new PartialSum();
	}
	
	var partial = AddListsUtil(l1.next, l2.next);
	int value = l1.value + l2.value + partial.carry;
	
	var final = InsertBefore(partial.sum, value % 10);
	
	partial.carry = value / 10;
	partial.sum = final;
	
	return partial;
}


public LinkedListNode InsertBefore(LinkedListNode l, int value){
	var node = new LinkedListNode(value);
	
	if(l != null){
		node.next = l;
	}
	
	return node;
}

public class PartialSum{
	public int carry;
	public LinkedListNode sum;
}

public class LinkedListNode {
	public int value;
	public LinkedListNode next;
	
	public LinkedListNode(int val){
		this.value = val;
	}
}

static void Print(LinkedListNode l){
	if(l == null) { "( )".Dump(); return;}
	
	Console.Write("\n( ");
	while(l.next != null){
		Console.Write($" {l.value} ->"); 
		l = l.next;
	}
	
	Console.Write($" {l.value}");
	
	Console.Write(" )");
}

## PowerSet (All subsets of a set)

void Main()
{
	var set = new List<int> {1,2,3};
	int n = 1 << set.Count();
	
	for(int i = 0; i < n; i++){
		convertIntToSet(set, i).Dump($"{i}");
	}
}

private static List<int> convertIntToSet(List<int> set, int n){
	var result = new List<int>();
	int index = 0;
	for(int i = n; i > 0; i >>=1){
		if((i & 1) == 1){
			result.Add(set[index]);
		}
		index++;
	}
	
	return result;
}

## Matrix Zigzag traverse

using System;
using System.Collections.Generic;

public class Program {
	public static List<int> ZigzagTraverse(List<List<int>> array) {
		bool down = true;
		var result = new List<int>();
		if(array == null) return result;
		
		int height = array.Count;
		int width = array[0].Count;
		int lastRow = height - 1;
		int lastColumn = width - 1;
		int totalCount = height * width;
		int r = 0;
		int c = 0;
		
		while(result.Count < totalCount){
			result.Add(array[r][c]);
			if(down){
				if(c == 0 || r == lastRow){
					down = false;
					if(r == lastRow){
						c++;
					}else{
						r++;
					}
				}else{
					r++;
					c--;
				}
			}else{ // going up
				if(r == 0 || c == lastColumn){
					down = true;
					if(c == lastColumn){
						r++;
					}else{
						c++;
					}
				}else{
					r--;
					c++;
				}
			}
		}
		return result;
	}
}

## Travelling salesperson (dynamic programming formula)
$$
g(i,s)=Min_{k \epsilon s}(C_{ik} + g(k, s-\{k\}))
$$

The formula is **recursive**.
`i` - ith element of graph (start of graph)
`g(i,s)` - the fucntion to calculate the optimal path
`Cik` - cost of travelling from `i`th vertex to the next
`S` - set of vertices
`S - {k}` - set of vertices where vertex k is excluded from the set

## Min/Max subset sum (dynamic programming)

static int isSubsetSum(int[] set, int sum, bool useMinItems = true){
		bool[,] dp = new bool[set.Length + 1, sum + 1];
		int[,] counts = new int[set.Length + 1, sum + 1];
		
		for(int i = 0; i <= sum; i++){
			dp[0, i] = false;
			counts[0,i] = -1;
		}
		
		for(int i = 0; i <= set.Length; i++){
			dp[i,0] = true;
			counts[i,0] = 0;
		}
		
		for(int i = 1; i <= set.Length; i++){
			for(int j = 1; j <= sum; j++){
				if(set[i-1] > j){
					dp[i,j] = dp[i-1,j];
					counts[i,j] = counts[i-1,j];
					
				}else{
					
					dp[i,j] = dp[i-1, j] || dp[i-1, j - set[i-1]];
					
					if(dp[i,j]) {
						counts[i,j] = useMinItems 
							? dp[i-1, j]  
            // prefer using the sum without including the next item
								? counts[i-1, j] 
								: 1 + counts[i-1,j-set[i-1]]
							: Math.Max(counts[i-1,j], counts[i-1,j-set[i-1]] + 1);
					}
				}
			}
		}
			
		return counts[set.Length, sum];
	}
	

## Next permutation

public class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    private void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

## Minimum Window Substring

class Solution {
  public String minWindow(String searchString, String t) {
    Map<Character, Integer> requiredCharacters = buildMappingOfCharactersToOccurrences(t);
    Map<Character, Integer> windowCharacterMapping = new HashMap<Character, Integer>();

    int left = 0;
    int right = 0;

    int totalCharFrequenciesToMatch = requiredCharacters.size();
    int charFrequenciesInWindowThatMatch = 0;

    int minWindowLengthSeenSoFar = Integer.MAX_VALUE;
    String minWindow = "";

    while (right < searchString.length()) {
      char characterAtRightPointer = searchString.charAt(right);
      addCharacterToHashtableMapping(windowCharacterMapping, characterAtRightPointer);

      boolean rightCharIsARequirement = requiredCharacters.containsKey(characterAtRightPointer);
      if (rightCharIsARequirement) {
        boolean requirementForCharacterMet = requiredCharacters.get(characterAtRightPointer)
            .intValue() == windowCharacterMapping.get(characterAtRightPointer).intValue();

        if (requirementForCharacterMet) {
          charFrequenciesInWindowThatMatch++;
        }
      }

      while (charFrequenciesInWindowThatMatch == totalCharFrequenciesToMatch && left <= right) {
        char characterAtLeftPointer = searchString.charAt(left);
        int windowSize = right - left + 1;

        if (windowSize < minWindowLengthSeenSoFar) {
          minWindowLengthSeenSoFar = windowSize;
          minWindow = searchString.substring(left, right + 1);
        }

        windowCharacterMapping.put(characterAtLeftPointer, windowCharacterMapping.get(characterAtLeftPointer) - 1);

        boolean leftCharIsARequirement = requiredCharacters.containsKey(characterAtLeftPointer);
        if (leftCharIsARequirement) {
          boolean characterFailsRequirement = windowCharacterMapping.get(characterAtLeftPointer)
              .intValue() < requiredCharacters.get(characterAtLeftPointer).intValue();

          if (characterFailsRequirement) {
            charFrequenciesInWindowThatMatch--;
          }
        }

        left++;
      }

      right++;
    }

    return minWindow;
  }

  private Map<Character, Integer> buildMappingOfCharactersToOccurrences(String s) {
    Map<Character, Integer> map = new HashMap<Character, Integer>();

    for (int i = 0; i < s.length(); i++) {
      int occurrencesOfCharacter = map.getOrDefault(s.charAt(i), 0);
      map.put(s.charAt(i), occurrencesOfCharacter + 1);
    }

    return map;
  }

  private void addCharacterToHashtableMapping(Map<Character, Integer> map, Character c) {
    int occurrences = map.getOrDefault(c, 0);
    map.put(c, occurrences + 1);
  }
}

## Min Heap

public class Heap{
		readonly List<int> array;
		readonly Func<int, int, bool> comparisonFunction;

		public Heap(Func<int, int, bool> comparisonFunction, List<int> list){
			this.comparisonFunction = comparisonFunction;
			this.array = BuildHeap(list);
		}
		
		public int Peek(){
			return array[0];
		}
		
		public int Length{
			get {return array.Count;}
		}
		
		public void Insert(int value){
			array.Add(value);
			SiftUp(array.Count - 1, array);
		}
		
		public int Remove(){
			Swap(0, array.Count - 1, array);
			int valueToReturn = array[array.Count - 1];
			array.RemoveAt(array.Count-1);
			SiftDown(0, array.Count - 1, array);
			return valueToReturn;
		}
		
		private List<int> BuildHeap(List<int> list){
			int firstParentIndex = (list.Count - 1 ) / 2;
			for(int i = firstParentIndex; i >= 0; i--){
				SiftDown(i, list.Count - 1, list);
			}
			
			return list;
		}
		
		private void SiftUp(int currentIndex, List<int> heap){
			while(currentIndex > 0){
				int parentIndex = (currentIndex - 1) / 2;
				if(comparisonFunction(heap[currentIndex], heap[parentIndex])){
					Swap(currentIndex, parentIndex, heap);
				}
				currentIndex = parentIndex;
			}
		}
		
		private void SiftDown(int currentIndex, int endIndex, List<int> heap){
			int childOneIndex = (currentIndex * 2) + 1;
			
			while(childOneIndex <= endIndex){
				int childTwoIndex = (currentIndex * 2) + 2 > endIndex ? -1 : (currentIndex * 2) + 2;
				int indexToSwap;
				if(childTwoIndex != -1 && comparisonFunction(heap[childTwoIndex], heap[childOneIndex])){
					indexToSwap = childTwoIndex;
				}else{
					indexToSwap = childOneIndex;
				}
				
				if(comparisonFunction(heap[indexToSwap], heap[currentIndex])){
					Swap(currentIndex, indexToSwap, heap);
					currentIndex = indexToSwap;
					childOneIndex = (currentIndex * 2) + 1;
				}else{
					return;
				}
			}
		}
		
		private void Swap(int i, int j, List<int> heap){
			int tmp = heap[i];
			heap[i] = heap[j];
			heap[j] = tmp;
		}
		
		public static bool MinFunction(int a, int b){
			return a < b;
		}
		
		public static bool MaxFunction(int a, int b){
			return a > b;
		}
	}

## Quickselect

using System;

public class Program {
	public static int Quickselect(int[] array, int k) {
		int position =  k - 1 ;
		return Quickselect(array, 0, array.Length - 1, position);
	}
	
	static int Quickselect(int[] array, int startIdx, int endIdx, int position){
		
		while(true)
		{
			if(startIdx > endIdx) { throw new Exception("This should never happen") ; }
			int pivotIdx = startIdx;
			int leftIdx = startIdx + 1;
			int rightIdx = endIdx;
			
			while(leftIdx <= rightIdx)
			{
				if(array[leftIdx] > array[pivotIdx] && array[rightIdx] < array[pivotIdx] ){
					swap(leftIdx, rightIdx, array);
				}
				if(array[leftIdx] <= array[pivotIdx]){
					leftIdx++;
				}
				if(array[rightIdx] >= array[pivotIdx]){
					rightIdx--;
				}
			}
			swap(rightIdx, pivotIdx, array);

			if(rightIdx == position){
				return array[position];
			}else if(rightIdx < position){
				startIdx = rightIdx + 1;
			}else{ endIdx = rightIdx - 1; }
		}
	}
	
	static void swap(int i, int j, int[] array){
		int tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;
	}
}

## Reverse Linked List

public class Program {
	public static LinkedList ReverseLinkedList(LinkedList head) {
		
		LinkedList prev = null;
		while(head != null){
			LinkedList next_node = head.Next;
			head.Next = prev;			 
			prev = head;
			head = next_node;
		}
		return prev;
	}

	public class LinkedList {
		public int Value;
		public LinkedList Next = null;

		public LinkedList(int value) {
			this.Value = value;
		}
	}
}

## LRUCache

using System.Collections.Generic;

public class Program {
	public class LRUCache {
		public int maxSize;
		readonly Dictionary<string, Node> map;
		readonly Node head = new Node();
		readonly Node tail = new Node();
		
		public LRUCache(int maxSize) {
			this.maxSize = maxSize > 1 ? maxSize : 1;
			map = new Dictionary<string, Node>(maxSize);
			head.next = tail;
			tail.prev = head;
		}

		public void InsertKeyValuePair(string key, int value) {
			if(map.ContainsKey(key)){
				Node node = map[key];
				node.value = value;
				UpdateNode(node); 
			}else{
				if(map.Count >= maxSize){
					Node leastRecent = tail.prev;
					map.Remove(leastRecent.key);
					RemoveNode(leastRecent);
				}
					Node newNode = new Node();
					newNode.key = key;
					newNode.value = value;

					AddNode(newNode);
					map.Add(key, newNode);
				}
			}

		public LRUResult GetValueFromKey(string key) {
			var result = new LRUResult(false, -1);
			if(map.ContainsKey(key)){
				var resultNode = map[key];
				result.found = true;
				result.value = resultNode.value;
				UpdateNode(resultNode);
			}
			return result;
		}

		public string GetMostRecentKey() {
			Node mostRecentNode = head.next;
			return mostRecentNode.key;
		}
		
		private void AddNode(Node node){
			// Add to head
			Node headNext = head.next;
			head.next = node;
			node.prev = head;
			node.next = headNext;
			headNext.prev = node;
		}
		
		private void RemoveNode(Node node){
			Node nextNode = node.next;
			Node prevNode = node.prev;
			nextNode.prev = prevNode;
			prevNode.next = nextNode;
		}
		
		private void UpdateNode(Node node){
			RemoveNode(node);
			AddNode(node);
		}
	}

	public class Node {
		public string key;
		public int value;
		
		public Node prev;
		public Node next;
	}
	
	public class LRUResult {
		public bool found;
		public int value;

		public LRUResult(bool found, int value) {
			this.found = found;
			this.value = value;
		}
	}
}

## Suffix Tries

using System.Collections.Generic;

public class Program {
	public class TrieNode {
		public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
	}

	public class SuffixTrie {
		public TrieNode root = new TrieNode();
		public char endSymbol = '*';

		public SuffixTrie(string str) {
			PopulateSuffixTrieFrom(str);
		}

		public void PopulateSuffixTrieFrom(string str) {
			for(int i = 0; i < str.Length; i++){
				PopulateStartingAt(i, str);
			}
		}

		public bool Contains(string str) {
			TrieNode node = root;
			for(int i = 0; i < str.Length; i++){
				char letter = str[i];
				if(!node.Children.ContainsKey(letter)){
					return false;
				}
				node = node.Children[letter];
			}
			return node.Children.ContainsKey(endSymbol);
		}
		
		public void PopulateStartingAt(int i, string str){
			TrieNode node = root;
			for(int j = i; j < str.Length; j++){
				char letter = str[j];
				if(!node.Children.ContainsKey(letter)){
					node.Children.Add(letter, new TrieNode());
				}
				node = node.Children[letter];
			}
			node.Children.Add(endSymbol, null);
		}
	}
}

## Spiral Traverse

using System.Collections.Generic;
using System;


public class Program {
	public static List<int> SpiralTraverse(int[,] array) {
		
		var result = new List<int>();
		
		int rowBegin = 0;
		int columnBegin = 0;
		int rowEnd = array.GetLength(0)-1;		
		int columnEnd = array.GetLength(1)-1;
		int maxSize = (rowEnd + 1) * (columnEnd + 1);
		
		while(result.Count < maxSize){
			for(int i=columnBegin; i<= columnEnd; i++){
				result.Add(array[rowBegin, i]);
			}
			rowBegin++;
			
			for(int i=rowBegin; i<= rowEnd; i++){
				result.Add(array[i, columnEnd]);
			}
			columnEnd--;
			
			if(columnBegin <= columnEnd && result.Count < maxSize){
				for(int i=columnEnd; i>=columnBegin; i--){
					result.Add(array[rowEnd, i]);
				}	
			}
			rowEnd--;
			
			if(rowBegin <= rowEnd && result.Count < maxSize){
				for(int i=rowEnd; i>=rowBegin; i--){
					result.Add(array[i, columnBegin]);
				}
			}
			columnBegin++;	
		}	
		
		return result;
	}
}

## In Order Traversal (Non-Recursive)

using System;
using System.Collections.Generic;

public class Program {
	public static void IterativeInOrderTraversal(BinaryTree tree, Action<BinaryTree> callback) {
		
		if(tree == null) return;
		
		BinaryTree current = tree;
		Stack<BinaryTree> stack = new Stack<BinaryTree>();
		
		while(current != null || stack.Count != 0){
			while(current != null){
				stack.Push(current);
				current = current.left;
			}
			
			current = stack.Pop();
			callback(current);
			current = current.right;
		}
	}

	public class BinaryTree {
		public int value;
		public BinaryTree left;
		public BinaryTree right;
		public BinaryTree parent;

		public BinaryTree(int value) {
			this.value = value;
		}

		public BinaryTree(int value, BinaryTree parent) {
			this.value = value;
			this.parent = parent;
		}
	}
}

## Merge Linked Lists

public class Program {
	// This is an input class. Do not edit.
	public class LinkedList {
		public int value;
		public LinkedList next;

		public LinkedList(int value) {
			this.value = value;
			this.next = null;
		}
	}
	public static LinkedList mergeLinkedLists(LinkedList headOne, LinkedList headTwo) {
		LinkedList p1 = headOne;
		LinkedList p2 = headTwo;
		LinkedList prev = null;
		
		while(p1 != null && p2 != null){
			if(p1.value < p2.value){
				prev = p1;
				p1 = p1.next;
			}else{
				if(prev != null)
					prev.next = p2;
				prev = p2;
				p2 = p2.next;
				prev.next = p1;
			}
		}
		
		if(p1 == null){
			prev.next = p2;
		}
		return headOne.value < headTwo.value ? headOne : headTwo;
	}
}