Funny Math

The question is what happens to a value if you increment or decrement it by a uniformly distributed value centered around zero?

As a disclaimer this isn't really the ha-ha kind of funny.  Its the other kind of funny.

To start this off lets ask a a simpler question.  Lets say you have a $100 dollars invested in a stock.  Today it goes down 10% tomorrow it goes up 10%, how much to you have? 100- 10% =$90.  90 + 10% = $99.  Rats you lost a dollar, its unfortuante but pretty straight forward.

Now lets say one out of every two days your stock goes up 10% and every other day it goes down 10%.  From the first example it is pretty easy to see that we would expect our value to steadily decline, and if we enumerate the values we can see that indeed that is the case.

Day	Movement	Value
0	--	100
1	10%	110
2	-10%	99
3	10%	108.9
4	-10%	98.01
5	10%	107.81
6	-10%	97.03
7	10%	106.73
8	-10%	96.06

From there is not so hard to see that it probably won't be any different using a random distribution than with set values.  But lets find out.  I am sure there is a way to prove this in a proof and or show it with a closed form formula.  But coming up with the formula/proof escapes me right now.  So we'll fall back to simulating it.

[TestMethod]

public void RandomWalking()

{

    for (int round = 0; round < 10; round++)

    {

        double start = 1000;

        Random randNumber = new Random((int)DateTime.Now.Ticks);

        double bias = 0;

        for (int i = 0; i < 10000; i++)

        {

            double diff = randNumber.Next(-100, 100) / 1000.0;

            start *= 1 + diff;

            bias += diff;

        }

        Console.WriteLine("1000 -> {0}, bias:{1}", start, bias);

    }

}

Generates:

1000 -> 0.329915187578686, bias:8.688
1000 -> 3.14340291320618E-06, bias:-2.75600000000002
1000 -> 5.88119745218127E-06, bias:-2.26699999999999
1000 -> 4.1356376989622E-10, bias:-12.037
1000 -> 1.38040135841817E-06, bias:-3.68200000000001
1000 -> 4.46395869719455E-09, bias:-9.291
1000 -> 1.26886933354314E-06, bias:-3.65099999999999
1000 -> 2.42195007654241E-08, bias:-7.97599999999999
1000 -> 9.08609341706222E-08, bias:-6.48599999999998
1000 -> 0.000263032702826233, bias:1.545

It appears that I wasn't lying.  So that's nice.  This shows that in 10,000 iterations of uniformly distributed random motion in almost every scenario almost all the original value was destroyed.

One observation that can be made from the above data set is that when the random values aren't quite centered around zero, specifically when they are a bit higher there is relatively less values lost, which makes a lot of sense.  

Which left me curious what center value leaves things more or less intact.  From trial and error it looks like if the distribution is centered around .00105 things stay pretty stable.  I imagine this is a very famous theorem.  Anyone know what its called?  I'll try to find out for the next post.

Favorite Interview Question (Part 3)

From Part 2 we know that we have asked the candidate to interleave a linked list. So how do we evaluate how smart they are based on their answer?

The first and possible most important part of the "answer" is that they ask more questions.  There is no way they have enough information to solve the problem at this point.  Some typical questions that should be asked are do we care more about space or time?  Should the list be swapped in place or do you want a new list to come out?  And of course some clarifying questions on what exactly interleaving a linked list is.

The answers are that we want to optimize for both space and time. And we want the list to be interleaved in place.  So given that there are usually three stages of solution that candidates come up with.

First:

• Get the first item.
  
• Traverse the list to the last item and insert it after the first item.
  
• Move the pointer over the (original) second item.
  
• Get the new last item.
  
• Rinse and repeat.
  

This is a good starting point.  It allows you to make sure that can traverse a linked list, and then have a conversation about how to measure the speed of an algorithm.  Then I ask, OK but how could you improve it? (O(n^2) time, O(1) space).

Which leads us to the second solution:

• Create an array of all the items in the linked list.
  
• Pull from from the array and build up a new linked list.
  

This is a arguably better answer (given that we want to minimize both time and space) as there is no n^2 in either time or space.  It interesting to see the thought process that gets people here.  Some people, now that that are more familiar with the problem space, grasp it right away and some take some prodding. (O(n) time, O(n) space).

Now I ask them if it can be improved.  Because this is usually where people stop advancing.  So I give "points" for realizing that there probably is a better way to do this without worrying about if they are actually able to figure out the algorithm.  So now that we've established there there is a better way to do it, how do you do it?  Very few people figure it out.

• Traverse the list once to get the length
• Traverse to half way through the list
• Flip the links for the back half of the list, so if we had 1 -> 2 -> 3 -> 4 -> 5 we end up with 1->2 -> 3 <- 4 <-5
• Now we can build the new list in one pass

This is the best solution I have come up with (O(n) time, O(1) space).  If the candidate gets this one, I still ask if there is a way to do better, 1) because if there is a better way that would be cool to learn.  And 2) to see if they stick to their points when they think their are right, which is an important skill too.

Once we get to the best possible solution the candidate can come up with I like to have them then come up with test cases for their solution.  I have yet to see it but I would give big bonus "points" to someone who wrote the tests first and did TDD for the interview question.

So there it is, now I've ruined my favorite question and will have to come up with a new one.  Any ideas?

Favorite Interview Question (Part 2)

From Part 1 we know what some properties a good interview questin should have.  So here is my question of choice:

Given a singly linked list, interleave the list. Interleaving a link list involves alteratinly taking the first and then last item to form the new list. So a list with elements: 1 2 3 4 5 when interleaved looks likes 1 5 2 4 3. Go.

So thats it. How would you solve it? In part 3 I'll discuse what makes a good answer.

Attribute Constructors

When does an attribute constructor get called?

Seems like a pretty straight forward question.  The MSDN documentation probably has it: Attribute Constructor, nope.  Well then the language specification must have it.  Section 17. Attributes, nope.

There seams to be two likely places that attribute constructor would be called:

1) Around the static constructor fo the type the attribute is defined on or in.

2) At the time you reflect over the object to find the attributes.

The test attribute looks like this:

    public class MyAttribute : Attribute

    {

        public MyAttribute()

        {

            Console.WriteLine("In Attribute Constructor");

        }

    }

To test theory #1 the code looks like this: 

    [My]

    class Program

    {

        static void Main(string[] args)

        {

            Console.WriteLine("In main");

        }

    }

The results: The attribute constructor isn't called.

So now we need to make sure it really is theory #2:

    [My]

    class Program

    {

        static void Main(string[] args)

        {

            Console.WriteLine("In main");

            typeof(Program).GetCustomAttributes(true);

        }

    }

As expected this causes the attribute constructor to be called.  Which raises a follow up question, if we just look for some other type of attribute, say just Obsolete attributes, will our attribute still get constructed?

    [My]

    class Program

    {

        static void Main(string[] args)

        {

            Console.WriteLine("In main");

            typeof(Program).GetCustomAttributes(typeof(ObsoleteAttribute),true);

        }

    }

Interestingly enough this does not cause our constructor to be called. So the moral of the story is that an attribute will be lazily constructed.  

Why is this interesting?  I ran into this question because I was creating an attribute that expired, so one of the parameters to the constructor would be a date, and in the constructor of the attribute it would throw an exception if that date had passed.  This behavior was going to be used to make sure if we ignored unit tests they had to eventually be turned back on.  So I wanted to see when exactly we could expect this exception to be called.  And it turns out to only be when you ask the type about this attribute.