Tuesday, September 1, 2015

Hey folks, many of you have complained about the wonky RSS feed. Yes, it is still a problem and I'm looking at it.

It *appears* as if my feed is getting re-published to different sources, which explains why folks are seeing multiple copies of my post, each with a different source URL.

I'm going to check with my blog hosting company to see if there's a reason this is happening on their end.

Thanks so much for your patience!

-Jim

Thursday, August 27, 2015

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**.

Wednesday, August 26, 2015

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

Wednesday, August 5, 2015

*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 **reference**. **You 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.

Tuesday, August 4, 2015

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**.