The Self-Taught Computer Scientist

Data Structures
142
If the character is already in your dictionary, you increment its value by 1.
if char in a_dict:
a_dict[char] += 1
If the character is not yet in your dictionary, you add it as a new key with a value of 1 since it is the 
first time the character has appeared so far.
else:
a_dict[char] = 1
When you print your dictionary at the end, it contains each letter in the string as well as the number 
of times it occurs.
print(a_dict)
Let’s take a look at what happens when you run your function. When you call your function and 
pass in the string 
"Hello"
, on the first iteration, your program will add an uppercase 
H
as a key in 
your dictionary and the number 1 as its value, which means your dictionary looks like this:
{"H": 1}
On the next iteration, the character is 
e
. Because 
e
is not in your dictionary yet, you add it to your 
dictionary as a key with a value of 1. Now your dictionary looks like this:
{"H": 1, "e": 1}
You do the same thing for the letter 
l
. Now your dictionary looks like this:
{"H": 1, "e": 1, "l": 1}
On the next iteration, the character is 
l
again. This time, the character is already in your dictionary, 
so you increment its key value by 1. Now your dictionary looks like this:
{"H": 1, "e": 1, "l": 2}
This process continues until you’ve gone through every character in your string. When your loop 
is over and you print your dictionary, it looks like this:
{'H': 1, 'e': 1, 'l': 2, 'o': 1}
By taking this approach, you’ve not only solved this problem but solved it in O(
n) time by using a 
hash table (in this case, 
n is the number of characters in the string).

---

Chapter 13 Hash Tables
143
Two Sum
Another common technical interview question you can use a hash table to solve is called 
two sum. In 
the two sum challenge, an interviewer asks you to return the two numbers’ indexes in an unsorted 
list that adds up to a target value. You can assume that only one pair adds up to the target number, 
and you may not use the same number in the list twice.
For example, say the target value is the number 5, and you have the following list of numbers:
[- 1, 2, 3, 4, 7]
In this case, the numbers at index positions 1 and 2 add up to the target number (5), so the answer 
is index 1 and index 2 (2 + 3 = 5).
One way to solve this problem is to use brute force by iterating through the list and adding up each 
pair of numbers to see if they add up to 5. Here is how to code a brute- force solution to this problem:
def two_sum_brute(the_list, target):
index_list = []
for i in range(0, len(the_list)):
for j in range(i, len(the_list)):
if the_list[i] + the_list[j] == target:
return [the_list[i], the_list[j]]
Your solution uses two nested loops. Your outer loop iterates through the list of numbers using 
i
, 
while your inner loop also iterates through the list using 
j
. You use both variables to create pairs, such 
as −1 and 2, 2 and 3, etc., and test if they add up to the target number. Your brute- force solution is 
simple, but it is not efficient. Because your algorithm requires two nested loops to iterate through 
every combination, it is O(
n**2).
A more efficient way to solve this problem is to use a dictionary. Here is how to solve the two sum 
challenge using a dictionary:
def two_sum(a_list, target):
a_dict = {}
for index, n in enumerate(a_list):
rem = target - n
if rem in a_dict:
return index, a_dict[rem]
else:
a_dict[n] = index 
Your function 
two_sum
takes two arguments, a list of numbers and the target number they should 
add up to:
def two_sum(a_list, target):

---