• Post Reply Bookmark Topic Watch Topic
  • New Topic

Efficient Array Scanning  RSS feed

 
Marvin Porte
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello Everyone! Here's another problem I want to discuss with:
Given an array of strings, return a new array without the strings that are equal to the target string. One approach is to count the occurrences of the target string, make a new array of the correct length, and then copy over the correct strings.

wordsWithout({"a", "b", "c", "a"}, "a") → {"b", "c"}
wordsWithout({"a", "b", "c", "a"}, "b") → {"a", "c", "a"}
wordsWithout({"a", "b", "c", "a"}, "c") → {"a", "b", "a"}

Here's my solution:

There is no problem with the code, it works fine and correct with every test. I just want to ask if there's another solution for this that will be more efficient? Because in my solution, I scanned the whole array twice. First is to know the occurences of target in the array and second is to output the array. Is there a way so that I could check the number of occurences and check if it's a target then output the array only in one loop?
 
Steve Myers
Ranch Hand
Posts: 47
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you can only use arrays, I think you might be able to do it with one loop with java.util.Arrays.copyOf(), copyOfRange() methods. I have my doubts as to whether it would be more efficient.
Otherwise, look at ArrayList.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Marvin Porte wrote:Is there a way so that I could check the number of occurences and check if it's a target then output the array only in one loop?

Simply put: no. What you could do is to create an array of indexes of non-matching entries, viz:which saves you having to do the comparison twice, but personally I reckon that your way is a lot clearer.

Also, there are other structures, such as a LinkedList, where you don't need to know the output size before you start, so using one of those might be better.

Only worry about efficiency if you know that your code is not fast enough. And you should be able to prove it before you start optimizing.

Winston
 
Jayesh A Lalwani
Rancher
Posts: 2762
32
Eclipse IDE Spring Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Steve Myers wrote:If you can only use arrays, I think you might be able to do it with one loop with java.util.Arrays.copyOf(), copyOfRange() methods. I have my doubts as to whether it would be more efficient.
Otherwise, look at ArrayList.


Internally Arrays.copyOf uses System.arrayCopy so I think it should be pretty fast. Of course, it depends on JVM, but the JVM would probably just copy blocks of memory internally.
 
Marvin Porte
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Sir Steve
No sir, the return type must be an array. I tried arraylist so that there will be no problem with the size but the test in codingbat does not accept arraylist for the solution.

@Sir Winston
Thanks very much again! What I want is to have the simplest solution for a problem and with my answer, I'm not very satisfied and I thought It's very long for that problem. So I consulted here if there's an easier way to solve it. Thanks a lot sir!

@Sir Jayesh
Thank you sir! =D
 
Steve Myers
Ranch Hand
Posts: 47
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Marvin Porte wrote:@Sir Steve
No sir, the return type must be an array. I tried arraylist so that there will be no problem with the size but the test in codingbat does not accept arraylist for the solution.



ArrayList.toArray()
 
Steve Myers
Ranch Hand
Posts: 47
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Check it out it passed the codingBat tests

 
Joanne Neal
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I haven't profiled it but I suspect that the Arrays.copyOf may be a bottleneck there (creating a new array and copying elements into it) so you could reduce it to one call to that method with
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Steve Myers wrote:ArrayList.toArray()

Or indeed, any List.toArray(). Winston
 
Marvin Porte
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
To ALL:
Thanks everyone for alternative solutions, I really appreciate it. You know I'm only a beginner and don't know anything aside from basic syntax and my logic. Maybe I should start reading API docs so I could use helpful methods for my solutions next time. Thanks a lot! =D
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!