Tricky Ebay Coding Interview Question - JavaScript

Solution to a very popular coding interview question asked recently by - Group Anagrams.

#softwareengineering #javascript #shorts

Music
Creative Commons / Attribution 3.0 Unported License (CC BY 3.0)

[emjizone]

A longer to write yet generally more efficient script would be to use a custom hash instead of an alphabet-sort hash.

[BhargavSushant]

Cool
Now Let me rewatch this 5 more time

[SirBearingtonSupporter]

Faster run time
Create custom hash
Map all characters to prime numbers.
Hash = 1
Hash *= characterPrime

Anything that has the same hash, will be an anagram.

We’ve reduced the O(n log n) sort of the string down to just O(n). But we also aren’t rejoining the array.

And we have a fast hashmap we can add have an array of matching strings be the value.

Important note: do not use a comparator operation for your character prime number lookup.

Create an array of the size of the ascii range that you’re evaluating and put the prime numbers as the value and use subtraction of the ascii character value as your index.

[gourabbhattacharjee]

This problem is a perfect example of using the reduce function in JavaScript.
Here's a similar snippet.
export const groupAnagrams2 = (strs) => {
const ordered = strs.map((str) =>

const freqMap = strs.reduce((anagramMap, currValue, currIndex) => {
if {
= [currValue];
} else {

}
return anagramMap;
}, {});

return Object.values(freqMap);
};

[otter]

Hashmap, where the key is the sorted letters and the value is an array list, where it either creates a new array list or appends to an already existing one based on the key

[DarkSwitchJ]

sort actually have the complexity of O(n logn). Given they are anagrams of 26 letters in the english alphabet, we can build a hashmap, where the key is the int array of the occurrences of each char of the strings, and the value is the list of strings with the same key.
Then what you have to do is return the list of values.
The complexity of this algorithms is O(n), where n is the total number of characters

[vasiledamian]

The heaviest part of this is the o(n^2) for the alphabetical ordering, you can easly improve that by simply computing the lexiographical(not sure if this is the correct word haha) value which is essentially ascii value mapping for your letters, then all you have to do is add them up and check the value, you just went from squared run time to o(n*m) m being the length of the string, I'm sure there's still better ways tho

[genericcommenter]

Could also do this by keeping track of a 32 bit number. Then for each letter, OR the number with 1 bitshifted bitshifted by the offset from 'a'. Do this for each word, then group the ones where the XOR of their numbers is 0. If my napkin math is correct, that should give you an O(n*m) solution, where n is the size of the word list and m is the length of the largest word.

[quantum_dongle]

I think bloom filters would be a better solution. It would eliminate the sorting required for each string

[otter]

This feels like making a custom hashmap where when it encounters a duplicate key (the sorted letters string) it will just append that to the end of the list, but it probably won't work since the hashing algorithm isn't perfect

[xINuke]

For Python 3.9+, this would be:

def group_ambigrams(strings: list[str]) -> list[list[str]]:
ans= {}
for string in strings:
anagram = "".join(sorted(string))
ans[anagram] = ans.get(anagram, []) + [string]
return list(ans.values())

^_^ I'm a little confused about this other implementation with multiplying primes? What does that look like in pseudocode?

[nomoredarts]

Pro tip, instead of using Object as map, just use... Map

[JoJo-jjid]

How much do they give you because it took me 3 mins

[zonebooth]

I wonder how efficient reducing each string to a sum of the characters would be at finding anagrams. I'm not sure if that would have false positives.

[randfamous]

i immediately paused the video and pretended i was in that interview and wrote the code below

const inputs = ["listen", "silent", "elbow", "below", "car", "arc"]

let anagrams = {

}

inputs.forEach(str=>{

const sortedStr =
if( ! anagrams[ sortedStr ] ){
anagrams[ sortedStr ] = [ ];
}
anagrams[ sortedStr ].push(str)
})



we just came up with same approach 🍻

[abstract_VnSn]

@AlgoJS Not exactly related but what theme are you using?

[Gameplay-psub]

JS newbie here...Why do you create a vanilla object and call it "map", while JS has a Map type, which seems to be designed for the mapping? The solution is understandable, but this bit is confusing imho. Cheers!

[lucaslevandoski]

why didn't you do it with a new Map() ?

[katanaut]

It would help if you use a plug-in that outputs logs if each code line as you type. Otherwise impossible to follow.

[hugodsa]

Won’t work if you have a word with the equal characters