Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Find repreating character in an array

 
Himanshu Gupta
Ranch Hand
Posts: 598
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • 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?

>
 
fred rosenberger
lowercase baba
Bartender
Pie
Posts: 12097
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • 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
  • 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
  • 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
  • Quote
  • Report post to moderator
This code is working fine for the given question.

 
fred rosenberger
lowercase baba
Bartender
Pie
Posts: 12097
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • 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
  • 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.

 
Adam Michalik
Ranch Hand
Posts: 128
  • Mark post as helpful
  • send pies
  • 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
  • Quote
  • Report post to moderator
---
(double submit, sorry)
 
Himanshu Gupta
Ranch Hand
Posts: 598
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • 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
  • 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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic