VON#

Programming Job Interview Challenge Answer Week #14

von — Tue, 05 Aug 2008 19:33:09 GMT

Here is the question: Programming Job Interview Challenge Question Week #14

This week was a fun and interesting question. Here is the answer

Step 1. As you're adding points to the polygon, determine a bounding rectangle by keeping track of the min x/y and the max x/y.

Step 2. Draw a line from the point you're interested in, to any point outside the bounding rectangle (because you know the outside point can't be within the polygon).

Step 3. Count the number of intersections between your newly created line and the polygon, if the number is even (0 included) the point in question is not within the polygon, if the number of intersections is odd, then the point is within the polygon.

Examples:

Outside = Even Intersections

Inside = Odd Intersections

Programming Job Interview Challenge #13 Answer

von — Tue, 22 Jul 2008 13:00:08 GMT

Programming Job Interview Challenge Question Week #13

Highlight the text below for the answer.

This is pretty simple, use a stack to track all open brackets and on all closed pop the stack to see if you have the correct matching bracket.

private bool AreBracketsClosedProperly(string input)
{
    Stack<char> openBrackets = new Stack<char>();
    foreach (char bracket in input)
    {
        switch (bracket)
        {
            case '(':
            case '[':
            case '<':
            case '{':
                openBrackets.Push(bracket);
                break;

            case ')':
                if (openBrackets.Pop() != ')')
                    return false;
            case ']':
                if (openBrackets.Pop() != ']')
                    return false;
            case '>':
                if (openBrackets.Pop() != '>')
                    return false;
            case '}':
                if (openBrackets.Pop() != '}')
                    return false;
                break;
        }
    }

    if (openBrackets.Count != 0)
        return false;
    else
        return true;
}

Programming Job Interview Challenge #10 Answer

von — Tue, 01 Jul 2008 16:00:57 GMT

If you select the text below, you can find the answer for this week's Job Interview Challenge #10 from dev102.com.

This is a fairly easy problem, you can find the missing number by taking the difference of the sum of the numbers you're given and what the total should be for 1 to n. If you actually do the sum of 1 to n via a for loop, the time complexity is O(2n), which is really just O(n), but if you want to get picky, you can make it actually O(1n) by only looping through the list you're handed and instead using the formula n(n+1)/2 to get the total of the numbers from 1 to n.

public static void FindMissingNumbers()
{
    //The O(n) that I discussed above is for
    //the FindMissingNumber method only

    int n = 100;
    List<int> numbers = CreateRandomList(n);
    Console.WriteLine("Found:     Left Out Number is: " + FindMissingNumber(numbers));

    n = 1000;
    numbers = CreateRandomList(n);
    Console.WriteLine("Found:     Left Out Number is: " + FindMissingNumber(numbers));

    n = 10000;
    numbers = CreateRandomList(n);
    Console.WriteLine("Found:     Left Out Number is: " + FindMissingNumber(numbers));

   //sample output
   //Generated: Left Out Number is: 31
   //Found:     Left Out Number is: 31
   //Generated: Left Out Number is: 840
   //Found:     Left Out Number is: 840
   //Generated: Left Out Number is: 6289
   //Found:     Left Out Number is: 6289

}

public static int FindMissingNumber(List<int> numbers)
{
    int numbersSum = numbers.Sum();
    int n = numbers.Count;
    int sum1ToNPlus1 = (n * (n + 1)) / 2; // this is much quicker than actually summing 1 through n+1

    return sum1ToNPlus1 - numbersSum;
}

public static List<int> CreateRandomList(int n)
{
    int nPlus1 = n + 1;
    List<int> allNumbersList = new List<int>();
    for (int i = 0; i < nPlus1; i++)
        allNumbersList.Add(i);

    Random rand = new Random();

    List<int> subsetNumbersList = new List<int>();
    while (allNumbersList.Count > 1)
    {
        int index = rand.Next(allNumbersList.Count);
        subsetNumbersList.Add(allNumbersList[index]);
        allNumbersList.RemoveAt(index);
    }

    Console.WriteLine("Generated: Left Out Number is: " + allNumbersList[0]);

    return subsetNumbersList;
}

Programming Job Interview Challenge #8 Answer

von — Mon, 16 Jun 2008 17:48:03 GMT

I've been trying to keep up with the Job Interview line of posts over at dev102.com, but unfortunately I've been running out of time to do all of them. Anyway, this weeks question can be found here. Stop reading if you don't want the answer.

This problem can be solved using a Finite State Machine. The only thing you're going to store is the current state of the machine, once you reach the end of the machine, you'll alert. On initialization of the piping component, you'll build a finite state machine for the given alert sequence. Every time you are given a message you check what you should do with the state machine based on where you are currently at.

I was going to write out the code to do this, but it becomes a little tricky when you have repeating data in your alert sequence because if you get a message you're not expecting you don't necessarily want to reset the state machine to its initial state. For example, if the alert sequence was "A, A, A, A, B", and your input is "A, A, A, A, A, B", you don't want to reset the machine to the first state when you get that 5th A, you want it to stay in its current state.

Quick Fix - Missing Using Statements

von — Thu, 05 Jun 2008 18:03:01 GMT

Do yourself a favor, next time you have a build error that says something like: The type or namespace name 'XYZ' could not be found (are you missing a using directive or an assembly reference?). Double click the error (which will highlight the unknown type) then hit Alt+Shift+F10. This will bring up a dropdown that has all of the types that match that class name and hitting enter will automatically add the appropriate using statement. Thank you Visual Studio!

Programming Job Interview Challenge #4 Answer

von — Mon, 19 May 2008 17:48:47 GMT

So one of the guys over at dev102.com has been posting job interview questions. While the most recent isn't the best interview question in the world, I thought I'd share the answer if anyone is interested.

Here is the question:

How would you implement the following method: Foo(7) = 17 and Foo(17) = 7. Any other input to that method is not defined so you can return anything you want. Just follow those rules:

Conditional statements (if, switch, …) are not allowed.

Usage of containers (hash tables, arrays, …) are not allowed.

The answer is crazy simple. Highlight the text below to reveal the answer.

public int Foo(int x)
{
return -1 * x + 24;
}

My Algebra teacher would be so proud.

DasBlog and the Web.Config Location Tag

von — Sun, 18 May 2008 16:02:55 GMT

So you may or may not have noticed that I haven't posted anything for the past two months and that most of my links have been broken. Well, the reason being is that I run a small intranet application for a group I belonged to at Iowa State. When I moved the application over to discountasp.net the application was living in a subdirectory of my vonsharp.net domain, and in doing so I ran into all sorts of messy web.config problems.

Well, I think finally have solved all the issues and should be posting once or twice a week from here on out. But just incase you're interested here is how I resolved my issues.

In order to run a seperate web application in a subdirectory of your DasBlog directory you'll need to do the following:

1. In your DasBlog web.config, wrap all of the configuration tag's children in one single "location" tag, except for the configSections tag and the runtime tag. Your dasBlog web.config should look something like:

<configuration>
<configSections> ... </configSections> <runtime> ... <runtime>
<location path="" allowOverride="true">
<newtelligence.ControlImages ... > ... <system.web ... > ... </location>
<configuration>

Note: DO NOT CHANGE THE PATH, LEAVE IT AS AN EMPTY STRING

2. Then in your new sub-directory web application's web.config you'll need to do the same thing, and leave the path string empty as long as your web.config is actually sitting in the sub directory. As I understand it, its possible to define this in your dasBlog's web config but I'd recommend against it.

Here is the tricky part. The location tag for the sub-directory application acts just like object inheritence. So your web application's web.config will inherit all of the same configuration from its parent directory. Since you probably don't want dasBlog running in your sub directory, you need to clear out it's http modules. So in your new web app's web config add the following markup to the httpModules section

<httpModules>
<!-- gets rid of dasBlog Modules --> <remove name="UrlMapperModule"/>
<remove name="TitleMapperModule"/>
<remove name="ProfileMapperModule"/>
<remove name="ControlImageModule"/>
<remove name="CompressionModule"/>
<remove name="IPBlackList"/>
</httpModules>

Hope this helps anyone who is going through the same pain that I had.

Boost Your Productivity - Remove Firefox Quick Launch

von — Tue, 18 Mar 2008 14:01:17 GMT

I have a big problem with launching firefox everytime I have 20 seconds of downtime (like when I'm building a big solution, or I'm waiting for a large file to load in my application). By the time I look at whatever site I decide to go to, it sucks up more than the 20 seconds of downtime and costs me a lot of time "context switching".

Something that has helped me with this problem: I took firefox off of my quick launch bar and put it on the desktop. I now have to be much more deliberate in when I actually need to use the "tubes".

Software Grandmaster

von — Mon, 03 Mar 2008 18:15:26 GMT

I just read this excellent essay by Jeff Moser on his blog and thought I'd share it with all of you. I highly recommend it, especially for students who are interested in a career in software development.

What does it take to become a Software Grandmaster

Most Everything the Immediate Window Can Do the Watch Window Can Do Better

von — Fri, 29 Feb 2008 14:53:29 GMT

I saw a post on oh null! that talks about how you can evaluate expressions within the immediate window, whether you're simply retrieving a variable or performing a calculation on multiple variables. I personally like to do all of this in the Watch Window because I can have an easy history of what variables I've interrogated. Like the immediate window, you can call Methods and display the results, but since methods can change state, they will not execute automatically after you step into a new line of code, but there is a nice little refresh button that will re-execute your method call.

As I understand it, the watch window is a wrapper around the simpler functionality of the immediate window, so it also supports Intellisense. But there are some things that you can only do in the immediate window, like the .load [dll] command which lets you import another assembly for your use, which is pretty damn slick. I've only ever really used that feature in one scenario: to load the Son of Strike assembly which helps you get detailed information on your executable (very detailed call stack info, very granular heap information, but kind of hard to use).

Another cool thing you can do in your immediate window: Declare new variables. Those variables will have the same scope as the current breakpoint in execution, but the ability opens the doors to some neat possibilities. For instance, you could declare a new variable, copy a subset of information from your current in scope variables and then use my Xml Utility Methods to copy your new object out to disk! I'm not quite sure why you would need to do that, but its nice to be able to!

Quick and Dirty Memory Utility Methods

von — Wed, 27 Feb 2008 19:36:28 GMT

With my work, I regularly deal with obscene amounts. Of course, our users demand that this information loads instantly and without running out of memory. So optimizing our data storage objects for time and memory constraints is incredibly important. So far, I think I've done a pretty good job, because I can load 125 million data points in a shade over 3 seconds (using a database to store some of this data flew out the window a while ago). But getting to this point has been an interesting journey. Doing quick prototyping of prospective storage mechanisms has been incredibly important and I thought I'd share some of the utility methods/classes I've created to speed up the process.

The first piece of code is incredibly similar to my StopwatchWriter Class. Instead of starting and stopping a Stopwatch, we're asking the garbage collector how much total memory is being used (in bytes), before and after you instantiate an object (or a whole set of objects)

 public class MemoryWriter
: IDisposable { long _startMem; string _text; public MemoryWriter(string text)
{ _text = text + "
- "; _startMem = GC.GetTotalMemory(true);
} public void Dispose()
{ Console.WriteLine("mem:
" + _text + (GC.GetTotalMemory(true) - 


_startMem).ToString()); } } Usage looks like: using (new MemoryWriter("CrazyBigObject"))
{ CrazyBigObject myCrazyBigObject = LoadCrazyBigObject(42);
}

This is the most accurate way of figuring out how much memory a specific object is taking up in memory. But there is a limitation to this method if you're using it in a multi-threaded application, such as a Win Form because another running thread could dereference objects on the heap after you've instantiated your MemoryWriter , but before its been disposed. I prefer to only use this class in small throw away console applications, to make my results as accurate as possible.

Sometimes though, you'll find yourself looking at an object in someone else's code and you want to easily find out how much memory its taking up, but the object in question is "built" over several methods along with several other objects that you don't care about. Which makes it impossible to use theMemoryWriter Class. You can use a memory profiling application to do this, but I've found that they are notoriously hard to pick up and use. And due to the nature of how they work, they take ages to work because they have to take a snapshot before and after the code you care about (i.e. copy your 700MB object heap twice and then "diff" the two heaps). So I've wrote two small methods that serialize the object to a stream and then return the length of the stream. Note: This is approximately how much data the object is holding in memory. It may besignificantly less than how much space it takes up on the heap. Case in point: Dictionary<K, V> takes up much more space in memory than it does when serialized.That's because it only serialized the key value pairs and it re-hydrates the dictionary on deserialization. Nor will it reflect the size of any properties on your object that are marked with the NonSerialized attribute. So it is far from perfect, but it helps give you an idea with out the pain of using a memory profiler . You can use these methods by setting a break point and calling them in your watch window (I prefer doing that over the immediate window).

///
<summary> ///
Returns a rough approximation of the size of an object 


/// (including ALL objects in/directly referenced by the object) ///
</summary> public static long ApproxSize(object obj)
{ BinaryFormatter formatter = new BinaryFormatter(); long length; using (MemoryStream
stream = new MemoryStream())
{ formatter.Serialize(stream, obj); stream.Seek(0, SeekOrigin.Begin); length = stream.Length;
} return length;
}

Sometimes though, your object is very large and serializing the object in memory will cause an OutOfMemory Exception. So use the below method instead, it serializes the object to disk and gives you the size of the file (and deletes the file after its done).

///
<summary>

/// Returns the approximate size of very large objects 


/// (time intensive) in bytes.

/// </summary> public static long ApproxSizeLarge(object obj)
{ FileInfo info = new FileInfo(@"c:\approxSizeTemp");
BinaryFormatter formatter = new BinaryFormatter(); using (StreamWriter
writer = new StreamWriter(@"c:\approxSizeTemp"))
{ formatter.Serialize(writer.BaseStream, obj); } long length = info.Length;
info.Delete(); return length;
}

What The Hell?

von — Sat, 16 Feb 2008 17:07:21 GMT

So I was never really expecting to make much money from my AdSense advertisements, if I made $10 in a year, I'd be happy. But perhaps I've only made 80 cents thus far because Google is serving absurd ads like:

What AdWords did these people buy that is displayed on my site talking about Microsoft Technologies? Is this some sort of joke perpetrated the FOSS Commie Zealots? My content might be a little crappy (or not) but C#, WPF and LINQ are simply bad-ass.

Put Down the XmlNode and Step Away From the StringBuilder

von — Tue, 12 Feb 2008 14:29:33 GMT

I'm sure there are plenty of you out there who have your boss hankering to use some of that "Xml Stuff". Sometimes we get sheltered in our own little world and haven't actually had to work with a whole lot of xml data that wasn't already wrapped up by the Project Settings object created by Visual Studio. So naturally, you'd probably go to the "tubes" and search for some additional information. Undoubtedly, you will run across pages telling you how to construct some Xml in C# by creating a new XmlDocument and adding XmlNode children which will have attributes and subnodes and namespaces, ad infinitum. And you'll realize you now have some of the world's fugliest code. So you decide, "oh, well xml is really similar to html, I'll just build it using a StringBuilder" and you end up with slightly less fugly code, that is until you try to read it back in.

These methods are completely unnecessary. PUT DOWN THE XMLNODE AND STEP AWAY FROM THE STRINGBUILDER. Slowly move your hand to the mouse and scroll down to read about the easiest way to write and read Xml in the .net framework.

Ok, quick show of hands: who thinks working with simple .net business model objects is brain dead easy? Alright, if your hand isn't up, you are beyond hope, please leave now. Of course, working with simple objects is about the simplest exercise for code next to "Hello World". If you can create a .net object that models the xml you want to store, you are 95% done with outputting well formed Xml.

Example: If I wanted to store information about a few people and their pets I would create three classes:

public class PetClub

{

public List<Person>
Members { get; set; }

}



public class Person

{

public string Name
{ get; set; }

public List<Pet>
Pets { get; set; }

}



public class Pet

{

public string Name
{ get; set; }

public string Type
{ get; set; }

}

To get an Xml representation of an instance of PetClub, all you have to do is use the XmlSerializer found in the System.Xml.Serialization namespace. I've wrapped up all the necessary code into a short utility method.

public static string ConvertToXml(object item)

{

XmlSerializer xmlser = new XmlSerializer(item.GetType());

using (System.IO.MemoryStream
ms = new System.IO.MemoryStream())

{

xmlser.Serialize(ms, item);

UTF8Encoding textconverter = new UTF8Encoding();

return textconverter.GetString(ms.ToArray());

}

}

Simply calling: ConvertToXml(myPetClubInstance) will spit back the following xml:

<PetClub xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema">
<Members>
    <Person>
      <Name>Jon</Name>
      <Pets>
        <Pet>
          <Name>Chester</Name>
          <Type>Savannah Cat</Type>
        </Pet>
        <Pet>
          <Name>Abby</Name>
          <Type>Domestic Miniature Panther</Type>
        </Pet>
      </Pets>
    </Person>
    <Person>
      <Name>Dan</Name>
      <Pets>
        <Pet>
          <Name>Lucy</Name>
          <Type>Semi-sweet Chocolate Lab</Type>
        </Pet>
      </Pets>
    </Person>
</Members>
</PetClub>

At this point you might be saying: "That is cool and all, Jon, but this looks like a lot of xml to be outputting for such little actual data. And what if I want to have more control over xml element naming". Dear friend, let not your heart be troubled for there is help on the way. By adding some simple Property Attributes to our classes we can completely change how our xml is constructed. We can have the object in whatever form is most convienient for our program while still allowing us to interoperate with an xml document created by a different application with a different idea of what good names are.

Changing our two classes to:

public class Person

{

[XmlElement("FirstName")]

public string Name
{ get; set; }

public List<Pet>
Pets { get; set; }

}



public class Pet

{

[XmlAttribute("Name")]

public string Name
{ get; set; }

[XmlAttribute("Breed")]

public string Type
{ get; set; }

}

Will output this xml:

<PetClub xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema">
<Members>
    <Person>
      <FirstName>Jon</FirstName>
      <Pets>
        <Pet Name="Chester" Breed="Savannah Cat" />
        <Pet Name="Abby" Breed="Domestic Miniature Panther" />
      </Pets>
    </Person>
    <Person>
      <FirstName>Dan</FirstName>
      <Pets>
        <Pet Name="Lucy" Breed="Semi-sweet Chocolate Lab" />
      </Pets>
    </Person>
</Members>
</PetClub>

Pretty simple, huh? Can you imagine how difficult it would be to make these changes via XmlNodes or a StringBuilder? There are about 10 other property attributes available for xml serialization, including the very useful XmlIgnore() attribute which makes the appropriate property not serialized. I'll leave the rest of the research up to you.

And I almost forgot, to read your xml back into an object use the following method:




public static T
FromXml<T>(string xml)

{

XmlSerializer xmlser = new XmlSerializer(typeof(T));

using (System.IO.StringReader
sr = new System.IO.StringReader(xml))

{

return (T)xmlser.Deserialize(sr);

}

}

Sample Code - XmlSerializerSample.cs (2.33 KB)

Custom Created Theme

von — Mon, 11 Feb 2008 05:47:16 GMT

Well, as you can tell I've got a new DasBlog theme I created myself. I'm not the most artistic person in the world, but I'm happy with what I've accomplished. Good lord did it take a long time, its been a while since I've pounded out HTML and CSS, but I'm glad to have it fresh in my head again but I'm totally disgusted at how differently IE and Firefox render, what a gigantic waste of time.

Have a good week!

Damn It Feels Good To Write Unit Tests Again

von — Fri, 08 Feb 2008 18:45:33 GMT

That is all.

Most Useful VS Feature No One Knows About

von — Thu, 07 Feb 2008 17:23:45 GMT

It really does shock and amaze me how many developers get through the day without knowing the wonders of the Exceptions Dialog box. You can access it via Debug>Exceptions or you can hit Ctrl-Alt-E. What this dialog box allows you do is to pick a set of exceptions (or all of them for that matter) and the debugger will automatically break when the exception is thrown. This allows you to inspect your call stack and interrogate your variables to determine the state of your application when the exception occurred. No longer do you have to look through an error message to find a line number and start setting break points. This becomes especially helpful if the error is occurring in a gigantic loop and your not sure how many times the loop executes before it runs into a null reference exception. It breaks automatically and voila, you can easily see all the variables that are associated with your null object (or whatever the error may be).

Sometimes you'll be responsible for code, that for one reason or another uses exception catching/handling as a normal part of code flow. This usually is considered a bad practice but sometimes you don't have a choice under the circumstances. When that happens, it is very easy to turn off custom typed exceptions, just click the "Add..." button and type in the fully qualified name of the exception you don't want to see every time it is thrown. As you can see in my screenshot, I've done this with the Sybase.Data.AseClient.AseException exception.

I hope this helps speed up any future debugging.

Patterns

von — Mon, 04 Feb 2008 14:46:19 GMT

I just found this site off of dotnetkicks, and it looks like a great reference site for information on patterns and anti-patterns

http://sourcemaking.com/

Dictionary Naming Guidelines

von — Wed, 23 Jan 2008 16:05:02 GMT

Generic dictionaries are a great thing, they let you add and retrieve objects very quickly. My current gig has a lot of need for them because we've got tons of data that needs to be quickly referenced (I'll post more about Dictionary memory performance later). The problem is that developers everywhere like to use very un-descriptive names for their dictionaries, especially nested dictionaries. Usually you'd like to avoid nesting these things, but sometimes you don't have a choice and making a bunch of derived classes adds a lot of code and more "stuff" you have to sift through.

Simple Example:

Dictionary<int, string>
_peopleDictionary;

What is the key? Is it a PersonId? Is it a CustomerId? Is it an EmployeeId? Is it a Social Security Number?

What about the value? Is it First Name, Last Name, First then Last, Last then First, Nickname?

In order to find out, a developer who takes over your code has to look up all references to PeopleDictionary and find out what the Key and Values are, yielding a gigantic waste of time. (Worse yet, it could be you looking up all the references because you haven't looked at this particular code in 7 months). And that is even a non-nested dictionary!

Now, can you tell me what kind of data is stored in the below object?

Dictionary<int,
Dictionary<int,
List<string>>>
_customerIdToOrderIdToDescriptions;

Sure the name is a little long, but think about how many different kinds of data are being stored in it. Plus you didn't have to make a custom object for a one-off need. Anyone who has to modify your code can easily use this object without trying to figure out what "OrdersDictionary" is actually storing.

FXCop Guys: I'll give you $10 if you add a rule saying that generic dictionary variable names have to contain the string literal "To".

Of note: it's generally considered bad practice to use nested generics, but if you do, just make sure that you don't expose nested generic types by returning them in public methods or by making a public property with a nested type. Keep them for internal use within your class only.

Free Copy of VS 2008

von — Fri, 18 Jan 2008 19:33:04 GMT

Register and attend for your local launch event and receive a free copy of Visual Studio 2008, SQL Server 2008 AND Windows Server 2008. Which by my estimate is at least $2000 in free software.

http://www.microsoft.com/heroeshappenhere/register/default.mspx

(If you're feeling generous, I would accept a 10% finders fee)