Array Iteration Interview Problem

[tylermenezes]

> Lots of people do this, which is fascinating to me, to handle the negative n case

It makes sense, because performance differences between that and the "optimal" solutions are usually negligible, and the "optimal" solutions aren't usually optimal when you take into account readability and maintainability.

Embedded development is significantly different than developing for the web. Buying more servers is usually more efficient than taking twice as long to develop and update code. Interviewing with people who refuse to acknowledge this is extremely frustrating.

[revelation]

Performance differences are anything but negligible. In the case of the "billion elements", you are now spending the majority of time for reversing the array twice.

As a programmer you should always know what kind of cost you are incurring, both asymptotically and down to cycles.

Trying to condense all the cases into one (using reverse or local state like 'step' from OPs version) is what hurts readability and maintainability.

Also, the "buy more metal" argument is hardly applicable for implementing this one way or another. Its an argument for using whatever platform you are most productive in.

[jazzychad]

> Interviewing with people who refuse to acknowledge this is extremely frustrating.

I agree. Let me be clear, I'm just having a bit of fun posing this challenge on my blog. In no way do I count minor inefficiencies in implementations against candidates. Now, if they come up with an n^2 solution I might be concerned...

I know how web development works, I understand throwing more servers at it usually is the easiest solution.

But also now that mobile is becoming hot, it is more like embedded systems than web development, so when I'm interviewing mobile candidates we definitely discuss things regarding runtime and memory tradeoffs.

[netmeta4]

My python solution, with commentary.

First step: the increment requirement, the in place requirement, the short circuit requirement, are all the same thing. So, break that part off.

    def addl(list, target, n):

        indexes = lazy_find_n(list, target, n)
        for index in indexes:
            list[index] += 1

The general purpose for loop gives me the willies.

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

What is the difference between i += step, arr[i]++, count++? Are you absolutely sure your start, stop, step & count won't over run your array boundaries? Are you willing to bet control of your users, CPU instruction pointer? What if a new requirement is an operation besides increment? What happens when the next guy, implementing the new operation, isn't as careful with his loop/subscript conditions? (end rant)

Second step: create a lazy_find_n() which returns an iterator of the indexes of the list items we want to modify.

    from itertools import ifilter, islice

    def lazy_find_n(list, target, n):
        # generate indexes in desired direction
        if n >= 0:
            indexes = xrange(len(list))
        else:
            indexes = xrange(len(list)-1, -1, -1)

        # filter indexes for items matching target
        indexes = ifilter(lambda i : list[i] == target, indexes)

        # only as many as requested
        if n != 0: indexes = islice(indexes, abs(n))

        return indexes

Since xrange, ifilter and islice return iterators, the value of indexes is computed only as needed. That is, if islice only returns a 2 item iterator, it doesn't matter how many items the iterator from ifilter would have returned, as long as there are at least 2. (If there are less, islice returns less.) Furthermore, the iterator from xrange only processes until ifilter, and islice are satisfied.

[AustinYun]

Here's my second Javascript draft. I intend to refactor it tomorrow so that the three if branches are unrolled into their own functions. Especially since some bizarre facet of Javascript's type coercion makes it impossible to do early returns inside the iterator function ([] << 1 somehow comes out as 1, not [1]).

https://github.com/austinyun/challenges/blob/master/array-it...

    function increment_where_pure(array, match, n) {
        var count;
    
        function iterator(f, acc, item) {
            // f is the function used to combine array arguments -- push || unshift
            if (count === 0) {
                f.call(acc, item);
            } else {
                if (item === match) { item += 1; }
                f.call(acc, item);
                count -= 1;
            }
            return acc;
        }
    
        if (n === 0) {
            return _.map(array, function(item) {
                return item === match ? item + 1 : item;
            });
        }
    
        if (n > 0) {
            count = n + 1;
            return _.reduce(array, iterator.bind(null, Array.prototype.push), []);
        }
    
        if (n < 0) {
            count = -n + 1;
            return _.reduceRight(array, iterator.bind(null, Array.prototype.unshift), []);
        }
    }

[telemachos]

I've posted and deleted this a few times, since I keep rethinking it. This is a Lua version, and I'm pretty new to Lua (it's good practice). No reverses needed; just numeric for loops.

I'd rather keep n = 0 as a separate case since it doesn't need to consider a break point or a count variable. The test - Is n 0? - happens once and by including it, you can omit a lot of pointless tests - Am I at the breakpoint? - and increments - Add another one to count. Those tests and increments seem much worse than the single test - especially if the array (a table in Lua) will grow to very, very large sizes.

But I would be happy to hear if I'm looking at it wrong or missing a good trick in Lua.

    function add1(t, val, n)
        if n >= 0 then
            start = 1; stop = #t; step = 1
        else
            start = #t; stop = 1; step = -1
        end
    
        if n == 0 then
            for i = start, stop, step do
                if t[i] == val then t[i] = t[i] + 1 end
            end
        else
            break_point = math.abs(n)
            count = 0
            for i = start, stop, step do
                if count == break_point then break end
    
                if t[i] == val then
                    t[i] = t[i] + 1
                    count = count + 1
                end
            end
        end
    
        return t
    end

[thomaspun]

I changed the interface to what I think it's more 'Ruby'. If you are looking for in-place solution, we should use the ! to indicate it's more 'dangerous' than the other solution which returns a new copy.

I'm new to Ruby so I'd love to hear feedback from other more experienced Rubyists on HN. (And I couldn't find reverse_each_with_index so I had to write my own.)

https://github.com/tpun/add1/blob/master/add1.rb

[brendino]

While the implementation of this would be pretty straightforward, the method signature you're asking for seems convoluted, in my opinion. Here's why:

- "add1" is not very descriptive of what the method actually does, since it adds one, but only sometimes. This title makes it sound like the method simply increments each value by one.

- When you say "if it is zero, do this, but if it is positive, do this...", this thinking creates a "secret handshake" in your code, so a new developer would have to read the method in depth to understand what it does in each case.

- If this method will have widespread use in your code for arrays, consider extending the array class with the method, so that you can call it directly on an instance of an array.

I propose you change the method signature to:

  increment_where_value_equals(value, options = {})

So you could call it like:

  increment_where_value_equals 1, { :direction => :forward, :limit => 2 }

or even like:

  increment_where_value_equals 1

While the implementation may get a little more complicated this way, you're making the method signature much more clear and descriptive, which will lead to better code overall.

[telemachos]

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

I doubt you mean anything very judgmental by 'normal', but this still jumped out at me. In Ruby an index-based for loop is pretty unusual. The for loop is non-idiomatic, and it also has a scope leak: https://gist.github.com/3232118.

[djur]

There actually _is no_ "normal, index-based" for loop in Ruby, only a for ... in iteration construct. Most C-style for loops can be implemented as #times or #up_to/#down_to/#step iterations.

[jazzychad]

hmm, my apologies if that sounded judgmental. I started coding a long time ago, so doing for loops was a very fundamental part of learning how to code. I (incorrectly?) assumed most people learned that form of looping first.

[rcfox]

Please never actually write code like this!

Here's my C version. :)

    #include <stdio.h>
    #include <stdlib.h>
    
    #define NELEMS(x) (sizeof(x) / sizeof(x[0]))
    
    void add1(int* arr, size_t size, int val, int n) {
        if(!arr || size == 0) return;
    
    #define add1_start ( n >= 0 ? 0 : size-1 )
    #define add1_end (( n >= 0 ? i < size : i >= 0 ) && ( n != 0 ? inc < abs(n) : 1 ))
    #define add1_iterate ( n >= 0 ? ++i : --i )
    
        int inc = 0;
        for(int i = add1_start; add1_end; add1_iterate) {
            arr[i] += (arr[i] == val ? ++inc, 1 : 0);
        }
    }
    
    void test(int val, int n) {
        int arr[] = {1,4,1,5,1};
        add1(arr,NELEMS(arr),val,n);
    
        for(int i = 0; i < NELEMS(arr); ++i) {
            printf("%d ",arr[i]);
        }
        printf("\n");
    }
    
    int main() {
        test(1,0);
        test(1,2);
        test(1,-2);
        return 0;
    }

[spicyj]

My Python solution:

    def add1(arr, val, n):
        it = xrange(len(arr))
        if n < 0:
            it = reversed(it)
            n *= -1

        found = 0
        for i in it:
            if arr[i] == val:
                arr[i] += 1
                found += 1
                if found == n:
                    break

        return arr

[mef]

One for ruby 1.9:

  def add1(arr, val, n)
    limit = (n == 0 ? arr.length : n.abs)

    enumerator = (n < 0 ? (arr.length-1).downto(0) : (0).upto(arr.length-1))
    enumerator.each do |i|
      if arr[i] == val
        arr[i] += 1
        limit -= 1
      end

      break if limit == 0
    end
    arr
  end

[jmkeyes]

Chicken Scheme:

  (use vector-lib)

  (define (add1 vec val n)
    (define *clone* (vector-copy vec)))
    (define fold-using (if (>= n 0) vector-fold vector-fold-right))
    (define (substitution-of total-replacements value)
      (define replacements-left (if (= total-replacements 0) (vector-length vec) (abs total-replacements)))
      (lambda (index mutable-vector current-element)
        (if (and (= current-element value) (> replacements-left 0)
          (begin
            (vector-set! mutable-vector index (+ 1 current-element))
            (set! replacements-left (- replacements-left 1))))
        mutable-vector))
  (fold-using (substitution-of n val) *clone* vec))

I don't like that I have to make a copy of the vector though. Maybe unfold ...

[knowtheory]

> 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.

Do you specify this to your candidates when they write their code?

This is the thing that annoys me most about interview programming questions. If you don't give me constraints, I am going to implement a naïve version of your requirements, because you have not given me any additional criteria by which you are going to judge my code.

Knowing things about what sorts of inputs the method has to expect (should I assume that i'm going to encounter a billion elements or not?) is really important to judge correctness of fit, or whether you're just wasting your time thinking about cases you'll never encounter.

[mbrameld]

Part of being a good developer is teasing the constraints out of the customer. You're never going to be handed a perfect requirement. If you're not given constraints don't get annoyed, simply ask about them.

[prophetjohn]

Here's my 10-minutes-of-thought JavaScript implementation. I was going to do Ruby until I realized how long it's been since I wrote any Ruby.

I only got it down to 2 cases

    function add1(arr, val, n) {
      var m = 0, i;
    
      if(n > 0) {
        for(i = 0; i < arr.length && m < n; i++) {
          if(arr[i] === val) {
            arr[i]++;
            m++;
          }
        }
      } else {
        for(i = arr.length; i >= 0 && (m !== n || !n); i--) {
          if(arr[i] === val) {
            arr[i]++;
            m--;
          }
        }
      }
      console.log(arr);
    }

[pbsd]

Overly complex C++11: http://ideone.com/yHzej

The output assembly is actually pretty good (std::vector specialization):

        ; prologue
    L19:
	add	eax, esi
	cmp	ebx, eax
	je	L4
    L8:
	mov	ecx, DWORD PTR [eax]
	cmp	ecx, DWORD PTR [edi]
	.p2align 4,,3
	jne	L10
	add	ecx, 1
	sub	edx, 1
	mov	DWORD PTR [eax], ecx
    L10:
	test	edx, edx
	jg	L19
    L4:
        ; epilogue

[tikhon]

this reminds me of how even fulton, the author of the ruby way, made a critical mistake in "the ruby way" 1st edition (fixed in 2nd edition) and matz chimed in saying " "Don't modify the receiver while you are iterating over it." http://www.justskins.com/forums/collect-with-block-modifying...

[jkbr]

My Python version (in-place, no reverse):

    def add1(arr, val, n):
        todo = abs(n) or len(arr)
        seq = xrange(0, len(arr), 1) if n >= 0 else xrange(len(arr) - 1, 0, -1)
        for i in seq:
            if arr[i] == val:
                arr[i] += 1
                todo -= 1
                if not todo:
                    break
        return arr

[kbenson]

perl, for fun:

  sub add1 {
      my ($arrayref,$val,$count) = @_;
      # Just incremet matches and return if we aren't limited
      # Useless return of array ref
      return \map { $_++ if $_ == $val } @$arrayref unless $count;
      # increment up to count matches
      for ($count<0 ? reverse @$arrayref : @$arrayref) {
          next if $_ != $val;
          $_++;
          # Advance count towards zero
          $count<0 ? $count++ : $count--;
          return if $count == 0;
      }
  }

Splitting the loop into separate versions for positive and negative counts is quicker than checking if count is positive or negative each iteration, but I figured that's a step more than I wanted to take it.

Alternatively, defining a variable for the amount the $count changes (-1 or 1) and just adding that to count would work as well, but I'm working under the assumption that's less likely to be special cased in the interpreter than post-{in,de}crement.

Edit: Clarified reasoning behind post-increment, etc.

[azylman]

Solution in CoffeeScript:

    add1 = (arr, val, n) ->
      n = arr.length if n is 0
      arr = arr.reverse() if n < 0
      count = 0
      for num, i in arr
        break if count > (Math.abs n)
        arr[i]++ if num is val
        count++
      return if n < 0 then arr.reverse() else arr

[jazzychad]

another double reverse... I guess coffeescript really does want to be ruby :)

[nwmcsween]

I wouldn't do any of this, Ruby / Python are OO so they provide already baked in primitives to do this, e.g:

    array.map { |e| e + val }

It bugs me when developers roll their own instead of utilizing what's already been done (minus performance reasons).