News for hackers. Stuff that matters.

netmeta4

Re:Array Iteration Interview Problem on Thursday August 02, 2012 @12:34AM (#4327276)
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.