### Site Tools

python_coding_interview

policy:

• new entries go in the end

### What is the difference between big-Theta, big-O, big-Omega notation?

context: growth rate of an algorithm

• big-Θ notation gives an asymptotically tight bound
• big-O notation gives an asymptotically upper bound
• big-Ω notation gives an asymptotically lower bound

Ref:

### two sum challenge

Q: Return the indexes of two numbers in an unsorted list that adds up to a target value.

Assume that:

• only one pair adds up to the target number
• there are no duplicates in the list

Example:

Say the list is [7, 2, 4, 3, -1] and the target value is 5.

In this case, the numbers at index positions 1 and 3 add up to the target number (5), so the answer is (1, 3)

Solution:

In [14]:
def two_sum(a_list, target):
a_dict = {}
for index, value in enumerate(a_list):
reminder = target - value
if reminder in a_dict:
return [a_dict[reminder], index]
else:
a_dict[value] = index

In [15]:
a = [7, 2, 4, 3, -1]

In [16]:
two_sum(a, 5)
Out[16]:
[1, 3]

Ref:-

• This is discussed in
The Self-Taught Computer Scientist
The Beginner's Guide to Data Structures & Algorithms
By Cory Althoff
2021

→ Chapter 13 Hash Tables → Two Sum → pages 143-144.

• The discussion is easy to follow; comprehensive.
• The input array given in the book is trivial in the sense that the numbers are sorted in ascending order. I just jumbled the entries to show that the algo works on unsorted lists as well.
• The book seems to have many mistakes. For example,
• in pg-143 → two_sum_brute() returns the values instead of indexes.
• the insert_left() in code snippet of pg-153 is not same as insert_left() in the first code snippet of pg-154.
• Todo: (1) How to report mistakes in this book? (2) Find a better reference.