Vivek Hingorani wrote:i said w/o iterating its not possible and interviewer asked there is a method in the api which does it for you? I was nt aware and hence asked.
Abhay Agarwal wrote:
Below mentioned is the dirty way to answer the question. This solution will work for the same arraylist given in question.
Here, we have not used any loop in above lines.
Jelle Klap wrote:Recursion?
Mike Simmons[i wrote:are[/i] there any implementations in a standard JDK that would involve iteration for get(listSize - 1)? I strongly doubt it. A singly-linked list might, but I don't think there is one in the JDK.
I suppose that a sufficiently crappy implementation of subList() might also involve iteration. But again, are there any out there that do?
Another variation could use list.remove(0). I accept that that one might have problems with some types of List available in the JDK. But at least it wouldn't iterate.
Mike Simmons wrote:I thought there would be a custom implementation for LinkedList that would handle it more efficiently.
Jeff Verdegan wrote:About the only way to make it more efficient for a LL to get something other than first or last would be to add pointers like second, third, secondFromEnd, thirdFromEnd, etc. Or, to generalize it, an array.
Probably T extends List & RandomAccess would permit such indexing without iteration.
Jeff Verdegan wrote:Unless you restrict your List type to ArrayList, list.get(listSize - 1) may require iteration.
I can't remember how to do it, but you can prove that recursion and iteration are equivalent to each other.
Jeff Verdegan wrote: . . . True, any problem that can be solved by iteration can also be solved by recursion. . . .