James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 159 , comments - 1334 , trackbacks - 0

My Links

News

Welcome to my blog! I'm a Sr. Software Development Engineer in the Seattle area, who has been performing C++/C#/Java development for over 20 years, but have definitely learned that there is always more to learn!

All thoughts and opinions expressed in my blog and my comments are my own and do not represent the thoughts of my employer.

Blogs I Read

Follow BlkRabbitCoder on Twitter

Tag Cloud

Archives

Post Categories

.NET

CSharp

Little Wonders

Little Wonders

vNext

Thursday, August 27, 2015

Solution to Little Puzzlers - Lowest Common Ancestor

This is the way I went about the "Lowest Common Ancestor" problem. However, keep in mind there are multiple ways to solve this, so don't worry if your solution has variations and it’s entirely possible there are more efficient ways.

Feel free to suggest your solution in the comments here or in the original post, but please be respectful of others’ efforts.

The Solution

The first tendency in this problem is to want to walk back up the tree.  This is obviously problematic because we do not have a parent node link at each node.  But, it turns out, there’s a better way anyway.

The first thing we want to do is examine the two values we are sent to find.  If the values are the same, they are obviously their own common ancestor – as long as the node actually exists in the tree.

If the nodes aren’t the same, we will “order” them by simply finding which node is less and which is greater.  Why do we care?  Because, it will simplify our search to be O(log n) by allowing us to drive down the tree in the BST fashion.

What we can do at each node, is take advantage of the ordering to tell us where to go.  If the current node’s value is < the smaller value, we know both nodes are on the right (if they exist in the tree).  Similarly, if the current node’s value is > the larger value, we know both nodes are on the left (if they exist in the tree). 

If neither of these conditions are true, one of two things are true: either a) one of the nodes equals the current node or b) the smaller is on the left and the larger is on the right.  Either way, we have a candidate for the LCA as long as both nodes are in the tree.  So, once we know this is the point that the LCA would be, we simply find the smaller and larger in this subtree.

   1: public class Trees 
   2: { 
   3:     // This is the public kick-off method, orders the first/second
   4:     public Node<int> FindLowestCommonAncestor(int first, int second, Node<int> root) 
   5:     { 
   6:         // if first and second happen to be same, it's simply a find
   7:         if (first == second) 
   8:         { 
   9:             return Find(first, root); 
  10:         }
  11:         
  12:         // otherwise, order the first and second by value
  13:         return first < second 
  14:             ? FindLowestCommonAncestorTraversal(first, second, root) 
  15:             : FindLowestCommonAncestorTraversal(second, first, root); 
  16:     }
  17:  
  18:     // a helper method that simply finds a node in the BST
  19:     public Node<int> Find(int value, Node<int> current) 
  20:     { 
  21:         if (current != null) 
  22:         { 
  23:             if (current.Value == value) 
  24:             { 
  25:                 return current; 
  26:             }
  27:  
  28:             return value < current.Value 
  29:                 ? Find(value, current.Left) 
  30:                 : Find(value, current.Right); 
  31:         }
  32:  
  33:         return null; 
  34:     }
  35:     
  36:     // the actual traversal
  37:     private Node<int> FindLowestCommonAncestorTraversal(int smaller, int larger, Node<int> current) 
  38:     { 
  39:         if (current != null) 
  40:         { 
  41:             // if larger < value then smaller is also by definition, both left
  42:             if (larger < current.Value) 
  43:             { 
  44:                 return FindLowestCommonAncestorTraversal(smaller, larger, current.Left); 
  45:             } 
  46:  
  47:             // if smaller is > value, then larger is also by definition, both right
  48:             if (smaller > current.Value) 
  49:             { 
  50:                 return FindLowestCommonAncestorTraversal(smaller, larger, current.Right); 
  51:             }
  52:  
  53:             // otherwise, we found divergent point, make sure nodes actually exist
  54:             if (Find(smaller, current) != null && Find(larger, current) != null) 
  55:             { 
  56:                 return current; 
  57:             } 
  58:         }
  59:  
  60:         return null; 
  61:     } 
  62: }

This algorithm ends up being O(log n) – assuming a well balanced BST implementation, which is fairly optimal.  At most, we’d find the LCA at the root, which would mean we’d do two finds, both of which are O(log n).

Summary

Hope you had fun with this one!  Of course, I’m sure many out there can tweak the answer for performance in various ways – but you get the point.

Have a solution that worked for you but was totally different?  I’d love to hear about it!

Stay tuned next week for the next Little Puzzler.

Posted On Thursday, August 27, 2015 12:52 AM | Comments (0) | Filed Under [ My Blog C# Software .NET Little Puzzlers Technology ]

Wednesday, August 26, 2015

Back in Seattle Again

Hey folks, after 8 months back in the mid-west, we had a family meeting and decided that it would be better for my career and our kids to go back to Seattle.  We're relocated again, though still waiting for all of our computers, furtniture, etc. 

As soon as I can, I will post the solution to the latest puzzler, and send you a new one! 

To those who were noticing duplications in my feed, I believe I fixed this, is anyone still noticing issues?

-Jim

Posted On Wednesday, August 26, 2015 5:07 PM | Comments (7) | Filed Under [ My Blog ]

Wednesday, August 5, 2015

Little Puzzlers–Lowest Common Ancestor

I like to keep my brain sharp by working on programming puzzlers. On off weeks I'm going to start posting programming puzzlers I've collected over the years. Hopefully you'll find them as entertaining as I do.

The Problem

A binary search tree is a tree with the ordered property.  That is, for every node in the tree with value x, all nodes in the left subtree are < x and all nodes in the right subtree are > x recursively.

So, given a binary search tree (BST) and two values, determine the lowest common ancestor of the two values.  That is, tracing up from the values, towards the root, find the lowest node (level wise) they have in common.

For example, given the following tree:

                        20

                    /          \

                  10            30

                /    \        /     \

               5      15    25       35

The Lowest Common Ancestor (LCA) of 5 and 15 is 10.  Similarly, the lowest common ancestor of 5 and 35 is 20.  Note that the value itself could be it’s own LCA, for example, the LCA of 20 and 35 is 20.

The tree itself is composed of standard nodes that only go down.  That is, they have a Left and Right child reference but not a Parent referenceYou may use the following as your template for a node class:

public class Node<T>
{
    public T Value { get; private set; }

    public Node<T> Left { get; set; }

    public Node<T> Right { get; set; }

    public Node(T value)
    {
        Value = value;
    }
}

Spoiler Alert!

Fair Warning: there may be discussion of the problem and potential solutions posted in the comments below. Read at your own risk.

Posted On Wednesday, August 5, 2015 10:59 AM | Comments (8) |

Tuesday, August 4, 2015

Solution to Little Puzzlers–“List All Anagrams in a Word”

This is the way I went about the "List all anagrams in a word” problems. However, keep in mind there are multiple ways to solve this, so don't worry if your solution has variations and it’s entirely possible there are more efficient ways.

Feel free to suggest your solution in the comments here or in the original post, but please be respectful of others’ efforts.

The Solution

There are many ways to tackle this problem.  Ultimately, the main goal of this problem was to be able to return all the anagram words of an input word as quickly as possible with little CPU overhead.  This pretty much eliminates attempting to perform all permutations of an input word, which can be a very expensive operation.

A major hint is in the fact we are given a dictionary.  Because we are given this dictionary we can prep it in any way we like when the program starts, and then the processing of any word input becomes simple.  Most dictionaries will easily fit within memory of modern computing hardware, so this should not be a major concern. 

So, having the dictionary, we have all possible valid word anagrams already.  The only trick is how to get from the input to these words. 

So let’s think, “what do all anagrams have in common?”  For example, the word “post” has “pots”, “stop”, “tops”, etc.  It may seem obvious, but all anagrams have the same letters.  Thus, if we can hash or organize these letters in a consistent way, we can store all anagrams under the same key.  In this way, we can apply the same hash/organization to the input word, immediately get the list of anagrams, and simply exclude the input word from the anagram list.

The simplest way to do this would simply be to sort the letters, this is a fairly simple operation in C#:

   1: var key = string.Concat(word.ToLower().OrderBy(c => c));

That would turn “post”, “pots”, etc. all into: “opst” which we can use as our key for our lookup.  Now, how to store them, you could download your own multidictionary, or create a Dictionary<string, List<string>>, but really C# already has one for you called a Lookup.  The Lookup stores a key to multiple values.

So first, let’s write a simple DAO for reading in our words from a file:

   1: public class WordFileDao : IWordDao 
   2: { 
   3:     public string FileName { get; private set; }
   4:  
   5:     public WordFileDao(string fileName) 
   6:     { 
   7:         FileName = fileName; 
   8:     }
   9:  
  10:     public IEnumerable<string> RetrieveWords() 
  11:     {
  12:         // make sure to remove any accidental space and normalize to lower case
  13:         return File.ReadLines(FileName).Select(l => l.Trim().ToLower()); 
  14:     } 
  15: } 

Then, we can create an anagram finder to create the lookup on construction, and then find words on demand:

   1: public class AnagramFinder 
   2: { 
   3:     private readonly ILookup<string, string> _anagramLookup; 
   4:  
   5:     public AnagramFinder(IWordDao dao) 
   6:     { 
   7:         // construct the lookup at initialization using the
   8:         // dictionary words with the sorted letters as the key
   9:         _anagramLookup = dao.RetrieveWords().ToLookup( 
  10:             k => string.Concat(k.OrderBy(c => c))); 
  11:     }
  12:  
  13:     public IList<string> FindAnagrams(string word) 
  14:     { 
  15:         // at lookup time, sort the input word as the key,
  16:         // and return all words (minus the input word) in the sequence
  17:         string input = word.ToLower(); 
  18:         string key = string.Concat(input.OrderBy(c => c));
  19:  
  20:         return _anagramLookup[key].Where(w => w != input).ToList(); 
  21:     } 
  22: }

Notice the ToLookup() extension method (in System.Linq), this method creates an instance of Lookup from any IEnumerable<T> if you provide it a key generator and a value generator.  For the key generator, I’m returning the word in sorted, lowercase (for consistency).  For the value, I’m just lower-casing the word (again, for consistency).  This effectively creates the “dictionary of key to list of values” that, when you query using the “[…]” operator, will return an IEnumerable<T> of the values, or empty sequence if the key was not found.

And that’s it!  We have our anagram word finder which can lookup words quickly with only the cost of sorting the letters in a word, which is much less expensive (processing-wise) than attempting all permutations of the letters in a word.

Summary

Hope you had fun with this one!  Of course, I’m sure many out there can tweak the answer for performance in various ways – but you get the point.

Have a solution that worked for you but was totally different?  I’d love to hear about it!

Stay tuned next week for the next Little Puzzler.

Posted On Tuesday, August 4, 2015 4:22 PM | Comments (6) | Filed Under [ My Blog C# Software .NET Little Puzzlers Technology CSharp ]

Tuesday, July 28, 2015

Little Puzzlers–List all anagrams for a word

I like to keep my brain sharp by working on programming puzzlers. On off weeks I'm going to start posting programming puzzlers I've collected over the years. Hopefully you'll find them as entertaining as I do.

The Problem

Given a file of all valid words in the English language, write an algorithm that would be suitable for a web page that will list all valid English words that are complete anagrams of the word entered by the user on the page.

That is, if the user visits the page and types in POST, the web page should quickly process the word and display that the valid anagrams are STOP and POTS.

Note that we are only looking for single-word anagrams, not anagram phrases. 

Hints

Remember the use case, the algorithm proposed should be suitable for a web application and thus should be performant and not hog the CPU. 

The longest word in the English language (at least that I’ve found so far) is pneumonoultramicroscopicsilicovolcanoconiosis, which is 44 characters long. 

You need only consider words in the dictionary, any word not in the dictionary can be considered “not a valid word” for this exercise.

Spoiler Alert!

Fair Warning: there may be discussion of the problem and potential solutions posted in the comments below. Read at your own risk.

Posted On Tuesday, July 28, 2015 1:43 AM | Comments (10) | Filed Under [ My Blog C# Software .NET Little Puzzlers Technology ]

Powered by: