How to find a number of instances of a particular String in a ArrayList but without using for loop

[Vivek Hingorani]

I have a arraylist

List<String> myname = new ArrayList<String>();
		myname.add("V");myname.add("I");myname.add("V");myname.add("E");myname.add("K");

I want to know the number of Occurences of "V" (which is 2) in the above arrayList but without a for loop.
Please help.

[Carles Gasques]

Interesting,

How do you expect to accomplish the requirement without iterate the list?

[Campbell Ritchie]

You can do it with a while loop, which fulfils the original question, but you will still have to iterate the List.
Lists are not designed to count instances of a particular object. You can create such a class by combining your List with a Map, and putting them into a wrapper class. And how does the Map do the counting? If you look in the Java Tutorials, you can see a Map example which counts.

[Vivek Hingorani]

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.

[Paul Beckett]

It is possible.

java.util.Collection contains a retainAll method. Using retainAll prevents you from having to iterate the collection but retainAll will probably be iterating the collection internally.

[Bear Bibeault]

Perfect fodder for "How to tell if an interviewer knowns nothing about interviewing".

[Jeff Verdegan]

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.

Yes, there are API methods you can use, but they still have to iterate the List. It's impossible to do it without iterating. Just hiding the iteration in another method doesn't change that, and the fact that it's a core API method instead of one that we write doesn't make it any different either.

[Abhay Agarwal]

Hi Vivek

Below mentioned is the dirty way to answer the question. This solution will work for the same arraylist given in question.

List<String> myname = new ArrayList<String>();
		myname.add("V");
		myname.add("I");
		myname.add("V");
		myname.add("E");
		myname.add("K");

Set<String> alphaSet = new HashSet<String>(myname);

System.out.println("Number of occurences of 'V' = " + ((myname.size() - alphaSet.size()) + 1));

Here, we have not used any loop in above lines.

Above code might not work if data varies (for example - if we have more than 2 Letters with multiple occurrences )
So above code work in restricted conditions but since this was an interview question, this solution should be acceptable.
However , if we have this requirement while writing a Production level Java code for any application, then, we have to use far better and generic solution to tackle such scenarios.

Hope this explanation helps !!

Thanks
Abhay

[Jelle Klap]

Recursion?

[Jeff Verdegan]

Abhay Agarwal wrote:
Below mentioned is the dirty way to answer the question. This solution will work for the same arraylist given in question.
[snip]
Here, we have not used any loop in above lines.

That doesn't actually work.

[Jeff Verdegan]

Jelle Klap wrote:Recursion?

Evil, yet interesting.

True, any problem that can be solved by iteration can also be solved by recursion. But I wonder if a recursive approach could avoid any and all API calls that iterate. I leave it to those in the mood to solve puzzles to work that out.

[Jelle Klap]

import java.util.Arrays;
import java.util.List;

public class Main {
	public static void main(String[] args) {
		List<String> list = Arrays.asList(new String[] { "V", "I", "V", "E", "K" });

		System.out.println(freq(list, "V", list.size()));
	}

	public static int freq(List<String> list, String value, int listSize) {
		if (listSize == 0) {
			return 0;
		} else if (list.get(listSize - 1).equals(value)) {
			return 1 + freq(list, value, listSize - 1);
		}
		return freq(list, value, listSize - 1);
	}
}

[Jeff Verdegan]

Unless you restrict your List type to ArrayList, list.get(listSize - 1) may require iteration.

[Mike Simmons]

Well, since List is an interface, we could imagine that any method call could involve iteration, if implemented in a silly enough way. But in practice, are 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. Not as an implementation of List, anyway.

The other possibility that comes to mind would be something like this:

  public static int freq(List<String> list, String value, int listSize) {
    if (listSize == 0) {
      return 0;
    } else if (list.get(0).equals(value)) {
      return 1 + freq(list.subList(1, listSize), value, listSize - 1);
    }
    return freq(list.subList(1, listSize), value, listSize - 1);
  }

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]

I guess it also depends what we mean by "iterate". The current LinkedList implementation does have a for loop that could iterate, but for get(listLength - 1) it won't execute the body of the loop even once. Which doesn't count as iterating, in my book, but it might in someone else's.

[Jeff Verdegan]

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.

At first I was going to point out that get(listSize - 1) != get(size() - 1), but just now I realized you're doing list.subList(1, listSize), value, listSize - 1. Hmm.... ponder... muddle... think...

I suppose that a sufficiently crappy implementation of subList() might also involve iteration. But again, are there any out there that do?

I guess it depends on what you count as iteration. Calling subList(1, ...) on a LinkedList iterates to the second element. I wouldn't consider iterating to the second element of N progressively smaller lists any different from iterating an entire N-element list.

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.

ArrayList.remove calls System.arraycopy, which, though native, presumably iterates if we're copying more than some fixed block size.

[Mike Simmons]

Hmmm, I guess the AbstractList.SubList implementation in JDK 7 does indeed do what I would call iteration. Not on creation of the SubList, but on the get(). OK, good point. I thought there would be a custom implementation for LinkedList that would handle it more efficiently. Oh well.

Point conceded on System.arraycopy().

[Jeff Verdegan]

Mike Simmons wrote:I thought there would be a custom implementation for LinkedList that would handle it more efficiently.

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.

This turned out to be more interesting that I first thought. Thanks for doing the heavy lifting!

[Mike Simmons]

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.

Well, there's more you could do for the subList() implementation, without making it an array. I would have the SubLinkedList locate its own first and last nodes just once, perhaps lazily. That might arguably involve iteration (by one element in this example). But at least you'd do it just once per SubLinkedList created. The AbstractList.SubList implementation does extra iteration pretty much every time you access the sublist.

[Campbell Ritchie]

Jeff Verdegan wrote:Unless you restrict your List type to ArrayList, list.get(listSize - 1) may require iteration.

Probably T extends List & RandomAccess would permit such indexing without iteration.

[Campbell Ritchie]

Jeff Verdegan wrote: . . . True, any problem that can be solved by iteration can also be solved by recursion. . . .

I can't remember how to do it, but you can prove that recursion and iteration are equivalent to each other.

Now, they call a language Turing complete if it supports selection iteration and sequence, but I think Turing actually described a theoretical language which supported sequence selection and recursion. I may be mistaken on that point.