Data Structures at Work: Hash Tables, Dictionaries, and Objects II
Using key-vale pairs to solve problems.
Hello stranger, it is I, your old friend.
Today, perhaps for the last time, we will discuss the application of key-value pairs in algorithms/problem solving.
We will solve two problems of varying difficulty but high similarity in solution. This will show the adaptability of this approach (dictionaries) in solving problems.
First, we cover the isAnagram problem.
Given two words word1 and word2, return true or false to indicate if both words are anagrams or not. Anagrams are words that contain the same characters but not necessarily arranged in the same order. For e.g, ate is an anagram of eat, and vice versa. Other examples are hate and heat, meat and team etc.
isAnagram(meat, team) => true
isAnagram(hate, heat) => true
isAnagram(mouse, mousse) => false
The fun part about this problem is that the characters can be arranged in any format, essentially preventing you from implementing a straightforward index based comparison.
At first thought, I considered:
Loop through word1
Check if the character at the current index is somewhere in word2.
Return false if any character is not found
Return false if the two words are not of the same length
Return true if I successfully made it to the end of the word1
All good! Sounds great. Until I thought about step 2. How do I efficiently check if the character in word1 is in word2? Can I use indexOf()? Or findIndex? or some other inbuilt function? What is the implication of using any of these methods on the overall run time? I am already looping once, I don’t want to use another O(n) function nested in this loop.
I quickly iterate over, can I use an object to store each character count? Would this make it easier to work with it if it is stored as a key-value pair, yes. Reading and writing to objects or dictionaries is constant O(1), thus it would be more efficient to use a key-value data structure to store the characters occurring in our words.
What does the new algorithm look like?
Loop through the first word
Create a count of all the characters occurring
Loop through word2
Reduce the count of each character when found, if not, return false
Return false if the two words are not of equal length
Return true if the second loop is successful
This has the advantage of being run time O(n), however, it has the disadvantage of extra storage O(n). Trade-off trade-off. This is a trade off I am willing to make.
Here is an implementation of this algorithm.
const isAnagram = (word1, word2) => {
if(word1.length !== word2.length) return false
let charCount = {}
for(let i=0; i<word1.length; i++){
if(!charCount[word1[i]]) {
charCount[word1[i]] = 0
}
charCount[word1[i]] += 1
}
for(let char in word2) {
let currentChar = word2[char]
if(!charCount[currentChar]) return false
charCount[word2[char]] -=1;
}
return true
}
Awesome, all done. Feel free to test and report edge cases!
Now, to the more interesting problem. Thanks to Ani for sending me this problem, it inspired this newsletter.
Given a list of sorted integer lists, write a function sort_lists to create a combined list while maintaining sorted order without importing any libraries or using the ‘sort’ or ‘sorted’ functions in Python.
Example:
lists = [[1,2,3,4,5,6],
[2,5,7,8],
[3,9,10,12],
[0,1,2,8]
]
def sort_lists(lists) -> [0,1,1,2,2,3,3,4,5,5,6,7,8,8,9,10,12]
The most interesting part of this problem is that it explicitly forbids the use of internal functions. Exciting. Of course it wouldn’t be much of a challenge if they let you use those; what’s the point?!
Looking at the question, my first thought was, if we join everything, we could easily sort it.
So…
Join all the lists
Sort the new long list.
Sounds easy enough. But if I can’t use the in-built sort function, what can I do? Bubble sort! No, too slow. Quicksort? Yeah…fast fast, but who’s going to implement Quicksort in an interview? Maybe I can try implementing Insertion sort? This is getting complicated.
Thinking about it a little more, it does seem like I just need to remember how many of each number occur in general. I can then form the response as a second step. Ok, this sounds better.
Go through all the numbers
Keep a count of all the occurrence of each character (hint: javascript object keys
Go through the key-value pair
Reconstruct the response array
const input = [
[1,2,3,4,5,6],
[2,5,7,8],
[3,9,10,12],
[0,1,2,8]
]
const
sortAllLists
= (lists) => {
let repeatedNumbers = {}
for(let i=0; i<lists.length; i++) {
for(let j=0; j<lists[i].length; j++) {
let currentNumber = lists[i][j]
if(!repeatedNumbers[currentNumber]) {
repeatedNumbers[currentNumber] = 0
} repeatedNumbers[currentNumber] += 1
}
}
let res = []
for(let num in repeatedNumbers) {
let numbers = repeatedNumbers[num]
for(let i=0; i<numbers; i++) {
res.push(Number(num))
}
}
return res
}
Here, we have a runtime of O(MxN) where MxN is the size of our input. We also use extra storage O(MxN) in the worst case - all numbers are unique.
Conclusion
As always, it has been a pleasure writing this (and solving these questions). I enjoy using objects/dictionaries when applicable because they provide optimal runtime solutions, albeit they often come at the cost of extra storage.
I should say that there are multiple ways of solving these problems, using a dictionary is just one way of doing it.
See ya!