Joel Spolsky is a BadAss once again

on Tuesday, January 26, 2010

So, this has probably been discussed by thousands of bloggers. But, Joel Spolsky “revealed” one of the questions he asks to potential interns (http://itc.conversationsnetwork.org/shows/detail4359.html). But, I want to take my stab at it; and how to think about it as an interviewer.

Before hand; here’s Joel Spolsky’s description about why he setup this test: “Asking them to code in front of you is a way for you to figure out if they are smart. … We want to see them doing it. Because, we want to hear them think, we want to see them think, we want to see how quickly they are doing it. We want proof they can do it. Because anybody can generate code for a million dollars. To get a job they will somehow find a way. You think they’re not asking their friends for help?” (summarized quote).

The question he asked was:

“Given an array of numbers. And, given a pointer into the middle of the array of numbers. It doesn’t have to be the middle, just an element within that array of number. Like the 37th element. Does all of the numbers summed up to the left of that pointer equal the sum of all the elements to the right of that pointer?”

When I was listening to that podcast my brain immediately sprung into work. Ignoring the rest of Joel’s words, I started trying to figure out how to program a solution to the problem. My initial solution to the problem was really ugly, because I started thinking of the solution as soon as he said “37th”. It was like my brain started to solve an SAT problem without reading the whole question.

So, I jumped on the computer, loaded up VS, and started to write a function that would do the quick and dirty solution:

static bool IsArrayEqual(int[] arr, int splitIndex)
{
int leftSum = 0, rightSum = 0;

for (int i = 0; i < arr.Length; i++)
{
if (i == splitIndex)
{
i++;
continue;
}

if (i < splitIndex)
{
leftSum += arr[i];
}
else
{
rightSum += arr[i];
}
}

return leftSum == rightSum;
}

As you can see the solution featured a straight O(n) algorithm with if statements in between.

It was a  really stupid solution. As soon as I looked over the code the first gut wrenching reaction was to remove the if statements. If statements are always branch statements to the compiler; and if the forward look ahead fails then they are costly. So, I rewrote the function to exclude the if statements.

static bool IsArrayValuesEqual(int[] arr, int splitIndex, out int leftSum, out int rightSum )
{
leftSum = SliceSum(arr, 0, splitIndex - 1);
rightSum = SliceSum(arr, splitIndex + 1, arr.Length - 1);

return leftSum == rightSum;
}

static int SliceSum(int[] arr, int startIndex, int endIndex)
{
int sum = 0;
for (int i = startIndex; i < endIndex; i++)
sum += arr[i];
return sum;
}

At this point I was pretty proud of myself. With no reason to be. Why be proud of a solution to an intern question? Because I was able to figure out an answer in under 5 minutes? Because no entry level programmer could write this code? WTF?? This code is “entry level”. The only reason I know it is because I know of all the .NET design practices that make this code shit. So, I was proud of shit code.

At this point I decided that I was going to going to make something useful out of this wasted time. I hadn’t thought of blogging about this (and, as I am blogging about this; I still don’t think of this as a useful means to my wasted time). But, I did think there must be a better way to look at the problem and find some usage from it.

It hit me immediately, I should make a comparison test. Something like a unit test, but not as useful. I should write a loop which will dynamically populate the integer array and when the elements to the left of the pointer are equal to the elements to the right of the pointer it will be a success:

var rand = new Random(DateTime.Now.Millisecond);
bool isEqual;
do
{
int[] arr = new int[100];
for (int i = 0; i < arr.Length; i++)
{
arr[i] = rand.Next(100);
}

isEqual = IsArrayEqual(arr, 37);
Console.WriteLine("Are equal: {0}", isEqual);
} while (!isEqual);

The test worked around the 100000th try, but I was confused by the way my computer handled the test. I thought that my computer would eat up all processor time trying to produce a result. But it didn’t. It used 2 processors. And, my comp has 8 procs (Core i7). So, I decided to rewrite the test code to use the Parallel library in .NET 4.0.

That turned into a bit of a research mission. Apparently, I couldn’t use the Parallel library without a For loop. And, my algorithm was using a Do … While loop. What was I to do? After a little looking, I found that .NET 4.0 allowed for multi-threading through lamba expressions and anonymous functions. It wasn’t the same as a Parallel loop, but it allowed for multi-threading.

So, I added a wrapper function around the code and executed multiple threads using anonymous functions:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace FogCreekInternTest
{
class Program
{
static void Main(string[] args)
{

int j = 0;
var isEqual = false;
int leftSum, rightSum;
var rand = new Random(DateTime.Now.Millisecond);
var found = false;

for (int t = 0; t < 5; t++)
{
Task.Factory.StartNew<bool>((threadNumber) =>
{
do
{
int[] arr = new int[100];
for (int i = 0; i < arr.Length; i++)
{
arr[i] = rand.Next(100);
}

isEqual = IsArrayValuesEqual(arr, 37, out leftSum, out rightSum);
Console.WriteLine("[{4}:{0}] Are equal: {1}\tleftSum: {2}, rightSum: {3}", j++, isEqual, leftSum, rightSum, threadNumber);
} while (isEqual == found);

found = true;
return isEqual;
}, t );
}

Console.ReadKey();
}

static bool IsArrayValuesEqual(int[] arr, int splitIndex, out int leftSum, out int rightSum )
{
leftSum = SliceSum(arr, 0, splitIndex - 1);
rightSum = SliceSum(arr, splitIndex + 1, arr.Length - 1);

return leftSum == rightSum;
}

static int SliceSum(int[] arr, int startIndex, int endIndex)
{
int sum = 0;
for (int i = startIndex; i < endIndex; i++)
sum += arr[i];
return sum;
}
}
}

With some testing, I discovered: With 1 thread I used 2 processors. With 2 threads I used 4 processors, with 3 threads I used 6, with 4 I used all 8. And with 5 threads I used all 8 to 80%.

In the end, I was able to do some real research; the parallel library in .NET 4.0 is pretty good. You just need to have a good reason to use it.

Now … How to think about it as an interviewer:

  1. Giving programmers take home assignments is stupid.
  2. Giving a coding test that you have to write out on paper is stupid.
  3. Bringing an interviewee into the office without doing a basic “look over the shoulder” programming test is stupid.
  4. Phone interviews are antiquated if you have the capability to remote desktop into a developers computer.
  5. Asking a developer to solve one problem in front of you is more useful than asking a hundred “do you know about this” questions.
  6. If a programmer can demonstrate ability while your looking over their shoulder; then the only question left to ask is “will you fit in with our development team”.
    • Sidenote: “How much money do you want?” should be an initial question. Why waste time on a developer who has dreams of a Midas touch?

Using Google Closure Compiler with .NET

Well, with C#.NET.

I maintain a service which updates the minified versions of reused Javascript libraries. It runs at a specified time each night, and will check through all javascript code within a directory for two things:

1) If a .js doesn’t have a .min.js file; then a minified version of the file is created.

2) If a .js file does have a .min.js file which is out of date; then a new minified version of the file is created.

(aka, its a nightly run service which updates all minified version of javascript librarys on a server)

This service has a couple of problems on the surface. Why doesn’t it also make a packed file version? Does the minified version always perform (without error) the same as the development version? And, what “minifier” does it use?

Here’s are some quick answers:

1) “Packed Version”:

Unfortunately, when I first created the service only minified files were being created (aka, a long time ago in a land far far away). And, I haven’t yet had time to implement “packed versions”. It should only take a night to do update the source code. But when will I have that night?

2) What language?

C#. Sorry all, but it’s the easiest for me to use.

3) Does the minified version always perform (without error) the same as the development version?

It depends on the “minifier”.

I have found that “jsmin” doesn’t really translate the code that well. YUI is pretty good; but not 100% accurate. It’s about 99% accurate.

This system does support the Microsft Implementation of javscript minifying … but I have never used it. Because …

Google’s implementation was pretty damn good. I have never had an error/problem with a file minimized through the google closure compiler (http://closure-compiler.appspot.com/home).

3) What “minifier” does it use?

Thankfully, I made the program agnositic to what minifier was used. Currently, it supports “jsmin”, “ajaxmin” (MS), “YuiCompressor”, and “Closure” (Google).

Hopefully, you can copy/paste this into your project and be able to use Google Closure-Compiler.

//    So, this is different than most of the other compilers because it uses a remote (web) service.
// the first thing is to read in the javascript file.
string fileContents;
using( var fileReader = new StreamReader( info.FullName ) )
{
fileContents = fileReader.ReadToEnd();
}

// The files contents have been read. Now they need to be formatted in a POST request with the
/// file contents URL encoded.
const string postFormat = "js_code={0}&compilation_level={1}&output_format={2}&output_info={3}";
var data = string.Format(
postFormat,
HttpUtility.UrlEncode( fileContents ),
"WHITESPACE_ONLY",
"text",
"compiled_code"
);

// finally, create the Http Request (POST request)
var request = WebRequest.Create( "http://closure-compiler.appspot.com/compile" );
request.Method = "POST";
request.ContentType = "application/x-www-form-urlencoded";

// and, write the contents to the request.
using( var dataStream = new StreamWriter( request.GetRequestStream() ) )
{
dataStream.Write( data );
}

// the response contains the javascript
var response = request.GetResponse();
using( var responseStream = response.GetResponseStream() )
{
var streamReader = new StreamReader( responseStream );
return streamReader.ReadToEnd();
}

If you would like to see more than just the Google Code portion, or even the whole code for the service please email or comment.

Invasion of the Blog-o-Snatchers

on Monday, January 25, 2010

I am thankful for all the blog-o-sphere websites which provide servers and websites for expressing opinions online. This doesn’t just include blogger.com, wordpress.com, or livejournal.com. I also include wikipedia and all of the wikia.com websites. And any website which allows people to add their opinions to the eternal flow of electronic information.

These websites are amazing. And they allow for the 80% of the world which isn’t represented by the mainstream news networks, hollywood movies, or local papers to express their opinions and find a community with those opinions.

But, I hate when those websites undermine the opinions of the bloggers or commenters by adding advertisements to a detriment to their content. Advertisements are a necessary part of every information medium, but it doesn’t need to be in your face. Or even worse, detract from the content which the end-user actually went to the website for.

Earlier tonight, I was trying to write a snippet of code which would use the Google Closure Compiler to condense some javascript used on the UCSB websites and ran into this blog post: http://www.bloggingdeveloper.com/post/C-Wrapper-for-Google-Closure-Compiler-Compressing-Javascript-Files-on-the-fly-with-ASPNET-and-Closure-Compiler.aspx

It’s a pretty decent post, but the code wasn’t complete. At this point I assumed that their website would have a download section to get the original source code. Near the bottom of the post there is text “Download Closure.cs”, which leads to nothing.

So far this website is zero for three.  I wanted to find some code that “just worked with Closure Compiler”. And I was blown away that the top google result that I found had an image for source code (which I couldn’t copy/paste), had missing variable definitions, and I couldn’t get the source code.

The strange thing is that none of that annoyed me. The source code on the website was very similar to the source code I wrote in my early attempts; so I felt that I was doing the right thing. I had already created a string format, and I didn’t think the real implementation of “data” would solve my problem. But, the idea that I couldn’t download the source from the website bugged me. There was explicit text that said “Download Closure.cs”.

Have you ever created a website that had a link “Download PDF”, and the link didn’t work? How many people complained? Everybody that tried it would complain. Even people that would never use the PDF document would complain that the link didn’t work.

BUT … BUT … That text is not that big on the screen. There is a huge image which says “Download” right below it. That image probably appears on every page, and it probably confuses every person that sees it. The HUGE  “DOWNLOAD” link only allows users to subscribe to an RSS feed. FTW??

What the hell does RSS feeds have to do with Downloading? What RSS feed on the planet Downloads? When has the term download ever been associated with RSS?

At this point I started to look at the website layout and started to notice the big images which say SUBSCRIBE and SPONSORS. Direct advertising! I understand that everybody needs to make money to survive. But, is it neccessary?

What is the business model of blogger, wordpress, and livejournal? How do they make money without pissing off their users?

Any why is anyone using a blogging website that would add content to your posts which you never asked for?

Creating your own javascript namespaces with jQuery

This isn’t cutting edge by a long shot, but if I had found a post on this a couple months ago it would have kept me from refactoring my code two or three times. One of the amazing things about working with jQuery is the programmers have dealt with every impossible situation you could imagine. And, when you look through their code you are given an insight into javascript best practices.

(function ($) {

if (!window.baseNamespace) { window.baseNamespace = {}; }
if (!baseNamespace.subNamespace) { baseNamespace.subNamespace = {}; }

var pseudoGlobal = 10;

$.extend(baseNamespace.subNamespace, {
someVariable: 10,

someFunction: function () {
alert(pseudoGlobal);
}
});

})(jQuery);

Unfortunately, this description doesn’t follow the exact same best practices that jQuery does. But, it works well when defining your own namespaces.

The outer function ensures the inner statements will be executed with jQuery as the definition of $. This will help out if you ever need to reuse your code in “no conflict” mode (http://api.jquery.com/jQuery.noConflict/).

Then, inside of the function, first check that the root namespace is defined under “window”, the global namespace. It took me longer than I would have liked to understand that “window” was the global namespace; I was under the sad impression that “document” was the global namespace.

Once the namespace you are looking to work with is created, then the $.extend() function gives the means to create the functionality you want.

You can then interact with your namespace the same way google of yahoo call their namespaced code:

alert(baseNamespace.subNamespace.someVariable); // 10
baseNamespace.subNamespace.someFunction(); // Also, 10

I hope this saves you a little bit of time when developing reusable javascript.


Creative Commons License
This site uses Alex Gorbatchev's SyntaxHighlighter, and hosted by herdingcode.com's Jon Galloway.