Channels ▼

Mark Nelson

Dr. Dobb's Bloggers

My Big Company Code Interview

April 09, 2014

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 a map that contains a range of products purchased by friends, along with their counts. The problem definition said that 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 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, stuff 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 within 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 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.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video