• 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Find repreating character in an array

 
Ranch Hand
Posts: 598
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
finds the index of the first repeating character in an array, by iterating through the array only once.

I implemented this as per the code given. Is there any other efficient way to do it?

>
 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think your idea is solid, although I may not have used a tree.

Basically, you have to remember every character you've encountered as you parse, then check each new one.

If we're simply talking about characters, I might just use an array of 256 ints. read a character, use it's ascii value as the index into the array. if the value there is 0, i have not encountered it, so I set the value to 1. If the value is 1, i've encountered it, so I'm done.
 
Himanshu Gupta
Ranch Hand
Posts: 598
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Fred for the reply. []
 
Himanshu Gupta
Ranch Hand
Posts: 598
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Himanshu Gupta wrote:finds the index of the first repeating character in an array, by iterating through the array only once.

I implemented this as per the code given. Is there any other efficient way to do it?

>



This will not work when we have an array like {'h','y','d','h'}
 
Himanshu Gupta
Ranch Hand
Posts: 598
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This code is working fine for the given question.

 
fred rosenberger
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
pseudocode:


From the Sun Javadocs:

char: The char data type is a single 16-bit Unicode character. It has a minimum value of '\u0000' (or 0) and a maximum value of '\uffff' (or 65,535 inclusive).



Note - my pseudocode is untested and not carefully thought out, but I think it would work.
 
Himanshu Gupta
Ranch Hand
Posts: 598
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks once again Fred. Do you see any problem in the code given by me. Just asking for your help if in case I have missed something.

 
Ranch Hand
Posts: 128
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Himanshu, both your solutions are literally fine (they do not iterate over the array) but they have a hidden iteration in the other data structures - the TreeSet.add() and ArrayList.contains() method both perform iteration to look for the given element. The TreeSet.add() takes O(log n) time, the ArrayList.contains() takes O(n). So using an ArrayList is no better than iterating over the given char array - it's just as if you were copying it and iterating over the char[] copy. The TreeSet solution is nice and fast (fastest possible in the general case of object repetition), though Fred's solution is fastest possible in the bounded by character's values case. See Wikipedia.
 
Adam Michalik
Ranch Hand
Posts: 128
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
---
(double submit, sorry)
 
Himanshu Gupta
Ranch Hand
Posts: 598
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Adam. Wonderful answers.

The question is described here.

[i]
Write a method that finds the index of the first repeating character in an array, by iterating through the array only once. If there is no repeating character, the method should return -1.

You are not allowed to use a inner loop like

because that would iterate through the array more than once.
(Hint: Data structures from the Collections framework can be used to avoid a nested loop)



[/i]
>
 
Adam Michalik
Ranch Hand
Posts: 128
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Judging from the hint, I'd say that the solution with set is the most suitable - fulfils the task's requirements, is fast enough and memory -optimal. You may consider using HashSet instead of a TheeSet initialized to the array's capacity - the add() operation will be even faster. The solution with the int array is smart, but for small char arrays a lot of memory will be wasted.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic