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;
}

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.

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!

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.

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.

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

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!

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)

publicclass MemoryWriter
: IDisposable { long _startMem; string _text; public MemoryWriter(string text)
{ _text = text +"
- "; _startMem = GC.GetTotalMemory(true);
} publicvoid 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>publicstaticlong 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>publicstaticlong 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;
}

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.

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:

publicclass PetClub

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

}

publicclass Person

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

}

publicclass Pet

{
publicstring Name
{ get; set; }
publicstring 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.

publicstaticstring 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:

publicclass Person

{

[XmlElement("FirstName")]
publicstring Name
{ get; set; }
public List<Pet>
Pets { get; set; }

}

publicclass Pet

{

[XmlAttribute("Name")]
publicstring Name
{ get; set; }

[XmlAttribute("Breed")]
publicstring 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:

publicstatic 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)

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!

That is all.

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.

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)

Do you ever get sick of having to write 4 whole lines for timing certain parts of your code. I know 4 lines isn't that bad, but they multiply quickly when you're testing a lot of different code, or different parts of the same method. That is why I came up with a StopwatchWriter class, it implements IDisposable so you can use it in a using statement which reduces the needed code to one line, put at the top of the code your testing (as opposed to before to setup and after to write). The constructor starts a stopwatch and when the Dispose method gets called, it stops the stopwatch and writes the time to the console, but it could easily be changed to write any type of log.

public class StopwatchWriter : IDisposable
{
    Stopwatch _stopwatch = new Stopwatch();
    string _text;

    public StopwatchWriter(string text)
    {
        _text = text + " - ";
        _stopwatch.Start();
    }

    public void Dispose()
    {
        _stopwatch.Stop();
        Console.WriteLine("stopw: "+_text + _stopwatch.ElapsedMilliseconds);
    }
}

Usage looks like:

using (new StopwatchWriter("populateStuff"))
{
    this.PopulateStep1();
    this.PopulateStep2();
}

-or-

using (new StopwatchWriter("doStuff"))
    DoStuff();

It certainly isn't easy to access what winform control was ultimately responsible for bringing up a ContextMenuStrip, but it is indeed possible, there is just some casting involved :)


private void selectAllToolStripMenuItem_Click(object sender, EventArgs e)
{
    if (((ContextMenuStrip)((ToolStripMenuItem)sender).Owner).SourceControl ==
        this.PrimeNumbersCheckBoxList)
    {
        this.SelectAllThePrimeNumbers();
    }
   
    if (((ContextMenuStrip)((ToolStripMenuItem)sender).Owner).SourceControl ==
        this.CompositeNumbersCheckBoxList)
    {
        this.SelectAllTheCompositeNumbers();
    }
}

It is incredibly easy to add a DotNetKicks "Kick It" Button to any DasBlog website. Simply navigate to your "themes" directory and open up the "itemTemplate.blogtemplate" file with text editor. And simply paste the following HTML wherever you'd like the button to display.

<a href="http://www.dotnetkicks.com/kick/?url=<%PermalinkUrl%>"><img src="http://www.dotnetkicks.com/Services/Images/KickItImageGenerator.ashx?url=<%PermalinkUrl%>" border="0" alt="kick it on DotNetKicks.com" /></a>

Pretty simple, huh? Thanks to John Forsythe for posting all the available DasBlog Macros.

If you're thinking about starting a blog, I highly recommend DasBlog, it was a very easy to setup, especially since it doesn't require a database! That makes the cost of hosting a blog at DiscountAsp.net only $10/month! Subtext on the other hand needs a database to store and will run you $20 a month. I don't really know why DasBlog doesn't advertise that fact more, I would have tried installing it first, is a relational database really that necessary for a blog? It also makes it brain dead simple to backup your blog or move hosting providers. I know because I started out hosting my blog at 1and1 (stay away!), I've been with DiscountAsp.net for a couple months and absolutely love it. Everything just works, I copied my DasBlog files over and I was done. Plus its cheap and since all they do is focus on Microsoft technologies, they always have the latest and greatest beta stuff running as soon as it comes out (like .Net 3.5 and IIS 7.0).

Anyone who has read about Ruby may have heard about Duck Typing; it allows any object to be passed into a method as long as the object has the properties/methods used by the originating method. If this were to be implemented in C# it would look something like:

public void Blah(object foo)
{
    Console.WriteLine(foo.Bar);
    Console.WriteLine(foo.Kung("Jackie Chan"));
}

And it would work completely fine at run-time as long as the object passed to the Blah method had a property called "Bar" and a method called "Kung" that took in a string as an argument. Unfortunately this won't work in C# because C# is a strongly typed language, "object" simply does not have a "Bar" property, nor a "Kung" method. Strong typing does have its advantages though, IntelliSense and compile time checking. If in Ruby you were to call the Blah method and it didn't have the appropriate properties and methods you would receive a run-time error. Run-time errors are bad because they make end-users cranky, which makes your boss cranky, which makes you cranky.

Strongly typed languages can have some of the benefits of this flexibility with Interfaces. Just create an IFoo interface with the needed properties and you're off to the races, right? Well, yeah, but only on objects that you have the ability to edit, which leaves you praying that the authors of your dependencies have your bizarre perfectly reasonable needs in mind (not likely).

For instance, I recently wrote a windows component that would listen for some events on a textbox and process the results. The only problem is I wanted to let the user hook up the component to either a TextBox or a ToolStripTextBox. Since those objects don't share a common interface, I have to have two separate properties on the component, a TextBox and a ToolStripTextBox and at run-time I have to throw an error if the user assigned a value to both properties (and remember, run-time error != desirable).

What I propose is the natural extension (pun intended) of Extension Methods -> Retroactive Interfaces. Simply put, I'd like to be able to tell the compiler that certain classes implement an interface, but do so from the interface, not from the class (because I may not be able to edit the class). I don't really care what the exact syntax is but I could imagine it going something like:

using System.Windows.Forms;

public Interface IText ImplementedBy TextBox, ToolStripTextBox
{
    string Text { get; set; }
    event EventHandler TextChanged;
}

This is if you wanted to be fairly precise about which classes implemented your new interface, but it would be also nice if to tell the compiler that you wanted any object that has the appropriate properties/methods/events to have it implement said interface. Such syntax could look like:

public Interface IText ImplementedByAllAppropriate  { ... }

And voilà, you now have the flexibility of Duck Typing and the compile time checking and IntelliSense of Strong Typing. I know bureaucracy can be a wildly beast, so Anders, if you're reading, I'm willing to grease proverbial wheels with $2,000,000 to get this feature in the next version of C#. (No, I don't have the $2,000,000 right now, but I'm working out a very lucrative deal with a rich Nigerian General)


Post Script: Like Extension Methods, Retroactive Interfaces aren't aimed at solving some unsolvable problem. You can definitely use the Adapter Pattern to wrap up the object and have the adapter class implement the needed interface. But lets be honest, its simply a pain in the ass, it takes time to write the adapter class and you have to explicitly create an adapter for every class you want to implement your interface (ImplementedByAllAppropriate, isn't really possible with an adapter). A Retroactive Interface is some syntatic sugar aimed at making developers lives easier.

After battling with with all the little quirks involved with switching hosting providers, I finally have a blog engine. I originally tried installing subtext but the most recent version is using the MS AJAX extensions, thus requiring that my 1and1 have the AJAX extensions installed and unfortunately 1and1 refuses to install it. Even though its been an officially supported MS product for almost a year. Anyway, I had to go with DasBlog and things seem to be going ok thus far, it took a while to tweak all the different config files just right. By the way, those are some ginormous config files (web.config => 190k). One confusing thing about DasBlog: it doesn't use a database! I always kind of thought a sql driven blogging engine was a little overkill, and if I knew that DasBlog just wrote everything to a xml config file, I would have started with it to begin with.

Anyway, I look forward to sharing my thoughts on .Net and development in general. Feel free to drop me a line at BOOjvongillernSPAM@gmail.com