These C# examples cover a wide range of programming areas in Computer Science. Every example program includes the description of the program, C# code as well as output of the program. All examples are compiled and tested on Visual Studio.
C# – Brute-Force Algorithm
In this example, we will learn C# implementation of Brute-Force Algorithm.Brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem’s statement.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace BruteForceAlgorithm { class BruteForceAlgo { public delegate bool BruteForceTest(ref char[] testChars); public static bool BruteForce(string testChars, int startLength, int endLength, BruteForceTest testCallback) { for (int len = startLength; len <= endLength; ++len) { char[] chars = new char[len]; for (int i = 0; i < len; ++i) chars[i] = testChars[0]; if (testCallback(ref chars)) return true; for (int i1 = len - 1; i1 > -1; --i1) { int i2 = 0; for (i2 = testChars.IndexOf(chars[i1]) + 1; i2 < testChars.Length; ++i2) { chars[i1] = testChars[i2]; if (testCallback(ref chars)) return true; for (int i3 = i1 + 1; i3 < len; ++i3) { if (chars[i3] != testChars[testChars.Length - 1]) { i1 = len; goto outerBreak; } } } outerBreak: if (i2 == testChars.Length) chars[i1] = testChars[0]; } } return false; } static void Main(string[] args) { BruteForceTest testCallback = delegate(ref char[] testChars) { var str = new string(testChars); return (str == "bbc"); }; bool result = BruteForce("abcde", 1, 5, testCallback); Console.WriteLine(result); } } } |
Output:
True
C# – Knapsack Problem
In this exapmles, we will write C# implementation for Knapsack problem
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Diagnostics; namespace KnapsackAlgo { class KnapsackAlgorithm { public static int KnapSack(int capacity, int[] weight, int[] value, int itemsCount) { int[,] K = new int[itemsCount + 1, capacity + 1]; for (int i = 0; i <= itemsCount; ++i) { for (int w = 0; w <= capacity; ++w) { if (i == 0 || w == 0) K[i, w] = 0; else if (weight[i - 1] <= w) K[i, w] = Math.Max(value[i - 1] + K[i - 1, w - weight[i - 1]], K[i - 1, w]); else K[i, w] = K[i - 1, w]; } } return K[itemsCount, capacity]; } static void Main(string[] args) { int[] value = { 10, 50, 70 }; int[] weight = { 10, 20, 30 }; int capacity = 40; int itemsCount = 3; int result = KnapSack(capacity, weight, value, itemsCount); Console.WriteLine(result); } } } |
C# – Bellman–Ford Algorithm
In this example, we will learn C# implementation of Bellman–Ford Algorithm for determining the shortest paths from a single source vertex to all of the other vertices in a weighted graph
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Diagnostics; namespace BellmanFordAlgorithm { class BellmanFordAlgo { public struct Edge { public int Source; public int Destination; public int Weight; } public struct Graph { public int VerticesCount; public int EdgesCount; public Edge[] edge; } public static Graph CreateGraph(int verticesCount, int edgesCount) { Graph graph = new Graph(); graph.VerticesCount = verticesCount; graph.EdgesCount = edgesCount; graph.edge = new Edge[graph.EdgesCount]; return graph; } private static void Print(int[] distance, int count) { Console.WriteLine("Vertex Distance from source"); for (int i = 0; i < count; ++i) Console.WriteLine("{0}\t {1}", i, distance[i]); } public static void BellmanFord(Graph graph, int source) { int verticesCount = graph.VerticesCount; int edgesCount = graph.EdgesCount; int[] distance = new int[verticesCount]; for (int i = 0; i < verticesCount; i++) distance[i] = int.MaxValue; distance[source] = 0; for (int i = 1; i <= verticesCount - 1; ++i) { for (int j = 0; j < edgesCount; ++j) { int u = graph.edge[j].Source; int v = graph.edge[j].Destination; int weight = graph.edge[j].Weight; if (distance[u] != int.MaxValue && distance[u] + weight < distance[v]) distance[v] = distance[u] + weight; } } for (int i = 0; i < edgesCount; ++i) { int u = graph.edge[i].Source; int v = graph.edge[i].Destination; int weight = graph.edge[i].Weight; if (distance[u] != int.MaxValue && distance[u] + weight < distance[v]) Console.WriteLine("Graph contains negative weight cycle."); } Print(distance, verticesCount); } static void Main(string[] args) { int verticesCount = 5; int edgesCount = 8; Graph graph = CreateGraph(verticesCount, edgesCount); // Edge 0-1 graph.edge[0].Source = 0; graph.edge[0].Destination = 1; graph.edge[0].Weight = -1; // Edge 0-2 graph.edge[1].Source = 0; graph.edge[1].Destination = 2; graph.edge[1].Weight = 4; // Edge 1-2 graph.edge[2].Source = 1; graph.edge[2].Destination = 2; graph.edge[2].Weight = 3; // Edge 1-3 graph.edge[3].Source = 1; graph.edge[3].Destination = 3; graph.edge[3].Weight = 2; // Edge 1-4 graph.edge[4].Source = 1; graph.edge[4].Destination = 4; graph.edge[4].Weight = 2; // Edge 3-2 graph.edge[5].Source = 3; graph.edge[5].Destination = 2; graph.edge[5].Weight = 5; // Edge 3-1 graph.edge[6].Source = 3; graph.edge[6].Destination = 1; graph.edge[6].Weight = 1; // Edge 4-3 graph.edge[7].Source = 4; graph.edge[7].Destination = 3; graph.edge[7].Weight = -3; BellmanFord(graph, 0); } } } |
Output:
Vertex Distance from source
0 0
1 -1
2 2
3 -2
4 1
C# – Floyd–Warshall Algorithm
In this article, we will learn C# implementation of Floyd–Warshall Algorithm for determining the shortest paths in a weighted graph with positive or negative edge weights
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Diagnostics; namespace FloydWarshallAlgorithm { class FloydWarshallAlgo { public const int cst = 9999; private static void Print(int[,] distance, int verticesCount) { Console.WriteLine("Shortest distances between every pair of vertices:"); for (int i = 0; i < verticesCount; ++i) { for (int j = 0; j < verticesCount; ++j) { if (distance[i, j] == cst) Console.Write("cst".PadLeft(7)); else Console.Write(distance[i, j].ToString().PadLeft(7)); } Console.WriteLine(); } } public static void FloydWarshall(int[,] graph, int verticesCount) { int[,] distance = new int[verticesCount, verticesCount]; for (int i = 0; i < verticesCount; ++i) for (int j = 0; j < verticesCount; ++j) distance[i, j] = graph[i, j]; for (int k = 0; k < verticesCount; ++k) { for (int i = 0; i < verticesCount; ++i) { for (int j = 0; j < verticesCount; ++j) { if (distance[i, k] + distance[k, j] < distance[i, j]) distance[i, j] = distance[i, k] + distance[k, j]; } } } Print(distance, verticesCount); } static void Main(string[] args) { int[,] graph = { { 0, 6, cst, 11 }, { cst, 0, 4, cst }, { cst, cst, 0, 2 }, { cst, cst, cst, 0 } }; FloydWarshall(graph, 4); } } } |
Output:
Shortest distances between every pair of vertices:
0 6 10 11
cst 0 4 6
cst cst 0 2
cst cst cst 0
C# – Dijkstra Algorithm for Determining the Shortest Path
In this article, we will learn C# implementation of Dijkstra Algorithm for Determining the Shortest Path
Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph.It was conceived by computer scientist Edsger W. Dijkstra in 1956.This algorithm helps to find the shortest path from a point in a graph (the source) to a destination.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Diagnostics; namespace DijkstraAlgorithm { class Dijkstra { private static int MinimumDistance(int[] distance, bool[] shortestPathTreeSet, int verticesCount) { int min = int.MaxValue; int minIndex = 0; for (int v = 0; v < verticesCount; ++v) { if (shortestPathTreeSet[v] == false && distance[v] <= min) { min = distance[v]; minIndex = v; } } return minIndex; } private static void Print(int[] distance, int verticesCount) { Console.WriteLine("Vertex Distance from source"); for (int i = 0; i < verticesCount; ++i) Console.WriteLine("{0}\t {1}", i, distance[i]); } public static void DijkstraAlgo(int[,] graph, int source, int verticesCount) { int[] distance = new int[verticesCount]; bool[] shortestPathTreeSet = new bool[verticesCount]; for (int i = 0; i < verticesCount; ++i) { distance[i] = int.MaxValue; shortestPathTreeSet[i] = false; } distance[source] = 0; for (int count = 0; count < verticesCount - 1; ++count) { int u = MinimumDistance(distance, shortestPathTreeSet, verticesCount); shortestPathTreeSet[u] = true; for (int v = 0; v < verticesCount; ++v) if (!shortestPathTreeSet[v] && Convert.ToBoolean(graph[u, v]) && distance[u] != int.MaxValue && distance[u] + graph[u, v] < distance[v]) distance[v] = distance[u] + graph[u, v]; } Print(distance, verticesCount); } static void Main(string[] args) { int[,] graph = { { 0, 6, 0, 0, 0, 0, 0, 9, 0 }, { 6, 0, 9, 0, 0, 0, 0, 11, 0 }, { 0, 9, 0, 5, 0, 6, 0, 0, 2 }, { 0, 0, 5, 0, 9, 16, 0, 0, 0 }, { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, { 0, 0, 6, 0, 10, 0, 2, 0, 0 }, { 0, 0, 0, 16, 0, 2, 0, 1, 6 }, { 9, 11, 0, 0, 0, 0, 1, 0, 5 }, { 0, 0, 2, 0, 0, 0, 6, 5, 0 } }; DijkstraAlgo(graph, 0, 9); } } } |
Output:
Vertex Distance from source
0 0
1 6
2 15
3 20
4 22
5 12
6 10
7 9
8 14
C# – Breadth First Search (BFS) using Queue
In this example, we will write a C# program to implement Breadth First Search (BFS) using Queue
Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph) and explores the neighbor nodes first, before moving to the next level neighbors.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 | using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace BreadthFirst { class Program { public class Employee { public Employee(string name) { this.name = name; } public string name { get; set; } public List<Employee> Employees { get { return EmployeesList; } } public void isEmployeeOf(Employee p) { EmployeesList.Add(p); } List<Employee> EmployeesList = new List<Employee>(); public override string ToString() { return name; } } public class BreadthFirstAlgorithm { public Employee BuildEmployeeGraph() { Employee Eva = new Employee("Eva"); Employee Sophia = new Employee("Sophia"); Employee Brian = new Employee("Brian"); Eva.isEmployeeOf(Sophia); Eva.isEmployeeOf(Brian); Employee Lisa = new Employee("Lisa"); Employee Tina = new Employee("Tina"); Employee John = new Employee("John"); Employee Mike = new Employee("Mike"); Sophia.isEmployeeOf(Lisa); Sophia.isEmployeeOf(John); Brian.isEmployeeOf(Tina); Brian.isEmployeeOf(Mike); return Eva; } public Employee Search(Employee root, string nameToSearchFor) { Queue<Employee> Q = new Queue<Employee>(); HashSet<Employee> S = new HashSet<Employee>(); Q.Enqueue(root); S.Add(root); while (Q.Count > 0) { Employee e = Q.Dequeue(); if (e.name == nameToSearchFor) return e; foreach (Employee friend in e.Employees) { if (!S.Contains(friend)) { Q.Enqueue(friend); S.Add(friend); } } } return null; } public void Traverse(Employee root) { Queue<Employee> traverseOrder = new Queue<Employee>(); Queue<Employee> Q = new Queue<Employee>(); HashSet<Employee> S = new HashSet<Employee>(); Q.Enqueue(root); S.Add(root); while (Q.Count > 0) { Employee e = Q.Dequeue(); traverseOrder.Enqueue(e); foreach (Employee emp in e.Employees) { if (!S.Contains(emp)) { Q.Enqueue(emp); S.Add(emp); } } } while (traverseOrder.Count > 0) { Employee e = traverseOrder.Dequeue(); Console.WriteLine(e); } } } static void Main(string[] args) { BreadthFirstAlgorithm b = new BreadthFirstAlgorithm(); Employee root = b.BuildEmployeeGraph(); Console.WriteLine("Traverse Graph\n------"); b.Traverse(root); Console.WriteLine("\nSearch in Graph\n------"); Employee e = b.Search(root, "Eva"); Console.WriteLine(e == null ? "Employee not found" : e.name); e = b.Search(root, "Brian"); Console.WriteLine(e == null ? "Employee not found" : e.name); e = b.Search(root, "Soni"); Console.WriteLine(e == null ? "Employee not found" : e.name); } } } |
Output:
Traverse Graph:
——–
Eva
Sophia
Lisa
John
Brian
Tina
Mike
Search in Graph:
——-
Eva
Brian
Emplyee not found
C# – Depth First Seach (DFS) using List
In this example, we will write a C# program to implement Depth First Search using List.
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace DefthFirst { class Program { public class Employee { public Employee(string name) { this.name = name; } public string name { get; set; } public List<Employee> Employees { get { return EmployeesList; } } public void isEmployeeOf(Employee e) { EmployeesList.Add(e); } List<Employee> EmployeesList = new List<Employee>(); public override string ToString() { return name; } } public class DepthFirstAlgorithm { public Employee BuildEmployeeGraph() { Employee Eva = new Employee("Eva"); Employee Sophia = new Employee("Sophia"); Employee Brian = new Employee("Brian"); Eva.isEmployeeOf(Sophia); Eva.isEmployeeOf(Brian); Employee Lisa = new Employee("Lisa"); Employee Tina = new Employee("Tina"); Employee John = new Employee("John"); Employee Mike = new Employee("Mike"); Sophia.isEmployeeOf(Lisa); Sophia.isEmployeeOf(John); Brian.isEmployeeOf(Tina); Brian.isEmployeeOf(Mike); return Eva; } public Employee Search(Employee root, string nameToSearchFor) { if (nameToSearchFor == root.name) return root; Employee personFound = null; for (int i = 0; i < root.Employees.Count; i++) { personFound = Search(root.Employees[i], nameToSearchFor); if (personFound != null) break; } return personFound; } public void Traverse(Employee root) { Console.WriteLine(root.name); for (int i = 0; i < root.Employees.Count; i++) { Traverse(root.Employees[i]); } } } static void Main(string[] args) { DepthFirstAlgorithm b = new DepthFirstAlgorithm(); Employee root = b.BuildEmployeeGraph(); Console.WriteLine("Traverse Graph\n------"); b.Traverse(root); Console.WriteLine("\nSearch in Graph\n------"); Employee e = b.Search(root, "Eva"); Console.WriteLine(e == null ? "Employee not found" : e.name); e = b.Search(root, "Brian"); Console.WriteLine(e == null ? "Employee not found" : e.name); e = b.Search(root, "Soni"); Console.WriteLine(e == null ? "Employee not found" : e.name); } } } |
Output:
Traverse Graph:
——–
Eva
Sophia
Lisa
John
Brian
Tina
Mike
Search in Graph:
——-
Eva
Brian
Emplyee not found
C# – Huffman coding using Dictionary
In this example, we will learn the C# implementation for Huffman coding using Dictionary.
Huffman coding is a lossless data compression algorithm. The idea is to assign variable-legth codes to input characters, lengths of the assigned codes are based on the frequencies of corresponding characters. The most frequent character gets the smallest code and the least frequent character gets the largest code.
Node.cs :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace HuffmanTest { public class Node { public char Symbol { get; set; } public int Frequency { get; set; } public Node Right { get; set; } public Node Left { get; set; } public List<bool> Traverse(char symbol, List<bool> data) { // Leaf if (Right == null && Left == null) { if (symbol.Equals(this.Symbol)) { return data; } else { return null; } } else { List<bool> left = null; List<bool> right = null; if (Left != null) { List<bool> leftPath = new List<bool>(); leftPath.AddRange(data); leftPath.Add(false); left = Left.Traverse(symbol, leftPath); } if (Right != null) { List<bool> rightPath = new List<bool>(); rightPath.AddRange(data); rightPath.Add(true); right = Right.Traverse(symbol, rightPath); } if (left != null) { return left; } else { return right; } } } } } |
HuffmanTree.cs :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; namespace HuffmanTest { public class HuffmanTree { private List<Node> nodes = new List<Node>(); public Node Root { get; set; } public Dictionary<char, int> Frequencies = new Dictionary<char, int>(); public void Build(string source) { for (int i = 0; i < source.Length; i++) { if (!Frequencies.ContainsKey(source[i])) { Frequencies.Add(source[i], 0); } Frequencies[source[i]]++; } foreach (KeyValuePair<char, int> symbol in Frequencies) { nodes.Add(new Node() { Symbol = symbol.Key, Frequency = symbol.Value }); } while (nodes.Count > 1) { List<Node> orderedNodes = nodes.OrderBy(node => node.Frequency).ToList<Node>(); if (orderedNodes.Count >= 2) { // Take first two items List<Node> taken = orderedNodes.Take(2).ToList<Node>(); // Create a parent node by combining the frequencies Node parent = new Node() { Symbol = '*', Frequency = taken[0].Frequency + taken[1].Frequency, Left = taken[0], Right = taken[1] }; nodes.Remove(taken[0]); nodes.Remove(taken[1]); nodes.Add(parent); } this.Root = nodes.FirstOrDefault(); } } public BitArray Encode(string source) { List<bool> encodedSource = new List<bool>(); for (int i = 0; i < source.Length; i++) { List<bool> encodedSymbol = this.Root.Traverse(source[i], new List<bool>()); encodedSource.AddRange(encodedSymbol); } BitArray bits = new BitArray(encodedSource.ToArray()); return bits; } public string Decode(BitArray bits) { Node current = this.Root; string decoded = ""; foreach (bool bit in bits) { if (bit) { if (current.Right != null) { current = current.Right; } } else { if (current.Left != null) { current = current.Left; } } if (IsLeaf(current)) { decoded += current.Symbol; current = this.Root; } } return decoded; } public bool IsLeaf(Node node) { return (node.Left == null && node.Right == null); } } } |
Program to test Huffman Coding:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; namespace HuffmanTest { class Program { static void Main(string[] args) { Console.WriteLine("Please enter the string:"); string input = Console.ReadLine(); HuffmanTree huffmanTree = new HuffmanTree(); // Build the Huffman tree huffmanTree.Build(input); // Encode BitArray encoded = huffmanTree.Encode(input); Console.Write("Encoded: "); foreach (bool bit in encoded) { Console.Write((bit ? 1 : 0) + ""); } Console.WriteLine(); // Decode string decoded = huffmanTree.Decode(encoded); Console.WriteLine("Decoded: " + decoded); Console.ReadLine(); } } } |
Output:
Please enter the string:
welcome to cce
Encoded: 01010101100100011101010101010010100101010100101010010101001010101011100101000111
Decoded: welcome to cce
C# – Coin change problem : Greedy algorithm
In this example, we will discuss an optimal solution to solve Coin change problem using Greedy algorithm.
A greedy algorithm is the one that always chooses the best solution at the time, with no regard for how that choice will affect future choices.Here, we will discuss how to use Greedy algorithm to making coin changes.
It has been proven that an optimal solution for coin changing can always be found using the current American denominations of coins
For an example, Let’s say you buy some items at the store and the change from your purchase is 63 cents. How does the clerk determine the change to give you? If the clerk follows a greedy algorithm, he or she gives you two quarters, a dime, and three pennies. That is the smallest number of coins that will equal 63 cents.
C# Implementation on Coin change Problem using Greedy algorithm :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | using System; using System.Text; using System.Security.Cryptography; public class CsharpHashAlgo { static void MakeChange(double origAmount, double remainAmount, int[] coins) { if ((origAmount % 0.25) < origAmount) { coins[3] = (int)(origAmount / 0.25); remainAmount = origAmount % 0.25; origAmount = remainAmount; } if ((origAmount % 0.1) < origAmount) { coins[2] = (int)(origAmount / 0.1); remainAmount = origAmount % 0.1; origAmount = remainAmount; } if ((origAmount % 0.05) < origAmount) { coins[1] = (int)(origAmount / 0.05); remainAmount = origAmount % 0.05; origAmount = remainAmount; } if ((origAmount % 0.01) < origAmount) { coins[0] = (int)(origAmount / 0.01); remainAmount = origAmount % 0.01; } } static void ShowChange(int[] arr) { if (arr[3] > 0) Console.WriteLine("Number of quarters: " + arr[3]); if (arr[2] > 0) Console.WriteLine("Number of dimes: " + arr[2]); if (arr[1] > 0) Console.WriteLine("Number of nickels: " + arr[1]); if (arr[0] > 0) Console.WriteLine("Number of pennies: " + arr[0]); } static void Main() { Console.WriteLine("Enter the amount you want to change:"); double origAmount = Convert.ToDouble(Console.ReadLine()); double toChange = origAmount; double remainAmount = 0.0; int[] coins = new int[4]; MakeChange(origAmount, remainAmount, coins); Console.WriteLine("The best way to change " + toChange + " cents is: "); ShowChange(coins); } } |
Output:
Enter the amount you want to change : 0.63
The best way to change 0.63 cents is:
Number of quarters : 2
Number of dimes: 1
Number of pennies: 3
C# – Hash data using salt
In this example, we will write a C# program to hash data/password using salt value
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | using System; using System.Text; using System.Security.Cryptography; public class CsharpHashAlgorithm { public static string ComputeHash(string plainText, string hashAlgorithm, byte[] saltBytes) { // If salt is not specified, generate it on the fly. if (saltBytes == null) { // Define min and max salt sizes. int minSaltSize = 4; int maxSaltSize = 8; // Generate a random number for the size of the salt. Random random = new Random(); int saltSize = random.Next(minSaltSize, maxSaltSize); // Allocate a byte array, which will hold the salt. saltBytes = new byte[saltSize]; // Initialize a random number generator. RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider(); // Fill the salt with cryptographically strong byte values. rng.GetNonZeroBytes(saltBytes); } // Convert plain text into a byte array. byte[] plainTextBytes = Encoding.UTF8.GetBytes(plainText); // Allocate array, which will hold plain text and salt. byte[] plainTextWithSaltBytes = new byte[plainTextBytes.Length + saltBytes.Length]; // Copy plain text bytes into resulting array. for (int i = 0; i < plainTextBytes.Length; i++) plainTextWithSaltBytes[i] = plainTextBytes[i]; // Append salt bytes to the resulting array. for (int i = 0; i < saltBytes.Length; i++) plainTextWithSaltBytes[plainTextBytes.Length + i] = saltBytes[i]; HashAlgorithm hash; // Make sure hashing algorithm name is specified. if (hashAlgorithm == null) hashAlgorithm = ""; // Initialize appropriate hashing algorithm class. switch (hashAlgorithm.ToUpper()) { case "SHA1": hash = new SHA1Managed(); break; case "SHA256": hash = new SHA256Managed(); break; case "SHA384": hash = new SHA384Managed(); break; case "SHA512": hash = new SHA512Managed(); break; default: hash = new MD5CryptoServiceProvider(); break; } // Compute hash value of our plain text with appended salt. byte[] hashBytes = hash.ComputeHash(plainTextWithSaltBytes); // Create array which will hold hash and original salt bytes. byte[] hashWithSaltBytes = new byte[hashBytes.Length + saltBytes.Length]; // Copy hash bytes into resulting array. for (int i = 0; i < hashBytes.Length; i++) hashWithSaltBytes[i] = hashBytes[i]; // Append salt bytes to the result. for (int i = 0; i < saltBytes.Length; i++) hashWithSaltBytes[hashBytes.Length + i] = saltBytes[i]; // Convert result into a base64-encoded string. string hashValue = Convert.ToBase64String(hashWithSaltBytes); // Return the result. return hashValue; } public class CsharpHashAlgo { static void Main(string[] args) { Console.WriteLine("Please enter the string for hashing:"); string plaintext = Console.ReadLine(); string passwordHashMD5 = CsharpHashAlgorithm.ComputeHash(plaintext, "MD5", null); string passwordHashSha1 = CsharpHashAlgorithm.ComputeHash(plaintext, "SHA1", null); string passwordHashSha256 = CsharpHashAlgorithm.ComputeHash(plaintext, "SHA256", null); string passwordHashSha384 = CsharpHashAlgorithm.ComputeHash(plaintext, "SHA384", null); string passwordHashSha512 = CsharpHashAlgorithm.ComputeHash(plaintext, "SHA512", null); Console.WriteLine("Original String : {0}", plaintext); Console.WriteLine("Hash values :\r\n"); Console.WriteLine("MD5 : {0}", passwordHashMD5); Console.WriteLine("SHA1 : {0}", passwordHashSha1); Console.WriteLine("SHA256: {0}", passwordHashSha256); Console.WriteLine("SHA384: {0}", passwordHashSha384); Console.WriteLine("SHA512: {0}", passwordHashSha512); Console.WriteLine(""); } } } |
Output:
Please enter the string for hashing: Welcome to cce
Original string: Welcome to cce
Hash values:
MD5 : SC4LSYSAkKILp2rPW1ZVpOP1WK7g
SHA1 : E0CfoAleTy9lDL8PmqLlY76jg3k/as3G5DPe
SHA256: p4OqMcDW33DzkGR7+UskcFv75yq/Jb7K49mRwRYHLdw0+HTwq3sS
SHA384: Tq6F1p1Hhan+tGPLOS+T6ltPh7wvTtPqgvgd4BKCTPEGnXCOEQpcrm0IELEjnobkWKY9
SHA512: UjtzgRAx4BWpMKYb1Qnrhn3Nlj84MrKNX1zJbNW33saM9IEtRmpzn4Ny6Y5oITg3TkSZ
C# – Encrypt and Decrypt data using a symmetric key – Rijndael Algorithm
In this example, we will write a C# program to Encrypt and Decrypt data using a symmetric key
What is Symmetric Key?
Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both encryption of plaintext and decryption of ciphertext. The keys may be identical or there may be a simple transformation to go between the two keys.
C# Implementation to Encrypt and Decrypt data using a symmetric key :
In below implementation, we will use Rijndael Algorithm to encrypt & decrypt data in C#. below are the few key parameters we will be using in C# implementation.
– passPhrase : Passphrase from which a pseudo-random password will be derived. The derived password will be used to generate the encryption key. Passphrase can be any string.
– saltValue : Salt value used along with passphrase to generate password. Salt can be any string.
– hashAlgorithm : Hash algorithm used to generate password. Allowed values are: “MD5” and “SHA256”
passwordIterations : Number of iterations used to generate password. One or two iterations should be enough.
– initVector : Initialization vector (or IV). This value is required to encrypt the first block of plaintext data. For RijndaelManaged class IV must be exactly 16 ASCII characters long.
– keySize : Size of encryption key in bits. Allowed values are: 128, 192, and 256.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 | public class RijndaelAlgorithm { public static string Encrypt ( string plainText, string passPhrase, string saltValue, string hashAlgorithm, int passwordIterations, string initVector, int keySize ) { // Convert strings into byte arrays. // Let us assume that strings only contain ASCII codes. // If strings include Unicode characters, use Unicode, UTF7, or UTF8 // encoding. byte[] initVectorBytes = Encoding.ASCII.GetBytes(initVector); byte[] saltValueBytes = Encoding.ASCII.GetBytes(saltValue); // Convert our plaintext into a byte array. byte[] plainTextBytes = Encoding.UTF8.GetBytes(plainText); // First, we must create a password, from which the key will be derived. // This password will be generated from the specified passphrase and // salt value. The password will be created using the specified hash // algorithm. Password creation can be done in several iterations. PasswordDeriveBytes password = new PasswordDeriveBytes ( passPhrase, saltValueBytes, hashAlgorithm, passwordIterations ); // Use the password to generate pseudo-random bytes for the encryption // key. Specify the size of the key in bytes (instead of bits). byte[] keyBytes = password.GetBytes(keySize / 8); // Create uninitialized Rijndael encryption object. RijndaelManaged symmetricKey = new RijndaelManaged(); symmetricKey.Mode = CipherMode.CBC; // Generate encryptor from the existing key bytes and initialization // vector. Key size will be defined based on the number of the key bytes. ICryptoTransform encryptor = symmetricKey.CreateEncryptor ( keyBytes, initVectorBytes ); // Define memory stream which will be used to hold encrypted data. MemoryStream memoryStream = new MemoryStream(); // Define cryptographic stream (always use Write mode for encryption). CryptoStream cryptoStream = new CryptoStream ( memoryStream, encryptor, CryptoStreamMode.Write ); // Start encrypting. cryptoStream.Write(plainTextBytes, 0, plainTextBytes.Length); // Finish encrypting. cryptoStream.FlushFinalBlock(); // Convert our encrypted data from a memory stream into a byte array. byte[] cipherTextBytes = memoryStream.ToArray(); // Close both streams. memoryStream.Close(); cryptoStream.Close(); // Convert encrypted data into a base64-encoded string. string cipherText = Convert.ToBase64String(cipherTextBytes); // Return encrypted string. return cipherText; } public static string Decrypt ( string cipherText, string passPhrase, string saltValue, string hashAlgorithm, int passwordIterations, string initVector, int keySize ) { // Convert strings defining encryption key characteristics into byte arrays. byte[] initVectorBytes = Encoding.ASCII.GetBytes(initVector); byte[] saltValueBytes = Encoding.ASCII.GetBytes(saltValue); // Convert our ciphertext into a byte array. byte[] cipherTextBytes = Convert.FromBase64String(cipherText); // First, we must create a password, from which the key will be // derived. This password will be generated from the specified passphrase and salt value. // The password will be created using the specified hash algorithm. Password creation can be done in several iterations. PasswordDeriveBytes password = new PasswordDeriveBytes ( passPhrase, saltValueBytes, hashAlgorithm, passwordIterations ); // Use the password to generate pseudo-random bytes for the encryption // key. Specify the size of the key in bytes (instead of bits). byte[] keyBytes = password.GetBytes(keySize / 8); // Create uninitialized Rijndael encryption object. RijndaelManaged symmetricKey = new RijndaelManaged(); // It is reasonable to set encryption mode to Cipher Block Chaining // (CBC). Use default options for other symmetric key parameters. symmetricKey.Mode = CipherMode.CBC; // Generate decryptor from the existing key bytes and initialization // vector. Key size will be defined based on the number of the key // bytes. ICryptoTransform decryptor = symmetricKey.CreateDecryptor ( keyBytes, initVectorBytes ); // Define memory stream which will be used to hold encrypted data. MemoryStream memoryStream = new MemoryStream(cipherTextBytes); // Define cryptographic stream (always use Read mode for encryption). CryptoStream cryptoStream = new CryptoStream ( memoryStream, decryptor, CryptoStreamMode.Read ); byte[] plainTextBytes = new byte[cipherTextBytes.Length]; // Start decrypting. int decryptedByteCount = cryptoStream.Read ( plainTextBytes, 0, plainTextBytes.Length ); // Close both streams. memoryStream.Close(); cryptoStream.Close(); // Convert decrypted data into a string. // Let us assume that the original plaintext string was UTF8-encoded. string plainText = Encoding.UTF8.GetString ( plainTextBytes, 0, decryptedByteCount ); // Return decrypted string. return plainText; } } /// Illustrates the use of RijndaelSimple class to encrypt and decrypt data. public class RijndaelSimpleTest { /// <summary> /// The main entry point for the application. /// </summary> [STAThread] static void Main(string[] args) { //string plainText = "Welcome to csharpstar.com!"; // original plaintext Console.Write("Input the Original Plain Text : "); string plainText = Console.ReadLine(); string passPhrase = "TestPassphrase"; // can be any string string saltValue = "TestSaltValue"; // can be any string string hashAlgorithm = "SHA256"; // can be "MD5" int passwordIterations = 2; // can be any number string initVector = "!1A3g2D4s9K556g7"; // must be 16 bytes int keySize = 256; // can be 192 or 128 Console.WriteLine(String.Format("Plaintext : {0}", plainText)); string cipherText = RijndaelAlgorithm.Encrypt ( plainText, passPhrase, saltValue, hashAlgorithm, passwordIterations, initVector, keySize ); Console.WriteLine(String.Format("Encrypted : {0}", cipherText)); plainText = RijndaelAlgorithm.Decrypt ( cipherText, passPhrase, saltValue, hashAlgorithm, passwordIterations, initVector, keySize ); Console.WriteLine(String.Format("Decrypted : {0}", plainText)); } } |
Output:
Input the Original Plain Text : welcome to cce!
Pliantext : welcome to csharpstar !
Encrypted : 1FJaiATQu8t5Mt23V+R1L1/Rj03JxYa18MSOHtpfYoA=
Decrypted : welcome to cce!
C# Program to Implement Traversal in Singly Linked List
In this example, we will write a C# program to implement Singly LinkedList traversal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace LinkedList { class singleLinkedlist { private int data; private singleLinkedlist next; public singleLinkedlist() { data = 0; next = null; } public singleLinkedlist(int value) { data = value; next = null; } public singleLinkedlist InsertNext(int value) { singleLinkedlist node = new singleLinkedlist(value); if (this.next == null) { node.next = null; this.next = node; } else { singleLinkedlist temp = this.next; node.next = temp; this.next = node; } return node; } public int DeleteNext() { if (next == null) return 0; singleLinkedlist node = this.next; this.next = this.next.next; node = null; return 1; } public void Traverse(singleLinkedlist node) { if (node == null) node = this; System.Console.WriteLine("Traversing Singly Linked List :"); while (node != null) { System.Console.WriteLine(node.data); node = node.next; } } } class Program { static void Main(string[] args) { singleLinkedlist node1 = new singleLinkedlist(100); singleLinkedlist node2 = node1.InsertNext(200); singleLinkedlist node3 = node2.InsertNext(300); singleLinkedlist node4 = node3.InsertNext(400); singleLinkedlist node5 = node4.InsertNext(500); node1.Traverse(null); Console.WriteLine("Deleting from Linked List..."); node3.DeleteNext(); node2.Traverse(null); System.Console.ReadLine(); } } } |
Output:
Traversing Singly Linked List :
100
200
300
400
500
Deleting from Linked List…
Traversing Singly Linked List :
200
300
500
Create a Circular Singly Linked List in C#
Circular Linked List is a linked data structure.
– In the circular linked list we can insert elements anywhere in the list
– In the circular linked list the previous element stores the address of the next element and the last element stores the address of the starting element.
– The circular linked list has a dynamic size and the memory can be allocated when it is required.
Implementation of Singly Linked Circular List in C# :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace CircularLinkedList { class Circularlist { private int currentdata; private Circularlist nextdata; public Circularlist() { currentdata = 0; nextdata = this; } public Circularlist(int value) { currentdata = value; nextdata = this; } public Circularlist Insdata(int value) { Circularlist node = new Circularlist(value); if (this.nextdata == this) { node.nextdata = this; this.nextdata = node; } else { Circularlist temp = this.nextdata; node.nextdata = temp; this.nextdata = node; } return node; } public int Deldata() { if (this.nextdata == this) { System.Console.WriteLine("\nOnly one node..."); return 0; } Circularlist node = this.nextdata; this.nextdata = this.nextdata.nextdata; node = null; return 1; } public void Traverse() { Traverse(this); } public void Traverse(Circularlist node) { if (node == null) node = this; System.Console.WriteLine("Forward Direction..."); Circularlist snode = node; do { System.Console.WriteLine(node.currentdata); node = node.nextdata; } while (node != snode); } public int Gnodes() { return Gnodes(this); } public int Gnodes(Circularlist node) { if (node == null) node = this; int count = 0; Circularlist snode = node; do { count++; node = node.nextdata; } while (node != snode); System.Console.WriteLine("\nCurrent Node Value : " + node.currentdata.ToString()); System.Console.WriteLine("\nTotal nodes :" + count.ToString()); return count; } static void Main(string[] args) { Circularlist node1 = new Circularlist(100); node1.Deldata(); Circularlist node2 = node1.Insdata(200); node1.Deldata(); node2 = node1.Insdata(200); Circularlist node3 = node2.Insdata(300); Circularlist node4 = node3.Insdata(400); Circularlist node5 = node4.Insdata(500); node1.Gnodes(); node3.Gnodes(); node5.Gnodes(); node1.Traverse(); node5.Deldata(); node2.Traverse(); node1.Gnodes(); node2.Gnodes(); node5.Gnodes(); Console.Read(); } } } |
Output:
Only one node…
Current Node Value : 100
Total Node: 5
Current Node Value : 300
Total Node: 5
Current Node Value : 500
Total Node: 5
Forward Direction…
100
200
300
400
500
Forward Direction…
200
300
400
500
Towers of Hanoi in C#
Towers of Hanoi or Tower of Brahma or Lucas’ Tower
Tower of Hanoi is a mathematical game or puzzle. It consists of three rods(towers), and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
- Only one disk can be moved at a time.
- Each move consists of taking the upper disk from one of the towers and placing it on top of another tower i.e. a disk can only be moved if it is the uppermost disk on a tower.
- No disk may be placed on top of a smaller disk.
Solving Towers of Hanoi using Recursion:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | public class TowersOfHanoi { public static void Main(String[] args) { char startPeg = 'A'; // start tower in output char endPeg = 'C'; // end tower in output char tempPeg = 'B'; // temporary tower in output int totalDisks = 3; // number of disks solveTowers(totalDisks, startPeg, endPeg, tempPeg); } private static void solveTowers(int n, char startPeg, char endPeg, char tempPeg) { if (n > 0) { solveTowers(n - 1, startPeg, tempPeg, endPeg); Console.WriteLine("Move disk from " + startPeg + ' ' + endPeg); solveTowers(n - 1, tempPeg, endPeg, startPeg); } } } |
Output:
Move disk from A to C
Move disk from A to B
Move disk from C to B
Move disk from A to C
Move disk from B to A
Move disk from B to C
Move disk from A to C
C# Program to Implement Stack with Push and Pop operations
In this example, we will write a C# program to implement stack with Push and Pop Operations.
The primary operations you perform with a stack are Push and Pop. Data is added to a stack with the Push method. Data is removed from the stack with the Pop method.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { stack st = new stack(); while (true) { Console.Clear(); Console.WriteLine("\nStack MENU(size -- 10)"); Console.WriteLine("1. Add an element"); Console.WriteLine("2. See the Top element."); Console.WriteLine("3. Remove top element."); Console.WriteLine("4. Display stack elements."); Console.WriteLine("5. Exit"); Console.Write("Select your choice: "); int choice = Convert.ToInt32(Console.ReadLine()); switch (choice) { case 1: Console.WriteLine("Enter an Element : "); st.Push(Console.ReadLine()); break; case 2: Console.WriteLine("Top element is: {0}", st.Peek()); break; case 3: Console.WriteLine("Element removed: {0}", st.Pop()); break; case 4: st.Display(); break; case 5: System.Environment.Exit(1); break; } Console.ReadKey(); } } } interface StackADT { Boolean isEmpty(); void Push(Object element); Object Pop(); Object Peek(); void Display(); } class stack : StackADT { private int StackSize; public int StackSizeSet { get { return StackSize; } set { StackSize = value; } } public int top; Object[] item; public stack() { StackSizeSet = 10; item = new Object[StackSizeSet]; top = -1; } public stack(int capacity) { StackSizeSet = capacity; item = new Object[StackSizeSet]; top = -1; } public bool isEmpty() { if (top == -1) return true; return false; } public void Push(object element) { if (top == (StackSize - 1)) { Console.WriteLine("Stack is full!"); } else { item[++top] = element; Console.WriteLine("Item pushed successfully!"); } } public object Pop() { if (isEmpty()) { Console.WriteLine("Stack is empty!"); return "No elements"; } else { return item[top--]; } } public object Peek() { if (isEmpty()) { Console.WriteLine("Stack is empty!"); return "No elements"; } else { return item[top]; } } public void Display() { for (int i = top; i > -1; i--) { Console.WriteLine("Item {0}: {1}", (i + 1), item[i]); } } } } |
Output:
Stack MENU(size — 10)
1. Add an element
2. See the Top Element
3. Remove the Top Element
4. Display Stack Elements
5. Exit
Select your Choice : 1
Enter the Element : 12
Item Pushed Successfully!
Select your choice :1
Enter the Element : 45
Item Pushed Successfully!
Select your choice : 4
Item 2 :45
Item 1 :12
Select your choice : 2
Top element is : 45
Select your choice : 3
Element removed : 45
Select your choice : 4
Item 1 :12
C# Program to Implement Stack
In this article, we will write a C# program to Implement Stack with an example
The stack is one of the most frequently used data structures. We define a stack as a list of items that are accessible only from the end of the list, which is called the top of the stack. For an example, trays at a cafeteria.Trays are always removed from the top, and the when the dishwasher or busboy puts a tray back on the stack, it is placed on the top also. A stack is known as a Last-in, First-out (LIFO) data
structure.
In below example, we will write a C# program that uses Stack to identify if the string is palindromic.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | namespace Stack { class CsharpStack { private int p_index; private ArrayList list; public CsharpStack() { list = new ArrayList(); p_index = -1; } public int count { get { return list.Count; } } public void push(object item) { list.Add(item); p_index++; } public object pop() { object obj = list[p_index]; list.RemoveAt(p_index); p_index--; return obj; } public void clear() { list.Clear(); p_index = -1; } public object peek() { return list[p_index]; } } class program { public static void Main(string[] args) { CsharpStack alist = new CsharpStack(); string ch; string word = "eye"; bool isPalindrome = true; for (int x = 0; x < word.Length; x++) alist.push(word.Substring(x, 1)); int pos = 0; while (alist.count > 0) { ch = alist.pop().ToString(); if (ch != word.Substring(pos, 1)) { isPalindrome = false; break; } pos++; } if (isPalindrome) Console.WriteLine(word + " is a palindrome."); else Console.WriteLine(word + " is not a palindrome."); Console.Read(); } } } |
Output:
eye is a palindrome
C# Program to Delete nodes from Binary Search Tree
In this article, we will learn:
- Removing a Leaf Node From a BST
- Deleting a Node With One Child
- Deleting a Node With Two Children
Removing a Leaf Node From a BST:
Removing a leaf is the simplest case sincethere are no child nodes to take into consideration.All we have to do is set each child node of the target node’s parent to null. So, the node will still be there, but there will not be any references to the node.
– The while loop takes us to the node we are deleting.
– The first test is to see if the left child and the right child of that node are null.
– Then we test to see if this node is the root node. If so, we set it to null, otherwise, we either set the left node of the parent to null (if isLeftChild is true) or we set the right node of the parent to null.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | public Node Delete(int key) { Node current = root; Node parent = root; bool isLeftChild = true; while (current.Data != key) { parent = current; if (key < current.Data) { isLeftChild = true; current = current.Right; else { isLeftChild = false; current = current.Right; } if (current == null) return false; } if ((current.Left == null) & (current.Right == null)) if (current == root) root == null; else if (isLeftChild) parent.Left = null; else parent.Right = null; } // the rest of the class goes here } |
C# Program to Implement Binary Search Tree Traversal – Preorder,InOrder & Postorder
In this article, we will learn : Binary Search Tree Traversal in C#
Binary Search Tree Traversal:
You can learn how to implement Binary search Tree in C# and Insert nodes in BST here.
There are three traversal methods used with Binary Search Tree: inorder, preorder, and postorder.
– An inorder traversal visits all the nodes in a BST in ascending order of the node key values.
– A preorder traversal visits the root node first, followed by the nodes in the subtrees under the left child of the root, followed by the nodes in the subtrees under the right child of the root
– A postorder traversal, the method first recurses over the left subtrees and then over the right subtrees.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 | class Node { public int item; public Node left; public Node right; public void display() { Console.Write("["); Console.Write(item); Console.Write("]"); } } class Tree { public Node root; public Tree() { root = null; } public Node ReturnRoot() { return root; } public void Insert(int id) { Node newNode = new Node(); newNode.item = id; if (root == null) root = newNode; else { Node current = root; Node parent; while (true) { parent = current; if (id < current.item) { current = current.left; if (current == null) { parent.left = newNode; return; } } else { current = current.right; if (current == null) { parent.right = newNode; return; } } } } } public void Preorder(Node Root) { if (Root != null) { Console.Write(Root.item + " "); Preorder(Root.left); Preorder(Root.right); } } public void Inorder(Node Root) { if (Root != null) { Inorder(Root.left); Console.Write(Root.item + " "); Inorder(Root.right); } } public void Postorder(Node Root) { if (Root != null) { Postorder(Root.left); Postorder(Root.right); Console.Write(Root.item + " "); } } } class Program { static void Main(string[] args) { Tree BST = new Tree(); BST.Insert(30); BST.Insert(35); BST.Insert(57); BST.Insert(15); BST.Insert(63); BST.Insert(49); BST.Insert(89); BST.Insert(77); BST.Insert(67); BST.Insert(98); BST.Insert(91); Console.WriteLine("Inorder Traversal : "); BST.Inorder(BST.ReturnRoot()); Console.WriteLine(" "); Console.WriteLine(); Console.WriteLine("Preorder Traversal : "); BST.Preorder(BST.ReturnRoot()); Console.WriteLine(" "); Console.WriteLine(); Console.WriteLine("Postorder Traversal : "); BST.Postorder(BST.ReturnRoot()); Console.WriteLine(" "); Console.ReadLine(); } } |
C# program to find the most frequent element in an Array
In this example, we will learn different ways to find the most frequent element in an Array in C#.
Using Hashtable:
You can use Hashtable, to find the most frequent element in an Array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | class MainClass { static void MaxOccurrence(int[] array, Hashtable hs) { int mostCommom = array[0]; int occurences = 0; foreach (int num in array) { if (!hs.ContainsKey(num)) { hs.Add(num, 1); } else { int tempOccurences = (int)hs[num]; tempOccurences++; hs.Remove(num); hs.Add(num, tempOccurences); if (occurences < tempOccurences) { occurences = tempOccurences; mostCommom = num; } } } foreach (DictionaryEntry entry in hs) { Console.WriteLine("{0}, {1}", entry.Key, entry.Value); } Console.WriteLine("The commmon numer is " + mostCommom + " And it appears " + occurences + " times"); } public static void Main(string[] args) { int[] array = new int[20] { 3, 6, 8, 5, 3, 5, 7, 6, 4, 3, 2, 3, 5, 7, 6, 4, 3, 4, 5, 7 }; Hashtable hs = new Hashtable(); MaxOccurrence(array, hs); } } |
Output:
8,1
7,3
6,3
5,4
4,3
3,5
2,1
The common number is 3 and it appears 5 times
HashTable is not generic, which means it will box every int to an object.So you can se a Dictionary<int, int=””> instead.</int,>
C# program to check for Matching Parentheses
In this article, the problem statement is to write a java program that can check and if a string has matching pair of parentheses or not.
For example,
() has matching parenthesis, but (() doesn’t.
For this, we can maintain a counter for the opening parentheses encountered.
When you find an opening parenthesis, add 1 to the counter. Similarly, when you find a closing parenthesis, reduce 1 from the counter. In the end, if the counter is 0, then the parentheses are properly nested.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 | namespace MatchingParentheses { class Program { const char LeftParenthesis = '('; const char RightParenthesis = ')'; static bool isBalancedWithStack(string str) { if (str.Length <= 1 || str.Equals(null)) return false; var items = new Stack<int>(str.Length); int errorAt = -1; for (int i = 0; i < str.Length; i++) { if (str[i].Equals(LeftParenthesis)) items.Push(i); else if (str[i].Equals(RightParenthesis)) { if (items.Count == 0) { errorAt = i + 1; return false; } items.Pop(); } } if (items.Count > 0) { errorAt = items.Peek() + 1; return false; } return true; } static bool isBalancedWithoutStack(string str) { int count = 0; if (str.Length <= 1) return false; for (int i = 0; i < str.Length; i++) { if (str[i].Equals('(')) count++; else if (str[i].Equals(')')) { count--; if (count < 0) return false; } } return (count == 0); } static bool checkParentheses(string str) { if (str.Length <= 1) return false; int count = 0; for (int i = 0; i < str.Length; i++) { switch (str[i]) { case '(': count++; break; case ')': count--; if (count < 0) return false; break; } } return (count == 0); } public static void Main(string[] args) { string[] arrSample = new string[] { " ", "", "(", "()))))))", "(()((fff))())", "(()", "((((()))))", "(()(((())))())", "(()(((())))()", "()()()()()()()()()()()()" }; for (int i = 0; i < arrSample.Length; i++) { if (isBalancedWithStack(arrSample[i])) { Console.WriteLine("{0} is True", arrSample[i]); } else { Console.WriteLine("{0} is False", arrSample[i]); } if (isBalancedWithoutStack(arrSample[i])) { Console.WriteLine("{0} is True", arrSample[i]); } else { Console.WriteLine("{0} is False", arrSample[i]); } if (checkParentheses(arrSample[i])) { Console.WriteLine("{0} is True", arrSample[i]); } else { Console.WriteLine("{0} is False", arrSample[i]); } Console.WriteLine(); } } } } |
Output:
is false
is false
is false
is false
is false
is false
( is false
( is false
( is false
())))))) is false
())))))) is false
())))))) is false
(()((fff))()) is true
(()((fff))()) is true
(()((fff))()) is true
(() is false
(() is false
(() is false
()()()()()()()()()()()() is true
()()()()()()()()()()()() is true
()()()()()()()()()()()() is true
C# – String Distance (Hamming Distance,Levenshtein Distance & Damerau-Levenshtein
Distance) Algorithm
In this article, we will discuss:
- Hamming Distance Algorithm
- Levenshtein Distance Algorithm
- Damerau-Levenshtein Distance Algorithm
1. Hamming Distance Algorithm:
The Hamming Distance measures the minimum number of substitutions required to change one string into the other.The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.The Hamming distance is named after Richard Hamming.
In below example, we will take two strings and if length of strings are not equal then we will show exception else it will calculate the distance between two strings.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | public static class StringDistance { public static int GetHammingDistance(string s, string t) { if (s.Length != t.Length) { throw new Exception("Strings must be equal length"); } int distance = s.ToCharArray() .Zip(t.ToCharArray(), (c1, c2) => new { c1, c2 }) .Count(m => m.c1 != m.c2); return distance; } } class Program { static void Main() { Console.WriteLine(StringDistance.GetHammingDistance("climax", "volmax")); Console.WriteLine(StringDistance.GetHammingDistance("Ram", "Rom")); Console.WriteLine(StringDistance.GetHammingDistance("Mam", "Mom")); } } |
Output:
3
1
1
2. Levenshtein Distance Algorithm:
The Levenshtein distance is a string metric for measuring the difference between two sequences. The Levenshtein distance between two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other. It is named after Vladimir Levenshtein.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | public static class StringDistance { /// <summary> /// Compute the distance between two strings. /// </summary> public static int LevenshteinDistance(string s, string t) { int n = s.Length; int m = t.Length; int[,] d = new int[n + 1, m + 1]; // Step 1 if (n == 0) { return m; } if (m == 0) { return n; } // Step 2 for (int i = 0; i <= n; d[i, 0] = i++) { } for (int j = 0; j <= m; d[0, j] = j++) { } // Step 3 for (int i = 1; i <= n; i++) { //Step 4 for (int j = 1; j <= m; j++) { // Step 5 int cost = (t[j - 1] == s[i - 1]) ? 0 : 1; // Step 6 d[i, j] = Math.Min( Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), d[i - 1, j - 1] + cost); } } // Step 7 return d[n, m]; } } class Program { static void Main() { Console.WriteLine(StringDistance.LevenshteinDistance("climax", "volmax")); Console.WriteLine(StringDistance.LevenshteinDistance("Ram", "Raman")); Console.WriteLine(StringDistance.LevenshteinDistance("Mama", "Mom")); } } |
Output:
3
2
2
Heap sort program in C#
In this example, we will discuss on Heap sort algorithm in C#
it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region
It first removes the topmost item (the largest) and replace it with the rightmost leaf. The topmost item is stored in an array and Re-establish the heap.this is done until there are no more items left in the heap.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | /* * C# Program to Heap Sort */ using System; class heapsort { int[] r = { 2,5,1,10,6,9,3,7,4,8}; public void hsort() { int i, t; for (i = 5; i >= 0; i--) { adjust(i, 9); } for (i = 8; i >= 0; i--) { t = r[i + 1]; r[i + 1] = r[0]; r[0] = t; adjust(0, i); } } private void adjust(int i, int n) { int t, j; try { t = r[i]; j = 2 * i; while (j <= n) { if (j < n && r[j] < r[j + 1]) j++; if (t >=r[j]) break; r[j / 2] = r[j]; j *= 2; } r[j / 2] = t; } catch (IndexOutOfRangeException e) { Console.WriteLine("Array Out of Bounds ", e); } } public void print() { for (int i = 0; i < 10; i++) { Console.WriteLine("{0}", r[i]); } } public static void Main() { heap obj = new heap(); Console.WriteLine("Elements Before sorting : "); obj.print(); obj.hsort(); Console.WriteLine("Elements After sorting : "); obj.print(); Console.Read(); } } |
Here is the output of the C# Program:
Elements Before Sorting :
2
5
1
10
6
9
3
7
4
8
Elements After Sorting :
1
2
3
4
5
6
7
8
9
10
Comb sort program in C#
In this example, we will discuss on Comb sort algorithm in C#
Comb sort is sorting algorithm and it is a variant of Bubble sort, the Comb Sort increases the gap used in comparisons and exchanges.
Comb sort improves on bubble sort.
The basic idea is to eliminate turtles, or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | public static void CombSort(ref int[] data) { double gap = data.Length; bool swaps = true; while (gap > 1 || swaps) { gap /= 1.247330950103979; if (gap < 1) gap = 1; int i = 0; swaps = false; while (i + gap < data.Length) { int igap = i + (int)gap; if (data[i] > data[igap]) { int temp = data[i]; data[i] = data[igap]; data[igap] = temp; swaps = true; } ++i; } } } |
Output
-119
-58
-10
0
85
250
785
Merge sort program in C
In this article, we will discuss Merge sort in C#
Merge Sort is one of the popular sorting algorithms in C# as it uses the minimum number of comparisons.
The idea behind merge sort is that it is merging two sorted lists.
Merge sort is of order O(nlogn)
Here is a high-level representation of the Merge sort algorithm :
1 2 3 4 5 6 7 | Start merge sort sort first half (recursive) sort second half(recursive) merge sorted halves into one sorted list End sort |
Here is in C#:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | using System; using System.Collections.Generic; using System.Text; namespace CSharpMergeSort { class Mergesort { static public void DoMerge(int [] numbers, int left, int mid, int right) { int [] temp = new int[25]; int i, left_end, num_elements, tmp_pos; left_end = (mid - 1); tmp_pos = left; num_elements = (right - left + 1); while ((left <= left_end) && (mid <= right)) { if (numbers[left] <= numbers[mid]) temp[tmp_pos++] = numbers[left++]; else temp[tmp_pos++] = numbers[mid++]; } while (left <= left_end) temp[tmp_pos++] = numbers[left++]; while (mid <= right) temp[tmp_pos++] = numbers[mid++]; for (i = 0; i < num_elements; i++) { numbers[right] = temp[right]; right--; } } static public void MergeSort_Recursive(int [] numbers, int left, int right) { int mid; if (right > left) { mid = (right + left) / 2; MergeSort_Recursive(numbers, left, mid); MergeSort_Recursive(numbers, (mid + 1), right); DoMerge(numbers, left, (mid+1), right); } } static void Main(string[] args) { int[] numbers = { 3, 8, 7, 5, 2, 1, 9, 6, 4 }; int len = 9; Console.WriteLine("MergeSort By Recursive Method"); MergeSort_Recursive(numbers, 0, len - 1); for (int i = 0; i < 9; i++) Console.WriteLine(numbers[i]); Console.WriteLine(numbers[i]); } } } |
Output:
MergeSort By Recursive Method
1
2
3
4
5
6
7
8
9
Shell sort program in C#
In this article, we will write the Shell sort program in C#
Donald Shell published the first version of this sort, hence this is known as Shell sort.
This sorting is a generalization of insertion sort that allows the exchange of items that are far apart
It starts by comparing elements that are far apart and gradually reduces the gap between elements being compared.
The running time of Shell sort varies depending on the gap sequence it uses to sort the elements.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | private void SortArrayWithShellSort() { int[] array = { 297,183, 464 }; ShellSort(array); } private void ShellSort(int[] array) { int n = array.Length; int gap = n / 2; int temp; while (gap > 0) { for (int i = 0; i + gap < n; i++) { int j = i + gap; temp = array[j]; while (j - gap >= 0 && temp < array[j - gap]) { array[j] = array[j - gap]; j = j - gap; } array[j] = temp; } gap = gap / 2; } } |
Output:
183 297 464
C# Program to Find whether the Number is Divisible by 2
In this example, we will write a C# program to find whether the number is divisible by 2 or not
Any whole number that ends in 0, 2, 4, 6, or 8 will be divisible by 2.Here the divisibility test is done by performing the mod function with 2.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | /* * C# Program to Find whether the Number is Divisible by 2 */ using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApplication16 { class Program { static void Main(string[] args) { int n; Console.WriteLine("Enter the Number :"); n = int.Parse(Console.ReadLine()); if (n % 2 == 0) { Console.WriteLine("Entered Number is Divisible by 2 "); } else { Console.WriteLine("Entered Number is Not Divisible by 2"); } Console.ReadLine(); } } } |
Here is the output of the C# Program:
Enter the Number :
57
Entered Number is Not Divisible by 2
C# Program to Display the Factors of the Entered Number
In this example, we will write a C# program to generate factors for a given number.
The factors of a number are all those numbers that can divide evenly into the number with no remainder.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Program { class Program { static void Main(string[] args) { int num, x; Console.WriteLine("Enter the Number "); num = int.Parse(Console.ReadLine()); Console.WriteLine("The Factors are : "); for (x = 1; x <= num; x++) { if (num % x == 0) { Console.WriteLine(x); } } Console.ReadLine(); } } } |
Here is the output of the C# Program:
Enter the Number : 27
The Factors are :
1
3
9
27
3 Different ways to calculate factorial in C#
1. Using For Loop:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace factorial { class Program { static void Main(string[] args) { int i, number, fact; Console.WriteLine("Enter the Number"); number = int.Parse(Console.ReadLine()); fact = number; for (i = number - 1; i >= 1; i--) { fact = fact * i; } Console.WriteLine("\nFactorial of Given Number is: "+fact); Console.ReadLine(); } } } |
2. Using Recursion:
1 2 3 4 5 6 7 8 9 | public double factorial_Recursion(int number) { if (number == 1) return 1; else return number * factorial_recursion(number - 1); } |
3. Using While loop:
1 2 3 4 5 6 7 8 9 10 11 12 | public double factorial_WhileLoop(int number) { double result = 1; while (number != 1) { result = result * number; number = number - 1; } return result; } |
C# program to find sum of digits of a number using Recursion
In this article, we will discuss how to find sum of digits of a number using Recursion.
This is a frequently asked interview question.
Lets have a look at the implementation in C#.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | using System; class program { public static void Main() { int num, result; pro pg = new pro(); Console.WriteLine("Enter the Number : "); num=int.Parse(Console.ReadLine()); result =pg.sum(num); Console.WriteLine("Sum of Digits in {0} is {1}", num, result); Console.ReadLine(); } } class pro { public int sum(int num) { if (num != 0) { return (num % 10 + sum(num / 10)); } else { return 0; } } } |
C# Program to Print Binary Equivalent of an Integer using Recursion
In this article, we will write a C# program to Print Binary Equivalent of an Integer using Recursion
This program finds the binary equivalent of a decimal number entered by the user. Decimal numbers are of base 10 while binary numbers are of base 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | using System; using System.Collections.Generic; using System.Linq; using System.Text; class Program { public static void Main(string[] args) { int num; prog pg = new prog(); Console.WriteLine("Enter a decimal number: "); num = int.Parse(Console.ReadLine()); Console.WriteLine("The binary equivalent of num is :"); pg.binaryconversion(num); Console.ReadLine(); } } public class prog { public int binaryconversion(int num) { int bin; if (num != 0) { bin = (num % 2) + 10 * binaryconversion(num / 2); Console.Write(bin); return 0; } else { return 0; } } } |
Calculate power of number using recursion in C#
In this article, we will write a C# program to calculate power of number using recursion
We know that nth power of a number x can be represented as :
xn = x * x * ..n times… * x
This can be written recursively as :
xn/2 * xn/2 , if n is even
(or)
x * xn/2 * xn/2, if n is odd
Here is a C# program that calculates xn using this approach :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | class Program { static void Main(string[] args) { double x= Power(10, 3); Console.WriteLine(x); } internal static double Power(double @base, int exponent) { if (exponent < 0) { Console.Error.WriteLine("Usage of this function is limited to positive exponents only"); throw new Exception(); } else if (exponent == 1) { return @base; } else if (exponent == 0) { return 1; } else { return @base * Power(@base, exponent - 1); } } } |
Fibonacci Series in C#
In this article, we will learn:
- What is Fibonacci Series ?
- Different ways to print fibonacci series in C#
- How to find nth fibonacci number?
What is Fibonacci Series?
Fibonacci series is a sequence of numbers in below order:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34… The next number is found by adding up the two numbers before it.
The formula for calculating these numbers is:
F(n) = F(n-1) + F(n-2)
where:
F(n) is the term number.
F(n-1) is the previous term (n-1).
F(n-2) is the term before that (n-2).
it starts either with 0 or 1.
Different ways to print Fibonacci Series in C#?
In C#, there are several ways to print Fibonacci Series.
- Iterative Approach
- Recursion Approach
Iterative Approach :
This is the simplest way of generating Fibonacci seres in C#.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | namespace ConsoleApplication { class Program { static int FibonacciSeries(int n) { int firstnumber = 0, secondnumber = 1, result = 0; if (n == 0) return 0; //To return the first Fibonacci number if (n == 1) return 1; //To return the second Fibonacci number for (int i = 2; i <= n; i++) { result = firstnumber + secondnumber; firstnumber = secondnumber; secondnumber = result; } return result; } static void Main(string[] args) { Console.Write("Enter the length of the Fibonacci Series: "); int length = Convert.ToInt32(Console.ReadLine()); for (int i = 0; i < length; i++) { Console.Write("{0} ", FibonacciSeries(i)); } Console.ReadKey(); } } } |
Binary search in C#
In this article, we will write a C# program to perform Binary search in C#
Using Recursion:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | public static object BinarySearchRecursive(int [] inputArray, int key, int min, int max) { if (min > max) { return "Nil"; } else { int mid = (min+max)/2; if (key == inputArray [mid]) { return ++mid; } else if (key < inputArray [mid]) { return BinarySearchRecursive(inputArray, key, min, mid - 1); } else { return BinarySearchRecursive(inputArray, key, mid + 1, max); } } } |
Binary Search without Recursion (Iterative):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | public static object BinarySearchIterative(int[] inputArray, int key, int min, int max) { while (min <=max) { int mid = (min + max) / 2; if (key == inputArray[mid]) { return ++mid; } else if (key < inputArray[mid]) { max = mid - 1; } else { min = mid + 1; } } return "Nil"; } |
C# Program to perform Quick Sort using Recursion
In this article, we will write a C# program to perform Quick sort.
Quicksort is a divide and conquer algorithm. Here Quicksort first divides a large array into two smaller sub-array: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace sortQuickAlgorithm { class quickSortAlgorithm { private int[] array = new int[20]; private int len; public void QuickSortAlgorithm() { sort(0, len - 1); } public void sort(int left, int right) { int pivot, leftend, rightend; leftend = left; rightend = right; pivot = array[left]; while (left < right) { while ((array[right] >= pivot) && (left < right)) { right--; } if (left != right) { array[left] = array[right]; left++; } while ((array[left] >= pivot) && (left < right)) { left++; } if (left != right) { array[right] = array[left]; right--; } } array[left] = pivot; pivot = left; left = leftend; right = rightend; if (left < pivot) { sort(left, pivot - 1); } if (right > pivot) { sort(pivot + 1, right); } } public static void Main() { quickSortAlgorithm q_Sort = new quickSortAlgorithm(); int[] array = { 41, 32, 15, 45, 63, 72, 57, 43, 32, 52, 183}; q_Sort.array = array; q_Sort.len = q_Sort.array.Length; q_Sort.QuickSortAlgorithm(); for (int j = 0; j < q_Sort.len; j++) { Console.WriteLine(q_Sort.array[j]); } Console.ReadKey(); } } } |
C# program to find GCD and LCM
In this article, we will learn how to calculate greatest common divisor (Least common multiple (LCM) of 2 given number.
This is a frequently asked interview questions.
GCD can be found with a simple while loop by comaring the two numbers and assigning the difference to the largest number until the two numbers are equal. Once you know GCD, finding LCM is easy with the formula
LCM(a,b) = (a * b)/ GCD(a,b)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 { class Program { static int GetGCD(int num1, int num2) { while (num1 != num2) { if (num1 > num2) num1 = num1 - num2; if (num2 > num1) num2 = num2 - num1; } return num1; } static int GetLCM(int num1, int num2) { return (num1 * num2) / GetGCD(num1, num2); } static void Main(string[] args) { Console.WriteLine("C# Program for LCM and GCD"); Console.Write("Enter First Number: "); int a = Convert.ToInt32(Console.ReadLine()); Console.Write("Enter Second Number: "); int b = Convert.ToInt32(Console.ReadLine()); int gcd = GetGCD(a, b); int lcm = GetLCM(a, b); Console.WriteLine("\nGCD({0,4},{1,4}) = {2,6}", a, b, gcd); Console.WriteLine("\nLCM({0,4},{1,4}) = {2,6}", a, b, lcm); } } } |
Calculate power of number using recursion in C#
In this article, we will write a C# program to calculate power of number using recursion
We know that nth power of a number x can be represented as :
xn = x * x * ..n times… * x
This can be written recursively as :
xn/2 * xn/2 , if n is even
(or)
x * xn/2 * xn/2, if n is odd
Here is a C# program that calculates xn using this approach :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | class Program { static void Main(string[] args) { double x= Power(10, 3); Console.WriteLine(x); } internal static double Power(double @base, int exponent) { if (exponent < 0) { Console.Error.WriteLine("Usage of this function is limited to positive exponents only"); throw new Exception(); } else if (exponent == 1) { return @base; } else if (exponent == 0) { return 1; } else { return @base * Power(@base, exponent - 1); } } } |
Output :
1000
C# Program to perform Quick Sort using Recursion
In this article, we will write a C# program to perform Quick sort.
Quicksort is a divide and conquer algorithm. Here Quicksort first divides a large array into two smaller sub-array: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace sortQuickAlgorithm { class quickSortAlgorithm { private int[] array = new int[20]; private int len; public void QuickSortAlgorithm() { sort(0, len - 1); } public void sort(int left, int right) { int pivot, leftend, rightend; leftend = left; rightend = right; pivot = array[left]; while (left < right) { while ((array[right] >= pivot) && (left < right)) { right--; } if (left != right) { array[left] = array[right]; left++; } while ((array[left] >= pivot) && (left < right)) { left++; } if (left != right) { array[right] = array[left]; right--; } } array[left] = pivot; pivot = left; left = leftend; right = rightend; if (left < pivot) { sort(left, pivot - 1); } if (right > pivot) { sort(pivot + 1, right); } } public static void Main() { quickSortAlgorithm q_Sort = new quickSortAlgorithm(); int[] array = { 41, 32, 15, 45, 63, 72, 57, 43, 32, 52, 183}; q_Sort.array = array; q_Sort.len = q_Sort.array.Length; q_Sort.QuickSortAlgorithm(); for (int j = 0; j <; q_Sort.len; j++) { Console.WriteLine(q_Sort.array[j]); } Console.ReadKey(); } } } |
Here is the output of the C# Program:
15
32
41
43
45
52
57
63
72
84
183
C# program to perform Bucket sort
In this example, we will learn how to perform Bucket sort in C#
Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort.
Bucket sort works as follows:
1. Set up an array of initially empty “buckets”.
2. Scatter: Go over the original array, putting each object in its bucket.
3. Sort each non-empty bucket.
4. Gather: Visit the buckets in order and put all elements back into the original array
1 2 3 4 5 6 7 8 9 10 11 | In this article, we will learn how to perform Bucket sort in C# Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort. Bucket sort works as follows: 1. Set up an array of initially empty “buckets”. 2. Scatter: Go over the original array, putting each object in its bucket. 3. Sort each non-empty bucket. 4. Gather: Visit the buckets in order and put all elements back into the original array |
C# program to perform Insertion Sort
In this example, we will learn how to perform Insertion sort in C#
The Insertion sort algorithm views the data in two halves.
The left half of sorted elements and the right half of elements to be sorted.
In each iteration, one element from the right half is taken and added to the left half so that the left half is still sorted.
Insertion sort is of order O(n2)
Insertion sort takes an element from the list and places it in the correct location in the list.
This process is repeated until there are no more unsorted items in the list.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { int[] arr = new int[5] { 83, 12, 3, 34, 60 }; int i; Console.WriteLine("The Array is :"); for (i = 0; i < 5; i++) { Console.WriteLine(arr[i]); } insertsort(arr, 5); Console.WriteLine("The Sorted Array is :"); for (i = 0; i < 5; i++) Console.WriteLine(arr[i]); Console.ReadLine(); } static void insertsort(int[] data, int n) { int i, j; for (i = 1; i < n; i++) { int item = data[i]; int ins = 0; for (j = i - 1; j >= 0 && ins != 1; ) { if (item < data[j]) { data[j + 1] = data[j]; j--; data[j + 1] = item; } else ins = 1; } } } } } |
Here is the output of the C# Program:
The Array is :
83
12
3
34
60
The Sorted Array is :
3
12
34
60
83
C# program to perform Selection sort
In this example, we will learn how to perform Selection sort in C#
Selection sort is an algorithm of sorting an array where it loop from the start of the loop, and check through other elements to find the minimum value. After the end of the first iteration, the minimum value is swapped with the current element. The iteration then continues from the 2nd element and so on.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | /* * C# Program to Perform a Selection Sort */ using System; class Program { static void Main(string[] args) { int array_size = 10; int[] array = new int[10] { 100, 50, 20, 40, 10, 60, 80, 70, 90, 30 }; Console.WriteLine("The Array Before Selection Sort is: "); for (int i = 0; i < array_size; i++) { Console.WriteLine(array[i]); } int tmp, min_key; for (int j = 0; j < array_size - 1; j++) { min_key = j; for (int k = j + 1; k < array_size; k++) { if (array[k] < array[min_key]) { min_key = k; } } tmp = array[min_key]; array[min_key] = array[j]; array[j] = tmp; } Console.WriteLine("The Array After Selection Sort is: "); for (int i = 0; i < 10; i++) { Console.WriteLine(array[i]); } Console.ReadLine(); } } |
Here is the output of the C# Program:
The Array Before Selection Sort is :
100
50
20
40
10
60
80
70
90
30
The Array After Selection Sort is :
10
20
30
40
50
60
70
80
90
100
C# program to perform Bubble sort
In this example, we will learn how to perform bubble sort in C#
Bubble sort changes the postion of numbers or changing an unordered sequence into an ordered sequence.
Bubble sort follows a simple logic. It compares adjacent elements in a loop and swaps them if they are not in order.
Bubble sort is named this way because, in this sorting method, the smaller elements gradually bubble up to the top of the list.
Bubble sort has worst-case and average complexity both О(n2), where n is the number of items being sorted.
Let’s have a look at the implementation in C#.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | using System; class bubblesort { static void Main(string[] args) { int[] a = { 30, 20, 50, 40, 10 }; int t; Console.WriteLine("The Array is : "); for (int i = 0; i < a.Length; i++) { Console.WriteLine(a[i]); } for (int j = 0; j <= a.Length - 2; j++) { for (int i = 0; i <= a.Length - 2; i++) { if (a[i] > a[i + 1]) { t = a[i + 1]; a[i + 1] = a[i]; a[i] = t; } } } Console.WriteLine("The Sorted Array :"); foreach (int aray in a) Console.Write(aray + " "); Console.ReadLine(); } } |
Here is the output of the C# Program:
The Array is :
30
20
50
40
10
The Sorted Array :
10
20
30
40
50
C# program to merge two sorted arrays into one
In this example, we will write a C# program to merge two sorted arrays into one
This is a frequently asked interview question.
Let’s look at the below C# implementation of this algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace CodingAlgorithms { //You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order. //Source: Cracking the Coding Interview 5th Edition p. 121 public static class MergeSortedArrays { //x array is assumed to be the length of x + y, and lastX is the position of the last stored element in x array public static int[] MergeArrays(int[] x, int[] y, int lastX) { int xIndex = lastX; int yIndex = y.Length - 1; int mergeIndex = x.Length - 1; while (yIndex >= 0) { if (y[yIndex] > x[xIndex]) { x[mergeIndex] = y[yIndex]; yIndex--; } else if (y[yIndex] < x[xIndex]) { x[mergeIndex] = x[xIndex]; xIndex--; } mergeIndex--; } return x; } } } |
C# program to find min and max in binary search tree
In this example, we will write a C# program to find min and max in binary search tree
The smallest value in a BST will always be found at the last left child node of a subtree beginning with the left child of the root node. On the other hand, the largest value in a BST is found at the last right child node of a subtree beginning with the right child of the root node.
This is a frequently asked interview question.
Let’s look at the below C# implementation of this algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace CodingAlgorithms { //Write a method to get the min from a binary tree //Write a method to get the max from a binary tree partial class BinarySearchTree { //Returns the data in the farthest left node public int GetMin(NodeBT root) { NodeBT cur = root; while (cur.Left != null) cur = cur.Left; return cur.Data; } //Returns the data in the farthest right node public int GetMax(NodeBT root) { NodeBT cur = root; while (cur.Right != null) cur = cur.Right; return cur.Data; } ////Run in Program.cs to test //BinarySearchTree bst = new BinarySearchTree(); //bst.Add(5); //bst.Add(10); //bst.Add(15); //bst.Add(-7); //bst.Add(2); //bst.Add(26); //bst.Add(98); //Console.WriteLine(bst.GetMin(bst.Root)); //Console.WriteLine(bst.GetMax(bst.Root)); } } |
C# program to check password
In this example, we will write a C# program to check password
This is a frequently asked interview question.
Let’s look at the below C# implementation of this algorithm.
The password should have:
1. min 6 char and max 12 char
2. No two similar chars consecutively
3. 1 lower case
4. 1 upper case
5. 1 special char
6. No white space
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace CodingPuzzles { //Write password checker method - must contain min 6 char and max 12 char, //No two similar chars consecutively, 1 lower case, 1 upper case, 1 special char, no white space public static class PasswordChecker { public static bool CheckPassword(string pass) { //min 6 chars, max 12 chars if (pass.Length < 6 || pass.Length > 12) return false; //No white space if (pass.Contains(" ")) return false; //At least 1 upper case letter if (!pass.Any(char.IsUpper)) return false; //At least 1 lower case letter if (!pass.Any(char.IsLower)) return false; //No two similar chars consecutively for (int i = 0; i < pass.Length - 1; i++) { if (pass[i] == pass[i + 1]) return false; } //At least 1 special char string specialCharacters = @"%!@#$%^&*()?/>.<,:;'\|}]{[_~`+=-" + "\""; char[] specialCharactersArray = specialCharacters.ToCharArray(); foreach (char c in specialCharactersArray) { if (pass.Contains(c)) return true; } return false; } } } |
C# program to remove duplicates from a sorted linked list
In this example, we will discuss how to remove duplicates from a sorted linked list
This is a frequently asked interview question.
Let’s look at the below C# implementation of this algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace LinkedListAlgorithm { partial class LinkedListStack { //Remove duplicates from a sorted linked list (Assumes nodes contain integers as data) //Source: https://leetcode.com/problems/remove-duplicates-from-sorted-list/ public void RemoveDuplicates() { Node lag = head; Node lead = head.Next; while (lead != null) { if ((int)lag.Data == (int)lead.Data) { lag.Next = lead.Next; lead = lag.Next; } else { lag = lag.Next; lead = lead.Next; } } } //LinkedListStack list = new LinkedListStack(); //list.Push(1); //list.Push(1); //list.Push(2); //list.Push(2); //list.Push(3); //list.Push(3); //list.RemoveDuplicates(); //Console.WriteLine(list.Pop()); //Console.WriteLine(list.Pop()); //Console.WriteLine(list.Pop()); } } |
C# program to find nth to last element of a singly linked list
In this example, we will discuss how to find nth to last element of a singly linked list.
This is a frequently asked interview question.
Let’s look at the below C# implementation of this algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace LinkedListAlgorithms { partial class LinkedListStack { //Find nth to last element of a singly linked list implemented as a stack //1 returns the last object in the linked list public object FindNToLast(int x) { if (head == null) throw new Exception("Empty linked list"); if (x < 1) throw new Exception("Index out of range"); Node lag = head; Node lead = head; //Move the lead pointer up (x-1 positions) while leaving the lag pointer behind for (int i = 1; i < x; i++) lead = lead.Next; //Move the lag and lead pointers up one at a time until the lead is at the end of the list while (lead.Next != null) { lag = lag.Next; lead = lead.Next; } return lag.Data; } } } |
C# program to reverse a string
In this article, we will learn how to reverse a string.
This is a frequently asked interview question.
Let’s look at the below C# implementation of this algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace CodingAlgorithms { //Reverse a string public static class ReverseString { public static string Reverse(string x) { string result = ""; for (int i = x.Length - 1; i >= 0; i--) result += x[i]; return result; } } } |
C# program to Count number of words in a string
In this article, we will learn how to count number of words in a string.
This is a frequently asked interview question. Let’s look at the below C# implementation of this algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace CodingAlgorithms { //Count the number of words in a string (Needs to handle multiple spaces between words) public static class WordCount { public static int Count(string x) { int result = 0; //Trim whitespace from beginning and end of string x = x.Trim(); //Necessary because foreach will execute once with empty string returning 1 if (x == "") return 0; //Ensure there is only one space between each word in the passed string while (x.Contains(" ")) x = x.Replace(" ", " "); //Count the words foreach (string y in x.Split(' ')) result++; return result; } } } |
C# program to Reverse words in a string
In this example, we will learn the c# program on how to reverse words in a string?
This is a frequently asked interview question. Let’s look at the below C# implementation of this algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | using System; using System.Collections; //Stack using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace CodingAlgorithms { public static class ReverseWords { //Reverse words in a string public static string Reverse(string s) { string result = ""; Stack temp = new Stack(); s = s.Trim(); //Remove extra white space between characters while (s.Contains(" ")) s = s.Replace(" ", " "); //Store each word on the Stack foreach (string x in s.Split(' ')) temp.Push(x); //Add each word to the result string in reverse order since a stack is a FIFO data structure while (temp.Count != 0) result += temp.Pop() + " "; return result.Trim(); } } } |
C# program to accept two integers and return remainder
In this example, we will discuss how to accept two integers in a C# program and return remainder back.
This is a frequently asked interview question. Let’s look at the below C# implementation of this algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace CodingAlgorithm { //Write a function that accepts two integers and returns the remainder //Source: Ace Programming Interview p. 349 //Need to handle System.DivideByZeroException //Need to handle case where the dividend (x) is less than the divisor (y) public class ReturnRemainder { public static int GetRemainder(int x, int y) { if (y == 0) throw new Exception("Can not divide by zero"); if (x < y) throw new Exception("Number being divided (dividend) can not be less than the divisor"); else return (x % y); } } } |
C# program to Determine if a string has all unique characters
In this example, we will discuss how to determine if a string has all unique characters.
This is a frequently asked interview question. Let’s look at the below C# implementation of this algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace CodingAlgorithms { //Implement an algorithm to determine if a string has all unique characters. //What if you cannot use additional data structures? //Source: Cracking the Coding Interview p. 73 //Uses a dictionary to store each character and checks for a duplicate entry public static class UniqueString { public static bool IsUnique(string s) { Dictionary<char, int> d = new Dictionary<char, int>(); foreach (char c in s) { if (d.ContainsKey(c)) return false; else d.Add(c, 1); } return true; } //Compares each character to every other character without using an additional data structure //O(n^2) time complexity public static bool IsUnique1(string s) { string temp1 = ""; string temp2 = ""; for (int i = 0; i < s.Length; i++) { temp1 = s.Substring(i, 1); for (int k = 0; k < s.Length; k++) { temp2 = s.Substring(k, 1); if ((temp1 == temp2) && (i != k)) return false; } } return true; } } } |
C# program to find sum of digits of a number using Recursion
In this article, we will discuss how to find sum of digits of a number using Recursion.
This is a frequently asked interview question.
Lets have a look at the implementation in C#.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | using System; class program { public static void Main() { int num, result; pro pg = new pro(); Console.WriteLine("Enter the Number : "); num=int.Parse(Console.ReadLine()); result =pg.sum(num); Console.WriteLine("Sum of Digits in {0} is {1}", num, result); Console.ReadLine(); } } class pro { public int sum(int num) { if (num != 0) { return (num % 10 + sum(num / 10)); } else { return 0; } } } |
C# program to find node in Linked List
In this example, we will learn how to find a node in Linked List.
This is a frequently asked interview question.
Lets have a look at the implementation in C#.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | using System; using System.Collections.Generic; class Program { static void Main() { // // Create a new linked list. // LinkedList<string> linked = new LinkedList<string>(); // // First add three elements to the linked list. // linked.AddLast("A"); linked.AddLast("B"); linked.AddLast("C"); // // Insert a node before the second node (after the first node) // LinkedListNode<string> node = linked.Find("A"); linked.AddAfter(node, "inserted"); // // Loop through the linked list. // foreach (var value in linked) { Console.WriteLine(value); } } } |
Find missing number in a sequence in C#
In this example, we will learn different ways to find missing number in a sequence in C#.
This is a frequently asked interview question. Let’s look at the below C# code.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | public static IEnumerable SequenceFindMissings(this IList sequence) { var missing = new List(); if ((sequence != null) && (sequence.Any())) { sequence.Aggregate((seed, aggr) => { var diff = (aggr - seed) - 1; if (diff > 0) missing.AddRange(Enumerable.Range((aggr - diff), diff)); return aggr; }); } return missing; } |
Quickway:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | public static bool IsSequenceBroken(this IEnumerable sequence) { bool broken = false; if (sequence != null) { var sequenceAsList = sequence.ToList(); if (sequenceAsList.Any()) { int lastValue = sequence.First(); broken = sequence.Any(value => { if ((value - lastValue) > 1) return true; lastValue = value; return false; }); } } return broken; } |
Reverse Linked List in C#
In this article, we will learn how to reverse a linked list in C#.
in this article, we will see 2 ways of doing it.
- Create a new linked list and insert all elements from 1st linked list in reverse order
- Swapping starts from the first node’s object and the first node’s object is swapped with the last node’s object
- Assuming we have N nodes in the link list:
- Swap: 1st node’s object with Nth node’s object
- Swap: 2nd node’s object with (N-1)th node’s object
- Swap: 3rd node’s object with (N-2)th node’s object
Way 1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | public void ReverseLinkedList (LinkedList linkedList) { // ------------------------------------------------------------ // Create a new linked list and add all items of given // linked list to the copy linked list in reverse order // ------------------------------------------------------------ LinkedList copyList = new LinkedList(); // ------------------------------------------------------------ // Start from the latest node // ------------------------------------------------------------ LinkedListNode start = linkedList.Tail; // ------------------------------------------------------------ // Traverse until the first node is found // ------------------------------------------------------------ while (start != null) { // ------------------------------------------------------------ // Add item to the new link list // ------------------------------------------------------------ copyList.Add (start.Item); start = start.Previous; } linkedList = copyList; } |
Way 2:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | public void ReverseLinkedList (LinkedList linkedList) { // ------------------------------------------------------------ // Create variables used in the swapping algorithm // ------------------------------------------------------------ LinkedListNode firstNode; // This node will be the first node in the swapping LinkedListNode secondNode; // This node will be the second node in the swapping int numberOfRun; // This variable will be used to determine the number of swapping runs // ------------------------------------------------------------ // Find the tail of the linked list // ------------------------------------------------------------ // Assume that our linked list doesn’t have a property to find the tail of it. // In this case, to find the tail, we need to traverse through each node. // This variable is used to find the tail of the linked list LinkedListNode tail = linkedList.Head; // Start from first link list node // and go all the way to the end while (tail.Next != null) tail = tail.Next; // ------------------------------------------------------------ // Assign variables // ------------------------------------------------------------ firstNode = linkedList.Head; secondNode = tail; numberOfRun = linkedList.Length / 2; // Division will always be integer since the numberOfRun variable is an integer // ------------------------------------------------------------ // Swap node’s objects // ------------------------------------------------------------ object tempObject; // This will be used in the swapping 2 objects for (int i=0; i < numberOfRun; i++) { // Swap the objects by using a 3rd temporary variable tempObject = firstNode.Item; firstNode.Item = secondNode.Item; secondNode.Item = tempObject; // Hop to the next node from the beginning and previous node from the end firstNode = firstNode.Next; secondNode = secondNode.Previous; } } |
Binary search in C#
In this example, we will write a C# program to perform Binary search in C#
Using Recursion:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | public static object BinarySearchRecursive(int [] inputArray, int key, int min, int max) { if (min > max) { return "Nil"; } else { int mid = (min+max)/2; if (key == inputArray [mid]) { return ++mid; } else if (key < inputArray [mid]) { return BinarySearchRecursive(inputArray, key, min, mid - 1); } else { return BinarySearchRecursive(inputArray, key, mid + 1, max); } } } |
Binary Search without Recursion (Iterative):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | public static object BinarySearchIterative(int[] inputArray, int key, int min, int max) { while (min <=max) { int mid = (min + max) / 2; if (key == inputArray[mid]) { return ++mid; } else if (key < inputArray[mid]) { max = mid - 1; } else { min = mid + 1; } } return "Nil"; } |
C# Program to Reverse a Number & Check if it is a Palindrome
In this article, we will write a C# program to reverse a number and check if it is palindrome or not.
Here First it reverses a number. Then it checks if given number and reversed numbers are equal. If they are equal, then its a palindrome.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | using System; class program { public static void Main() { int num, temp, remainder, reverse = 0; Console.WriteLine("Enter an integer \n"); num = int.Parse(Console.ReadLine()); temp = num; while (num > 0) { remainder = num % 10; reverse = reverse * 10 + remainder; num /= 10; } Console.WriteLine("Given number is = {0}", temp); Console.WriteLine("Its reverse is = {0}", reverse); if (temp == reverse) Console.WriteLine("Number is a palindrome \n"); else Console.WriteLine("Number is not a palindrome \n"); Console.ReadLine(); } } |
Output
Enter an integer
636
Given number is = 636
Its reverse is = 636
Number is a palindrome
C# program to Sort an array in descending order
In this article, we will learn how to sort an array in descending order
For doing it, first we need to sort the array and then reverse it. It will give us the expected result.
Lets have a look at the implementation.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace CodingAlgorithms { //Write a method to sort the elements of an array in descending order public static class SortDesc { public static void Sort(int[] x) { Array.Sort(x); Array.Reverse(x); } } } |
C# program to implement Binary Search Tree
In this article, we will learn how to implement Binary Search Tree (BST) in C# and how to insert a node in BST
This is an important interview question.
A binary tree is defined as a tree where each node can have no more than two children. By limiting the number of children to 2, we can write efficient programs for inserting data, deleting data, and searching for data in a binary tree.
Once we’re inside the BST, the next step is to determine where to put the new node.This is performed inside a while loop that we break once we’ve found the correct position for the new node. The algorithm for determining the proper position for a node is as follows:
1. Set the parent node to be the current node, which is the root node.
2. If the data value in the new node is less than the data value in the current node, set the current node to be the left child of the current node. If the data value in the new node is greater than the data value in the current node, skip to Step 4.
3. If the value of the left child of the current node is null, insert the new node here and exit the loop. Otherwise, skip to the next iteration of the While loop.
4. Set the current node to the right child node of the current node.
5. If the value of the right child of the current node is null, insert the new node here and exit the loop. Otherwise, skip to the next iteration of the While loop
Let’s have a look at the implementation in C#.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Diagnostics; using System.Collections; namespace BinarySearchTree { public class BinarySearchTree { public class Node { public int Data; public Node Left; public Node Right; public void DisplayNode() { Console.Write(Data + " "); } } public Node root; public BinarySearchTree() { root = null; } public void Insert(int i) { Node newNode = new Node(); newNode.Data = i; if (root == null) root = newNode; else { Node current = root; Node parent; while (true) { parent = current; if (i < current.Data) { current = current.Left; if (current == null) { parent.Left = newNode; break; } else { current = current.Right; if (current == null) { parent.Right = newNode; break; } } } } } } static void Main() { BinarySearchTree nums = new BinarySearchTree(); nums.Insert(50); nums.Insert(17); nums.Insert(23); nums.Insert(12); nums.Insert(19); nums.Insert(54); nums.Insert(9); nums.Insert(14); nums.Insert(67); nums.Insert(76); nums.Insert(72); } } } |
C# program to determine total ways stairs can be climbed
In this article, we will see, Given N steps to climb to reach a floor, a person can take 1 or 2 step at a time to climb. Find the number of ways to reach nth step?
This is a frequently asked interview question. Let’s have a look at the implementation.
There are 2 ways of doing it.
1. Recursive way
2.Iterative way
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace CodingAlgorithms { public static class ClimbingStairs { //A child is running up a staircase with n steps, and can hop either 1, 2, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs. //Source: Cracking the Coding Interview p. 109 //Answer will overflow integer datatype(over 4 billion) at 37 steps //Recursive solution public static int CombosRecursive(int numStairs) { if (numStairs > 36) throw new Exception("Int overflow"); if (numStairs <= 0) return 0; if (numStairs == 1) return 1; if (numStairs == 2) return 2; if (numStairs == 3) return 4; return CombosRecursive(numStairs - 1) + CombosRecursive(numStairs - 2) + CombosRecursive(numStairs - 3); } //Iterative solution with caching public static int CombosIterative(int numStairs) { if (numStairs > 36) throw new Exception("Int overflow"); if (numStairs <= 0) return 0; if (numStairs == 1) return 1; if (numStairs == 2) return 2; if (numStairs == 3) return 4; int[] prev = { 1, 2, 4 }; //We only start caching results if numStairs is more than 3 int current = 3; while (current < numStairs) { int preTotal = prev[0] + prev[1] + prev[2]; prev[0] = prev[1]; prev[1] = prev[2]; prev[2] = preTotal; current++; } return prev[2]; } } } |
C# program to Rotate array to the right given a pivot
In this article, we will learn how to rotate an array to the right given a pivot
.Let’s have a look at the implementation in C#. This is a very important interview question.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace CodingAlgorithm { public static class RotateArrayRight { //Rotate array to the right of a given pivot public static int[] Rotate(int[] x, int pivot) { if (pivot < 0 || x == null) throw new Exception("Invalid argument"); pivot = pivot % x.Length; //Rotate first half x = RotateSub(x, 0, pivot - 1); //Rotate second half x = RotateSub(x, pivot, x.Length - 1); //Rotate all x = RotateSub(x, 0, x.Length - 1); return x; } private static int[] RotateSub(int[] x, int start, int end) { while (start < end) { int temp = x[start]; x[start] = x[end]; x[end] = temp; start++; end--; } return x; } } } |
C# program to determine if any two integers in array sum to given integer
In this article, we will learn how to determine if two integers in array sum to given integer
This is a frequently asked interview question.
Let’s have a look at the implementation.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace CodingAlgorithm { //Given an integer and an array of integers determine whether any two integers in the array sum to that integer. public static class TargetSum { //Brute force solution, O(n^2) time complexity public static bool TwoIntegersSumToTarget(int[] arr, int target) { for (int i = 0; i < arr.Length; i++) { for (int k = 0; k < arr.Length; k++) { if (i != k) { int sum = arr[i] + arr[k]; if (sum == target) return true; } } } return false; } } } |
C# program to move zeros to end of array
In this example, we will learn the C# implementation of moving zeros to end of an array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace CodingPuzzles { //Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements. //For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0]. //Note: //You must do this in-place without making a copy of the array. //Minimize the total number of operations. //Source: https://leetcode.com/problems/move-zeroes/ public static class MoveZeros { public static void Move(params int[] x) { for (int i = 0; i < x.Length; i++) { if (x[i] == 0) MoveZeroToEnd(x, i); } } private static void MoveZeroToEnd(int[] x, int index) { for (int i = index; i < x.Length - 1; i++) { int temp = x[i]; x[i] = x[i + 1]; x[i + 1] = temp; } } } } |
C# program to Swap min and max element in integer array
In this example, we will learn how to swap min and max element in integer array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace CodingPuzzles { //Write a method to swap the min and max element in an integer array //Source: Cracking Coding Interview p. 58 public static class MinMaxArraySwap { public static void MinMaxSwap(int[] input) { if (input.Length == 0) return; int maxPos = 0; int minPos = 0; int valMax = 0; int valMin = 0; for (int i = 1; i < input.Length; i++) { if (input[maxPos] < input[i]) maxPos = i; if (input[minPos] > input[i]) minPos = i; } valMax = input[maxPos]; valMin = input[minPos]; input[maxPos] = valMin; input[minPos] = valMax; } //Cleaner implementation public static void MinMaxSwap2(int[] x) { int min = 0; int max = 0; for (int i = 1; i < x.Length; i++) { if (x[min] > x[i]) min = i; if (x[max] < x[i]) max = i; } int temp = x[min]; x[min] = x[max]; x[max] = temp; } } } |
C# program to find if an array contains duplicate
In this example, we will learn if an array contains duplicate then how to find it in C#.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace CodingAlgorithms { //Given an array of integers, find if the array contains any duplicates. //Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct. public static class ArrayDuplicates { //Dictionary solution public static bool ContainsDuplicates(params int[] x) { Dictionary<int, int> d = new Dictionary<int, int>(); foreach (int i in x) { if (d.ContainsKey(i)) return true; else d.Add(i, 1); } return false; } } } |
C# program to implement FizzBuzz
In this example, we will learn a simple math algorithm where the program prints from 1 to 100 and for multiples of 3, it prints Fizz and for multiples of five it prints Buzz instead of numbers. For numbers which are multiples of both 3 and 5, it prints FizzBuzz.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace CodingPuzzles { public static class FizzBuzz { public static string GetFizzBuzz() { string fbString = ""; for (int i = 1; i < 101; i++) { if ((i % 3 == 0) && (i % 5 == 0)) fbString += "FizzBuzz" + Environment.NewLine; else if (i % 3 == 0) fbString += "Fizz" + Environment.NewLine; else if (i % 5 == 0) fbString += "Buzz" + Environment.NewLine; else fbString += i.ToString() + Environment.NewLine; } return fbString; } ////Call this in Program.cs to test //Console.WriteLine(FizzBuzz.GetFizzBuzz()); } } |
C# program to reverse a stack
In this example, we will learn how to reverse a stack.
This is an important interview question.
Let’s have a look at the implementation in C#.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Collections; //Necessary for Stack namespace CodingPuzzles { //Reverse a stack public static class ReverseStack { //This method returns a stack public static Stack Reverse(Stack input) { //Declare another stack to store the values from the passed stack Stack temp = new Stack(); //While the passed stack isn't empty, pop elements from the passed stack onto the temp stack while (input.Count != 0) temp.Push(input.Pop()); return temp; } } } |
