Code Test from a place we all know

About two months ago I was invited to participate in the interview process for a large well known company. I was unsure about participating because I was not at all prepared to interview at a company of this caliber. I had no idea what to expect, but considering the reputation of this company, I figured this would be a good learning experience and exposure to the level of software developers they were looking for. The first round of interviews was a code test which I had about 3 days to complete (although if I needed more time, I could request it). The code test was to be taken on my own time, online, through one of those code test sites. As an aside, a colleague of mine did make it to a final round of interviews with this company, so I had some idea already what I might be in for.

The code test consisted of 3 questions. Technically, there was no time limit, but it was stated that taking too long could hurt your results. They wanted to ‘see’ how you thought and all the input was recorded and could be played back by the reviewers. The languages which could be used were C++, Java, or C#. I chose C#.

Question 1
This one was by far the hardest of the 3 for me to answer. I didn’t record my final answer, or the exact question for that matter, but it was an open ended question about designing an API for a vector graphics program. What I found difficult about the question was that my mathematical mind didn’t really know where to stop; I kept thinking about all the things I could do or include in a vector graphics library. Additionally, the way the site was set up, the text boxes expected code so it was a very awkward question to answer on the site. I couldn’t really tell how extensive an answer was desired so I did the best I could and moved on after what I thought was a pretty poor answer. I made a comment about how I didn’t want to take very long on the question but ultimately gave a vague outline of the approach I would take.

Thankfully, questions #2 and #3 were for more direct and relatively straightforward.

Question 2
Setup: Assume primitive Facebook. FB has Members.

class Member {
    String name;
    String email;
    List friends;
}

Code printSocialGraph(Member m). Direct friends of m are Level 1 friends. Friends of friends are level 2 friends…..and so on Print level 1 friends first. Then print level 2 friends….and so on

void printSocialGraph (Member m) {
    //Your code here
}

Fairly quickly, I identified this as a Breadth First Search (BFS) problem. I hadn’t implemented BFS in quite a while so after a quick trip to Google for the algorithm, I modified it slightly to suit the problem and used LinqPad to test and troubleshoot. Below is my code:

class Member {
    public string Name;
    public string Email;
    public List<Member> Friends;
	
    public Member(string name, string email) {
	Name = name;
	Email = email;
	Friends = new List<Member>();
    }
}

void printSocialGraph(Member m) {
    Queue<Member> _queue = new Queue<Member>();
    _queue.Enqueue(m);
    
    while(_queue.Count > 0) {
        var currentMember = _queue.Dequeue();
        
        if (currentMember == null)
            continue;
        
        foreach(var friend in currentMember.friends)
            _queue.Enqueue(friend);
            
        Console.WriteLine(string.Format("Name: {0}, Email: {1}", currentMember.name, currentMember.email));
    }
}

Below is an example of how to use this class and method:

Member josh = new Member("Josh", "josh@email.com");
josh.Friends = new List<Member>();
	
josh.Friends.Add(new Member("Level1-A","A@email.com"));
josh.Friends.Add(new Member("Level1-B","B@email.com") { 
	Friends = new List<Member>() { 
		new Member("Level2-B1", "L2B1@email.com"),
		new Member("Level2-B2", "L2B2@email.com"),
		new Member("Level2-B3", "L2B3@email.com") {
			Friends = new List<Member>() { 
				new Member("Level3-B1", "L3B1@email.com"),
				new Member("Level3-B2", "L3B2@email.com"),
				new Member("Level3-B3", "L3B3@email.com")
			}
		}
	}
});
josh.Friends.Add(new Member("Level1-C"," C@blah.com") { 
	Friends = new List<Member>() { 
		new Member("Level2-C1", "L2C1@email.com"),
		new Member("Level2-C2", "L2C2@email.com"),
		new Member("Level2-C3", "L2C3@email.com")
	}
});
	
printSocialGraph(josh);

The output:

Name: Josh, Email: josh@email.com
Name: Level1-A, Email: A@email.com
Name: Level1-B, Email: B@email.com
Name: Level1-C, Email:  C@blah.com
Name: Level2-B1, Email: L2B1@email.com
Name: Level2-B2, Email: L2B2@email.com
Name: Level2-B3, Email: L2B3@email.com
Name: Level2-C1, Email: L2C1@email.com
Name: Level2-C2, Email: L2C2@email.com
Name: Level2-C3, Email: L2C3@email.com
Name: Level3-B1, Email: L3B1@email.com
Name: Level3-B2, Email: L3B2@email.com
Name: Level3-B3, Email: L3B3@email.com

The code works as expected thanks to the BFS implementation. I believe coding/testing took me around an hour.

Question 3
Write a function that converts an int into its alpha-numeric equivalent
represented as a null terminated string. The function should accept an
int as input and return a string as output. For instance, calling the
function with an int value of 324 would return a null terminated string
containing “324″. Ensure that your function checks for appropriate boundary
conditions and edge cases. Assume you cannot use any standard libraries
(for example, no itoa or sprintf).

For this question, I wasn’t sure exactly what I could and couldn’t use as far as a string library. I didn’t really want to worry about string concatenation, so I used what was available in C#.

My code is below

public string IntToString(int number) {
    string intString = string.Empty;
    bool isNegative = false;
    
    if (number == 0)
        return "0";
	
    if (number == int.MinValue)
        return "-2147483648";
	
    if (number < 0) {
        isNegative = true;
        number *= -1;
    }
    
    while (number > 0) {
        int lastDigit = number % 10;
        string lastDigitString = ((char)(48 + lastDigit)).ToString();
        intString = string.Concat(lastDigitString, intString);
        number /= 10;
    } 
    
    if (isNegative)
        intString = string.Concat("-", intString);
        
    return intString;
}

Its use is simple:

IntToString(123456)

An output to the console produces

123456

as expected. I believe this took me about an hour of coding/testing time.

The rest of the story

After a few weeks, I was contacted by the company. I was a bit surprised because enough time had passed that I thought I didn’t do very well. However, based on their enthusiasm and our discussion, I did quite well and I was invited for a second, in person interview, at their company headquarters. Unfortunately (after some excitement and thought), I declined to proceed further because I could not in good conscience continue the interview process knowing that I wouldn’t accept a position in the near future. Overall, it was a great and humbling experience.

ASP.NET MVC: Passing model from AJAX call into a Controller – The Easy Way!

Last Friday at work, a fellow developer asked during a meeting about how to pass an object from Javascript to an ASP.NET controller. To make a long story short, I proposed a method which I believe is simple and elegant. I hadn’t used it in some time, and wasn’t clear on all the details so I took and hour (and another two to write this post) to code and present the solution.

The idea is simple, I will create a page which takes input from a user. The user can submit this data and receives a response.

First let’s state what needs to be done from a programmatic sense (in no particular order).

  1. Create a Model class to retrieve information from a user and create a Model class to respond to a user
  2. Create an ASPX page which uses this model (the project uses MVC 2 without the Razor engine).
  3. Write Javascript to handle the submission of the information, AJAX call, etc.
  4. Write the Controller to handle the AJAX call for this page.

I’ll be using jQuery and Microsoft Visual Web Developer 2010 Express to do the actual development. I’m going to assume anyone reading this can add jQuery to their project and to the web page.

Let’s get started.

Models

Below is a simple Model class which contains properties for a first name, last name, and age.

public class Info {
    [DisplayName("First Name")]
    public string FirstName { get; set; }

    [DisplayName("Last Name")]
    public string LastName { get; set; }

    public int Age { get; set; }        
}

The attribute [DisplayName()] allows me to specify what text the label tag will display. Otherwise, it will just display the name of the property in CamelCase. If you wish to use this attribute, you’ll need to include System.ComponentModel in your using statements.

Next, I can create a Model for the response class:

public class Response {
    public bool IsSuccess { get; set; }
    public string Message { get; set; }

    public Response(bool isSuccess, string message) {
        IsSuccess = isSuccess;
        Message = message;
    }
}

The property IsSuccess will be used by the Javascript to decide what to do with the response, and the Message property can be used to display some text. Of course the sky’s the limit as far as what you want to pass back to Javascript.

That completes the Model classes. I saved these both in the Models folder of the project.

ASPX Page

Now I can create an ASPX page. Well, I lied a bit. I’m actually going to create a partial view and render that in an ASPX page. Assuming you’re working with an ASP.NET MVC project. Go to the Solution Explorer. In your project you should have a folder for your Views (by default this is, in fact called Views). Wherever you wish you place the partial view within the Views folder, right click and select Add > View. You should see a dialog similar to the one below:

AjaxMVCAddPartialView

I named the view Info.ascx. Make sure the checkbox Create a partial view (.ascx) is selected and since I want to strongly this view to my model make sure the Create a strongly-typed view is selected as well. The dropdown under this labeled View data class: should point to the Info model class created above. Note that the namespace points to where I saved the Info.cs class described above.

Now that the partial view is created. I just add the mark-up to display the properties I want to show from the Info class. Below is the full ASCX file:

<%@ Control Language="C#" Inherits="System.Web.Mvc.ViewUserControl<JSSerializeTestMVC2.Models.Info>" %>

<fieldset id="infoForm">            
    <div style="margin: 1em .5em">
        <%: Html.LabelFor(model => model.FirstName)%>
        <%: Html.TextBoxFor(model => model.FirstName)%>            
    </div>
            
    <div style="margin: 1em .5em">
        <%: Html.LabelFor(model => model.LastName)%>
        <%: Html.TextBoxFor(model => model.LastName)%>
    </div>

    <div style="margin: 1em .5em">
        <%: Html.LabelFor(model => model.Age)%>
        <%: Html.TextBoxFor(model => model.Age)%>
    </div>
            
    <p>
        <input id="submitButton" type="button" value="Submit Info" />
    </p>
</fieldset>

Note, the model for the page (Inherts=...) is the Info class created. I used HtmlHelper class for convenient rendering of the model. I skipped using a CSS class since the example is so short but for good practice, you should generally use CSS classes instead of the style attribute. Let me point out the two important IDs. The fieldset has the ID attribute set as id="infoForm" and the bottom input tag has the ID attribute set as id="submitButton". These will both be used explicitly in the Javascript code following.

Next, this partial view needs to be rendered in an ASPX page. I’ll leave most of that to you expect to say I simply added the following line the main page (Index.aspx) I created:

<div>
     <%: Html.Partial("Info") %>
</div>

If you run the project, the partial view looks something like this:

AJAXMVCPartialView

Javascript

Below is the Javascript to handle the submit button event and the AJAX call to the controller:

$(function () {
    var submitButton = $("#submitButton");
    var infoForm = $("#infoForm");
    
    //  Attach event handler to submit button
    submitButton.click(function () {
        SubmitInfo(infoForm);
    });
});

//  Submits the Info form to Controller
//  formContainer: (jQuery) The form model to submit
function SubmitInfo(formContainer) {
    $.ajax({
        url: "Home/SubmitInfo",
        type: 'post',
        data: formContainer.serialize(),
        success: function (data) {
            if (data.IsSuccess) {
                // Clear the input tags
                formContainer.find("input[type='text']").each(function (i, element) {
                    $(this).val('');
                });
            }

            alert(data.Message);
        },
        error: function (jqXHR, textStatus, errorThrown) {
            alert(errorThrown);
        }
    });
}

There are two pieces. When the document is ready, lines #1-9 simply attach the onclick event to the submit button. This calls the function SubmitInfo and passes in the jQuery object infoForm for the fieldset. SubmitInfo simply executes and AJAX call. Note the following key/value pairs for the call. The URL is set to the SubmitInfo method of the HomeController which handles the request (we have yet to examine this). I marked the TYPE as POST. The DATA key passes the serialized jQuery object. This is the most important step to keep the code elegant. All the fields of the form will be deserialized in the Conroller as the Model class Info as we will see. Finally the SUCCESS key takes the Response class, clears the input if the returned object’s IsSuccess is true, and displays a message. For the purposes of this example, the ERROR key can be ignored.

Controller

Finally, the code for the Controller (I placed this in the HomeController):

List<Info> _contactList = new List<Info>();

[HttpPost]
public JsonResult SubmitInfo(Info contactInfo) {
    _contactList.Add(contactInfo);    // Do something with contactInfo

    var response = new Response(true, "Contact Successfully Submitted");
    return Json(response);
}

The attribute [HttpPost] disallows access to this controller except through a POST. The return value of the controller is set to JsonResult since I am returning JSON to the AJAX call (this is another key/value pair which can be set to something else, e.g. HTML).

I created a private list of type Info just for explanatory purposes. When this controller is hit by the AJAX request, it will try to deserialize the object into the type Info. Then you can do with it what you wish. Probably you’d end up doing some processing and inserting the information into a DB somehow (ADO.NET, Linq to SQL, Entity Frameworks, etc). The point is, it will be your Model. After this, I just create a Response model to send back so the Javascript can handle the submission.

Closing remarks

Certainly there is a lot more that can be said. For example, no error checking or validation is performed on the submission. To recap: The simple clean elegant way to pass a Model through an AJAX request is to serialize it. Hope this helps anyone who might stumble upon this. Below is the Visual Studio solution:

AjaxMVC.zip

P.S. – Regretfully, I have yet to post what I was referring to in the XOR post, but all in good time!

Swapping values in C#:
Tmp variable vs. XOR with performance times.

While doing a bit of coding for an upcoming post (probably the one following this) I was doing a variable swap. I started with a temporary variable swap but then decided to be cute and implement an XOR swap. As a benefit, I had the chance to remind myself how to do this (without cheating). However, I ran into an issue when I wanted to create a generalize swap function. Researching the issue, I came upon a post about how the XOR swap is not as efficient in modern architecture. Surprising! Dot Net Perls has a page about it with a link to the Wikipedia article.

As a reminder, an XOR swap can be achieved by doing the following on two variables:

int x = 1;
int y = 2;

x ^= y;
y ^= x;
x ^= y;

Console.WriteLine("x = {0}", x);
Console.WriteLine("y = {0}", y);

Output:

x = 2
y = 1

Below is the code I used to check the performance of the two methods.

int[] numbers = { 1, 2 };
int iterations = 100000000;		//Number of swap iterations
var timer = new Stopwatch();

//	XOR Swap Test
timer.Start();
for (int i = 0; i < iterations; ++i) {
	numbers[0] ^= numbers[1];
	numbers[1] ^= numbers[0];
	numbers[0] ^= numbers[1];
}
timer.Stop();

Console.WriteLine("XOR Swap time: {0}", timer.Elapsed);

timer.Reset();

//	Temporary Variable Swap Test
timer.Start();
for (int i = 0; i < iterations; ++i) {
	int tmp = numbers[0];
	numbers[0] = numbers[1];
	numbers[1] = tmp;
}
timer.Stop();

Console.WriteLine("Temp Variable Swap time: {0}", timer.Elapsed);

Here is sample output of a few runs:

XOR Swap time: 00:00:01.1918037
Temp Variable Swap time: 00:00:00.6617117

XOR Swap time: 00:00:01.1561061
Temp Variable Swap time: 00:00:00.6587373

XOR Swap time: 00:00:01.1674577
Temp Variable Swap time: 00:00:00.6651171

Of course these times vary a bit with the number of iterations and what else your computer is doing when it’s run, but I never saw the XOR swap performance beat the temporary variable. Who says bit manipulation is always faster?

Formula for the sum of the integers from m to n, with Proof!

So I’m reading some math for pleasure (and for some scripting ideas) and I arrive at the following problem:

Find a formula for the sum of the natural numbers from m to n.

In the chapter they discuss and derive the formula for the sum of the integers from 1 to n. This can be stated as

(1)   \begin{equation*} \sum_{k=1}^{n} k = 1 + 2 + \ldots + n = \frac{n(n+1)}{2} \end{equation*}

The solution then is relatively straightforward, just subtract the first m – 1 integers from equation (1). That is, the sum from 1 to the m – 1 natural numbers is given by

(2)   \begin{equation*} \sum_{k=1}^{m-1} k = \frac{(m-1)(m)}{2} \end{equation*}

Subtracting (2) from (1) gives

(3)   \begin{equation*} \sum_{k=m}^{n} k = \frac{1}{2} [n(n + 1) - (m - 1)m] \end{equation*}

Note that m and n are natural numbers, and that m ≤ n.

Programmatically speaking, it would be nice if when I divided by 2, I always got an integer. Logically, this should be the case since I’m just adding together natural numbers and they should sum to an natural number. However, I thought it might be a nice exercise to write out a proof of this fact.

Preliminaries

First, a quick preliminary (which I won’t prove). Note that any even integer multiplied by any odd integer always results in an even integer. The the proof follows from the fact that since an even integer is divisible by 2, the product of an even and odd integer is still divisible by 2 and thus also even.

Note then that (m - 1)m is the product of an even integer times an odd integer. Similarly for n(n + 1). This result extends to natural numbers since the natural numbers are a subset of the integers.

Here is a quick example. Pick m = 5. Then m - 1 = 4 and so (m - 1)m = 4 \times 5 = 20. In other words if m is odd then m - 1 is even. Conversely, if m is even then m - 1 is odd. A similar situation occurs with n and n + 1.

The proof

Suppose that m and n are natural numbers and that m \le n. Consider the expression n(n + 1) - (m - 1)m. Note that both (m - 1)m and n(n + 1) are always even since they are always the product of and even number and odd number for any choice of m, n \in \mathbb{N}. Since 2 \hspace{1 mm} \vert \hspace{1 mm} (m - 1)m and 2 \hspace{1 mm} \vert \hspace{1 mm} n(n + 1) this means 2 \hspace{1 mm} \vert \hspace{1 mm} [(m - 1)m + n(n + 1)]. Therefore the expression (m - 1)m + n(n + 1) is always an even natural number and further

(4)   \begin{equation*} \frac{1}{2} [(m-1)m + n(n+1)] \in \mathbb{N} \end{equation*}

This completes the proof

At some point maybe I’ll write up a script to calculate the sum of the integers numbers from m to n.

Notes

If you’re not math symbol aware then I’ll point out that \mathbb{N} represents the set of natural numbers. These are the numbers 1, 2, 3, \ldots. So n \in \mathbb{N} means that n is an natrual number. The expression 2 \hspace{1 mm} \vert \hspace{1 mm} 4 says that “2 divides 4″. Another way to say this is 4 is divisible by 2.

Differences between functions and stored procedures

Sangunni @ CodePoject posted a great article on the
differences between stored procedures and functions

To summarize (Stored Procedures = SP, User defined functions = UDF)

  • SP: Can return zero or n values
    UDF: Returns one value which is mandatory.
  • SP: Can have input/output parameters
    UDF: Can have only input parameters.
  • SP: Allows select & DML statements
    UDF: Allows only select statements (Note: Other logical operations possible)
  • SP: Can use functions within definition
    UDF: Cannot use SPs within definition
  • SP: Can exception handle via Try-Catch block
    UDF: Cannot use a Try-Catch block
  • SP: Transaction management possible
    UDF: No transactions
  • SP: Can not be utilized in a select statement
    UDF: Can be used in a select statement (and WHERE/HAVING)
  • UDF: Can be used in JOINs and other Rowset operations (if it returns a TABLE)

Properly throwing exceptions in C#

While taking a proficiency test for a job, the following question arose (which I got wrong):

Explain the difference between

catch (Exception ex) {
	//exception handling code
	throw ex;
}

and

catch (Exception ex) {
	//exception handling code
	throw;
}

At the time, I thought they were the same so I was at a loss for an answer. The short answer is the latter preserves the full stacktrace and the former truncates it. Quite handy to know.

If repackaging the exception is necessary, then it should be passed to the new exception type like below (at least this I was already doing correctly!):

catch (Exception ex) {
	//exception handling code
	throw new MyException("A lucid exception message.", ex);     
	//MyException is of course some real exception
}

A good explanation can be found at Scott Dorman’s blog.

Do four points create a square?

Can you determine programmatically if four points create a square? This was the programming problem posed at Programming Praxis.

The idea is to find the distance between all points. Essentially, you create a complete graph, where the points are your nodes and the distances are the edges. Four of the distances should be equal. These represent the sides of the square. The other two (representing the diagonals), must be greater than any side but equal to each other, for all but the degenerate case in which the length of the sides of the square is zero (Is this a square?).

Below is my unsophisticated solution:

First, two helpers

//	Point
//	A container for a 2-D Point
public class Point {
	public double X { get; set; }
	public double Y { get; set; }
	
	public Point(double x, double y) {
		this.X = x;
		this.Y = y;
	}
}

//	EuclidianDistanceSquared
//	Finds the square of the Euclidian distance.
//	Returns: The Euclidian Distance between the two points.
public double EuclidianDistanceSquared(Point p1, Point p2) {
	return (p2.X - p1.X) * (p2.X - p1.X) + (p2.Y - p1.Y) * (p2.Y - p1.Y);
}

I thought it easiest to have a class to instantiate points and a helper distance function. When I originally created the metric, is used strict Euclidian distance

public double EuclidianDistance(Point p1, Point p2) {
	return Math.Sqrt((p2.X - p1.X) * (p2.X - p1.X)  + (p2.Y - p1.Y) * (p2.Y - p1.Y));
}

but since I was just comparing distances, I figure I could add the optimization of not computing the square root.

Now the IsSquare function will compute the six distances, store them in a list and sort the list. This alleviates the need to figure out which distances are sides and which are diagonals. The first four points in the list should be the distances of the sides of the square and the last two should be the distances of the diagonals. Finally, to determine if these point are indeed a square, the first and fourth entries in the list should be equal (all sides are equal) and the fifth and sixth entries (the lengths of the diagonals) should also be equal. For good measure, I also check if the length of one of the sides is less than or equal to the length of a diagonal.

//	IsSquare
//	Determines if four points create a square
//	Returns: True if the four point create a square, false otherwise.
public bool IsSquare(Point p1, Point p2, Point p3, Point p4) {
	double p1p2 = EuclidianDistanceSquared(p1, p2);
	double p1p3 = EuclidianDistanceSquared(p1, p3);
	double p1p4 = EuclidianDistanceSquared(p1, p4);
	double p2p3 = EuclidianDistanceSquared(p2, p3);
	double p2p4 = EuclidianDistanceSquared(p2, p4);
	double p3p4 = EuclidianDistanceSquared(p3, p4);
	
	List<double> distances = new List<double>() { p1p2, p1p3, p1p4, p2p3, p2p4, p3p4 };
	distances.Sort();
	
	return (distances[0] == distances[3]) && (distances[4] == distances[5]) && (distances[0] <= distances[4]);
}

Remarks:

Certainly some would argue this isn’t an elegant solution to the problem but I think it’s very readable and hopefully understandable to someone unfamiliar to the problem/solution.

I think it would be good when using metrics/distances to create a metric or distance class to be able to easily choose a distance function for use between points, lines, planes, etc.

Complete Source

//	Point
//	A container for a 2-D Point
public class Point {
	public double X { get; set; }
	public double Y { get; set; }
	
	public Point(double x, double y) {
		this.X = x;
		this.Y = y;
	}
}

//	EuclidianDistanceSquared
//	Finds the square of the Euclidian distance.
//	Returns: The Euclidian Distance between the two points.
public double EuclidianDistanceSquared(Point p1, Point p2) {
	return (p2.X - p1.X) * (p2.X - p1.X) + (p2.Y - p1.Y) * (p2.Y - p1.Y);
}

//	IsSquare
//	Determines if four points create a square
//	Returns: True if the four point create a square, false otherwise.
public bool IsSquare(Point p1, Point p2, Point p3, Point p4) {
	double p1p2 = EuclidianDistanceSquared(p1, p2);
	double p1p3 = EuclidianDistanceSquared(p1, p3);
	double p1p4 = EuclidianDistanceSquared(p1, p4);
	double p2p3 = EuclidianDistanceSquared(p2, p3);
	double p2p4 = EuclidianDistanceSquared(p2, p4);
	double p3p4 = EuclidianDistanceSquared(p3, p4);
	
	List<double> distances = new List<double>() { p1p2, p1p3, p1p4, p2p3, p2p4, p3p4 };
	distances.Sort();
	
	return (distances[0] == distances[3]) && (distances[4] == distances[5]) && (distances[0] <= distances[4]);
}

Here is a sample program using the IsSquare function:


Point p1 = new Point(0,0);
Point p2 = new Point(1,1);
Point p3 = new Point(0,1);
Point p4 = new Point(1,0);
		
Console.WriteLine(IsSquare(p1,p2,p3,p4));