• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Paul Clapham
  • Bear Bibeault
  • Junilu Lacar
Sheriffs:
  • Jeanne Boyarsky
  • Tim Cooke
  • Henry Wong
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • salvin francis
  • Frits Walraven
Bartenders:
  • Scott Selikoff
  • Piet Souris
  • Carey Brown

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

 
Ranch Hand
Posts: 45
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have a arraylist


I want to know the number of Occurences of "V" (which is 2) in the above arrayList but without a for loop.
Please help.
 
Ranch Hand
Posts: 199
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Interesting,

How do you expect to accomplish the requirement without iterate the list?
 
Marshal
Posts: 70234
282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 45
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

 
Ranch Hand
Posts: 96
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Marshal
Posts: 67447
173
Mac Mac OS X IntelliJ IDE jQuery Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Perfect fodder for "How to tell if an interviewer knowns nothing about interviewing".
 
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.
 
Ranch Hand
Posts: 1376
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Vivek

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.

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
 
Bartender
Posts: 1952
7
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Recursion?
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Bartender
Posts: 1952
7
Eclipse IDE Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Unless you restrict your List type to ArrayList, list.get(listSize - 1) may require iteration.
 
Rancher
Posts: 3625
40
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:

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
Rancher
Posts: 3625
40
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Rancher
Posts: 3625
40
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Rancher
Posts: 3625
40
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Marshal
Posts: 70234
282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Marshal
Posts: 70234
282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
    Bookmark Topic Watch Topic
  • New Topic