User Tools

Site Tools



  • 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


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


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)


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]
            a_dict[value] = index

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

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


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

    → 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.

python_coding_interview.txt · Last modified: 2024/06/08 23:05 by admin