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.