Saturday, October 11, 2008

Great Thomas Friedman Quote

I heard this quote from a presentation given at this year's National Academy of Engineering induction ceremony. It really drove home a great point, and gave me a lot of direction into what I'm really looking for in an economic recovery as well as a presidential candidate I can support.

From NY Times columnist Thomas Friedman

"We need to get back to making stuff, based on real engineering not just financial engineering."
http://www.nytimes.com/2008/09/28/opinion/28friedman.html

Friday, October 03, 2008

How I Interview Software Engineer Candidates

Generally my interviews go like this. They may fluctuate depending on the skill of the candidates, but in almost all cases, this line of questions is sufficient to determine the skill of the candidate, without any ambiguity.

I introduce myself to the candidate and I let them know what I do, what I’m responsible for and also my level of technical detail. I’ll also at this point let them know that the interview is going to be technical one.

Then I’ll setup the next line of questioning. I try to get a feel for how well they remember their data structures. I then let them know I’ll be talking to them about the Binary Search Tree. Then, I let them know that I’m not necessarily worried about whether or not they remember all the details, but am focusing on their problem solving skills.

Sometimes the candidate tries to make this problem more complicated than it is by thinking about balancing the binary search tree. So I usually let them know at this point if they have some recollection of binary search trees that they shouldn’t worry about balancing the tree and that unbalanced trees are perfectly fine for this example. If the candidate does seem to remember these concepts fairly well, then maybe I’ll ask later on how they would go about balancing a BST.

The first question I ask is if they remember the properties of the binary search tree. If they don’t then I ask them if they could describe a general tree structure. Anyone with any sort of programming background should be able to describe a tree. If they recall the tree structure, but don’t recall the BST, I let them know the properties of a BST. What I am getting to here is that I want it to be clear that a BST is tree structure in which the value of the left node is less than the parent node’s value, and the value of the right node is greater than the parent node’s value.

Here’s where we get into the question. Usually I give them this simple array (now, you might be thinking this is really simple, but you’d be so surprised at how few people actually get this stuff.)

[4, 2, 6, 1, 7, 3, 5]

Then I’ll ask them to walk me through how they would take that array of values and arrange them in a BST structure, if they were serially iterating over that array, and not using any temporary storage devices (they almost always want to go to 1 first, and I almost always tell them that they can’t do that, because they’ll be losing their place in the array.)

I’m expecting something like the following:

clip_image002Step 1

clip_image004Step 2

clip_image006Step 3

clip_image008Step 4

clip_image010Step 5

clip_image012Step 6

clip_image014Step 7

Simple right?  You should see some of the answers I get.

Once they’ve successfully done that, I ask them what the advantages of this structure are over an array. I’m expecting to hear that it is more performant than an array because the search time is less as it divides the results based upon the path of the tree. If they’re totally up to speed on this, I’ll ask them the order of magnitude of this performance gain.  I’m expecting to hear log(n).

Once we’ve chatted about this, I’ll ask the candidate to model a BST in the language they are most comfortable in.  In C#, I'm looking for an answer like so:

public class BST
{
    public int Value;
    public BST LeftNode;
    public BST RightNode;
    public BST(int value, BST leftNode, BST rightNode)
    {
        Value = value;
        LeftNode = leftNode;
        RightNode = rightNode;
    }
}

 

Sometimes they don't get to exactly this (again, you'd be surprised at some of the answers that you get here.)  So what I'll do is discuss why they did it the way they did, and then we eventually end up here.

Next I'll ask them to construct a simple tree that looks like step 3 above using the constructor that they've defined above.  What I'm expecting is something like this:

BST myBst = new BST(4, new BST(2, null, null), new BST(6, null, null));

 

Usually they'll have three or four lines of code for the constructor.  If they do, I'll immediately ask them to get it down to a single line of code.

After this I'll do some small, short questions off of their resume, and dig in a bit about what they're doing.

After that I'll ask them "What questions do you have for me?"  It's important to phrase it this way because it insinuates an expectation that they have questions for me.

All of this usually fits into a 45 minute time slot, which is usually what I've been given as an interviewer historically.

Again, this simple flow really gives me a great idea of the candidate's technical skill.  It works really well for entry level to mid-level candidates, it can be language agnostic, and it's really unambiguous.

Why am I writing about this?  Well, I'm going to switch it up.  I'm going to stick to this type of questioning, but I think I'm going to try a new computer science concept.  Could be another structure, could be a sorting algorithm, could be a balancing problem, who knows.

ADO.NET Data Services (Project "Astoria") Query Interceptors

One of the interesting/handy features in ADO.NET Data Services is called query interceptors.  Query interceptors give you the ability to take action on the items returned from the service.

Each Query Interceptor is a method defined in your service and attributed with a QueryInterceptor interface.    The attribute takes an argument of the type of entity in which it is responsible for acting upon.  The results for all requests for this type of entity will then pass through the interceptor.

The interceptor is implemented as a lambda expression, using the Expression and Func types in C#.  An example of a Query Interceptor is below.  You see that it returns a generic Expression type with a specific type of Func, that takes an employee, and returns a boolean.

[QueryInterceptor("Employee")]
public Expression<Func<Employee, bool>> OnQueryEmployee()
{
 
    return pc => pc.Manager.LoginID.Equals("adventure-works\\"
                        + HttpContext.Current.User.Identity.Name) ||
        pc.LoginID.Equals("adventure-works\\"
            + HttpContext.Current.User.Identity.Name);
}

 

This is a pretty cool way of filtering/altering your results,  but what you have to keep in mind is that this expression is going to execute on each of the entities returned from the request.  I'll follow up with a post on another feature of ADO.NET Data Services called Service Operations that allows you to act upon a set of records.

Thursday, October 02, 2008

W3C Selectors API

CSS Selectors have been a slick way of finding elements in the DOM. Something as simple as the following would select all the td tags that are children of a tbody tag within an table with the id of "score" and set the background color to gray.


<style>
#score>tbody>tr>td { background: gray; }
</style>

The selectors syntax for CSS 2.1 is simply described below:

Picture 1.png
Until I became familiar with JQuery, I had been ignorant of the fact that the syntax I've been using for CSS styles would be a fantastic way to get things out of the DOM from Javascript.

Now, the W3C standards body is introducing a selector API that will be available in both IE 8 and Firefox 3.1. So the following syntax will do the same selection as above, except available in javascript:

var cells = document.querySelectorAll("#score>tbody>tr>td");

The W3C draft says that all objects that implement Document, DocumentFragment and Element interfaces, must now also implement the NodeSelector interface.

The NodeSelector interface is defined as follows:

interface NodeSelector {
Element querySelector(DOMString selectors);
NodeList querySelectorAll(DOMString selectors);
};

Pretty cool stuff.

Of course, with every step towards a common implementation across browsers, there's awlays a catch. The selectors syntax is different between CSS 2.1 and CSS 3. And of course IE has decided to use CSS 2.1 selector syntax, and Firefox is using CSS 3. So, you'll probably want to make sure you write for CSS 2.1. Below is a summary of differences:

  • the list of basic definitions (selector, group of selectors, simple selector, etc.) has been changed; in particular, what was referred to in CSS2 as a simple selector is now called a sequence of simple selectors, and the term "simple selector" is now used for the components of this sequence

  • an optional namespace component is now allowed in type element selectors, the universal selector and attribute selectors

  • a new combinator has been introduced

  • new simple selectors including substring matching attribute selectors, and new pseudo-classes

  • new pseudo-elements, and introduction of the "::" convention for pseudo-elements

  • the grammar has been rewritten

  • profiles to be added to specifications integrating Selectors and defining the set of selectors which is actually supported by each specification

  • Selectors are now a CSS3 Module and an independent specification; other specifications can now refer to this document independently of CSS

  • the specification now has its own test suite