5. What is a Hash Table, and what is the average case and worst case time for each of its operations? How can we use this structure to find all anagrams in a dictionary? JavaScript. Interview Questions at toptal.com .
By: Chrysanthus Date Published: 27 Oct 2025
Meaning of Hash Table
A hash table is an array whose indexes are mapped from different sequences of text. The effective contents of the different array cells can be different (use of pointers in C). The different sequences of text are arbitrary; they are not from any list. The mapping of a sequence of text to an array index, is done by a hash function. This same hash function does the mapping for all the corresponding text sequences and array indexes.A hash table consists of key/value pairs. A key is the sequence of text. For the illustration in this article, the key is one string of letters, sorted in ascending order, and the value is a list of related words.
Accessing, inserting and deleting, each has an average time complexity of O(1). The worse case time complexity for each of these operations is O(N), where N is the number of elements in the Hash Table (array).
What is Anagram?
An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. The original word or phrase is known as the subject of the anagram. Any word or phrase that exactly reproduces the letters in another order is an anagram.In the following table, the first column has groups of letters, and the letters of each group are arranged in alphabetical order. Each of these group of letters is the subject. The rest of the words in the row, are anagrams of the word (group of letters) in the first column cell. The rest of the words in the row are anagrams of one another. In fact all the words in a row are anagrams of one another, though the first word may not make sense.
acer: acer acre care race
abekr: baker brake break kebar
aceehrst: cheaters hectares rechates recheats teachers
aabcdkrw: backward drawback
deeilnst: enlisted lintseed listened tinseled
adehrst: hardset dearths hardest hatreds threads trashed
aelmny: laymen meanly namely
amnopst: postman tampons topsman
einoprst: proteins pointers porniest repoints tropines
aeehrstw: wreathes weathers
Strategy
A function has to be written that returns a structure consisting of rows. The first element in the row is the subject or key for the rest of the row. All the elements in each row of the structure returned, are anagrams of one another. The first element in each row is detached from the rest of the elements in the row. In fact, the structure returned, is a hash table.For the program below, all the above words, except those in the first column, are considered as the dictionary. They are sent into the program in reverse order, beginning from weathers, then wreathes and then ending with acre and acre, in that order. They are sent as one array (one list). The output has to be the above table, with the first word in each row being the key of the returned hash table. The rest of the row is the corresponding list of anagrams. The key is the group of letters arranged alphabetically.
In JavaScript the hash table to use is the map data structure. The hash table is returned with the keys as shown in the table above (similar). Each list will not necessarily be arranged in ascending order, in order to reduce the total running time of the whole function.
The algorithm function will operate as follows:
- Get the first word from the input array. Sort it by letters and use the sorted copy as a key in the hash table.
- Every word obtained from the input array (input list) is sorted first.
- It is then verified if the sorted group of letters (word) is already one of the keys in the hash table. If yes, the unsorted word is added to the list for its key. If no, the sorted word becomes a new key. In the algorithm function below, no time really, is used for this step (to search for a key).
The above algorithm continues until the end of the dictionary (end of input list).
The Program
The program is (read any comment as well):<script type='text/javascript'>
"use strict";
function find_anagrams(words) {
const mp = new Map();
for (let i=0; i < words.length; i++) {
let sorted_stringOri = words[i];
let sorted_string = sorted_stringOri.split('').sort().join(''); //sorting the string
//without searching for key across map's length
if (mp.has(sorted_string)) {
mp.get(sorted_string).push(words[i]);
}
else {
let arr = [words[i]];
mp.set(sorted_string, arr);
}
}
return mp;
}
const words = ["weathers", "wreathes", "tropines", "repoints", "porniest", "pointers", "proteins", "topsman", "tampons", "postman", "namely", "meanly", "laymen", "trashed", "threads", "hatreds", "hardest", "dearths", "hardset", "tinseled", "listened", "lintseed", "enlisted", "backward", "drawback", "teachers", "recheats", "rechates", "hectares", "cheaters", "kebar", "break", "brake", "baker", "race", "care", "acre", "acer"];
const ht = find_anagrams(words); //hash table returned
for (const [key, value] of ht) {
document.write(key + ': ');
for (let q=0; q < value.length; q++)
document.write(value[q] + ' ');
document.write('<br>');
}
</script>
The output is:
aeehrstw: weathers wreathes
einoprst: tropines repoints porniest pointers proteins
amnopst: topsman tampons postman
aelmny: namely meanly laymen
adehrst: trashed threads hatreds hardest dearths hardset
deeilnst: tinseled listened lintseed enlisted
aabcdkrw: backward drawback
aceehrst: teachers recheats rechates hectares cheaters
abekr: kebar break brake baker
acer: race care acre acer
Remarks
Only single words have been used in the above example. However, phrases can also be used in the place of words. Note that the space character is below 'a', 'A', and '0' in both ASCII and UTF-8 character code.The time complexity is obtained by multiplying the length of the given list, by the number of operations to sort the letters within a string (word). Let the length of the given list be N. Let the longest string length be L . Expect the time to sort a string to be L.log2L . So the time complexity for the find_anagrams() function is:
O(N.L.log2L)
No time is used to determine whether or not, a key is present in the hash table. The compound statement:
if (mp.has(sorted_string)) {
mp.get(sorted_string).push(words[i]);
}
else {
let arr = [words[i]];
mp.set(sorted_string, arr);
} adds
a key and its first string (with its array), if the key is not present
in the hash table. If the key is present, this same compound statement
just adds the next string (word) to the end of the corresponding array.Thanks for reading.