Foundations
2 / 170FoundationsLesson 2 of 5About 60 min
The sequence operations that show up in almost every solution, and the three that quietly cost you a factor of n.
A Python list is a growable array. Indexing and appending are cheap. Inserting or deleting anywhere other than the end is not, because everything after the hole has to shift.
nums = [3, 1, 4, 1, 5] nums.append(9) # cheap, adds at the endnums.pop() # cheap, removes from the endnums.pop(0) # expensive, shifts everything leftnums.insert(0, 7) # expensive, shifts everything right print(nums)A slice copies. It does not give you a view onto the original, and that single fact is behind a whole class of accidental quadratic solutions: taking s[i:] inside a loop over i copies the tail of the string on every pass.
s = "interview" print(s[0:5]) # from 0 up to but not including 5print(s[5:]) # from 5 to the endprint(s[:-1]) # everything except the lastprint(s[::-1]) # reversed, a common idiomprint(s[::2]) # every second characterYou cannot assign into a string. Every operation that looks like it edits one actually builds a new one, which is why building a string by repeated concatenation in a loop is a trap.
# Do not do this in a loop over large inputout = ""for ch in "abcdef": out += ch # Do this insteadpieces = []for ch in "abcdef": pieces.append(ch)out = "".join(pieces)print(out)Reaching for range(len(x)) out of habit is a Java reflex. Usually you want the element, sometimes you want the index and the element, and occasionally you want two sequences at once.
words = ["alpha", "beta", "gamma"] for word in words: pass # you only need the value for i, word in enumerate(words): print(i, word) # index and value together scores = [90, 80, 70]for word, score in zip(words, scores): print(word, score) # walk two sequences in stepsorted() returns a new list. list.sort() sorts in place and returns None, which is a classic way to accidentally assign None to your variable. Both take a key function, and both are stable: elements that compare equal keep their original relative order.
words = ["pear", "fig", "banana", "kiwi"] print(sorted(words, key=len)) # by lengthprint(sorted(words, key=len, reverse=True)) # longest firstprint(sorted(words, key=lambda w: (len(w), w))) # length, then alphabetical pairs = [(2, "b"), (1, "a"), (2, "a")]print(sorted(pairs)) # tuples compare element by elementA grid is a list whose elements are lists. grid[r] is the row at index r, and grid[r][c] is one cell. Row first, then column, always in that order.
len(grid) is the number of rows and len(grid[0]) is the number of columns. Walking every cell is two nested loops, the outer over rows and the inner over columns.
grid = [ [1, 2, 3], [4, 5, 6],] print(len(grid), len(grid[0])) # 2 rows, 3 columnsprint(grid[1][2]) # row 1, column 2 for r in range(len(grid)): for c in range(len(grid[r])): print(r, c, grid[r][c])Putting an f before a string lets you drop expressions into it inside braces. It is the readable way to assemble output, and it appears in a few later lessons.
name = "ana"score = 91print(f"{name} scored {score}")print(f"{len(name)}:{name}") # expressions work too, not just namesMultiple assignment reads better than temporary variables and is used constantly in two-pointer and linked-list code.
left, right = 0, len("abcdef") - 1a, b = 1, 2a, b = b, a # swap, no temporaryprint(left, right, a, b) start, end = [3, 9] # unpack a listprint(start, end)Two names, one list. Type exactly what this prints, including the brackets and spaces.
a = [1, 2, 3]b = ab.append(4)print(a)This is the mistake everyone makes exactly once. Type what it prints.
nums = [3, 1, 2]result = nums.sort()print(result)Python's // is floor division, not truncation. Type the two values separated by a single space.
print(7 // 2, -7 // 2)One loop empties a list by calling nums.pop(0) n times. The other empties a deque by calling popleft() n times. Both remove the same n items in the same order. Which statement is right?
Three small functions, no imports needed. second_largest returns the second largest distinct value. reverse_words reverses the order of the words in a sentence but not the letters inside them. running_totals returns a list where position i holds the sum of everything up to and including i.
Tests
print(second_largest([3, 1, 4, 4, 5, 5]))print(reverse_words("the quick brown fox"))print(running_totals([1, 2, 3, 4]))print(running_totals([]))Output
Run tests to see output.