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
• Paul Clapham
• Ron McLeod
• Bear Bibeault
• Liutauras Vilda
Sheriffs:
• Jeanne Boyarsky
• Junilu Lacar
• Henry Wong
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Jj Roberts
• Tim Holloway
• Piet Souris
Bartenders:
• Himai Minh
• Carey Brown
• salvin francis

# Better code for interview question list duplicate characters in a String

Master Rancher
Posts: 237
24
Here is the solution as I would write it for a coding interview:

Quick, easy, and clean (at least in my opinion)

Time complexity is O(n).
Justification: We loop through each letter in the String exactly once (and only perform O(1) operations on it, which is the HashSet's add). Therefore the algorithm is T(n) where n = length of String, in the best and worst case, therefore it is O(n).

Space complexity is O(n).
Justification is easiest through examples.

Take the worst case. String "aabbcc". This would result in duplicates holding "A", "B", "C", and allCharactersSet holding "A", "B", "C", therefore worst case is T(n * 2)
Take the best case. String "aaaaa". This would result in duplicates holding "A", and allCharactersSet holding "A", therefore best case is T(1)
Average case would be T(n), you can work out example "abc" to see why.

Because the worst case is n times a constant, this is linear, and therefore the space complexity is O(n).

Marshal
Posts: 71047
291
• 1
Nice
I might change “letter” to “character” or “keystroke” throughout in that documentation comment, and I would also say that triplicates, quadruplicates, etc., are counted together with duplicates and not otherwise distinguished from them.
OP: Do you think ZG was correct to make that method static? Please justify your opinion.
OP: There are at least three differences between my suggestion and ZG's. I used a silly name for a Set. I didn't use toUpperCase(), so MS and ms wouldn't appear as duplicates. There is one more difference between our solutions. Did you notice what it is, and what difference that will make to any output?

Bartender
Posts: 2732
133
• 2
I wanted to share.. this would have been my submission:

Master Rancher
Posts: 3719
47
• 2
Nice use of distinct() there to simplify, Salvin.  Internally it ends up doing basically the same thing as a two-set solution, but more clearly and concisely.

My own 2-set solution was similar but without the distinct():

There are many different ways we can organize this, trading off readability, reusability, concision, flexibility to requirement change, and other factors.  And a lot of "readability" depends on what you are used to.  I like the potenial reusability and flexibility of the map of character counts:

By the way I am a bit disappointed to see everyone else ignoring safe code point handling.

Zachary Griggs
Master Rancher
Posts: 237
24
• 1
Lots of good solutions here!

Personally I made the method static because if I had to use this in my project, I would create some sort of StringHelper or StringUtility class that does not get instantiated. The method itself doesn't need any sort of state to operate correctly. Though this is very much open for debate; I don't think there's a "correct" answer here so I'd be interested in hearing other perspectives.

I believe you could also do a toSet() call, rather than the .distinct().toList(). Though that works completely fine as well.

Mike Simmons
Master Rancher
Posts: 3719
47
• 1
I think many of these choices depend on how you imagine this functionality might be reused.  Right now we have exactly one use case.  In my code I didn't really bother extracting reusable methods, because I don't know what else you might want to do.  But I could imagine various ways it could be reused.

For example, you might need to check for duplicates across a very large volume of input, perhaps too big (or from different sources) to fit comfortably in a single String.  So you might need a stateful object to do something like this:

Something like that could be totally reasonable if you're going to reuse it.  But it's overkill right now.  Probably.

I also might imagine different ways the question might change in the future.  What if they want to know what is the most common character?  What about the non-repeated characters?  Characters repeated exactly 3 times?  For these reasons, I imagine the most reusable thing to code here would be to make a map of character counts.  Well, code point counts.  But others may find that unnecessary, and therefore it feels like unnecessary overhead, either cognitive or in physical memory.  (Though I'm pretty sure it's not any actual overhead, in terms of physical memory.)  I think both interpretations are valid, absent more info on what the customer actually wants, or may need in the future.

With all this room for interpretation, anything that simply solves the problem as stated, accurately and clearly, seems like fair game.  In an interview, I think a candidate should try to ask about these sort of questions as they occur.  Interviewers often want to know your thought processes, how you solve problems, including how you analyze potentially incomplete requirements.

Ranch Hand
Posts: 42

Zachary Griggs wrote:Lots of good solutions here!

Personally I made the method static because if I had to use this in my project, I would create some sort of StringHelper or StringUtility class that does not get instantiated. The method itself doesn't need any sort of state to operate correctly. Though this is very much open for debate; I don't think there's a "correct" answer here so I'd be interested in hearing other perspectives.

I believe you could also do a toSet() call, rather than the .distinct().toList(). Though that works completely fine as well.

I found this thread from the code ranch October journal and I came here to respond the exact same thing. I saw some one ask the OP an opinion on why Zachary Griggs made the method static.

Campbell Ritchie
Marshal
Posts: 71047
291
• 1
Unfortunately OP didn't answer my question. Do you think ZG was right to make that method static?

Anand Athinarayanan
Ranch Hand
Posts: 42
• 1
Yes I think ZG was right. In my mind I think of this like a utility type of method which can stand alone and can operate on the given input. I also think this is like some of the Apache IO Utils library most of which are static.
Would love to hear your opinion.

Campbell Ritchie
Marshal
Posts: 71047
291
• 2
I agree with you.

Ranch Foreman
Posts: 2060
12

Campbell Ritchie wrote:
OP: Do you think ZG was correct to make that method static? Please justify your opinion.

Thanks.
Yes , I believe  that's right.
Reason is that is a method is just doing something and not affecting anything related to class.

Example where one would not go for static :

No id this do something is DoSomeGeneralPurpose thing which does not alter x then we can make them static .
Is that's correct ?

Campbell Ritchie
Marshal
Posts: 71047
291

Monica Shiralkar wrote:. . . not affecting anything related to class. . . .

You mean, not affecting anything related to an object. Not that static variables are good design in the first place.

Monica Shiralkar
Ranch Foreman
Posts: 2060
12

You mean, not affecting anything related to an object.

Thanks. Yes.   So does that mean that :
If the method modifies properties of the objects, then make it non static
If the method does some general purpose computation and does not modifies properties of the objects, then make it  static.

Is that correct?

What does this mean?

Campbell Ritchie
Marshal
Posts: 71047
291
What do you mean by “general purpose”?

Monica Shiralkar
Ranch Foreman
Posts: 2060
12
General purpose means suppose class has properties employeeName and employeeAge, then do something which doesnt have anything to do with modifying either of these.It does something else.

Campbell Ritchie
Marshal
Posts: 71047
291
Please supply a definition of “general purpose” rather than an example. I don't think you think “general purpose” means the same as what I think it does.

Monica Shiralkar
Ranch Foreman
Posts: 2060
12

Campbell Ritchie wrote:Please supply a definition of “general purpose” rather than an example. I don't think you think “general purpose” means the same as what I think it does.

By general purpose I meant for a purpose other than setting (and thus modifying ) one or more properties of the object.

Campbell Ritchie
Marshal
Posts: 71047
291
• 1
Not what it means in this country; it means suitable for use in most situations. If the toString() method isn't suitaable for use anywhee, I don't know what is.

Monica Shiralkar
Ranch Foreman
Posts: 2060
12

Campbell Ritchie wrote:Not what it means in this country.

What does this mean ?

Monica Shiralkar
Ranch Foreman
Posts: 2060
12

Campbell Ritchie wrote:If the toString() method isn't suitaable for use anywhee, I don't know what is.

How is this related?

Monica Shiralkar
Ranch Foreman
Posts: 2060
12

Campbell Ritchie wrote:If the toString() method isn't suitaable for use anywhee, I don't know what is.

So method is a non static method and it does not even manipulate the properties of the object. So what I had mentioned above is incorrect that use static method if it does not manipulate the property of an object. So this is wrong but  what is correct?

Campbell Ritchie
Marshal
Posts: 71047
291
No, toString() doesn't alter any of the state of the object. But it does use and read it.

Marshal
Posts: 26128
77
• 2

Monica Shiralkar wrote:So what I had mentioned above is incorrect that use static method if it does not manipulate the property of an object. So this is wrong but  what is correct?

An instance method belongs to an object, whereas a static method belongs to a class. An instance method can therefore access variables and methods of the object which it belongs to. ("Instance" variables and methods) Whereas a static method can only access variables and methods of the class which it belongs to. ("Static" variables and methods)

It therefore follows that if a method doesn't access any instance variables and methods, then one should seriously consider making it a static method.

The example of toString()... clearly it is designed to access instance variables of an object so clearly it could not be a static method.

Monica Shiralkar
Ranch Foreman
Posts: 2060
12
So based on this :
If a method accesses/manipulates properties of an object ,make it non static.
If a method does not access/manipulate properties of an object but instead accesses/manipulates only class variables (static variables ),then make it static.

Is that correct ?

Campbell Ritchie
Marshal
Posts: 71047
291
• 1
No. You most probably shouldn't be altering static variables in the first place. What about methods which don't use any fields at all? What about factory methods which have to alter variables in objects, but are usually marked static? What about methods inherited from interfaces? What about the most dubious classification of methods I have ever seen, written by quite a dubious character?

Paul Clapham
Marshal
Posts: 26128
77
Again you reference the Second Law of Life, the Universe, and Everything: "It's Actually More Complicated Than That."

Monica Shiralkar
Ranch Foreman
Posts: 2060
12
So If a method does not READ properties of an object but instead READS and uses only class variables (static variables ) or nothing at all ,then make it static.

Is that correct ?

Monica Shiralkar
Ranch Foreman
Posts: 2060
12

Campbell Ritchie wrote: What about methods which don't use any fields at all?

Yes, that's a common scenario for Helper class methods which can be made static .

Paul Clapham
Marshal
Posts: 26128
77

Monica Shiralkar wrote:So If a method does not READ properties of an object but instead READS and uses only class variables (static variables ) or nothing at all ,then make it static.

Is that correct ?

No. You may have to take into consideration the possibility that a method may be overridden by a subclass of the class you're designing. The class you're designing may not have a firm idea of what method X is supposed to do in any subclass, but you assume that the subclasses will have a better idea. This happens all the time with abstract classes and interfaces -- your rule would make it impossible to have abstract methods and to declare interfaces.

Monica Shiralkar
Ranch Foreman
Posts: 2060
12
Thanks. So in that case I think what I said is one part of the answer but not the complete one.