James Michael Hare

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

My Links

News

Welcome to my blog! I'm a Sr. Software Development Engineer 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

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 (6) | Filed Under [ My Blog C# Software .NET Little Puzzlers Technology ]

Monday, July 20, 2015

Solution to Little Puzzlers–Find the Majority Element

This is the way I went about the "The Majority Element” 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.

A Linear-Time, Linear-Space Solution

As with so many puzzlers, there is more than one way to tackle this problem.  Let’s first consider the more straight-forward approach.

If we think about it, what we really want to do in the simplest sense, is to get a count of each element and see if an element occurs more than n/2 times (roughly speaking).

An easy way to do this would be to create a Dictionary<int, int> that would use the element as the key, and hold a count of occurrences as the value.  This would let us take a linear pass through the list to populate the Dictionary, and then one linear pass through the Dictionary to find the count (if any) > n/2.

This would give us an O(n) solution since we know that the number of items in the dictionary is <= the number of items in the sequence.  In fact, if we had foreknowledge that the range was limited (say the values ‘1’ – ‘10’) we could easily create an array to hold the counts.  However, let’s assume that is unknown and go with the dictionary:

   1: public static int? LinearTimeMajority(IEnumerable<int> sequence)
   2: {
   3:     int total = 0;
   4:     var counts = new Dictionary<int, int>();
   5:  
   6:     foreach (var item in sequence)
   7:     {
   8:         int count;
   9:         counts[item] = counts.TryGetValue(item, out count) ? ++count : 1;
  10:         ++total;
  11:     }
  12:  
  13:     var majority = counts.FirstOrDefault(p => p.Value > total / 2.0);
  14:  
  15:     return majority.Value != 0 ? majority.Key : (int?)null;
  16: }

This gives us linear time – O(n) – but also, potentially takes linear space since we may potentially need one entry in the hash for every element in the list, worst case.

A Linear-Time, Constant-Space Solution

It turns out, there is an algorithm to determine the majority element in linear time that also only takes constant space.  That is, you do not need to hold a count for every unique element.  This algorithm (the Boyer-Moore Majority Vote Algorithm) has three very simple steps:

  • Start a counter at 0 and hold a current candidate
  • For each element in the list:
    • If counter = 0, set current candidate to the element and counter to 1
    • If counter != 0, increment counter if element is current candidate, decrement if not.

Sounds simple, but why does it work?  It’s actually pretty simple.  If counter is zero, it means there isn’t a current majority, so look for a new candidate.  If current is > 1, it means that for the list so far, the candidate is a possible majority.  When you complete the list, you will be left with one candidate which will either be the majority, or no majority exists.  You can then do a simple compare against the count / 2.0 to see if the element is the majority.

Think of it this way, every time the counter becomes zero, we’re effectively throwing away the list up to that point because there is no majority in the list before us.  If there WERE, the counter would be positive because it would have to occur more times (increment) than not (decrement) to be positive.

For example, say we have the sequence: 1, 2, 2, 1, 1, 1, 2, 1, 3, 1

Let’s look at how this algorithm would play out:

Index 0 1 2 3 4 5 6 7 8 9
Value 1 2 2 1 1 1 2 1 3 1
State candidate = 1
count = 1
candidate = 1
count
= 0
candidate = 2
count
= 1
candidate = 2
count
= 0
candidate = 1
count
= 1
candidate = 1
count
= 2
candidate = 1
count
= 1
candidate = 1
count
= 2
candidate
= 1
count
= 1
candidate = 1
count
= 2

 

Notice in the two places the count goes back down to zero (indexes 1 and 3) that we determined that in those lists (so far) we had no majority, so we can start over looking for a new candidate.  However, starting at index 4, the count of 1s from that point forward remains positive because we never have enough non-1s to get us back down to zero.  Hence, 1 is our candidate majority, and we need only now count those 1s (another linear pass) to check if 1 is the majority, or if no majority exists.

Thus, the algorithm is linear complexity in time, and constant complexity in space (only need to hold a candidate and a count).  Of course, this assumes you have the ability to re-iterate over your sequence.

   1: public static int? LinearSpaceAndTimeMajority(IEnumerable<int> sequence)
   2: {
   3:     int total = 0;
   4:     int currentCount = 0;
   5:     int? current = null;
   6:  
   7:     foreach (var item in sequence)
   8:     {
   9:         if (currentCount == 0)
  10:         {
  11:             current = item;
  12:             currentCount = 1;
  13:         }
  14:         else if (current == item)
  15:         {
  16:             ++currentCount;
  17:         }
  18:         else
  19:         {
  20:             --currentCount;
  21:         }
  22:         ++total;
  23:     }
  24:  
  25:     return current.HasValue && (sequence.Count(i => i == current.Value) > total / 2.0)
  26:         ? current.Value : (int?)null;
  27: }

 

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 Monday, July 20, 2015 10:53 AM | Comments (4) | Filed Under [ My Blog C# Software .NET Little Puzzlers Technology ]

Tuesday, July 7, 2015

Little Puzzlers–The Majority Element

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

The problem is simple to state, but not immediately apparent how to solve efficiently.

Given a list of numbers, determine the number in the majority – that is, find the number that occurs over 50% of the time (for a list of size n that’s ⌊n/2⌋ times).

For example, in this sequence:

1, 2, 1, 4, 2, 1, 1, 5, 1, 1

The majority element is 1 occuring 6 times in a sequence of length 10.

However, in this sequence:

1, 2, 5, 4, 2, 1, 5, 5, 1, 1

There is no majority element since no element occurs > 50% of the time.

Hints

Please note that it is not enough to say which element occurs the most often, you have to also determine it’s the majority as well.

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 7, 2015 11:19 AM | Comments (25) |

Thursday, July 2, 2015

Summer Vacation & 2015 Visual C# MVP Award

image Hey folks, it’s been a busy summer here at work and at home.  I’ve been busy helping to keep the kids entertained as well as working on a major project at work, which has left me with a few weeks hole in my blogging schedule.  Rest assured, I am not gone and will be blogging again in the next week or so.  Probably with a new puzzler on Monday.

In other news, I received word yesterday that I’ve been awarded a Visual C# MVP award for the 5th consecutive year now.  Thank you all so much for reading my blog posts!  It’s much appreciated.

Posted On Thursday, July 2, 2015 1:13 PM | Comments (2) |

Friday, June 5, 2015

C#/.NET Little Wonders: Null Conditional Operator in C# 6

Once again, in this series of posts I look at the parts of the .NET Framework that may seem trivial, but can help improve your code by making it easier to write and maintain. The index of all my past little wonders posts can be found here.

Visual Studio 2015 is on the horizon!  In fact, some of you may already have played with the preview and seen some of the many neat new things to come – both in the IDE and in the C# language.

Note: All of the C# 6 features mentioned are current with the latest CTP of VS2015 as of the time of this writing.  The syntax and exact feature behaviors may be subject to change in the final released version.

Too many layers of null checks!

How many times have you had to consume a web service, and that web service has had many layers of nested objects, each of which can potentially be null

Often times, to be safe, this makes us end up having to write logic like this:

   1: var response = someProxy.SomeWebMethod();
   2:  
   3: // so many layers, so many potential nulls...
   4: if (response != null && response.Results != null && response.Results.Status == Status.Success)
   5: {
   6:     Console.WriteLine("We were successful!");
   7: }

And this is just a status buried down two layers, imagine if the model was four, five, or six layers deep!

This happens a lot in C# (and Java) where at any step along the way of a deeply-nested model, you could encounter a null.  Indeed it would be nice to be able to have an option to cascade the null down the chain if there’s a null along the way.

Now, we get this new feature in C# 6, the null conditional operator.  This operator does exactly what we’re talking about: if the left side of the operator is null, it cascades a null of the resulting type to the right. 

In short, if you replace your “.” with the null conditional operator “?. it will cascade the null down the line:

   1: var response = someProxy.SomeWebMethod();
   2:  
   3: // so much better!
   4: if (response?.Results?.Status == Status.Success)
   5: {
   6:     Console.WriteLine("We were successful!");
   7: }

So, if response is null, or if response.Results is null, then the result will be a null matching the return type of Status.  If not, you will get the actual value of Status.

Now, notice that we have “?.” in there twice, this is because we need to use the “?.” everywhere that we want to cascade the null otherwise a null will throw as expected.

For example, consider the following four similar conditionals:

   1: // #1
   2: if (response.Results.Status == Status.Success) { }
   3:  
   4: // #2
   5: if (response?.Results.Status == Status.Success) { }
   6:  
   7: // #3
   8: if (response.Results?.Status == Status.Success) { }
   9:  
  10: // #4
  11: if (response?.Results?.Status == Status.Success) { }

Let’s look at each of these in turn:

  1. The first will throw if either response or response.Results are null 
  2. The second will throw only if response.Results is null, but will cascade if response is null
  3. The third will throw if response is null, but will cascade if response.Results is null
  4. The fourth will cascade if either response or response.Results are null

Most of the time, unless you know an element cannot be null in a chain (like if it’s a struct), you’ll want to continue to cascade down an identifier chain once you start.

What does null-cascading with a value type result do?

Let’s say that Results has a Count field that evaluates to an int, what would happen if we did this?

   1: // what is the type of the LHS?
   2: if (response?.Results?.Count > 0)
   3: {
   4:     Console.WriteLine("We got data!");
   5: }

The above does compile.  This is because C# is smart enough to realize that the end result of the chain is a value type, so it converts it to a Nullable<int> instead.  This means we may be comparing null to zero.  However, if you study the way nullable math works in C# (much like in SQL) you’ll find that null > 0 is false (incidentally so is null < 0).  For more details, see this post on Nullable Math Doesn’t Always Add Up.

Or, let’s do this instead:

   1: // won't compile, will complain that can't implicitly convert
   2: // Nullable<int> to int
   3: int count = response?.Results?.Count;

You’ll see right away that C# considers the end result of that identifier chain to be Nullalble<int> (also referred to as int?) instead of int.

Want a default other than null? 

What if you want to cascade the null, but want to use another default value instead.  For example, take the Count expression above where it gave us a Nullable<int> that can cause some interesting math comparisons if the value is null, it would be better if we could cascade to something like zero.

Well, you can combine the null conditional operator with the null-coalescing operator (??) to provide a different default on null.

   1: // This will compile, if the expression evaluate to null then 0 will be used.
   2: int count = response?.Results?.Count ?? 0;

Indeed, notice that now we can type the value of count to int since null is no longer an option.

What if we’re dealing with an indexer property?

So, you may have noticed we’ve been dealing directly with members accessed using the dot (“.”) operator, what happens if we want to use an indexer property (“[]”)?

For example, let’s say that Results contained a List<Address> called Addresses. And List<T> has an indexer property.

We don’t want to have to go back to:

   1: // notice the [...] indexer on addresses
   2: if (response != null && response.Results != null && response.Results.Addresses != null
   3:     && response.Results.Addresses[0] != null && response.Results.Addresses[0].Zip == "63368")
   4: {
   5:     Console.WriteLine("Are we neighbors?");
   6: }

Notice the indexer on Addresses, so we can’t use “?.“ because indexers use a different syntax than fields, properties, and methods.  Fortunately, C# provides a null conditional form of the indexer operator “?[]” which works just like the standard member-access null conditional operator, but for indexers instead.

So now, we can write:

   1: // Again, much cleaner...
   2: if (response?.Results?.Addresses?[0]?.Zip == "63368")
   3: {
   4:     Console.WriteLine("Are we neighbors?");
   5: }

With this, if response, response.Results, response.Results.Addresses, or response.Results.Addresses[0] are null, we will coalesce a null as the final result.

But wait, it works for more than just fields and properties…

The null conditional operator is not simply for fields and properties, it can be used for method calls as well.  Once again, if the identifier chain on the left evaluates to null the method will not be called and a null matching the return type (if any) will be cascaded along.

For example, how often do you have code like this:

   1: if (x != null)
   2: {
   3:     x.Dispose();
   4: }

This is a fairly common occurrence, we want to call a function if the instance is not null, but it takes 4 lines of code to write that (assuming we do our full set of curlies).

Now, however, this can be simplified to one line:

   1: // a great one-liner!
   2: x?.Dispose();

Much cleaner!  Especially if you are doing a lot of these kind of statements in a larger cleanup operation; just imagine the lines you will save!

And what about processing events?  Those of you who have done any event raising know that there’s a standard pattern for raising an event where you take a copy of the handler, and then check the copy for null.  This is so that the value of the handler doesn’t change between the time you check and the time you invoke it.  We don’t want to lock the invocation, because that could be a very expensive lock if the subscribers do anything heavy.

   1: // to avoid locking, yet be thread-safe, must make a copy of the delegate
   2: // and then invoke the copy.  
   3: var copy = OnMyEvent;
   4: if (copy != null)
   5: {
   6:     copy(this, new EventArgs());
   7: }

For more details on this pattern, see Safely and Efficiently Raising Events

Now with the null conditional operator, we can do this instead:

   1: // again, reduced to a great one-liner:
   2: OnMyEvent?.Invoke(this, new EventArgs());
So, the ?. will evaluate first and make a copy of the reference (hence satisfying the copy pattern) and then based on whether that is null or not, it will invoke the delegate.

Summary

The null conditional operator is a great code-reducer to eliminate a lot of very verbose null-checking logic where cascading makes sense.  Keep in mind that a null-conditional chain that results in a value type will create a Nullable<T> instead, and particularly pay attention when you try to perform arithmetic or logical comparisons versus null.

Thanks for reading my Little Wonders of C# 6 series, I’ll be back soon with more Little Wonders and Little Puzzlers in the weeks to come.

Posted On Friday, June 5, 2015 12:26 AM | Comments (4) |

Powered by: