• 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
  • Bear Bibeault
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • paul wheaton
Saloon Keepers:
  • Ganesh Patekar
  • Frits Walraven
  • Tim Moores
  • Ron McLeod
  • Carey Brown
Bartenders:
  • Stephan van Hulst
  • salvin francis
  • Tim Holloway

Given a LinkedHashSet of anagrams, print each set of anagrams alphabetically and on a new line.  RSS feed

 
Ranch Hand
Posts: 32
3
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
(This is a small part of a larger question - )

Given a LinkedHashSet of anagrams, print each set of anagrams alphabetically and on a new line. (The anagrams will always be grouped like below because of the way they were added to the LinkedHashSet )

[lamp, palm, finger, fringe, elbow, below, bowel]

I am trying to traverse my LinkedHashSet to give the following output :

lamp palm
finger fringe
elbow below bowel

I cant see how this output is possible, even by changing the LinkedHashSet to a linkedlist or other data structure.

Any tips or ideas ?

 
Marshal
Posts: 6263
420
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Kevin Mckeon wrote:Given a LinkedHashSet of anagrams, print each set of anagrams alphabetically and on a new line.

...

I am trying to traverse my LinkedHashSet to give the following output :

lamp palm
finger fringe
elbow below bowel


Please explain what do you mean by alphabetically, I don't see it reflected in your given output example.
 
Rancher
Posts: 3757
40
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That looks like it's been orderd by length, with increasing length getting a new line, and then ordered alphabetically.
But I expect your requirements will specify that?
 
Master Rancher
Posts: 3002
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My 2 cents:

If you have a method, say normalizeString, that turns a String "abcabcd" into "aabbccd", then you can create a LinkedHashMap<String, TreeSet<String>> with key the normalized Strings, and value a List (or Set) of the input Strings. Should be just a few lines.
 
Liutauras Vilda
Marshal
Posts: 6263
420
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Dave Tolls wrote:and then ordered alphabetically


output example wrote:elbow below bowel


Alphabetically supposed to be: below, bowel, elbow
 
Liutauras Vilda
Marshal
Posts: 6263
420
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Kevin Mckeon wrote:Any tips or ideas ?


Not really the tip, but would you be able to solve this exercise if you'd be able to tell whether two given strings are anagrams?

For instance:


Kevin Mckeon wrote:I cant see how this output is possible


Please clarify, what exactly you don't understand. How to check whether something is anagram of something? Or how to present the result in the given form?
 
Dave Tolls
Rancher
Posts: 3757
40
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:

Dave Tolls wrote:and then ordered alphabetically


output example wrote:elbow below bowel


Alphabetically supposed to be: below, bowel, elbow



Apart from that one...
 
Kevin Mckeon
Ranch Hand
Posts: 32
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Apologies for the confusion. I will forget about the alphabetically ordered output because at the moment I am way off,

Here is the full question and my solution

Problem

Two words are matched if they are anagrams.
Given a set of words, print out all matched words.

- Each set of words should be printed on a separate line.
- Words that are not matched should not be printed.
- The output should be alphabetically ordered across each line and within each line. (forget about this for the moment)

Input : "lamp", "palm", "finger", "deal", "elbow", "fringe", "silent", "teaching", "below", "bowel",

Expected output :

lamp palm
finger fringe
elbow below bowel


Solution



I hope that using a LinkedHashSet is the best option for a solution. My first attempt involved loops and inner loops and it was a nightmare!
 
Sheriff
Posts: 12748
210
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I like Piet's suggestion to get the normalized form of each input word, then see if it matches other normalized forms. You'd put all words that have the same normalized form in one "bucket" then print out each bucket that has more than one entry in it.
 
Liutauras Vilda
Marshal
Posts: 6263
420
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Looking to Piet's tip (missed it before), I must say I like it too. I have solution ready.

@OP
I really advise to follow Piet's suggestion, certainly easier approach than I had initially in my mind.

Anyway, go small.

First thing is to figure out how to normalize string/anagram. There is a habitual approach or using streams. As for habitual, think if you could convert string to an array of(?) and use Collections class to sort it? So later you could construct back the string from sorted array. Using streams api is slightly easier.
 
Kevin Mckeon
Ranch Hand
Posts: 32
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:Looking to Piet's tip (missed it before), I must say I like it too. I have solution ready.

@OP
I really advise to follow Piet's suggestion, certainly easier approach than I had initially in my mind.

Anyway, go small.

First thing is to figure out how to normalize string/anagram. There is a habitual approach or using streams. As for habitual, think if you could convert string to an array of(?) and use Collections class to sort it? So later you could construct back the string from sorted array. Using streams api is slightly easier.



I will give this ago, thanks @piet.

On a side note, would this question be considered a difficult interview question ? As I am a junior full stack developer, I don't think a single developer in my office would have gotten the answer out correctly. Only someone (like piet) who is probably working with HashMaps and TreeMaps on a daily basis and who is lucky enough to spot the correct structure would stand any chance.

This was one of two code questions (the other is write a method to check if two unsorted string arrays have the same elements) and two multiple choice questions about MultiThreading. The test was 90 minutes.

Personally I felt this was difficult but maybe I am underestimating the Java developer required skill level.

Some feedback on whether or not my solution was up to scratch or not would be very much appreciated.
 
Marshal
Posts: 61766
193
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Kevin Mckeon wrote:. . . would this question be considered a difficult interview question ? . . .

No, I don't think it is too difficult. You would need ive minutes to think about the question and it should be possible to complete those questions in the 1½ hours. The two programming questions are actually similar.
 
Liutauras Vilda
Marshal
Posts: 6263
420
BSD
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Kevin Mckeon wrote:On a side note, would this question be considered a difficult interview question ?


Probably the most difficult part is to come up with a decent idea what approach to take down the route (it isn't about the code, it is about the strategy). This is in fact what Piet suggested - a possible approach, he didn't mention a lot of specifics how to achieve it at a low level, however, he did mention the possible data structure(s) you may want to use - so these were part of the hint.

My approach in a stressful moment most likely (surely) would have been different (meaning worse, but all that comes with experience, how quickly you can identify the problem and choose a reasonable approach, it is still due ), which would have taken more time to implement.

Now that Piet gave an idea how this could be solved, personally for me it took about 15 minutes to implement at a code level (time may differ based on experience, some would implement quicker, some maybe slower). But that's the question now, did you catch his hint in general? Do you have an abstract idea what he was talking about?

Kevin Mckeon wrote:Personally I felt this was difficult but maybe I am underestimating the Java developer required skill level.


Well, it isn't a rocket science, let's put it that way, so probably you were/are expected to come up with some kind of solution (might not complete, but with a visible light at the end of the tunnel). Regardless how you feel and this interview went - definitely solve this exercise now, so you know the possible solution(s) for such (or similar) problem next time you see it. And guess what, maybe Piet saw this problem before? (that comes with practice which builds the baggage of experience, remember?). It is useful to spend some time on forums seeing what problems floating around as there is a big chance in one or another form these are going to be asked in an interview(s) - usually many problems share similar parts with other problems. Certainly we saw anagrams questions on these forums before, but personally myself never attempted to solve it - so in this case I could blame just myself, but now granted, if somebody ever asks me such question in interview, it wouldn't take me more than 15 minutes to solve. So get it solved and same will apply to you.

After some time I guess we could share our solutions, and wouldn't be surprised that even knowing same idea, solutions would differ to some extent.
 
Kevin Mckeon
Ranch Hand
Posts: 32
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for all the help. It feels like it has been invaluable if not eye-opening.

Seems like I have a bit of work to do before the next interview.

Anyway, Id really like to view someones solution using the LinkedHashMap<String, TreeSet<String>> approach

I understand the concept but I am finding it hard to implement without multiple loops which I think is incorrect. In the end I had to settle for a similar method which is far from short and took a lot longer than 15 minutes  :

 
Sheriff
Posts: 23876
50
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't see the need for copying the original array into a List. Why not just sort the original array and use that for building your TreeSet?
 
Liutauras Vilda
Marshal
Posts: 6263
420
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The method signatures you have they don't go inline with the requirements you have been given.

Requirements wrote:Given a LinkedHashSet of anagrams


So you have been given a tip to normalize potential anagrams.

So the normalization of the string how do you think it would look like? It is simply by taking string characters apart, sort them alphabetically and assembling back to string.

For that there are at least 2 approaches, one is a more habitual, more seen, and the other which derives from recent Java (Java 8+) versions.

Habitual:

More modern:

Both methods by passing in string "abcabcd" would return "aabbccd" (characters sorted alphabetically). So now you can do the same with each word before deciding what to do next.

What else been suggested, is to use certain data structure, which you could use for mapping. So lets say you have strings "abcabcd" and "baacbcd", so they are anagrams. By using normalize function both inputs would return same output "aabbccd". Now what you can do with that?

You can do some mapping:

What that results to, is by the given "abcabcd" and "baacbcd" anagrams, it maps their normalized form to the original their forms.

i.e.:

Check method's implementation how it's done.

Then you mentioned, that needs to print out only anagrams. Meaning if there are at least two words which are anagrams of each other. So to filter the result you are interested in, you need to return the ones, which have size greater than 1 and simply prepare these values for the desired output. I'll show you singular method which does both things, but I'd recommend you to extract it to few:

So from the method above you can extract one more method which acomplishes step .filter (I did so in my final version shown below).

And the final method simply calls a method which calls another methods... and it may look like:

Now, there were a mentioning of sorting (horizontally and vertically), so TreeSet data structure retains sorting alphabetically, so really you don't need to do anything else in this case as you are dealing with Strings.

My final program looked like that:

And the output was:
below, bowel, elbow
finger, fringe
lamp, palm


Probably there are more elegant or more efficient solutions, I haven't tested it much on bigger inputs, so really don't know whether the performance is on an issue side. If that would prove to be the case - would look for optimizations.

What I see now, is that I could improve naming as it lacks on some aspects or a bit misleading, inconsistent.

Kevin Mckeon wrote:In the end I had to settle for a similar method which is far from short


The solution I showed also isn't very short. I could shorten it (probably twice) by simply having all in one or two methods, use stream for several actions to acomplish, but does the length of code is most important? Readability probably is more important, to have methods which do one thing only, even though you have to have quite a few of them.
 
Piet Souris
Master Rancher
Posts: 3002
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Liutauras
a cow for your superb replies! My code was indeed a bit shorter, but in essence the same. It is advisable, to get a good impression of what the effects are on the outcome, to try various Map and Collection types. So, for instance, try a LinkedHashMap<String, TreeSet<String>>, and a TreeMap<String, List<String>>, where that TreeSet and the TeeeMap are subject to several Comparators.

@Kevin
It is indeed a matter of experience and knowledge. First of all, the Java Collections Framework is a very powerful piece of software, very much worth getting to grips with! It can save you a lot of code, and a lot of practice will make you think often in the direction of Collections when devising a solution to some problem. (with the emphasize on: practise!).
In fact, the Oracle tutorial about the JCF gives an explicit example of using anagrams. See: anagram demo, section: Multimaps.

A couple of years ago I followed an introductory Scala course at Coursera, and one of the assignments was: given a sentence, produce all the anagram sentences.  So, for instance, given the sentence "you olive", an anagram sentence would be "I love you", and once having dealt with such assignments, no anagram puzzle will ever scare you again!

Another example of the power of the JCF is your second assignment: given two unsorted arrays of Strings, see if both arrays are the same. Well, turn both arrays into two Lists, and use list1.containsAll(list2). One line of code (plus another one to test a necessary other condition!).

 
Saloon Keeper
Posts: 5157
54
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:

I prefer the slighlty more java-8-esq approach using computeIfAbsent().
 
Liutauras Vilda
Marshal
Posts: 6263
420
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the cow, Piet!

@Carey, indeed, way nicer approach, noted

Now that we started unofficial competition about the program's length...

Piet, I bet 8 bits that was your "just a bit" shorter version. So you didn't want to put me on shame, what a gentleman!
 
Carey Brown
Saloon Keeper
Posts: 5157
54
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
 
Piet Souris
Master Rancher
Posts: 3002
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Be sad that we don't get paid at all!    

Here is my version. I extended it on second thoughts. It is now not so short anymore, but I hope it makes it more clear what is going on.
I did not use the computeIfAbsent method, but the plain old groupingBy, in several variants, just to illustrate some possibilities.

@Kevin
we've been throwing quite some violence at you! So have a cow, both for your topic, your contributions and as encouragement for things to come! (but that will be tomorrow).
 
Liutauras Vilda
Marshal
Posts: 6263
420
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:@Kevin
we've been throwing quite some violence at you! So have a cow,


Indeed. Have one from me too. This topic appeared to be very popular, already been viewed more than 10.000 times in just slightly more than 1 day.

@Kevin
We messed up cards for you by showing how we'd solve this task, however, you still have one to go (meaning second part of the exercise).
 
Piet Souris
Master Rancher
Posts: 3002
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And here's the cow that I promised.
 
Saloon Keeper
Posts: 1174
73
Eclipse IDE Hibernate jQuery MySQL Database Spring Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Congratulations Kevin Mckeon,

Your question has made it to our Journal  

Have a Cow!
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!