Tree Traversals For Strongly-Typed Generic Trees (C# Solution)
Copyright (2008) Ahmed Arsalan. All Rights Rserved.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace TreeTraversals
{
class TreeTraversalsLauncher
{
static void Main(string[] args)
{
TreeTraversals treeTraversal = new TreeTraversals();
Console.WriteLine("The tree has been initialized to:");
foreach (TreeNode node in treeTraversal.Tree)
{
Console.Write(node.NodeValue.ToString() + " ");
}
Console.WriteLine();
treeTraversal.Traversed.Clear();
treeTraversal.InOrderTraversal(treeTraversal.Root);
Console.WriteLine("In Order traversal processes nodes in the following order:");
foreach (int node in treeTraversal.Traversed)
{
Console.Write(node.ToString() + " ");
}
Console.WriteLine();
treeTraversal.Traversed.Clear();
treeTraversal.PreOrderTraversal(treeTraversal.Root);
Console.WriteLine("Pre Order traversal processes nodes in the following order:");
foreach (int node in treeTraversal.Traversed)
{
Console.Write(node.ToString() + " ");
}
Console.WriteLine();
treeTraversal.Traversed.Clear();
treeTraversal.PostOrderTraversal(treeTraversal.Root);
Console.WriteLine("Post Order traversal processes nodes in the following order:");
foreach (int node in treeTraversal.Traversed)
{
Console.Write(node.ToString() + " ");
}
Console.ReadKey();
}
}
public class TreeNode
{
#region ----- Private Data Members -----
private T nodeValue;
private TreeNode left;
private TreeNode right;
#endregion
#region ----- Public Properties -----
public T NodeValue
{
get
{
return this.nodeValue;
}
set
{
this.nodeValue = value;
}
}
public TreeNode Left
{
get
{
return this.left;
}
set
{
this.left = value;
}
}
public TreeNode Right
{
get
{
return this.right;
}
set
{
this.right = value;
}
}
#endregion
}
public class TreeTraversals
{
#region ----- Constructors -----
public TreeTraversals()
{
root = new TreeNode();
tree = new List<treenode>();
traversed = new List();
PopulateInitialTree();
}
#endregion
#region ----- Private Data Members -----
private TreeNode root;
private List < TreeNode < int > > tree;
private List traversed;
#endregion
#region ----- Public Properties -----
public TreeNode Root
{
get
{
return this.root;
}
}
public List Traversed
{
get
{
return this.traversed;
}
}
public List < TreeNode < int > > Tree >
{
get
{
return this.tree;
}
}
#endregion
#region ----- Private Methods -----
private void PopulateInitialTree()
{
TreeNode node8 = new TreeNode();
node8.NodeValue = 99;
node8.Left = null;
node8.Right = null;
TreeNode node7 = new TreeNode();
node7.NodeValue = 62;
node7.Left = null;
node7.Right = null;
TreeNode node6 = new TreeNode();
node6.NodeValue = 4;
node6.Left = node7;
node6.Right = node8;
TreeNode node5 = new TreeNode();
node5.NodeValue = 100;
node5.Left = null;
node5.Right = null;
TreeNode node4 = new TreeNode();
node4.NodeValue = 68;
node4.Left = null;
node4.Right = null;
TreeNode node3 = new TreeNode();
node3.NodeValue = 151;
node3.Left = null;
node3.Right = node5;
TreeNode node2 = new TreeNode();
node2.NodeValue = 10;
node2.Left = node4;
node2.Right = null;
TreeNode node1 = new TreeNode();
node1.NodeValue = 6;
node1.Left = node2;
node1.Right = node3;
root.NodeValue = 5;
root.Left = node1;
root.Right = node6;
this.tree.Add(root);
this.tree.Add(node1);
this.tree.Add(node2);
this.tree.Add(node3);
this.tree.Add(node4);
this.tree.Add(node5);
this.tree.Add(node6);
this.tree.Add(node7);
this.tree.Add(node8);
}
#endregion
#region ----- Public Methods -----
public void InOrderTraversal(TreeNode root)
{
if (root == null) return;
InOrderTraversal(root.Left);
Traversed.Add(root.NodeValue);
InOrderTraversal(root.Right);
}
public void PreOrderTraversal(TreeNode root)
{
if (root == null) return;
Traversed.Add(root.NodeValue);
PreOrderTraversal(root.Left);
PreOrderTraversal(root.Right);
}
public void PostOrderTraversal(TreeNode root)
{
if (root == null) return;
PostOrderTraversal(root.Right);
Traversed.Add(root.NodeValue);
PostOrderTraversal(root.Left);
}
#endregion
}
}
}
Count prime numbers in a range (C# Solution)
Problem: Given a range of integers, count the number of primes. Also list the prime numbers in the range.
using System;
namespace SolvingSmallProblems
{
public class Program
{
static void Main(string[] args)
{
int defaultLowNum = 1;
int defaultHighNum = 50;
int lowNum, highNum;
PrimeNumberPuzzles prime = new PrimeNumberPuzzles();
Console.WriteLine("PRIME NUMBER COUNT PROGRAM");
Console.WriteLine();
Console.WriteLine("Please enter start number");
try
{
lowNum =
Convert.ToInt32(Console.ReadLine());
}
catch (Exception)
{
lowNum = defaultLowNum;
}
Console.WriteLine("Please enter end number");
try
{
highNum = Convert.ToInt32(Console.ReadLine());
}
catch (Exception)
{
highNum = defaultHighNum;
}
if (lowNum < 1)
{
lowNum = defaultLowNum;
}
if (highNum < lowNum)
{
highNum = defaultHighNum;
}
int totalPrimes = prime.CountPrimes(lowNum, highNum);
Console.WriteLine();
Console.WriteLine("Total number of prime numers between " +
lowNum.ToString() + " and " + highNum.ToString() +
" is " + totalPrimes + ".");
Console.ReadKey();
}
}
public class PrimeNumberPuzzles
{
public int CountPrimes(int low, int high)
{
int count = 0;
for (int num = low; num <= high; num++)
{
if (IsPrime(num))
{
Console.Write(num + " ");
count++;
}
}
return count;
}
bool IsPrime(int num)
{
bool isNumPrime = true;
if ((num == 1) || (num == 2))
{
return true;
}
else if (num < 1)
{
throw new Exception("Invalid number!");
}
else
{
int remainder;
for (int test = 2; test < num - 1; test++)
{
remainder = num % test;
if (remainder == 0)
{
isNumPrime = false;
}
}
return isNumPrime;
}
}
}
}
String Problems: Reverse A String and Remove Characters From A String (C# Solution)
Problem 1 Description: Reverse a string such that “a cat has paws” becomes “paws has cat a”.
Problem 2 Description: Remove a set of characters from a given string.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace StringManipulationProblems
{
class Program
{
const string DEFAULT_COMMAND = "ReverseString";
const string DEFAULT_ARGUMENT_1 = "messages that have been in Spam more than 30 days will be automatically deleted";
const string DEFAULT_ARGUMENT_2 = "aioeu";
static void Main(string[] args)
{
string commandName;
string commandArg1;
string commandArg2;
if (args.Length < 1)
{
commandName = DEFAULT_COMMAND;
commandArg1 = DEFAULT_ARGUMENT_1;
commandArg2 = DEFAULT_ARGUMENT_2;
}
else if (args.Length == 1)
{
commandName = args[0];
commandArg1 = DEFAULT_ARGUMENT_1;
commandArg2 = "aioeu";
}
else if (args.Length == 2)
{
commandName = args[0];
commandArg1 = args[1];
commandArg2 = "aioeu";
}
else
{
commandName = args[0];
commandArg1 = args[1];
commandArg2 = args[2];
}
string result = String.Empty;
StringPuzzles puzzles = new StringPuzzles();
switch (commandName)
{
case "ReverseString":
if (commandArg1.Equals(DEFAULT_ARGUMENT_1))
{
Console.Out.Write("No string argument provided. Using default string: ");
Console.WriteLine(DEFAULT_ARGUMENT_1);
}
Console.Out.WriteLine("About to call method " + commandName);
result = puzzles.ReverseString(commandArg1);
break;
case "RemoveChars":
if (commandArg1.Equals(DEFAULT_ARGUMENT_1))
{
Console.Out.Write("No string argument provided. Using default string: ");
Console.WriteLine(DEFAULT_ARGUMENT_1);
}
Console.Out.WriteLine("About to call method " + commandName);
result = puzzles.RemoveChars(commandArg1, commandArg2);
break;
default:
Console.Out.WriteLine("Incorrect command! Please try again.");
break;
}
Console.Out.WriteLine("The original string was:");
Console.Out.WriteLine(commandArg1);
Console.Out.WriteLine("The modified string is:");
Console.Out.WriteLine(result);
Console.Out.WriteLine("Please press ENTER to continue...");
Console.In.ReadLine();
}
}
class StringPuzzles
{
public string ReverseString(string inputString)
{
List<string> wordList;
StringBuilder reversedString = new StringBuilder();
wordList = new List<string>(inputString.Split(' '));
for (int i = wordList.Count - 1; i >= 0; i--)
{
reversedString.Append(wordList[i] + " ");
}
return reversedString.ToString();
}
public string RemoveChars(string str, string remove)
{
List<char> toDelete = new List</char><char>();
StringBuilder deletedStr = new StringBuilder();
// Create a list of characters to delete from string
toDelete.AddRange(remove.ToCharArray());
// Create string with specified characters removed
foreach (char c in str.ToCharArray())
{
if (!(toDelete.Contains(c)))
{
deletedStr.Append(c);
}
}
return deletedStr.ToString();
}
}
}
Simple zig-zag numeric spiral
I propose the following problem. Take the number of columns and a series of numbers between 10 and 99 as input and create a zig-zag pattern on console output. The output should be centered so that it fills an 80 char wide screen. For example,
prompt>ZigZag 3 12 45 78 48 34 67 90 23 72 67 34 56 17 32 88
will give the following output:
12
45
78
48
34
67
90
23
72
67
34
56
17
32
88
———————————————————————————
I will try to write C# code to solve this problem below within a day or two.
Adding rows and columns in a square matrix (C# Solution)
This is a variation to the problem/solution posted on Ali Abbas Rizvi’s blog. I wanted to allow the user to enter matrix size for each run and to get a view of a randomly generated matrix in addition to all the sums for rows and columns. I also wanted to create a design that would lend itself favorably to adding new functionality. As an example, two methods (AddAllRows and AddAllColumns) have been added to the SquareMatrix class.
// Problem: Given a matrix, add rows and columns
// Author: Ahmed Arsalan
// (c) 2008. Please cite source if used in your presentation.
using System;
using System.Linq;
using System.Text;
namespace SolvingSmallProblems
{
class Program
{
static void Main(string[] args)
{
SquareMatrix aMatrix;
int matrixSize;
Console.Out.WriteLine("Please enter matrix size (e.g. 10):");
try
{
matrixSize = Int32.Parse(Console.In.ReadLine().Trim());
}
catch (Exception)
{
Console.Out.WriteLine("Please entger a valid integer.");
throw new Exception("Invalid size entered!");
}
Console.Out.WriteLine("The randomly generated matrix looks like this:");
aMatrix = new SquareMatrix(matrixSize);
for (int underline = 0; underline < matrixSize; underline++)
{
Console.Out.Write("____");
}
aMatrix.Show();
Console.Out.WriteLine("Press ENTER to generate sums...");
Console.In.ReadLine();
// display sums
long [] rowSums = new long [matrixSize];
long [] columnSums = new long [matrixSize];
for (int rowOrColumn = 0; rowOrColumn < matrixSize; rowOrColumn++)
{
rowSums[rowOrColumn] = aMatrix.AddRow(rowOrColumn);
columnSums[rowOrColumn] = aMatrix.AddColumn(rowOrColumn);
Console.Out.WriteLine (String.Format ("The sum of row {0} is {1}, " +
"and the sum of column {2} is {3}. ", rowOrColumn,
rowSums[rowOrColumn], rowOrColumn, columnSums[rowOrColumn]));
}
Console.Out.WriteLine (String.Format ("The MAX of all rows is {0}, " +
"and the MAX of all columns is {1}", rowSums.Max(), columnSums.Max()));
Console.In.ReadLine();
}
}
class SquareMatrix
{
# region ------------------------ Instance Variables ------------------------
private const int DEFAULT_MATRIX_SIZE = 10;
int[,] matrix;
Random randomNumber;
int selectedMatrixSize;
#endregion
#region ------------------------ Constructors ------------------------
public SquareMatrix() :this(DEFAULT_MATRIX_SIZE)
{
// use default size
}
public SquareMatrix(int matrixSize)
{
randomNumber = new Random(99);
selectedMatrixSize = matrixSize;
matrix = new int[matrixSize, matrixSize];
for (int row = 0; row < matrixSize; row++)
{
for (int column = 0; column < matrixSize; column++)
{
try
{
matrix[row, column] = RandomNumber; // random # between 1 and 99
}
catch (Exception)
{
Console.out.WriteLine ("Error generating random number!");
throw new Exception ("Error generating random number.");
}
}
}
}
#endregion
# region ------------------------ Public Properties ------------------------
public int RandomNumber
{
get
{
return randomNumber.Next(1, 99);
}
}
#endregion
#region ------------------------ Public Methods ------------------------
public void Show()
{
for (int row = 0; row < selectedMatrixSize; row++);
for (int column = 0; column < selectedMatrixSize; column++)
{
Console.Out.Write(matrix[row, column]);
Console.Out.Write(" ");
}
Console.Out.WriteLine();
}
}
public long AddRow(int rowNumber)
{
long addedRow = 0;
for (int column = 0; column < selectedMatrixSize; column++)
{
addedRow += matrix[rowNumber, column];
}
return addedRow;
}
public long AddColumn(int columnNumber)
{
long addedColumn = 0;
for (int row = 0; row < selectedMatrixSize; row++)
{
addedColumn += matrix[row, columnNumber];
}
return addedColumn;
}
public long AddAllRows()
{
long addedAllRows = 0;
for (int row = 0; row < selectedMatrixSize; row++)
{
addedAllRows += AddRow(row);
}
return addedAllRows;
}
public long AddAllColumns()
{
long addedAllColumns = 0;
for (int column = 0; column < selectedMatrixSize; column++)
{
addedAllColumns += AddColumn(column);
}
return addedAllColumns;
}
#endregion
}
}
WordPress makes posting source code to your blog easy
When I decided to start a blog to post source code for small projects, I needed a blogging platform that would make posting source code with keyword highlights, line numbers, and proper indentation a snap. After a bit of search and general disappointment with blogging systems, I came across the wonderful feature in WordPress that let’s you post beautifully styled source code simply by enclosing the code inside the SourceCode tag! And that was all I had to do! Brilliant!
The only caveat I found so far is that the view seems fixed in width. So you have to choose a theme that gives you more space in the main text area. If a line in your code is longer than what the template allows, you will get a horizontal scroll bar. However, if you scroll right to see the overflowing code, you will notice that the alternating background color scheme does not apply there. Clearly a bug and a big disappointment. I hope some body at WordPress sees this post and removes that defect. This is still the best and easiest way to date to showcase your source code in a blog.
Here is the FAQ for WordPress.
Happy coding!
Time Math Interview Problem (C# Solution)
This is a solution for the problem posted by Ali Abbas Rizvi here. Command line arguments are method name (e.g. AddMinutes), start time (e.g. 9:24AM), and minutes to add (e.g. 18). The result will be the new time after addminutes in the same time format.
using System;
using System.Text.RegularExpressions;
using System.Collections.Specialized;
namespace SolvingSmallProblems
{
class Program
{
static void Main(string[] args)
{
TimeConversions timeConv = new TimeConversions();
string commandName;
string baseTime;
string incrementalTime;
string output;
if (args.GetLength(0) == 3)
{
commandName = args[0];
baseTime = args[1];
incrementalTime = args[2];
switch (commandName.ToUpper())
{
case ("ADDMINUTES"):
output = timeConv.AddMinutes(baseTime, Int32.Parse(incrementalTime));
Console.Out.WriteLine(output);
Console.Out.Flush();
break;
}
}
else
{
throw new Exception("Incorrect number of arguments: 2 expected...");
}
}
}
class TimeConversions
{
private StringCollection meridiemValidValues;
public StringCollection methodsAvailable;
public TimeConversions()
{
meridiemValidValues = new StringCollection();
meridiemValidValues.Add("AM");
meridiemValidValues.Add("PM");
methodsAvailable = new StringCollection();
methodsAvailable.Add("AddMinutes");
}
public string AddMinutes(string time, int minutesToAdd)
{
long convertedTime = ConvertTimeToMinutes(time);
string finalTime = ConvertMinutesToTime(convertedTime + minutesToAdd);
return finalTime;
}
private string ConvertMinutesToTime(long minutes)
{
long calculatingHours;
long calculatingMinutes;
string calculatingMeridiem;
calculatingMinutes = minutes % 60;
// Rolling over hours for a 24-hour clock
calculatingHours = (minutes / 60) % 24;
if (calculatingHours < 12)
{
calculatingMeridiem = "AM";
// 0 am should be written as 12 am
if (calculatingHours == 0)
{
calculatingHours = 12;
}
}
else
{
calculatingMeridiem = "PM";
calculatingHours -= 12;
}
return calculatingHours.ToString() + ":" + calculatingMinutes.ToString().PadLeft(2, '0') +
" " + calculatingMeridiem;
}
private long ConvertTimeToMinutes(string time)
{
long normalizedTime;
string regexStringForTimeConversion = @"^(?<Hours>[\d]{1,2}):(?<minutes>\d\d)[\s]?(?<meridiem>[AP]M)$";
Regex regexForTimeConversion = new Regex(regexStringForTimeConversion);
Match matchedTime = regexForTimeConversion.Match(time);
int hours, minutes;
string meridiem;
try
{
hours = Int32.Parse(matchedTime.Groups["Hours"].Value);
}
catch (Exception)
{
throw new Exception("Invalid characters in Hours!");
}
try
{
minutes = Int32.Parse(matchedTime.Groups["Minutes"].Value);
}
catch (Exception)
{
throw new Exception("Invalid characters in Minutes!");
}
if (meridiemValidValues.Contains( matchedTime.Groups["Meridiem"].Value))
{
meridiem = matchedTime.Groups["Meridiem"].Value;
}
else
{
throw new Exception("Invalid characters in Meridiem!");
}
// Rule: 12 PM will be 12 in a 24-hour clock, 12 AM will be 0
if ((hours == 12) && (meridiem == "AM"))
{
hours = 0;
}
else if ((hours < 12) && (meridiem == "PM"))
{
hours += 12;
}
normalizedTime = (hours * 60) + minutes;
return normalizedTime;
}
}
}
