2
\$\begingroup\$

Given an infinite stream with the property, such that after all 0's there are only all 1's, find the index of the last 0.

I'm looking for code review, best practices, optimizations etc. Verifying complexity to be O (log n) where n is the first 1 encountered in the search (not the first 1 in the stream).

/**
 * An infinite list takes in an the number of zeros'.
 * After those many zero's only 1's are followed.
 * This is a hypothetical class to represent a inifinite stream in real world.
 * like lets assume a linkedlist shared my multiple threads which keep appending 1's
 */
class InfiniteList extends ArrayList<Integer> {

    InfiniteList(int zeroCount) {
        super(zeroCount);
        add(zeroCount);
    }

    private void add (int zeroEnd) {
        for (int  i = 0; i < zeroEnd; i++) {
            super.add(0);
        }
    }

    @Override
    public Integer get(int i) {
        return super.size() <= i ? 1 : super.get(i);
    }

    @Override
    public int size() {
        throw new UnsupportedOperationException("The array size cannot be obtained.");
    }
}


public final class FindZeroEndInInfiniteStream {

    private FindZeroEndInInfiniteStream() {}

    /**
     * Takes in a infinite list, such that after stream of all 0's we encounter only all 1's.
     * Returns the last index of zero.
     * If no zero is found then -1 is returned.
     * This code would block until a zero is found in an infinite stream.
     * If the infinite has 0's and 1's mixed randomly then output is unpredicatable/
     * 
     * @param infinite      the infinite stream of 0's followed by 1's
     * @return              the last index of zero.
     */
    public static int zeroLastIndex(InfiniteList infinite) {
        if (infinite == null) throw new NullPointerException("The inifinte array was null");
        return modifiedBinarySearch(infinite);
    }

    private static int modifiedBinarySearch(InfiniteList infinite) {
        if (infinite.get(0) == 1) return -1;
        if (infinite.get(1) == 1) return 0;

        int passive = 0;  // does nothing, simply stores previous lower bound.
        int active = 1; // does the searching, toggling back and forth

        while(!(infinite.get(active) == 0 && infinite.get(active + 1) == 1)) {
            if (infinite.get(active) == 0) {
                passive = active;
                active = active * 2;
            } else {
                active = (passive + active)/2; // active has gone beyond the 38th parallel :). Now go back to south korea.
            }
        }
        return active;
    }


    public static void main(String[] args) {
       InfiniteList iList = new InfiniteList(15);
       Assert.assertEquals(14,  zeroLastIndex(iList));

       iList = new InfiniteList(27);
       Assert.assertEquals(26,  zeroLastIndex(iList));
    }
}
\$\endgroup\$
3
\$\begingroup\$

You might have misunderstood the program requirements: an ArrayList is not an infinite Stream.


If you don't want a stream and do instead want to assume that multiple-threads are adding to it then you shouldn't use ArrayList because it's not thread-safe; apparently, a better alternative for that purpose would be Vector.

\$\endgroup\$
  • \$\begingroup\$ And here I was thinking: How on earth to make an infinite stream? Is a good old InputStream / OutputStream considered infinite? I have to agree though that a class that extends ArrayList is not an infinite stream. \$\endgroup\$ – Simon Forsberg Feb 21 '14 at 23:32
  • 1
    \$\begingroup\$ @SimonAndréForsberg Another way to represent it would be something like Iterable<Boolean>. \$\endgroup\$ – svick Feb 21 '14 at 23:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.