Array Iteration Interview Problem


– 835 words

Over the past year, I have interviewed several cadidates for programming positions at tech startups. The following problem is a variation of a question I have asked in each of those interviews.

I say that the candidate can use any language they choose, and most use ruby. I am not a rubyist. My background is in C and functional languages like Lisp, so the answers I see in ruby are sometimes a little bit strange to me.

Maybe it's the Ruby Way, and I'm not used to it. So, dear internet, I open the floor to you to show me your implementation of the following problem statement.

Implement the following function:

# add1 - increments items in an array matching specified value
#
# param: arr - array of integers to manipulate
# param: val - integer, value to increment
# param: n   - integer, control value specifying behavior of manipulation
#   n == 0 means increment all occurrences of val
#
#   n > 0  means increment up to n occurrences of val
#          from left-to-right (forward)
#
#   n < 0  means increment up to n occurrences of val
#          from right-to-left (backward)
#
# return: arr with proper values incremented

Examples:

# add1 [1,4,1,5,1], 1, 0 -> [2,4,2,5,2]

# add1 [1,4,1,5,1], 1, 2 -> [2,4,2,5,1]

# add1 [1,4,1,5,1], 1, -2 -> [1,4,2,5,2]

Ok, have you done it? Right. Now here are some questions to consider about your implementation:

Are you manipulating the array in-place? If not, can you change it so that it does (in which case I guess rubyists would say the function name should be 'add1!')?

Do you have 3 separate cases for handling the value of n (n == 0, n > 0, n < 0)? Can you collapse it down to 2? How about only 1?

Let's say that n is positive (> 0) and the array has a billion elements, but you've already incremented n values after the first 100 or so elements. Does your implementation continue to loop over the whole array, or can it short-circuit and return early?

Did you use array#reverse twice somewhere in your code? (Lots of people do this, which is fascinating to me, to handle the negative n case)

Are you using iterators like .each or .map, or are you using a normal, index-based for loop?

I find the wide variety of answers I get very interesting, but almost all use a double reverse technique when handling negative n values (reverse the array, use .each or similar, reverse array again before returning it).

To be clear, this is not a 'gotcha' question. I am not looking for a particular answer which I consider correct. I care more about how the candidate can explain the choices they made in their implementation and how they communicate while they code. A working implementation counts for a lot, of course, but I know there is more than one way to skin a cat. Whether I consider their answer to be optimal or something that I would use in production is another issue, but it is not something that weighs much in my overall decision.

My background is mainly in embedded systems programming. My main concern when I code is for speed and efficiencey, both in runtime and in memory consumption.

Since this is the internet, and nothing is at stake, I pose the following challenge: I want to see your most optimal implementation of this problem. Mainly I want to see the array updated in-place and with no wasted cycles while looping. I'm mostly curious to look at the ruby answers.

For reference, below is my implementation written in javascript (since I have no idea how I would do this similarly in ruby), just so you can see how my mind thinks about this type of problem.

/*
 * add1 - increments items in an array matching specified value
 *
 * param: arr - array of integers to manipulate
 * param: val - integer, value to increment
 * param: n   - integer, control value specifying behavior of
 *              manipulation
 *   n == 0 means increment all occurrences of val
 *
 *   n > 0  means increment up to n occurrences of val
 *          from left-to-right (forward)
 *
 *   n < 0  means increment up to n occurrences of val
 *          from right-to-left (backward)
 *
 * return: arr with proper values incremented
 */

function add1(arr, val, n) {

  var step, start, stop, count;

  if (n >= 0) {

    if (n == 0) {
      n = arr.length;
    }
    start = 0;
    stop = arr.length;
    step = 1;

  } else { // n < 0

    n = Math.abs(n);
    start = arr.length - 1;
    stop = -1;
    step = -1;

  }

  count = 0;

  for (var i = start; i != stop; i += step) {
    if (arr[i] == val) {
      arr[i]++;
      count++;

      if (count == n) {
        break;
      }
    }
  }

  return arr;

}

By the way, we are hiring at Exec, so you should come join us!

Further discussion on Hacker News.

— Fin.
Tagged: code javascript ruby

Like this post? Please share the love!
blog comments powered by Disqus