Would the interviewer be right?

Please avoid stating which problem these are solutions for.

During a recent discussion the following code was suggested

int desc(const Node* node, int d)
{
  int l = d, r = d;
  if (node->l) l = desc(node->l, d + 1);
  if (node->r) r = desc(node->r, d + 1);  // edit: thanks, Nico
  return max(l, r);
}
int d2(const Node* root)
{
  return root ? desc(root, 1) : 0;
}

One of the folks in the discussion shook his head and said: “If this was an interviewer, they would want you to do it in one function, though”. Then he presented this:

int d1(const Node* root)
{
  if (root == nullptr) return 0;
  return max(d1(root->l) + 1, d1(root->r) + 1);
}

Then he made the assertion “this is what an interviewer would be looking for”.

I suspect that what he meant was “I’ve asked this question in interviews and this is the answer I look for”.

The second version of the code has a number of merits: its shorter, there’s just one function… If you moved the +1 outside the max, it has a little less duplication.

But it’s not the same code. It seems to me that, in the context of an interview, you’d probably want to start with clearer code for walking through your process and consider reducing your code during the process.

On a whim, I decided to look at both versions under the microscope. It turns out that the snazzy 3-liner version gets significantly slower as the trees get larger.

    return 1 + max(d1(root->l), d1(root->r));

The compiler is forced to call d1 on root->l and root->r for every node it visits compared to the original version

  if (node->l) l = desc(node->l, d + 1);
  if (node->r) r = desc(node->r, d + 1);

This version of the code has an extra conditional overhead in the trampoline function that checks if the tree is empty, but once we get into desc the test is used to make calls conditional, rather than having to make the call to test the condition.

And the performance difference is quite impressive: For a roughly-balanced 1,000 node tree, Visual Studio sees a near 50% improvement in the first version (first version = d2), Clang with -O3 shows 37% improvement and GCC is almost 50% again.

Finally, if we look at the assembly this generates, the short version generates 740 lines while the original version generates 1700.

So, all things considered, would the interviewer have been right?

 

Leave a Reply

Name and email address are required. Your email address will not be published.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

You may use these HTML tags and attributes:

<a href="" title="" rel=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <pre> <q cite=""> <s> <strike> <strong> 

%d bloggers like this: