dboyle

Languages I have learned

2013-04-17T14:25:00Z

Ok, that should more accurately read “used” or even “abused" - as most of these have only enterd my domain when required by a job or college course. However some have been a major part of life over a much longer periods - C++, C# and of course SQL (in some flavour) have featured heavily over the last couple of decades.

So I had the idea to write down the full list. This is just an exercise in nostalgia, not a critique or comparison. I just got to thinking about some of the languages I have used or even seen at their peak, which are now mostly forgotten – at least by me. This list will be fairly chronological, as that should help me to remember most of them.

BASIC

Didn’t we all start with this? I did have some limited and infrequent exposure to Commodore 64’s and the like in the mid-80’s but did not really get the bug until the seminal moment in 1989 when I first attended the Crawley College of Technology (now the Central Sussex College) part-time BASIC programming course. That short (c30 hours over a couple of months) course actually landed me a job with a company called N.E.T. (now Sonus) configuring IDNX network topologies, and occasionally remoting into live installations to change config values using Unix shell scripts.

Turbo Pascal

I have fond memories of a fairly powerful tool which just needed Tp.exe (on a 3.5in floppy) and an editor.

RPG III

Not so fond memories of report design with this one

Lisp

Find the mis-matched bracket – that that's what I mainly remember from using this 20 years ago

Dbase IV/Clipper

Used to develop my first commercial code, a database system for a local company which had revolutionary pop-up “windows”.

CoBOL

I. E. D. P. (Information, Environment, Data, Processing) – still etched on my mind. Thought I had left this behind at college until I worked for a bank on the nuts and bolts of mainframe/server/client communications between various apps. I had to write a couple of libraries for their Cobol system to call and they insisted I did a few days re-training to be familiar with the CoBOL devs pain.

X86 Assembler

Powerful stuff. Back in college this was how we wrote games and some of the open-book exams involved questions like “Add auto-fire to the gun” etc... Then in the early days of Windows programming this was how you saw into some libraries when debugging (the second screen was often full of it). And then in at least one contract I’ve even ended up maintaining what were known as TSR’s (Terminate and Stay Resident programs) which set up buffers and other temporary things on users HDDs on startup.

DOS batch files

Always and everywhere. We have all seen full build systems written in this stuff. I still write them when I need to iterate over bunch of files (like moving files between changelists in SD).

The big one. Loved it at college, Then, when I got to work, I wrote my first Windows apps in it (and hand coded the resources .rc files in the Brief editor). I feel I owe this language a debt as it opened the door for most of what I do today. I still have Kelly and Pohl’s “A book on C” on my shelf here (and I’m sure Kernighan and Ritchie’s book is at home somewhere).

C++

I remember in the early 90s there was an funny e-mail used to do the rounds about “why C++ is like sex” and one of the lines was something like “because everybody thinks everybody else is doing it, but really most people haven’t done as much of it as you think”. And it was like that, we could not wait to get into this cool new way of coding (OOP). I eventually did, and it became my trade. Back during my self-employed years I titled myself a “Contract C++ dev”. I have used a few flavours of this over the years, from Ansi to Visual C++ (and MFC) to Borland and the OWL library.

Lotus 1-2-3 macros

Back in the day we had a full test automation suite for the 1-2-3 product, written entirely in it’s own macros. It was impressive and took quite a bit of learning, and worked.

Lotus Notes macros

Notes was a great rapid development platform back in the 90s and this was the way to add “code-behind”. It did sometimes mean late nights using print statements to debug, but it also meant I sometimes quickly produced really useful centralised project repositories with workflows etc... (Think Sharepoint, but in 1994).

LotusScript

Or Lotus Basic as I think it may have once been known. This added more power to the code behind Notes databases and came with some step-through debugging capabilities.

Java

I did my first course in Java in 1996 or 7 and I well remember the excitement over how the web was gaining traction at that time. I even remember a discussion with other course attendees about the end of the PC, and the advent of thin client machines. I suppose we were right – it just took a while longer (and reliable broadband). Anyways I have mainly only used Java on subsequent college courses (finished a Masters a couple of years ago) and I still like it – if my next job was a shift to that stack I imagine I’d be nearly as happy as I currently am on .Net.

When i was a C++ dev an agency once sent me for an interview. 5 minutes in the guy asked where I learned CL – turns out the agency had confused either C or C++ with CL, a SQL or 4GL language from a company called Multibase pty. So I told him that I had never heard of it, but as I was just recently arrived in Australia and needed a job I asked them to give me a week to learn it. I subsequently delivered on that first project for them (Y2K compliance testing) by writing a rudimentary parser to match patterns and identify Y2K smells

SQL

Like batch files this seems to have been omni present, from DB2, Oracle, Sybase to Multibase and then MS came out with their own SQL Server and it’s Express and compact version. I've probably been using MS SQL Server for the best part of a decade.

Nortel Meridian scripts

As I recall the Nortel Meridian Call centre server had it’s own scripting language, which allowed the use of variables to assign calls to different levels of operators depending on their skillset and that of the forwarding operator.

JavaScript

While I’ve never worked as a “web developer” I have done my fair share of html parsing and that have needed to know what the scripts are doing too. Over the last few years working with MS Dynamics CRM has required more ramping up in this area as nearly every form in every CRM solution I have ever created has required at least some Javascript (Jscript) behind it. I like it and I like that there is a ton of resources out there to help with it.

Since the first time I walked in the doors of MS as a contractor I’ve been using this (and .Net of course). Currently it’s what I use everyday – I’ve even got the cert to prove I know it

VB.Net

I don’t use this too much, but every now and then I find myself fixing or extending a tool written with it and am always glad that .Net makes it more immediately familiar than it might otherwise be.

Powershell

I don’t write any big scripts with this, but I use it from time to time to boss my O/S or that of remote machines around.

Bourne Shell, C Shell

Infrequent use over the years when using Unix based machines

When I look back at this list now it actually doesn’t appear that long, considering the time frame. So now I’m thinking there may be others which I’ve forgotten (did OS/2 have a scripting language). If I do remember more, I’ll add them here.

Exam 70-483: Programming in C# 5.0

2013-03-27T16:11:00Z

I took and passed this exam this morning and am feeling quite happy with myself. It is the first of the three exams which are building blocks towards the Microsoft Certified Solutions Developer (Windows Store Apps) certification, but on it’s own it does confer Microsoft Specialist (C# 5.0 Programming) status. For more information on the MCSD see here as you have the option of pursuing this through C# and Xaml or Javascript and Html 5.

My route to certification

So I have worked in C# quite a bit over the years, but have been wary of the certification exams and the specificity of their questioning. This was due to my belief that modern resources like IntelliSense and MSDN have meant that we don’t tend to memorise the specifics of the languages and frameworks with which we work anymore. There was a time when one always required books on the desk and it was natural to save that kind of slow research time by remembering API method signatures etc... whereas now I think I tend to more naturally remember concepts and then quickly look up implementation specifics when required. But earlier this year I finally got my first certification and so my fear of specific questioning was reduced and ultimately the experience made me want to get more certs. I purchased “Pro C# and the .Net 4.5 Framework” a couple of months ago and as I worked my way through it I thought now might be a good time to think about some of the programming certifications.

So although I was at that stage only half way through the big book (it’s 1400 pages) I checked out the certification paths and discovered that as an employee I could get the recommended training course (Course 20483B) documentation soft copy for free. Over the last few weeks in the evenings I worked through the modules and was pleasantly suprised to find no surprises; what I mean by this is that is I had pretty much covered everything in the course before (the fact that I’ve written a few Windows Phone and Windows 8 apps over the last year certainly helped with the newer stuff).

After I finished the course I went ahead and booked the exam, and then revised by following the links from the blog pages of a couple of folk who had already passed it (Thank you Andreas Hammar, Claudio Bernasconi and of course MSDN and Technet). I also speed read the course modules again, but paid extra attention to the areas to areas to which I have had less exposure (Performance counters, Reflection, using unmanaged code and encryption/decryption).

On the day I actually found this exam a little easier than the previous CRM one - I think in programming subjects it might be easier to spot definitively correct answers. It was also shorter (at only 40 questions) and I found that sometimes when I'd marked a question for review a later question which included a code sample might help clear up the ambiguity (in my mind) and let me go back an finish the "marked for review" question (only happened for a couple of questions). Anyway, I am now a certified Microsoft Specialist in C# 5.0 programming and have already acquired the course materials for the the next one (Essentials of Developing Windows Store Apps using C#). I’m on vacation next week, so I may get to make a start on it...

Detecting repeated parameter values across multiple method calls

2013-03-11T13:03:00Z

So this was actually asked of me once in an "interview style" situation and it took me quite a while to twig that the use of a queue would be required. I can't fully remember the wording of the question but it was basically something like this: "For every thousand session requests recieved by your server, if the same IP address appears 3 times, then flag it as a possible problem/hacker address".

So as I mentioned the use of a queue is the key to this implementation, as controlling the queue size allows us to restrict ourselves to the most recently pased 1000 (or any other limit number) values. In real life I would probably use something more like this implementation for a fixed size queue but right now I've just knocked up something quick and dirty which is not thread safe etc... But it illustrates the general logic.

I'm using a generic queue of strings (in real life I could probably use the System.Net.IPAddress class) and to keep the count (up to 3) of times a address appears in each thousand I use a Dictionary implementation with the IP address strings as my keys. So the logic is:

For each IP address passed, add it to the queue
If the queue has more than 1000 items, remove the oldest one
Upon removal of an address from the queue, also decrement the "per thousand" count associated with it in the Dictionary (if this is 0 or less, ralso emove the dictionary entry)
Upon addition of an address to the queue, also increment the "per thousand" count associated with it in the Dictionary (if this is no entry, add it with a count value of 0)

and the code works out as:

 private static bool IsSuspectIP(string address)
 {
 addressQueue.Enqueue(address);
 
 if (addressQueue.Count() > 999)
 {
 string oldAddr = addressQueue.Dequeue();
 DecrementCounter(oldAddr);
 }
 
 IncrementCounter(address);
 
 if (addressCounters[address] >= 2)
 {
 return true;
 }
 return false;
 }

 private static void IncrementCounter(string address)
 {
 if (addressCounters.ContainsKey(address))
 {
 addressCounters[address]++;
 }
 else
 {
 addressCounters.Add(address, 0);
 }
 }

 private static void DecrementCounter(string address)
 {
 if (addressCounters.ContainsKey(address))
 {
 if (addressCounters[address] < 0)
 {
 addressCounters.Remove(address);
 }
 else
 {
 addressCounters[address]--;
 }
 }
 }

Ok, that's end of the coding tests series for now. These were fun(ish) to write and also pretty quick to write (so they've really upped my posting frequency recently). But I do have an overdue requested update to add to my Windows 8 app, and have another app idea to work on, so I need to divert my spare time in that direction again now.

Linked list stuff in a modern environment

2013-03-11T11:18:00Z

So recently somebody asked about this and seemed surprised when I said that owing to the availability of lots of lists and collection classes in modern frameworks, I had not coded a linked list in a couple of decades, at least not since I completed my BSc (finished in 1996 while employed by IBM). So anyways, I decided to include them in this blog series just to show I can do it if I have to! I suppose it still makes sense to think about collection class implementation every now and then - it may be very useful in some future role if performance tweaking on structures like these becomes important. One caveat is that I have just included these quickly, and so haven't really optimised or thought about the "best" way to do the following methods - just made ones that work (without much testing).

For these examples I have used a Single Linked List. This class defines it and the following method is used just to display the list contents of the list:

 class SLLNode
 {
 public int value;
 
 public SLLNode pNext;
 
 public SLLNode(int val)
 {
 value = val;
 pNext = null;
 }
 }
 
 private static void DisplayLL(SLLNode current)
 {
 while (current != null)
 {
 Console.WriteLine("Node value {0}", current.value);
 current = current.pNext;
 }
 }

Copying a Single Linked List

Can be little confusing as you're effectively stepping through two lists, the existing list and the one you are creating as you go:

 private static SLLNode CopySLL(SLLNode n1)
 {
 SLLNode current = n1;
 
 
 SLLNode newHead = new SLLNode(n1.value);
 SLLNode prev = newHead;
 
 while (current != null)
 {
 current = current.pNext; //old list
 
 if (current != null)
 {
 SLLNode newNode = new SLLNode(current.value);
 prev.pNext = newNode;
 prev = prev.pNext;
 }
 }
 
 DisplayLL(newHead);
 return newHead;
 }

Sorting a Single Linked List

Just using a simple bubble sort here for a list with integer values in the payload. I'm writing this on a tired Sunday evening, so feel free to suggest "improvements"!

 private static void SortSLL(SLLNode head)
 {
 SLLNode current;
 int swaps = 1;
 
 while (swaps > 0)
 {
 current = head;
 swaps = 0;
 while (current != null)
 {
 SLLNode next = current.pNext;
 
 if (next != null)
 {
 if (current.value > next.value)
 {
 int tmp = current.value;
 current.value = next.value;
 next.value = tmp;
 swaps++;
 }
 }
 current = next; //move along
 }
 }
 }

Reverse a Single Linked List

Walk the list, reversing the "pNext" pointers as you go - just need to remember not to orphan any nodes, and to set the original head's "next" pointer to point to null as it becomes the tail

 private static SLLNode ReverseSLL(SLLNode head)
 {
 SLLNode current = head;
 
 SLLNode prev;
 
 SLLNode next = current.pNext; 
 
 while (next != null)
 {
 prev = current;
 current = next;
 next = current.pNext;
 current.pNext = prev;
 }
 head.pNext = null;
 
 return current;
 }

Checking for a prime number

2013-03-08T16:16:07Z

Ok, looking back at the original post I'm nearly regretting it as I need to find the time to actually write these - but at least this one was quick and simple. In fact it may be too simple to use as a tech test, but anyways here it is.

A prime number is any number greater than 1 which is only divisible by itself and 1. The method I use here simply checks all the values up to the number under investigation to see if division by them would leave a remainder of zero. There are probably faster ways to do this using smarter maths, and if you know of one, please post a comment!

 private static bool IsPrime(int num)
 {
 if (num <= 1)
 {
 return false;
 }
 
 for (int i = 2; i < num; i++)
 {
 if (num % i == 0)
 {
 return false;
 }
 }
 
 return true;
 }

Checking if a string is a palindrome

2013-03-08T15:52:00Z

Back in my original college days (over 20 years ago now) this used to be the subject of a running joke. It seemed that with every new language learned one of the first exercises was to check for palindromes, and the joke was that we couldn't wait to get into gainful employment with some large corporation, hopefully working with their Palindrome product group - as we had so much experience!.

So what's a palindrome? Wikipedia explains it as "a word, phrase, number, or other sequence of symbols or elements, whose meaning may be interpreted the same way in either forward or reverse direction". So we're basically checking if the string can be reversed and still have the same letter order. In .Net we could use String.Reverse() and work on the resulting list, but doing it the old fashioned way I get code like this

 char[] checkChars = testString.ToCharArray();
 
 for (int i = 0; i < checkChars.Length / 2; i++)
 {
 if (checkChars[i] != checkChars[checkChars.Length - i - 1])
 {
 return false;
 }
 }
 return true;

But that method would fail on some common palindromic strings like "Navan" (casing) or "A man a plan a canal panama" (casing and spaces). So in the full version I ignore casing and spaces to get an implementation like:

 private static bool IsPalindrome(string testString)
 {
 StringBuilder checkChars = new StringBuilder();
 
 foreach (char c in testString.ToLower())
 {
 if (c != ' ')
 {
 checkChars.Append(c);
 }
 }
 
 for (int i = 0; i < checkChars.Length / 2; i++)
 {
 if (checkChars[i] != checkChars[checkChars.Length - i - 1])
 {
 return false;
 }
 }
 return true;
 }

Quicksort

2013-03-06T22:36:00Z

Along with Mergesort, Bubblesort and others, Quicksorting of arrays is a standard on any fully fledged undergraduate computer science course. It’s a simple theory, and like a lot of theories can be easily described verbally, on a whiteboard or even in pseudocode, but they all take a little work to actually implement. Quicksort is a "divide and conquer” comparison sorting algorithm. The basic idea is that you continually reduce the area of the array under inspection (or unsorted area) by arranging the values around a pivot value (which can be chosen randomly), and then doing the same to the left and right sub arrays in a recursive fashion. Acually Wikipedia explain this much better so here is their link. They also have a nice pseudocode version, repeated here:

 function quicksort('array')
 if length('array') ≤ 1
 return 'array' // an array of zero or one elements is already sorted
 select and remove a pivot value 'pivot' from 'array'
 create empty lists 'less' and 'greater'
 for each 'x' in 'array'
 if 'x' ≤ 'pivot' then append 'x' to 'less'
 else append 'x' to 'greater'
 return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls

It is common (and makes the explanation easy) to refer to dividing the array into left and right sub arrays or lists. In .Net you certainly could use lists, but it is much more efficient to use the same array, moving values and passing indices to inform each recursion of their sub portion of the array. In my implementation I use a class called Quicksorter, and calling QuickSort() on an instance of this class will trigger a call to the recursive method qsort passing the initial 0 and Length-1 parameters.

 class QuickSorter
 {
 int[] intArray;
 
 public QuickSorter(int[] unsorted)
 {
 intArray = new int[unsorted.Length];
 unsorted.CopyTo(intArray, 0);
 
 }
 
 public void PrintArray()
 {
 for (int i = 0; i < intArray.Length - 1; i++)
 {
 Console.Write(intArray[i] + ", ");
 }
 Console.WriteLine(intArray[intArray.Length - 1]);
 }
 
 public void QuickSort()
 {
 qsort(0, intArray.Length - 1);
 }
 
 private void qsort(int left, int right)
 {
 int pivot, lft, rgt;
 
 lft = left;
 rgt = right;
 pivot = intArray[left];
 
 while (left < right)
 {
 while ((intArray[right] >= pivot) && (left < right))
 {
 right--;
 }
 
 if (left != right)
 {
 //now we know the rhs value is less than the pivot, so move it (left was saved as the pivot value)
 //and move the lhs counter after the operation
 intArray[left++] = intArray[right];
 }
 
 while ((intArray[left] <= pivot) && (left < right))
 {
 left++;
 }
 
 if (left != right)
 {
 //now we know the lhs value is greater than the pivot, so move it, rhs is pointing to a value which has been copied/duped to the lhs, basically a free space
 //and move the rhs counter after the operation
 intArray[right--] = intArray[left];
 }
 }
 
 //pivot value can slot back in to the free/duplicate lhs space
 intArray[left] = pivot;
 
 //reset lhs, rhs and pivot
 pivot = left;
 left = lft;
 right = rgt;
 
 if (left < pivot)
 {
 qsort(left, pivot - 1);
 }
 
 if (right > pivot)
 {
 qsort(pivot + 1, right);
 }
 }
 }

This class could easily be adapted for other value types and could easily be altered to sort arrays of any object by:

a) Implementing the IComparer interface
b) Changing the comparison lines to use the results of .Compare(object1, object2)

Greatest Common Divisor (and Lowest Common Multiple)

2013-03-04T11:06:00Z

It's worth repeating the wikipedia definition for GCD here, as it's explains it well: "The greatest common divisor (gcd), also known as the greatest common factor (gcf), or highest common factor (hcf), of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4. (See their full explanation here).

Euclid's algorithm to derive the GCD is simple and fast, and easily implemented in code as:

 static int GetGCD(int num1, int num2)
 {
 //check for valid inputs
 if (num1 < 1 || num2 < 1)
 {
 return -1;
 }
 
 while (num1 != num2)
 {
 if (num1 > num2)
 {
 num1 = num1 - num2;
 }
 if (num2 > num1)
 {
 num2 = num2 - num1;
 }
 }
 return num1;

In this approach the greater number decreases by the difference each time until they equal each other (at which point there woult also be no remainder from a modulus operation between them). This lower, equal number is the GCD. In some implementations you might see an "else" clause between the two "if" statements, but leaving it out as is done here allows for two reduction operations to happen between loop tests. You can do the same by applying the modulus operand to the two numbers swapping the results each time as you re-enter the loop. It's all about getting the remainder to equal 0. We can do this with recursion as seen here:

 public static int RecursiveGCD(int num1, int num2)
 {
 if (num2 == 0)
 {
 return num1;
 }
 else
 {
 return RecursiveGCD(num2, num1 % num2);
 }
 }

This second example has no handling for zero values, and while it won't crash it will give results for zeroes or minus numbers. One way of bullet-proofing this would be to have two methods - one which performs the valid inputs check, and then just calls the recursive method.

Lowest (or least) common multiple

Again using the Wikipidea definition: "The least common multiple (also called the lowest common multiple or smallest common multiple) of two integers a and b, usually denoted by LCM(a, b), is the smallest positive integer that is divisible by both a and b.[1] If either a or b is 0, LCM(a, b) is defined to be zero.

So I can't remember if this was also a Euclides formula, but dividing the product of the two numbers by their greatest common divisor gives the smallest possible common product of these two numbers individually multiplied with another, as follows:

 static int GetLCM(int num1, int num2)
 {
 return (num1 * num2) / GetGCD(num1, num2);
 }

Binary Search Tree

2013-02-22T17:36:00Z

This is a simple data structure, but again one with which many of us may have not been familiar with in some time. But it seems to beloved of tech screeners (and very useful in networking software) so a refresher is always nice; I have here put together a simple sorted tree and some equally simple methods, both recursive and non-recursive for the main operations, which are:

Insertion
Finding nodes in the tree
Displaying the tree

I created a class imaginatively called "BinarySearchTree" to implement this. In retrospect this constrcted my recursion to require helper methods, as I needed to pass the root node into the helper which was then treated as the "current" node and passed to future recursions. Not a big overhead, but a tad annoying. Here is the code:

First class is the TreeNode class, a simple class which assigns the identifier value upon construction.

 class TreeNode
 {
 public int nodeValue{get;set;}
 public TreeNode leftBranch, rightBranch;
 
 public TreeNode(int value)
 {
 nodeValue=value;
 leftBranch=null;
 rightBranch=null;
 }
 
 }

Then the BinarySearchTree class with Insert, Find and Display methods. This Display method does not show the nodes in order of value. Will make one of those next.

 class BinarySearchTree
 {
 TreeNode root = null;
 
 public BinarySearchTree(TreeNode rootNode)
 {
 root = rootNode;
 }
 
 public TreeNode Find(int keyValue)
 {
 TreeNode currentNode = root;
 
 while (currentNode != null)
 {
 if (currentNode.nodeValue == keyValue)
 {
 return currentNode;
 }
 else
 {
 if (keyValue < currentNode.nodeValue)
 {
 currentNode = currentNode.leftBranch;
 }
 if (keyValue > currentNode.nodeValue)
 {
 currentNode = currentNode.rightBranch;
 }
 }
 }
 
 return null;
 }
 
 public TreeNode FindRecursive(int keyValue)
 {
 return findRecursiveHelper(root, keyValue);
 }
 
 private TreeNode findRecursiveHelper(TreeNode current, int keyValue)
 {
 if (current == null)
 {
 return null;
 }
 
 if (current.nodeValue == keyValue)
 {
 return current;
 }
 
 if (keyValue < current.nodeValue)
 {
 if (current.leftBranch != null)
 {
 return (findRecursiveHelper(current.leftBranch, keyValue));
 }
 else
 {
 return null;
 }
 }
 
 if (keyValue > current.nodeValue)
 {
 if (current.rightBranch != null)
 {
 return (findRecursiveHelper(current.rightBranch, keyValue));
 }
 else
 {
 return null;
 }
 }
 
 return null;
 }
 
 
 public void Insert(TreeNode newNode)
 {
 InsertHelper(root, newNode);
 }
 
 private void InsertHelper(TreeNode current, TreeNode newNode)
 {
 if (newNode.nodeValue < current.nodeValue)
 {
 if (current.leftBranch == null)
 {
 current.leftBranch = newNode;
 }
 else
 {
 InsertHelper(current.leftBranch, newNode);
 }
 }
 if (newNode.nodeValue > current.nodeValue)
 {
 if (current.rightBranch == null)
 {
 current.rightBranch = newNode;
 }
 else
 {
 InsertHelper(current.rightBranch, newNode);
 }
 }
 }
 
 public void DisplayTree()
 {
 displayTreeHelper(root);
 }
 
 private void displayTreeHelper(TreeNode current)
 {
 Console.WriteLine(current.nodeValue.ToString());
 
 if (current.rightBranch != null)
 {
 displayTreeHelper(current.rightBranch);
 }
 
 if (current.leftBranch != null)
 {
 displayTreeHelper(current.leftBranch);
 }
 }
 }

To use the classes then I can call them from Main() as follows:

 BinarySearchTree bst = new BinarySearchTree(root);
 bst.Insert(new TreeNode(25));
 bst.Insert(new TreeNode(45));
 bst.Insert(new TreeNode(75));
 bst.Insert(new TreeNode(85));
 bst.Insert(new TreeNode(95));
 bst.Insert(new TreeNode(15));
 bst.Insert(new TreeNode(27));
 TreeNode tn = bst.Find(85);
 TreeNode trn = bst.FindRecursive(27);
 bst.DisplayTree();

As in the other articles the next things I need to ponder is, "If a candidate delivers this answer, what questions do we ask next?" Some potentials are:

Rewrite the Display method to display the nodes in order of values (in-order Traversal)
What optimisations can be applied to these trees?

If using the tree to store data, then manipulation of regularly searched-for data to be acessible the top of a tree makes sense - extra points here for any mention of AVL, Red-black, treap etc...

and of course - what unit tests would you write

which can be applied to every method in the classes

Checking a string for a valid ISBN number

2013-02-20T17:43:00Z

Continuing the series of "things you may have done in college" this next one is all about array manipulation. Again it's one I've heard of being used in a whiteboard/tech interview situation (so worth brushing up on!). The scenario here is just the creation of a method which:

Accepts a string
Checks to see if that string is actually a valid 10 digit ISBN number format (valid format - an actually valid ISBN no. is one which has been issued to a published book)

The only other stipulation is to do it in the first instance without using the built-in .NET string methods. So it would be quicker to use String.Split('-') etc... but the idea here is to test the basic knowledge, so the first effort here uses just standard array walking loops. I may add a more modern implementation later, but as previously stated I would love if these post generated some comments, and perhaps other implementation styles in those comments.

I took the "business logic", i.e. the 10 digit ISBN rules from here: http://www.isbn.org/standards/home/isbn/international/html/usm4.htm

This is the first hastily written version:

 private static bool IsTenDigitISBN(string isbnString)
 {
 if (string.IsNullOrWhiteSpace(isbnString))
 {
 return false;
 }
 
 char[] isbnArray = isbnString.ToArray();
 
 if (isbnArray[0] == '-' || isbnArray[isbnArray.Length - 1] == '-')
 {
 return false;
 }
 
 if (isbnArray.Length != 10 && isbnArray.Length != 13)
 {
 return false;
 }
 
 int dashCount = 0;
 int sum = 0;
 int digit=0;
 
 //now replace the '-' chars in pos 0-9
 for (int i = 0; i < isbnArray.Length-1; i++)
 {
 if (isbnArray[i] == '-')
 {
 dashCount++;
 isbnArray[i]=isbnArray[i--+1];
 for (int x = i + 1; x < isbnArray.Length-1; x++)
 {
 isbnArray[x] = isbnArray[x + 1];
 }
 }
 }
 if (dashCount != 0 && dashCount != 3)
 {
 return false;
 }
 
 //if array is 13 long, we must have 3 dashes, 10 long must have no dashes
 if ((isbnArray.Length == 13 && dashCount !=3) && (isbnArray.Length == 10 && dashCount !=0))
 {
 return false;
 }
 
 for (int i=0; i < 9; i++)
 {
 if (ToDigit(isbnArray[i], ref digit))
 {
 int multiplier = 10 - i;
 int val=digit*multiplier;
 sum += val;
 }
 else
 {
 return false;
 }
 }
 
 //now add the check digit (or 10 if it is an 'X' character)
 if (isbnArray[9] == 'X' || isbnArray[9] == 'x')
 {
 sum += 10;
 }
 else
 {
 if (ToDigit(isbnArray[9], ref digit))
 {
 sum += digit;
 }
 else
 {
 return false;
 }
 }
 
 //Sum of digits + check digit should have a remainder of 0 when divided by 11
 int check = sum % 11;
 
 if (check == 0)
 {
 return true;
 }
 else
 {
 return false;
 }
 }

As you can see there is one other small method called within the check method - the ToDigit() method which converts a char to an int (if the char is one of '0' - '9'). It is shown here:

 /// <summary>
 /// An "atoi()" style function for single characters
 /// </summary>
 /// <param name="ch">character which should represent a digit</param>
 /// <param name="digit">pass by ref int used to return the value</param>
 /// <returns></returns>
 private static bool ToDigit(char ch, ref int digit)
 {
 char[] digits = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
 bool found=false;
 
 for (int i = 0; i < digits.Length; i++)
 {
 if (ch==digits[i])
 {
 digit=i;
 found=true;
 }
 }
 
 if (found)
 {
 return true;
 }
 
 return false;
 }

So that's it - comments welcome. Questions which could be asked around this include the standard "which unit tests would you write". Here's some examples of strings to pass:

Valid - return true:

IsTenDigitISBN("90-70002-34-5"));
IsTenDigitISBN("0-8436-1072-7"));
IsTenDigitISBN("1590593006"));

Invalid - return false:

IsTenDigitISBN("-"));
IsTenDigitISBN("--1234556789--"));
IsTenDigitISBN("123-45-567-8-9"));

Other questions to ask then would be perhaps:

How to improve it/rewrite it using .NET string methods.
How to check for a 13 digit ISBN also - in the same method?