Re:Array Iteration Interview Problem
by netmeta4 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.
First step: the increment requirement, the in place requirement, the short circuit requirement, are all the same thing. So, break that part off.
The general purpose for loop gives me the willies. 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.
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.