Fix for Samsung Focus beeping issue

For the last couple of days my Windows Phone have been very sick. It would not go to sleep when the power button was pressed. And when I unmuted the sound, I discovered that it was beeping incessantly.

This was happening only when the device was on battery power. When I plugged it in, it behaved correctly. At first I assumed that it has something to do with the battery. Rebooting the device and removing/reinserting the battery did not help, however.

The sound that it was making though was the same as the one for connecting the power. So I looked closely at the USB power connector in the phone, and discovered that the signal carrier was bent and was touching the walls of the adapter. I straightened it with a tiny screwdriver, and the problem disappeared.

North Korea has its own - official - reddit

The comments on it are absolutely hilarious.

http://www.reddit.com/r/pyongyang

Nice try, Amazon!

I am sure this offer is entirely fair :-).

Sir Francis Bacon on Obama

"Hope is a good breakfast, but it is a bad supper."

http://www.brainyquote.com/quotes/quotes/f/francisbac125278.html

National Defense Authorization Act for Fiscal Year 2012 (it looks like this time of the year again)

"Göring: Why, of course, the people don't want war. Why would some poor slob on a farm want to risk his life in a war when the best that he can get out of it is to come back to his farm in one piece. Naturally, the common people don't want war; neither in Russia nor in England nor in America, nor for that matter in Germany. That is understood. But, after all, it is the leaders of the country who determine the policy and it is always a simple matter to drag the people along, whether it is a democracy or a fascist dictatorship or a Parliament or a Communist dictatorship.

Gilbert: There is one difference. In a democracy, the people have some say in the matter through their elected representatives, and in the United States only Congress can declare wars.

Göring: Oh, that is all well and good, but, voice or no voice, the people can always be brought to the bidding of the leaders. That is easy. All you have to do is tell them they are being attacked and denounce the pacifists for lack of patriotism and exposing the country to danger. It works the same way in any country.

In an interview with Gilbert in Göring's jail cell during the Nuremberg War Crimes Trials (18 April 1946)"

http://en.wikiquote.org/wiki/Hermann_Göring#Nuremberg_Diary_.281947.29

Why you should leave your vote for President (and most likely, Senator) blank next year

http://jonathanturley.org/2011/12/15/obama-breaks-promise-to-veto-bill-allowing-indefinite-detention-of-americans/

No matter what the Republican alternative is, the Democrats MUST be held accountable for this.

"Virtually all Democrats and Republicans voted to strip citizens of their rights in a vote of 93-7."
http://jonathanturley.org/2011/12/02/42285/

Here is the roll call.

http://www.govtrack.us/congress/vote.xpd?vote=s2011-218

The following people voted Nay:
    Sanders, VT
    Lee, UT
    Wyden, OR
    Merkley, OR
    Coburn, OK
    Paul, KY
    Harkin, IA

Both WA senators voted for it. None of them will get my vote next election season, no matter what the alternative is.

Is Facebook driving the Greek debt crisis?

http://www.businessweek.com/magazine/correlation-or-causation-12012011-gfx.html

Generating random numbers with normal distribution

Question: Given a standard generator with uniform distribution, generate a normally distributed sequence of random numbers.
Answer: Box-Muller transform!

http://en.wikipedia.org/wiki/Box%E2%80%93Muller_transform

Source snippet:

class NormalRandom
{
        private bool haveNextRandom = false;
        private  double nextRandom = 0;
        private  Random rnd = new Random();

        /// <summary>
        /// Implements random number generator with normal distribution

        /// based on the polar form of Box-Muller transform.

        /// </summary>
        /// <returns>A random number with normal distribution.</returns>

        public double NextDouble()

        {

            if (haveNextRandom)

            {

                haveNextRandom = false;

                return nextRandom;

            }

            double x1, x2, w;

            do

            {

                x1 = 2.0 * rnd.NextDouble() - 1.0;

                x2 = 2.0 * rnd.NextDouble() - 1.0;

                w = x1 * x1 + x2 * x2;

            } while (w >= 1.0);

            w = Math.Sqrt((-2.0 * Math.Log(w)) / w);

            nextRandom = x2 * w;

            haveNextRandom = true;

           return x1 * w;

        }

}

...and here are the results:

Graphics in console application

A long, long time ago when programming for Windows you had to make a choice - your application would have to be either console, or GUI, but not both. If you liked your app for the console subsystem, you could not create windows or dialog boxes, and the application did not have a message loop. If you were a GUI app, you could only use console if you created it yourself, and your app could not inherit its parent's console.

At some point down the line this got fixed, so a console application today can have UI elements - for example, it can call MessageBox(). Despite the weirdness - I am sure HCI purists/Apple would never approve of it - it can actually come quite handy. I, for one, quite often find myself in need of a graphic in the middle of a simple application (sometimes to just visualize something as part of a debug code path) - which I don't want to convert to fully-fledged GUI.

Unfortunately, there is precious little information on how to do do mixed mode console/GUI programming on the Internet, so I figured I'd fill the void :-).

First add references to System.Windows.Forms and System.Drawing (only if you are going to be drawing of course) to your app, as well as the corresponding "using"s.

Then you can create a dialog box that derives from Form:

    using System.Windows.Forms;
    class MyForm : Form
    {
    }

...and display it as follows:

    MyForm f = new MyForm();
    f.ShowDialog();

ShowDialog function is blocking - your console thread will not get control until user closes the window. Of course, standard console functions all work, you can print to the screen like so:


    class MyForm : Form
    {
        protected override void OnPaint(PaintEventArgs e)
        {
            base.OnPaint(e);
            Console.WriteLine("Paint called!");
        }
    }

As an example, here is a very simple application that allows a user to plot simple functions from Math library:

//-----------------------------------------------------------------------

// 

// Copyright (C) Sergey Solyanik.

//

// This file is subject to the terms and conditions of the Microsoft Public License (MS-PL).

// See http://www.microsoft.com/opensource/licenses.mspx#Ms-PL for more details.

// 

//----------------------------------------------------------------------- 

using System;

using System.Drawing;

using System.Reflection;

using System.Windows.Forms;

namespace Graph

{

    class Graph : Form

    {

        public delegate double Function(double x);

        public Function F;

        public double X1;

        public double X2;

        public double Y1;

        public double Y2;

        private double stretchX;

        private double stretchY;

        private int ToScreenX(double x)

        {

            return ClientRectangle.Left + (int)((x - X1) * stretchX);

        }

        private int ToScreenY(double y)

        {

            return ClientRectangle.Bottom + (int)((y - Y1) * stretchY);

        }

        private double ToPlaneX(int x)

        {

            return X1 + ((double)(x - ClientRectangle.Left)) / stretchX;

        }

        private double ToPlaneY(int y)

        {

            return Y1 + ((double)(y - ClientRectangle.Bottom)) / stretchY;

        }

        protected override void OnPaint(PaintEventArgs e)

        {

         base.OnPaint(e);

            stretchX = (double)(ClientRectangle.Right - ClientRectangle.Left) / 

                (X2 - X1);

            stretchY = (double)(ClientRectangle.Top - ClientRectangle.Bottom) /

                (Y2 - Y1);

            if (Math.Sign(X1) != Math.Sign(X2))

            {

                e.Graphics.DrawLine(

                    Pens.Black,

                    ToScreenX(0),

                    ClientRectangle.Bottom,

                    ToScreenX(0),

                    ClientRectangle.Top);

            }

            if (Math.Sign(Y1) != Math.Sign(Y2))

            {

                e.Graphics.DrawLine(

                    Pens.Black,

                    ClientRectangle.Left,

                    ToScreenY(0),

                    ClientRectangle.Right,

                    ToScreenY(0));

            }

            for (int x = ClientRectangle.Left; x < ClientRectangle.Right - 1; ++x)

            {

                e.Graphics.DrawLine(

                    Pens.Blue,

                    x,

                    ToScreenY(F(ToPlaneX(x))),

                    x + 1,

                    ToScreenY(F(ToPlaneX(x + 1))));

            }

        }

    }

    class Program

    {

        private static Graph.Function SelectFunction()

        {

            Console.WriteLine("Available functions:");

            Type t = typeof(Math);

            MethodInfo[] m = t.GetMethods();

            for (int i = 0; i < m.Length; ++i)

            {

                if (m[i].IsPublic && m[i].IsStatic && m[i].ReturnType == typeof(double))

                {

                    ParameterInfo[] p = m[i].GetParameters();

                    if (p.Length == 1 && p[0].ParameterType == typeof(double))

                        Console.WriteLine("    " + m[i].Name);

                }

            }

            while (true)

            {

                Console.Write("Select a function to plot: ");

                string response = Console.ReadLine();

                for (int i = 0; i < m.Length; ++i)

                {

                    if (m[i].IsPublic && m[i].IsStatic && m[i].ReturnType == typeof(double))

                    {

                        ParameterInfo[] p = m[i].GetParameters();

                        if (p.Length == 1 && p[0].ParameterType == typeof(double))

                        {

                            if (m[i].Name.Equals(response))

                            {

                                return (Graph.Function)

                                    Delegate.CreateDelegate(typeof(Graph.Function), m[i]);

                            }

                        }

                    }

                }

            }

        }

        private static double GetNumber(string prompt)

        {

            for (; ; )

            {

                Console.Write(prompt);

                string response = Console.ReadLine();

                double result;

                if (double.TryParse(response, out result))

                    return result;

            }

        }

        static void Main(string[] args)

        {

            Console.CancelKeyPress += delegate

            {

                Console.WriteLine("Cancelled!");

                Environment.Exit(1);

            };

            Console.WriteLine("Press Ctrl-C to quit.");

            Console.WriteLine();

            Graph g = new Graph();

            g.F = SelectFunction();

            g.X1 = GetNumber("Abscissa lower boundary: ");

            g.X2 = GetNumber("Abscissa upper boundary: ");

            g.Y1 = GetNumber("Ordinate lower boundary: ");

            g.Y2 = GetNumber("Ordinate upper boundary: ");

            g.ShowDialog();

        }

    }

}

War on Christmas

WCF web services and a calculator implementation in one easy snippet!

I wanted to write a calculator that supported parentheses and operator precedence for a while, but never got to sit down and do it. Recently I was poking around WCF (yes, I know I am VERY late for that party!) and wanted something less trivial than "Hello, world" to explore it. Suddenly, it felt like a reasonable opportunity to kill two birds with one stone.

Below is an implementation of a calculator web service. A problem like this is most frequently dealt with using a parse tree, and this solution is no exception. A parse tree is a binary tree representation of an expression which makes the result very easy to calculate by recursive evaluation. Our service exposes two APIs: one takes a string and returns a computed result, the other returns the parse tree for the expression for educational purposes (and to give WCF something non-trivial to marshal).

A parse tree has operators such as +, -, *, and / stored in the nodes with the children of the nodes being the operands. For example, 2 + 2 would generate the following parse tree:

                             +
                2                        2

A more complex example, 3 * 4 + 2 will result in:

                             +
                 *                       2
     3                    4

Once a parse tree is built, the evaluation is trivial: at every node, apply evaluation recursively to the children, then perform the arithmetic operator on the results. The trick here is to build it, as its construction must account for the operator precedence, parentheses, and such.

The  data structure for the node contains an operator, its two children (only would of which will be set for unary operator and in other cases), the parent, and value field used for nodes that represent values. A parenthesized subexpression lives under the separate node rooted in its right child, as illustrated below:

2 * (3 + 5) =>

           *
2                     ()
                                 +
                         3               5

The program moves alongside the expression and adds the nodes corresponding to the tokens it parses to the tree. For example, given the following expression: 2 + 2 + 2 it will:
1) Read 2, create a value node for 2, and remember it as its current node:

                        2 <=

2) Read +, create an operator node for +, set node for 2 as its left child:

                         + <=
               2

3) Read 2, create a value node for 2, and add it to the current (+) node as its right child;


                         +
               2                    2 <=


4) Read +, create an operator node for +, set node for 2 as its left child and hooking it in place of the value node under the earlier +:


                         +
               2                   + <=
                          2

5) Read 2, create a value node for 2, and add it to the current (+) node as its right child;

                         +
               2                   +
                          2                 2 <=

How does the operator precedence work in this scheme? It is encoded in the tree itself. Note that the tree for 3 * 4 + 2 must be built as follows:


                             +
                 *                       2
     3                    4

and not like this:

                 *
     3                    +
                  4                 2

The later would treat the expression as 3 * (4 + 2), which is, of course incorrect. However, this would be the tree that a naive algorithm that just reads the next token and stuffs it into a tree would build.

To account for operator precedence, before adding a new operator node, our algorithm would look at the parent nodes of its current position and if the operator at that node has a higher precedence than the operator we are about to add, it will move up the chain and hook the new node above all the higher-precedence operators, so the tree construction for 3 * 4 * 5 + 2 will proceed like this;

3<=  =>       *<=   =>       *           =>        *             =>       *              =>             +

               3                    3      4<=           3     * <=             3    *                       *        2

                                                                  4                          4   5 <=            3   *

                                                                                                                          4  5

Once this concept is clear, the rest is pure accounting (as is most of the software development :-)). The code below implements it and publishes the results through a template implementation of WCF web service, which takes on the order of 7 functional lines of code (at the very end, in the main function).

//-----------------------------------------------------------------------
//
// Copyright (C) Sergey Solyanik.
//
// This file is subject to the terms and conditions of the Microsoft Public License (MS-PL).
// See http://www.microsoft.com/opensource/licenses.mspx#Ms-PL for more details.
//
//----------------------------------------------------------------------- 
using System;
using System.ServiceModel;
using System.ServiceModel.Description;
using System.Runtime.Serialization;


namespace WCFCalc
{
    [ServiceContract]
    public interface IWCFCalc
    {
        [OperationContract]
        int Calculate(string expr);


        [OperationContract]
        ExprNode Parse(string expr);
    }


    public enum Operator
    {
        PLUS,
        MINUS,
        MUL,
        DIV,
        VAL,
        EXPR,
        OPENPAREN,
        ERROR
    }


    [DataContract]
    public class ExprNode
    {
        [DataMember]
        public ExprNode Left;
        
        [DataMember]
        public ExprNode Right;


        // This is not exported because the
        // serialization would take it as a
        // circular reference.
        public ExprNode Parent;


        [DataMember]
        public Operator Op;


        [DataMember]
        public int Value;
    }


    public class WCFCalcSvc : IWCFCalc
    {
        private void Err(string s)
        {
            Console.WriteLine(s);
            throw new FaultException(
                new InvalidOperationException(s), s);
        }


        private Operator ToOp(char c)
        {
            switch (c)
            {
                case '+': return Operator.PLUS;
                case '-': return Operator.MINUS;
                case '*': return Operator.MUL;
                case '/': return Operator.DIV;
                default: return Operator.ERROR;
            }
        }


        private bool HigherPrecedence(Operator o1, Operator o2)
        {
            if ((o2 == Operator.PLUS || o2 == Operator.MINUS) &&
                (o1 == Operator.MUL || o1 == Operator.DIV))
                return true;


            return false;
        }


        int Calculate(ExprNode expr)
        {
            if (expr.Op == Operator.VAL)
                return expr.Value;


            if (expr.Op == Operator.EXPR)
                return Calculate(expr.Right);


            if (expr.Op == Operator.PLUS)
                return Calculate(expr.Left) + Calculate(expr.Right);


            if (expr.Op == Operator.MINUS)
            {
                if (expr.Left == null)
                    return -Calculate(expr.Right);


                return Calculate(expr.Left) - Calculate(expr.Right);
            }


            if (expr.Op == Operator.MUL)
                return Calculate(expr.Left) * Calculate(expr.Right);


            if (expr.Op == Operator.DIV)
                return Calculate(expr.Left) / Calculate(expr.Right);


            Err("Internal error: unknown operator!");
            return 0;
        }


        public int Calculate(string expr)
        {
            return Calculate(Parse(expr));
        }


        public ExprNode Parse(string expr)
        {
            int x = 0;
            ExprNode current = null;
            while (x < expr.Length)
            {
                if (expr[x] == ' ')
                {
                    ++x;
                    continue;
                }


                if (expr[x] == '(')
                {
                    ++x;


                    ExprNode node = new ExprNode();
                    node.Op = Operator.OPENPAREN;
                    if (current == null)
                    {
                        current = node;
                        continue;
                    }


                    if ((current.Op == Operator.VAL) ||
                        (current.Right != null))
                    {
                        Err("Error @ " + x);
                    }


                    node.Parent = current;
                    current.Right = node;
                    current = node;
                    continue;
                }


                if (expr[x] == ')')
                {
                    ++x;


                    while (current != null && current.Op != Operator.OPENPAREN)
                        current = current.Parent;


                    if (current == null)
                        Err("Error @ " + x);


                    // Close the paren
                    current.Op = Operator.EXPR;
                    continue;
                }


                Operator op = ToOp(expr[x]);
                if (op != Operator.ERROR)
                {
                    ++x;


                    ExprNode node = new ExprNode();
                    node.Op = op;


                    // currently no support for unary ops
                    if (current == null ||
                        (current.Op != Operator.VAL &&
                        current.Op != Operator.EXPR))
                    {
                        if (op == Operator.MINUS)
                        {
                            node.Parent = current;
                            if (current != null)
                                current.Right = node;
                            current = node;
                            continue;
                        }


                        Err("Error @ " + x);
                    }


                    // This ensures that the higher precedence
                    // operators are lower in the expression
                    // tree, and therefore execute before the
                    // lower precedence operators.
                    while (current.Parent != null &&
                        current.Parent.Op != Operator.OPENPAREN &&
                        !HigherPrecedence(op, current.Parent.Op))
                    {
                        current = current.Parent;
                    }


                    node.Parent = current.Parent;
                    if (current.Parent != null)
                        current.Parent.Right = node;
                    current.Parent = node;
                    node.Left = current;
                    current = node;


                    continue;
                }


                // value
                if (expr[x] >= '0' && expr[x] <= '9')
                {
                    int n = 0;
                    while (x < expr.Length && (expr[x] >= '0' && expr[x] <= '9'))
                    {
                        n = n * 10 + (expr[x] - '0');
                        ++x;
                    }


                    ExprNode node = new ExprNode();
                    node.Op = Operator.VAL;
                    node.Value = n;
                    if (current == null)
                    {
                        current = node;
                        continue;
                    }


                    if (current.Op == Operator.VAL)
                        Err("Error @ " + x);


                    if (current.Right != null)
                        Err("Error @ " + x);


                    node.Parent = current;
                    current.Right = node;
                    current = node;
                    continue;
                }
            }


            while (current != null && current.Parent != null)
            {
                if (current.Op == Operator.OPENPAREN)
                    Err("Not enough closed parens!");


                current = current.Parent;
            }


            if (current != null && current.Op == Operator.OPENPAREN)
                Err("Not enough closed parens!");


            return current;
        }
    }


    class Program
    {
        static void Main(string[] args)
        {
            Uri baseAddress = new Uri("http://localhost:8000/Calculator");
            ServiceHost selfHost = new ServiceHost(typeof(WCFCalcSvc), baseAddress);
            try
            {
                selfHost.AddServiceEndpoint(
                    typeof(IWCFCalc),
                    // DANGER! DO NOT CARRY SecurityMode.None
                    // INTO PRODUCTION SERVICE BY DEFAULT!!!
                    new WSHttpBinding(SecurityMode.None),
                    "Calculator");




                ServiceMetadataBehavior smb = new ServiceMetadataBehavior();
                smb.HttpGetEnabled = true;
                selfHost.Description.Behaviors.Add(smb);


                selfHost.Open();
                Console.WriteLine("The service is ready.");
                Console.WriteLine("Press to terminate service.");
                Console.WriteLine();
                Console.ReadLine();


                selfHost.Close();
            }
            catch (CommunicationException ce)
            {
                Console.WriteLine("An exception occurred: {0}", ce.Message);
                selfHost.Abort();
            }
        }
    }
}

To compile the service, create an empty console project, add System.Runtime.Serialization and System.ServiceModel to the list of references, and copy the code into it.

To consume the service, create a client project with the following code:

//-----------------------------------------------------------------------

//

// Copyright (C) Sergey Solyanik.

//

// This file is subject to the terms and conditions of the Microsoft Public License (MS-PL).

// See http://www.microsoft.com/opensource/licenses.mspx#Ms-PL for more details.

//

//----------------------------------------------------------------------- 

using System;

using WCFTestClient.WCFCalc;

namespace WCFTestClient

{

    class Program

    {

        static void Print(ExprNode n)

        {

            Console.Write("(" + n.Op + " ");

            if (n.Left != null && n.Right != null)

            {

                Print(n.Left);

                Console.Write(", ");

                Print(n.Right);

                Console.Write(")");

            }

            else if (n.Left != null || n.Right != null)

            {

                Print(n.Left != null ? n.Left : n.Right);

                Console.Write(")");

            }

            else

            {

                Console.Write(n.Value + ")");

            }

        }

        static void Main(string[] args)

        {

            WCFCalcClient svc = new WCFCalcClient();

            for (; ; )

            {

                Console.Write("> ");

                string s = Console.ReadLine();

                if (s.Equals("exit", StringComparison.OrdinalIgnoreCase))

                    break;

                try

                {

                    if (s.StartsWith("p"))

                    {

                        s = s.Substring(1);

                        ExprNode n = svc.Parse(s);

                        Print(n);

                        Console.WriteLine();

                    }

                    else

                    {

                        Console.WriteLine(s + " = " + svc.Calculate(s));

                    }

                }

                catch (Exception e)

                {

                    Console.WriteLine(e.Message);

                }

            }

        }

    }

}

As you can see, it only takes 1 line of code (!) to connect to our service. The rest constitutes the logic of the program itself.

Now run the service from a command line. Right-click on Service References, select "Add Service Reference", point it to http://localhost:8000/Calculator, set WCFCalc as a namespace, and click import. That's it - you are done. The service importer will create app.config with all the endpoint details, you can now just run the client.

Prefix your expression with p to display the parse tree for it, like so: p2+2, or type "exit" to leave.

Pepper spray

"It is becoming more and more fashionable right now, this day and age, to use chemical on people who have an opinion. And that to me is a complete lack of leadership both in the police department and other people who cannot really deal with the root of the problem and they want to spray people to quiet them down. And it’s really not supposed to be that. It’s not a thing that solves any problem nor is it something that quiets people down.”

Kamran Loghman, inventor of modern pepper spray and developer of police procedures for its use

http://boingboing.net/2011/11/30/pepper-spray-inventor-its.html

"War on militancy"

The attack comes as relations between the United States and Pakistan — its ally in the war on militancy — are already strained following the killing of al-Qaida leader Osama bin Laden by U.S. special forces in a secret raid on the Pakistani garrison town of Abbottabad in May.
http://www.msnbc.msn.com/id/45442885/ns/world_news-south_and_central_asia/#.TtDjXPLCcSg

Our ministry of self-censorship is clearly still recovering from a Thanksgiving dinner today...

Economics, as understood by Alan Greenspan

http://cscs.umich.edu/~crshalizi/weblog/841.html

State secrets

"By the way, during seven of the eight George W. Bush years, the IRS report on the top 400 taxpayers was labeled a state secret, a policy that the Obama administration overturned almost instantly after his inauguration."
http://wweek.com/portland/article-17350-9_things_the_rich_dont_want_you_to_know_about_taxes.html

Hiring at elite companies

A friend sent me a pointer to this blog post: http://econlog.econlib.org/archives/2011/11/how_elite_firms.html
The original paper is about hiring practices in financial institutions, but the fact that the best companies prefer applicants from the best universities (much in the same way the top grad schools mostly accept people from the top undergrad schools) is a recurring complaint in software industry as well.

In all cases the preferential treatment is driven by selectivity of the school, not so much by the quality of skills developed there: the idea is that since colleges are highly selective, you can apply them as the first filter to the applicant pool. The system then continues - the resumes from the candidates working at the top companies draw more attention than the resumes from lesser brands, and so it goes.

Which means that if you missed out on a good school early on, you are kinda screwed; while upward mobility is not impossible, it becomes much, much harder.

A long time ago I experienced something similar myself. When I came to the United States, I took the GRE and applied to several top graduate programs in physics. My GRE scores were far, far above the published average scores for all of these programs except MIT, where it was closer to (but still above) average.

In the Soviet Union where I was from, test results were the only allowed criteria for admission. There was no concept of reference letters, legacy status, nor other out-of-band information that would feed into the decision making process. In fact, anything resembling legacy considerations were considered corruption and would earn all involved parties a one-way, all expenses paid, trip to Siberia's finest labor camps (corruption did of course exist, and when discovered it was dealt with harshly; one of the people on my alma mater admission committee ended up in jail for bartering admissions spots for favors from other well-connected people).

Imagine my surprise when I got the rejection letter from UPenn - UPenn! - where the average subject GRE score was in 600s! At the time I did not know what a "safety school" was, but if I did I have thought about it as such at the time. I only applied to UPenn because I lived in Philadelphia at the time, all our relatives lived there, and I needed to show that I was not dismissing the idea of staying "close to the family" outright.

Completely baffled, I wrote them a letter, pointing out the huge discrepancy in the scores and asking them to explain the decision. Soon I befriended another Russian who had emigrated a year earlier and who filled me in on admission practices in the US. According to him, most of the people in the theoretical physics department at Princeton did not even take the GRE - which was listed as a requirement.

Instead, they were being accepted based strictly on references from their undergrad professors. And because people from the top grad schools knew people from the top undergrad schools, their references were trusted far more.

I, on the other hand, was completely unaware of the relative importance of the references, so I got them from random people who were unknown to the admissions committees, and so my application was roundly rejected - the letters from all the other schools arrived a bit later. (UPenn later reversed its decision and accepted me - they must have read my letter and decided that a guy so naive would end up living under a bridge were they not to save me).

But I digress.

This system of course leads to very high rate of false negatives - essentially, first strike out. Also, not surprisingly, it results in some amount of false positives as well - once inside, you have a larger than normal share of opportunities to recover from previous failures - regardless of your skills, that degree from Harvard will keep opening doors for you years from now.

The system is obviously sub-optimal, so over the years we tried our best to fix it. Microsoft pioneered the concept of a coding interview - where people are forced to write code on the whiteboard as part of the interview process, a system that is now standard almost everywhere.

http://www.amazon.com/Would-Move-Mount-Microsofts-Puzzle/dp/0316919160
http://www.amazon.com/Cracking-Coding-Interview-Programming-Questions/dp/1466208686

This is infinitely better than hiring people based strictly on their resume and some feel-good conversation during the interview, but it is not entirely fool-proof.

First, it emphasizes a set of skills - specifically, algorithm design - that are not all that frequently required in the actual jobs that people do. Ask yourself, how many times have you had to write quick sort, a hash table, an AVL tree, or a read-write lock implementation at work (and if you did, I would really be interested to know why :-)). The vast majority of people - especially those who work on maintaining very large code bases - like Windows - simply do not get the opportunity to exercise their algorithmic muscle very often.

Yet these are all fair questions during the interview. Don't get me wrong - I BELIEVE that these are fair questions, and I ask them myself: even if you don't need to code hashtables every day, it still helps to know how they work.

For example, I ran into a situation at a hiring committee at Google where an interviewer was unhappy that the interviewee could not find an O(1) solution to a problem that - as far as I was concerned - did not have one. When I asked how exactly could one solve it in O(1) time, the person said - why, by using a hash, of course! Put a person who is convinced that a hash always exhibits O(1) performance on an OS component, and you are in for a number of interesting and intractable performance bugs down the road.
So knowing algorithms and data structures well is very important, but our jobs are not preparing us for that. Which is why I found that often hiring a person from college - especially, an elite college - is easier than hiring a person from the industry - they have not yet had time to forget the theory.

Also, knowing the things that are testable in the coding interview - algorithms, design practices, etc - is necessary, but not sufficient for engineering stardom. I've seen - and hired! - a number of people who were fantastic during the interview, but were very ineffective when they needed to deal with a real engineering problem - such as fixing a complex bug in a large system in a way that does not break existing functionality. To this day I have no idea how to do a practical examination of this skill in an interview setting!

Meanwhile, the candidate pool is huge, and the resumes are mostly BS. I once did an experiment. We needed a contractor for web development - AJAX, Javascript, things like that. So I took every person who claimed to be an expert in Web development on the resume that the contract agencies gave me for a standardized test - about 20 people in all. The test was not very advanced. The questions were "What is a closure in Javascript?", "What is the difference between A.foo = 'bar'; and A.prototype.foo = 'bar';", etc - introductory stuff. The best person on the test scored 25%. The average was below 10%.

Therein lies the cornerstone problem of the software industry, which I will summarize thus:

1) Success of a software company is dependent on hiring great people. A star software engineer is an order of magnitude more productive than an average engineer, but costs only marginally more. Thus there is a huge incentive for companies to hire the best of the best.

2) Many qualities of the best of the best engineers are very hard to measure directly. We can test problem solving, knowledge, and design skills during the interview, but we are forced to rely on a candidate's word when it comes to equally important qualifications such as ability to face ambiguity, passion, leadership, and working with others.

3) There is a huge pool of candidates. The resume databases at the top companies have literally millions of entries. Most of the resumes are "enhanced" for "quality".

4) Vast majority of the candidates are not... well, they are not in the top 10% :-). They may be enough to perform a lot of the jobs adequately, but they are nowhere near the productivity of the best of the best (see #1), and once the job for which they were hired is done, they may not be easily transferable to a different one.

5) Firing someone from a big company requires a lot of work, is a very lengthy process, and so the cost of false positive is very high - both in the company's bottom line as well as in morale of the team.

So... what do we do? How do we even screen the resumes - in a fully meritocratic system that pays no attention to selectivity of the previous places of work or study - given the pure amount of BS in an average sample?

The existing system that relies both on the selectivity of the environment as well as on the interview performance works in the sense that everything else we tried was worse.

After all, I do not ever see anything near the stuff people reported on this thread at work: http://www.reddit.com/r/AskReddit/comments/mk7yn/managers_supervisors_and_hr_people_of_reddit_tell/. As a matter of fact, even things worthy of the Daily WTF (http://thedailywtf.com/Default.aspx) almost never come up - at least as long as you are staying inside MSFT product development teams.

This does not mean that the system cannot be improved further - but how? Your ideas are welcome in the comments.