It’s always exciting to get an email like this from an iconic tech giant:

Hi Mark, I recently found your profile in our database, and your background is impressive. The (redacted big company) Media Division will be flying several candidates in for interviews at our (redacted big city) headquarters in April and considering you.

I’m not actively seeking a new job, so normally I’d just file this away in my emergency just-laid-off folder, but this email had a twist that got my attention:

If interested in exploring Development opportunities with us, the first step will be to complete our coding challenge ideally within the next 3 to 5 days.

Who doesn’t love a coding challenge?

The Code Interview

It’s been years since I gave up on chat interviews. It just seems like these don’t work so well - we all feel like we are insightful judges of candidate quality, but somehow the people we hire just don’t always turn out as well as we hope.

So now when my name shows up on the list of people interviewing a candidate, I forgo the usual get-to-know-you experience in exchange for one or two simple programming exercises. Watching someone think on their feet under modest pressure seems more enlightening than anything I can get through conversation.

Apparently the big company contacting me has decided on a similar approach. The link included with the email sent me to a site called Interview Zen that promised an interactive experience:

In this interview you will be shown a number of questions and asked to answer each one in turn. ... Your interviewer will be able to see your answer unfold as if they were sitting at the keyboard next to you.

This sounded pretty cool, but the actual implementation fell quite short of what I had hoped to see.

First, the promise of seeing me solve the problem interactively was just not met. I was asked a single fairly complex question by Interview Zen, and given a choice from a dropdown of maybe 25 different languages to use for my solution. Interview Zen doesn’t provide any sort of IDE; they specifically asked me to develop my answer elsewhere and post it when complete.

After posting my solution to the site, it was reformatted using some sort of pretty printer, and then… nothing. No message indicating I was done, no next step, just a page with my solution. So much for interaction.

And any interviewer watching the process would see my screen sit there completely blank for almost an hour, then a deus ex machina as somewhere around a hundred lines appear on the screen.

I expect that if you want to use Interview Zen properly, you need to create a staged series of questions so you can actually see this happen, and my big company didn’t bother to do this.

But still, they get what they are looking for, which is a completed code sample of a reasonable size - big enough to actually demonstrate some work, small enough to evaluate quickly.

On To the Challenge

What’s more interesting is the challenge itself. I’ll lay out the assignment for you, show you my solution, and then you can decide whether I am worth hiring based on my work.

The challenge question is to write a function that produces a list of products based on what your friends are buying. I am given two functions:

getFriendsListForUser(): This function returns a list of users who are friends of a given user.

getPurchasesForUser(): This function returns a list of products that have been purchased by a given user.

The function I am asked to write will create a list of all the products purchased by a given user’s friends, ranked by frequency - the most frequently purchased products should appear first. The list should exclude any products that the user has already purchased.

I’m going to present the code I created step by step, excluding comments and verbiage that belong in the finished file. You can see the whole thing by downloading getRecommendations.cpp.

The Interface

To kick things off I need to define the types I’m using, the functions provided in the problem definition, and the function I’m writing.

No big surprises here. About the only thing of interest to note is that I’m using a typedef for the customer and product ids. It would be easy enough to just leave these as type std::string, but adding a little type safety is a nicety - and it actually surfaced a mistake made during development.

typedef std::string CustomerId;
typedef std::string ProductId;

std::vector<CustomerId> getFriendListForUser(const CustomerId &user );
std::vector<ProductId> getPurchasesForUser(const CustomerId &user );

std::vector<ProductId> getRecommendations(const CustomerId &user)
{
...

Getting the Product Counts

In the body of my function, I need to iterate over all the friends of this user, and add each of their purchases to a master list, which I store in an std::map. This code is pretty straightforward. It could have been made prettier by using C++11 features, but I’d rather be sure that my code could be tested with tools that might not be completely up to date.

Using the size() method of a vector in a loop comparison is a bit controversial as well, but I erred on the side of readability here.

std::map<ProductId,int> product_counts;
std::vector<CustomerId> friends = getFriendListForUser(user);
for ( size_t i = 0 ; i < friends.size() ; i++ ) {
  std::vector<ProductId> friend_purchases = getPurchasesForUser( friends[i] );
  for ( size_t j = 0 ; j < friend_purchases.size() ; j++ ) 
    product_counts[friend_purchases[j]]++; 
}

Cleansing the Product Counts

At this point I have map that contains a range of products products purchased by friends, along with their counts. The problem definition said I need to remove products that have already been purchased by this user, so I have to iterate over that list and remove each found match from the map:

std::vector<ProductId> user_purchases = getPurchasesForUser( user );
for ( size_t i = 0 ; i < user_purchases.size() ; i++ ) {
  std::map<ProductId,int>::iterator ii = product_counts.find(user_purchases[i]);
  if ( ii != product_counts.end() )
    product_counts.erase(ii);
}

Inverting the Map

So far so good. I have one last bit of work to do. I need to return the list of products sorted by the frequency of purchase. I have that information in the map already, but to sort properly I need the product count to reside in the Key, not the Element.

There are a number of choices for fixing this - I do it by simply copying the elements of the map into a properly structured map. I could do this without a loop in a number of ways, including a range constructor and the std::copy algorithm, but the explicit loop should be just as efficient and again, the simplicity helps with readability. I think. And because multiple products may have the same count, this needs to be an std::multimap:

std::multimap<int,ProductId> sorted_products;
for (std::map<ProductId,int>::iterator ii = product_counts.begin() ; 
     ii != product_counts.end();
     ii++ )
  sorted_products.insert(std::make_pair(ii->second,ii->first));

Returning the Results

The problem didn’t ask for me to return anything but the product IDs - no counts were requested. Just the product IDs in the proper order. So I iterate over the map in reverse order, getting the highest product counts first, stuffing the results into a vector, and return the result:

std::vector<ProductId> result;
for ( std::multimap<int,ProductId>::reverse_iterator ii = sorted_products.rbegin();
      ii != sorted_products.rend();
      ii++ )
  result.push_back(ii->second);
return result;

All done!

My Take, Their Take

I think they scoped this task pretty well. In practice you could probably write and test this on a system you are familiar with in 15 minutes. But for me to properly document it, then add some unit test and so on ran the time up to about an hour. The problem has plenty of pitfalls for you to do things poorly - either incorrect code or inefficient code.

And my implementation is far from flawless - there are a lot of details that could be improved upon here, and I’ll leave it up to you to help flush them out.

Not perfect, but good enough, because my next email from the big company had good news:

A hiring manager from the Media team at (redacted big company) has reviewed your resume and would like you to speak to a member of their team about the position below. ...

Well, I wasn’t looking for a job today, so I politely and gratefully declined, but it’s always good to know you can at least make the first cut.

Moral and Legal Hazards

I was kind of surprised that none of this process was cloaked in any sort of corporate secrecy, either implicit or explicit.

The email from the recruiter didn’t make any mention of confidentiality, and in fact at one point in the process I was given the chance to share the job posting with others.

The Interview Zen web site didn’t offer up Terms of Service, and had no links to such on any of the pages I went to.

So it would seem that legally, I am not under any sort of obligation to avoid disclosing parts of this test.

But what about ethically? By discussing this aren’t I giving away possible answers to future cheaters?

Maybe so, but I’m not going to sweat this. First, real cheaters would have to find this post, and since the company name is missing, it’s not going to be trivial. Second, if the code is found, simply doing a verbatim copy is not going to work - that will raise flags right away. In order to customize this code and make it your own, you end up having to understand it as well as I do - in many ways this is just as much a test as it would be to do the original composition.

So I post this with a clean conscience. I hope you enjoyed running through the challenge as much as I did.