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

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

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.