search

kdn251 / interviews

Everything you need to know to get the job.
https://www.youtube.com/channel/UCKvwPt6BifPP54yzH99ff1g?view_as=subscriber
MIT License
62.86k stars 12.84k forks source link

interviews/company/facebook/GroupAnagrams.java #91

Open knasim opened 5 years ago

knasim commented 5 years ago

The given solution for this can be improved by not having to sort at all.
There are 2 calls to Arrays.sort().... This can become expensive if the program input array is large over 10K. A faster solution would just be to compute the hash of each value using a prime number assigned to each letter from a-z ( can be quckly generate in code). Then for each value in the array compute hash and store it inside a map. Then to get all the grouped anagrams you lookup the map or insert whatever the case maybe. I can provide code...too

GauravMohla commented 5 years ago

I don't think there is any reason for using the first sort. It would anyhow group together using just one sort method in inner loop. Coming to your approach, how sure are you that there would be no hash collisions?

knasim commented 5 years ago

yes no need to sort. collisions ? a solid hash function. but since this is an interview question - the interviewer (depending on their degree of analness) may not dig you for that.