PART 2 · PYTHON FOUNDATIONS · CHAPTER 3

Lists, tuples, sets and Big-O

FreeLesson 26 of 78

Picking the right container is most of the answer in a coding round. The cost table below is worth memorising.

SLICING AND SORTINGPYTHON 3.12

amounts = [1198, 796, 1499, 1999, 1348]
print(amounts[0], amounts[-1], amounts[1:3], amounts[::-1][:2])

print(sorted(amounts, reverse=True)[:3])  # new list
amounts.sort()                  # in place, returns None
print(amounts)

orders = [("Delhi", 747), ("Pune", 3498), ("Delhi", 846),
          ("Pune", 1598), ("Mumbai", 796)]
by_city_then_amt = sorted(orders, key=lambda o: (o[0], -o[1]))
print(by_city_then_amt)

Output

1198 1348 [796, 1499] [1348, 1999]
[1999, 1499, 1348]
[796, 1198, 1348, 1499, 1999]
[('Delhi', 846), ('Delhi', 747), ('Mumbai', 796), ('Pune', 3498), ('Pune', 1598)]

SETS DO RECONCILIATION IN ONE LINEPYTHON 3.12

source = {101, 102, 103, 104, 105}
target = {101, 102, 104, 106}

print("missing in target:", source - target)
print("extra in target:  ", target - source)
print("in both:          ", source & target)
print("all ids:          ", sorted(source | target))

point = (12.97, 77.59)          # tuple: fixed record
lat, lon = point
print(lat, lon, {point: "Bengaluru"}[point])

Output

missing in target: {105, 103}
extra in target:   {106}
in both:           {104, 101, 102}
all ids:           [101, 102, 103, 104, 105, 106]
12.97 77.59 Bengaluru

Tuples are immutable, so they can be dict keys and set members. Lists cannot.

The cost table

Operation	list	set / dict	Why it matters
`x in c`	O(n) scan	O(1) average	Checking 1 lakh ids against a list of 1 lakh is 10 billion comparisons. Make it a set.
Append / add	O(1) amortised	O(1) average	Both fine
Insert or delete at front	O(n)	n/a	Use `collections.deque`: O(1) at both ends
Get by index / key	O(1)	O(1) average	dict lookups are why one-pass solutions work
Sort	O(n log n)	n/a	Top 3 of a million? `heapq.nlargest` is O(n log k)
Memory	Lowest	Higher (hash table)	For huge data, stream it instead (page 35)

Practice before you move on

Use sets to find the customer_ids that appear in orders.csv but not in customers.json.
Sort the rows of orders.csv by amount, highest first, and print the first three order_ids.