These are the notes for Python Coding Questions, episode 15, the fifth and last round of string questions. Three questions that come up in placement interviews: building a long string in a loop (why += can get slow and "".join doesn't), the caesar cipher (letters as numbers with ord and chr, wrapped with % 26), and checking whether one string is a rotation of another (the a + a trick, and the length check it needs). Along the way you'll see a loop timed for real that gets four times slower when the input doubles, TypeError: sequence item 2: expected str instance, int found, a cipher that turns xyz into {|}, and a rotation check that says yes to a substring.
Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real. Two things will differ on your machine: timings (they change from run to run and from computer to computer; each one shown here is a representative run) and tracebacks, which show the full path to your file; here it is shortened to main.py.
Q1: Building a long string in a loop (+= vs "".join)
Real-life example: a chai stall writes one line on the bill for every order: chai 10. By night there are thousands of lines. Imagine a shopkeeper who, for every new order, copies the whole bill onto a fresh page and then adds one line. The more orders, the more copying. A smarter shopkeeper puts each slip on a spike and glues them together once, at night.
The question: build one big string out of many small pieces (lines of a bill, rows of a CSV file, words of a sentence), as fast as possible.
Ask the interviewer: how many pieces, roughly? Is there a separator between the pieces (a newline, a comma, a space)? Are all the pieces already strings?
Attempt 1: bill += line
The obvious way: start with an empty string and add one line per order. Time it for 25,000, 50,000 and 100,000 orders with time.perf_counter(), a clock for timing short pieces of code (call it before and after, and subtract).
import time
for n in [25_000, 50_000, 100_000]:
start = time.perf_counter()
bill = ""
for i in range(n):
bill += "chai 10\n" # one line per order
print(n, "orders:", round(time.perf_counter() - start, 2), "seconds")
Output:
25000 orders: 0.06 seconds
50000 orders: 0.25 seconds
100000 orders: 1.24 seconds
(25_000 is just 25000: Python lets you put underscores in numbers to make them easier to read.)
Twice the orders, about four times the time. That's the fingerprint of O(n²) (quadratic) work: double n, and n × n becomes four times bigger.
Why: strings are immutable
A Python string is immutable: once it's made, it can never change. So bill += line can't add to the old bill. It builds a brand new string, copies every character of the old bill into it, adds the line, and the old string is thrown away.
| Order number | Characters copied by this += |
|---|---|
| 1 | 8 |
| 2 | 16 |
| 3 | 24 |
| ... | ... |
| n | 8 × n |
Adding all of those up gives about 8 × n²/2 characters copied. For 100,000 orders, that's about 40 billion character copies. That's the shopkeeper rewriting the whole bill for every order.
You can check that += makes a new string with is, which tells you whether two names point to the very same object:
a = "chai"
b = a # b and a are the same string
a += " 10" # a new string is made for a
print(a, "|", b)
print(a is b)
Output:
chai 10 | chai
False
b still holds the old string: += didn't change it, it made a new one and moved the name a to it.
The fix: collect the pieces in a list, then "".join once
A list is mutable: it can grow. lines.append(line) puts one more item at the end without copying the others (on average O(1)). At the end, "".join(lines) is called on the separator (here the empty string: nothing between the pieces). It adds up the total length once, makes one string of exactly that size, and copies each piece once: O(n) in total.
import time
start = time.perf_counter()
lines = []
for i in range(100_000):
lines.append("chai 10\n") # a list grows cheaply
bill = "".join(lines) # one copy at the end
print(len(bill), "characters")
print(round(time.perf_counter() - start, 4), "seconds")
Output:
800000 characters
0.0041 seconds
The same 800,000-character bill, in a few thousandths of a second: hundreds of times faster than the += loop.
An honest note: CPython's += shortcut
CPython is the standard Python (the one you download from python.org, and the one SyntaxPilot runs). It has an optimisation: when a string is a local variable inside a function and nothing else points to it, += can sometimes grow it in place instead of copying. So the same loop inside a function can be fast:
import time
def build_plus(n):
bill = ""
for i in range(n):
bill += "chai 10\n"
return bill
def build_join(n):
lines = []
for i in range(n):
lines.append("chai 10\n")
return "".join(lines)
for f in (build_plus, build_join):
start = time.perf_counter()
f(100_000)
print(f.__name__, round(time.perf_counter() - start, 4), "seconds")
Output:
build_plus 0.0045 seconds
build_join 0.0027 seconds
Don't rely on it. It's an implementation detail: it doesn't work at the top level of a script (as you saw above), it stops working as soon as a second name points to the string, and other Pythons (PyPy, for example) don't do it at all. "".join is always linear, and it's what interviewers expect.
The join trap: everything must be a string
words = ["masala", "chai", 10]
print(" ".join(words))
Output:
Traceback (most recent call last):
File "main.py", line 2, in <module>
print(" ".join(words))
~~~~~~~~^^^^^^^
TypeError: sequence item 2: expected str instance, int found
join only glues strings; it never converts anything for you. "Sequence item 2" is the item at index 2, the number 10. Convert each item with str() first. The separator can be any string, and join even works on a string, because a string is a sequence of characters:
words = ["masala", "chai", 10]
print(" ".join(str(w) for w in words))
print(", ".join(["dal", "roti", "sabzi"]))
print("-".join("2026"))
Output:
masala chai 10
dal, roti, sabzi
2-0-2-6
str(w) for w in words is a generator expression: it hands join one converted item at a time, without building another list first.
Complexity: O(n) time for the appends plus O(n) for the join, where n is the total number of characters. O(n) space for the list and the final string.
Q2: The caesar cipher
Real-life example: two friends pass a secret note in class: meet at 5. They shift every letter 3 places forward in the alphabet: a becomes d, b becomes e, m becomes p. The friend shifts back by 3 to read it. This is the caesar cipher, one of the oldest codes in the world (Julius Caesar is said to have used a shift of 3). And what comes 3 places after x, y and z? The alphabet should go round like a clock: a, b, c.
The question: write caesar(text, shift) that shifts every letter by shift places, wrapping around after z. Keep capital letters capital, and leave anything that isn't a letter (spaces, digits, punctuation) unchanged. Decoding should be caesar(secret, -shift).
| Call | Result |
|---|---|
caesar("abc", 3) |
'def' |
caesar("xyz", 3) |
'abc' |
caesar("Meet at 5, Zoya!", 3) |
'Phhw dw 5, Crbd!' |
caesar("abc", -1) |
'zab' |
Letters are numbers: ord and chr
To shift a letter, we need it as a number. Every character has a number called its Unicode code point. ord(ch) gives the number of a character, and chr(n) gives the character for a number. The lowercase letters are 97 to 122, and the capitals 65 to 90, in alphabet order.
print(ord("a"), ord("b"), ord("z"))
print(ord("A"), ord("Z"), ord(" "), ord("5"))
print(chr(97), chr(100), chr(123))
Output:
97 98 122
65 90 32 53
a d {
Attempt 1: chr(ord(ch) + shift)
def caesar(text, shift):
out = ""
for ch in text:
out += chr(ord(ch) + shift)
return out
print(ord("a"), ord("b"), chr(100))
print(caesar("abc", 3))
print(caesar("xyz", 3))
print(caesar("Meet at 5", 3))
Output:
97 98 d
def
{|}
Phhw#dw#8
abc becomes def, correct. But xyz becomes {|}, the space became # and 5 became 8.
Why it fails
The code points don't stop at z (122). After it come { (123), | (124), } (125). Nothing told the numbers to go back to a. And we shifted everything, including spaces (32 + 3 = 35, which is #) and digits.
The fix: work with the position in the alphabet, and wrap with % 26
- Turn the letter into its position in the alphabet:
ord(ch) - ord("a")is 0 fora, up to 25 forz. - Add the shift, then take
% 26, the remainder after dividing by 26. That turns a straight line of numbers into a circle:25 + 3 = 28, and28 % 26 = 2, which isc. - Turn the position back into a letter:
chr(ord("a") + position).
Capital letters have their own range, so their base is ord("A") instead. Anything else is kept as it is.
| Letter | Position | + 3 | % 26 | Result |
|---|---|---|---|---|
a |
0 | 3 | 3 | d |
w |
22 | 25 | 25 | z |
x |
23 | 26 | 0 | a |
z |
25 | 28 | 2 | c |
In Python, % with a positive number on the right always gives a result from 0 to 25, even when the left side is negative. So shifting back works with the same line:
print(28 % 26, 26 % 26, 3 % 26)
print(-1 % 26, -3 % 26, (0 - 3) % 26)
print(29 % 26) # a shift of 29 is the same as 3
Output:
2 0 3
25 23 23
3
(This is different from C, C++ and Java, where -1 % 26 is -1. In Python the result takes the sign of the right-hand side.)
def caesar(text, shift):
out = []
for ch in text:
if ch.islower():
base = ord("a")
elif ch.isupper():
base = ord("A")
else:
out.append(ch) # spaces, digits stay
continue
pos = (ord(ch) - base + shift) % 26 # 0..25, wraps
out.append(chr(base + pos))
return "".join(out)
secret = caesar("Meet at 5, Zoya!", 3)
print(secret)
print(caesar(secret, -3)) # shift back to decode
print(caesar("xyz", 3), caesar("abc", 29), caesar("abc", -1))
Output:
Phhw dw 5, Crbd!
Meet at 5, Zoya!
abc def zab
The space, the 5, the comma and the ! stayed. Capital Z wrapped to capital C. Shifting by -3 gives the note back. A shift of 29 is the same as 3, and -1 turns a into z. Notice we used a list and "".join from question one.
ch.islower() is True for a lowercase letter, ch.isupper() for a capital. continue skips the rest of the loop body and goes to the next character.
One caution: islower() is also True for lowercase letters outside the English alphabet, like é or ß. The formula above would then give a wrong letter. If the input can contain them, test for the English letters only: "a" <= ch <= "z" and "A" <= ch <= "Z".
ord takes exactly one character
print(ord("ab"))
Output:
Traceback (most recent call last):
File "main.py", line 1, in <module>
print(ord("ab"))
~~~^^^^^^
TypeError: ord() expected a character, but string of length 2 found
The ready-made tools: string.ascii_lowercase and str.translate
Once you understand the formula, Python can do the whole shift with a translation table: str.maketrans(from, to) builds a table that maps each character of from to the character at the same position in to, and text.translate(table) applies it to every character at once.
import string
def caesar(text, shift):
lower, upper = string.ascii_lowercase, string.ascii_uppercase
k = shift % 26
table = str.maketrans(lower + upper, lower[k:] + lower[:k] + upper[k:] + upper[:k])
return text.translate(table)
print(string.ascii_lowercase)
print(caesar("Meet at 5, Zoya!", 3))
print(caesar("Phhw dw 5, Crbd!", -3))
Output:
abcdefghijklmnopqrstuvwxyz
Phhw dw 5, Crbd!
Meet at 5, Zoya!
lower[3:] + lower[:3] is the alphabet rotated by 3: defg...xyzabc. That's question three's idea already.
Complexity: O(n) time, one step per character; O(n) space for the result.
Q3: Is one string a rotation of another?
Real-life example: four friends sit at a round table: A, B, C, D going clockwise. They all get up and move two seats. Starting from the same chair, it now reads C, D, A, B: same people, same neighbours, just turned. That's a rotation: cut the string somewhere and swap the two parts. "waterbottle" cut after wat gives "erbottle" + "wat" = "erbottlewat". But A, C, B, D has the same people with different neighbours: not a rotation.
The question: given strings a and b, is b a rotation of a?
| a | b | Rotation? |
|---|---|---|
"waterbottle" |
"erbottlewat" |
yes |
"abcd" |
"cdab" |
yes |
"abcd" |
"acbd" |
no (same letters, different order) |
"abcd" |
"bc" |
no (a piece, not the whole) |
"aab" |
"aba" |
yes |
"" |
"" |
yes |
Attempt 1: same letters? Compare them sorted
def is_rotation(a, b):
return sorted(a) == sorted(b)
print(is_rotation("waterbottle", "erbottlewat"))
print(is_rotation("abcd", "cdab"))
print(is_rotation("abcd", "acbd"))
Output:
True
True
True
The third one is True, but acbd is the shuffled table. Why? Sorting throws the order away. It checks that the same people are at the table, not who sits next to whom. That's the anagram check from episode 12; a rotation is much stricter.
Attempt 2: try every cut point
Do exactly what a rotation is: the lengths must match, and for every cut point i, a[i:] + a[:i] is one rotation. If any of them equals b, it's a rotation.
import time
def is_rotation(a, b):
if len(a) != len(b):
return False
for i in range(len(a)):
if a[i:] + a[:i] == b: # cut at i, swap the halves
return True
return len(a) == 0
print(is_rotation("abcd", "cdab"), is_rotation("abcd", "acbd"))
a = "ab" * 100_000 # 200,000 letters
b = "ab" * 99_999 + "ba" # not a rotation
start = time.perf_counter()
print(is_rotation(a, b), round(time.perf_counter() - start, 2), "seconds")
Output:
True False
False 2.33 seconds
Correct now, but the big test takes seconds. Why? There are n cut points, and every cut builds a new string of length n with slicing and +. n × n: O(n²). (Why is b not a rotation? Every rotation of "abab...ab" still alternates letters; b ends with "abba", two bs in a row.)
The last line, return len(a) == 0, handles two empty strings: the loop never runs, and "" is a rotation of "".
The fix: every rotation lives inside a + a
Write a twice in a row: it's like walking round the table twice. Every rotation of a appears inside a + a, starting at position 0, 1, 2, ... n − 1:
a = "abcd"
doubled = a + a
print(doubled)
for i in range(len(a)):
print(i, doubled[i:i + len(a)])
Output:
abcdabcd
0 abcd
1 bcda
2 cdab
3 dabc
So b is a rotation of a when b is a substring of a + a. Python's in operator searches for a substring.
Attempt 3: b in a + a (and the trap)
def is_rotation(a, b):
return b in a + a
print(is_rotation("abcd", "cdab"), is_rotation("abcd", "acbd"))
print(is_rotation("abcd", "bc"))
Output:
True False
True
"bc" says True. Why? in finds any substring, of any length. A rotation must use every letter. So check that the lengths are equal first.
The final version
import time
def is_rotation(a, b):
return len(a) == len(b) and b in a + a
tests = [("waterbottle", "erbottlewat"), ("abcd", "cdab"), ("abcd", "acbd"),
("abcd", "bc"), ("aab", "aba"), ("", ""), ("a", "")]
for a, b in tests:
print(repr(a), repr(b), is_rotation(a, b))
a = "ab" * 100_000
b = "ab" * 99_999 + "ba"
start = time.perf_counter()
print(is_rotation(a, b), round(time.perf_counter() - start, 4), "seconds")
Output:
'waterbottle' 'erbottlewat' True
'abcd' 'cdab' True
'abcd' 'acbd' False
'abcd' 'bc' False
'aab' 'aba' True
'' '' True
'a' '' False
False 0.0005 seconds
Every case is right, and the big test takes under a millisecond instead of seconds. and short-circuits: if the lengths differ, Python never builds a + a at all.
Complexity: building a + a is O(n). CPython's substring search is fast in practice (for long patterns it uses an algorithm called "two-way" that is linear in the worst case, in recent versions). O(n) space for a + a. If an interviewer asks for a guaranteed linear search you write yourself, the answer is the KMP algorithm (Knuth-Morris-Pratt), covered in the DSA course.
Follow-up: how far was it turned?
(a + a).find(b) gives the position where b starts inside a + a, which is the cut point: how many seats everyone moved. find returns -1 when it isn't there.
def rotation_amount(a, b):
if len(a) != len(b):
return -1
return (a + a).find(b)
print(rotation_amount("abcd", "cdab"))
print(rotation_amount("waterbottle", "erbottlewat"))
print(rotation_amount("abcd", "acbd"))
Output:
2
3
-1
Common mistakes (and what you really see)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
bill += line in a long loop |
25k / 50k / 100k lines: about 0.06 / 0.25 / 1.3 s | strings are immutable: every += copies the whole string |
lines.append(line), then "".join(lines) |
" ".join(["masala", "chai", 10]) |
TypeError: sequence item 2: expected str instance, int found |
join never converts |
" ".join(str(x) for x in items) |
",".join forgetting the separator goes between |
"a,b,c", not "a,b,c," |
join puts the separator only between pieces |
add the ending yourself if you need it |
lines.join("") |
AttributeError: 'list' object has no attribute 'join' |
join is a string method |
"".join(lines) |
chr(ord(ch) + shift) |
"xyz" → "{|}" |
code points go past z |
(ord(ch) - base + shift) % 26 |
| shifting every character | "Meet at 5" → "Phhw#dw#8" |
spaces and digits shifted too | only shift letters, keep the rest |
| one base for all letters | capitals come out as wrong characters | capitals are 65..90, lowercase 97..122 | base = ord("A") for capitals |
ord("ab") |
TypeError: ord() expected a character, but string of length 2 found |
ord takes one character |
loop over the characters |
sorted(a) == sorted(b) for a rotation |
"acbd" → True |
sorting forgets the order | b in a + a |
| trying every cut | about 2.4 s for 200,000 letters | O(n²) | b in a + a, O(n) |
b in a + a alone |
"bc" → True |
any substring matches | len(a) == len(b) and ... |
Here are the two errors from the table you haven't seen yet, run for real:
lines = ["chai 10", "samosa 15"]
print(",".join(["a", "b", "c"]))
print(lines.join(""))
Output:
a,b,c
Traceback (most recent call last):
File "main.py", line 3, in <module>
print(lines.join(""))
^^^^^^^^^^
AttributeError: 'list' object has no attribute 'join'
Your turn: crack the code (solution)
You found a secret note, "Wkh fkdl lv uhdgb", but nobody told you the shift. Try every shift from 0 to 25 and print each try with its number; one line will be readable English. This is called a brute-force attack: with only 26 possible keys, trying them all takes no time, which is why the caesar cipher is a puzzle, not real security.
Solution
Decoding with shift k is caesar(note, -k).
def caesar(text, shift):
out = []
for ch in text:
if ch.islower():
base = ord("a")
elif ch.isupper():
base = ord("A")
else:
out.append(ch)
continue
out.append(chr(base + (ord(ch) - base + shift) % 26))
return "".join(out)
note = "Wkh fkdl lv uhdgb"
for k in range(26):
print(k, caesar(note, -k))
Output:
0 Wkh fkdl lv uhdgb
1 Vjg ejck ku tgcfa
2 Uif dibj jt sfbez
3 The chai is ready
4 Sgd bgzh hr qdzcx
5 Rfc afyg gq pcybw
6 Qeb zexf fp obxav
7 Pda ydwe eo nawzu
8 Ocz xcvd dn mzvyt
9 Nby wbuc cm lyuxs
10 Max vatb bl kxtwr
11 Lzw uzsa ak jwsvq
12 Kyv tyrz zj ivrup
13 Jxu sxqy yi huqto
14 Iwt rwpx xh gtpsn
15 Hvs qvow wg fsorm
16 Gur punv vf ernql
17 Ftq otmu ue dqmpk
18 Esp nslt td cploj
19 Dro mrks sc bokni
20 Cqn lqjr rb anjmh
21 Bpm kpiq qa zmilg
22 Aol johp pz ylhkf
23 Znk ingo oy xkgje
24 Ymj hmfn nx wjfid
25 Xli glem mw viehc
Shift 3: "The chai is ready". A program can even pick it for you by counting how many common English words each try contains:
def caesar(text, shift):
out = []
for ch in text:
if ch.islower():
base = ord("a")
elif ch.isupper():
base = ord("A")
else:
out.append(ch)
continue
out.append(chr(base + (ord(ch) - base + shift) % 26))
return "".join(out)
COMMON = {"the", "is", "a", "and", "of", "to", "in", "it", "ready", "chai"}
note = "Wkh fkdl lv uhdgb"
best = max(range(26), key=lambda k: sum(w in COMMON for w in caesar(note, -k).lower().split()))
print(best, caesar(note, -best))
Output:
3 The chai is ready
sum(w in COMMON for w in ...) adds up True (1) and False (0), so it counts the common words; max(range(26), key=...) picks the shift with the most.
Practice questions (with solutions)
1. Reverse the words of a sentence. "chai is ready" → "ready is chai". Extra spaces between words should not matter.
Solution
split() with no argument splits on any run of spaces and drops empty pieces (episode 13); [::-1] reverses the list; " ".join glues it back.
def reverse_words(s):
return " ".join(s.split()[::-1])
print(repr(reverse_words("chai is ready")))
print(repr(reverse_words(" hello world ")))
print(repr(reverse_words("")))
Output:
'ready is chai'
'world hello'
''
O(n) time and space.
2. ROT13. ROT13 is a caesar shift of 13. Show that applying it twice gives the original text, and explain why.
Solution
There are 26 letters, and 13 + 13 = 26, so two shifts of 13 go all the way round the circle: (p + 13 + 13) % 26 == p. ROT13 is its own decoder. Python even has it built in as a codec.
import codecs
def caesar(text, shift):
out = []
for ch in text:
if ch.islower():
base = ord("a")
elif ch.isupper():
base = ord("A")
else:
out.append(ch)
continue
out.append(chr(base + (ord(ch) - base + shift) % 26))
return "".join(out)
once = caesar("Meet at 5, Zoya!", 13)
print(once)
print(caesar(once, 13))
print(codecs.encode("Meet at 5, Zoya!", "rot13"))
Output:
Zrrg ng 5, Mbln!
Meet at 5, Zoya!
Zrrg ng 5, Mbln!
3. Build a CSV line. Given a list of rows (each a list of values, some numbers), build the text of a CSV file: values joined by commas, rows joined by newlines.
Solution
Two joins: the inner one per row (convert each value with str), the outer one for the lines.
rows = [["item", "qty", "price"], ["chai", 2, 10], ["samosa", 3, 15]]
text = "\n".join(",".join(str(v) for v in row) for row in rows)
print(text)
Output:
item,qty,price
chai,2,10
samosa,3,15
(For real CSV files, with commas or quotes inside values, use the csv module, which handles quoting for you.)
4. Are two strings rotations, ignoring case? "Chai" and "aich" should be True.
Solution
Normalise both first with casefold() (a stronger lower() meant for comparisons), then use the same check.
def is_rotation_ignore_case(a, b):
a, b = a.casefold(), b.casefold()
return len(a) == len(b) and b in a + a
print(is_rotation_ignore_case("Chai", "aich"))
print(is_rotation_ignore_case("Chai", "iach"))
Output:
True
False
5. Rotate a string by k. Write rotate_left(s, k) and rotate_right(s, k), where k may be larger than the length.
Solution
Rotating left by k is s[k:] + s[:k]. Take k % len(s) first so a large k works, and guard the empty string (% 0 would be a ZeroDivisionError). Rotating right by k is rotating left by -k, and Python's % makes that positive.
def rotate_left(s, k):
if not s:
return s
k %= len(s)
return s[k:] + s[:k]
def rotate_right(s, k):
return rotate_left(s, -k)
print(rotate_left("abcdef", 2), rotate_right("abcdef", 2))
print(rotate_left("abcdef", 8), rotate_right("abcdef", 13))
print(repr(rotate_left("", 3)))
Output:
cdefab efabcd
cdefab fabcde
''
6. A vigenère cipher (a caesar cipher with a key word). Shift each letter by the matching letter of a key word (a = 0, b = 1, ...), repeating the key. vigenere("attack at dawn", "lemon") → "lxfopv ef rnhr".
Solution
Keep a separate counter j for the key that only moves on letters, so spaces don't use up key letters.
def vigenere(text, key, sign=1):
out = []
j = 0
for ch in text:
if "a" <= ch <= "z":
shift = ord(key[j % len(key)]) - ord("a")
out.append(chr(ord("a") + (ord(ch) - ord("a") + sign * shift) % 26))
j += 1
else:
out.append(ch)
return "".join(out)
secret = vigenere("attack at dawn", "lemon")
print(secret)
print(vigenere(secret, "lemon", -1))
Output:
lxfopv ef rnhr
attack at dawn
Quick quiz
What does this print?
print("-".join("chai"))
print(chr(ord("y") + 2))
(A) chai- then a (B) c-h-a-i then { (C) c-h-a-i then a (D) TypeError
Answer
(B). join works on any sequence of strings, and a string is a sequence of characters, so the dash goes between the letters. ord("y") is 121; plus 2 is 123, and chr(123) is {. Nothing wraps unless you use % 26.
print("-".join("chai"))
print(chr(ord("y") + 2))
Output:
c-h-a-i
{
Interview questions
- Why can
s += piecein a loop be O(n²)? Strings are immutable, so each+=builds a new string and copies everything so far. The copies add up to about n²/2 characters. - What's the fast way, and why is it O(n)? Append the pieces to a list (amortised O(1) each), then
"".join(pieces)once: it computes the total length, allocates one string, and copies each piece once. - Doesn't CPython optimise
+=? Sometimes, for a local variable with no other references, it resizes in place. It's an implementation detail (not at module level, not when another name refers to the string, not in PyPy), so don't rely on it. - What does
"".join([1, 2])do?TypeError: sequence item 0: expected str instance, int found. Convert first:"".join(map(str, items)). - What are
ordandchr?ordgives a character's Unicode code point (ord("a")is 97);chris the reverse (chr(97)is'a'). - How do you wrap a caesar shift? Work with the position:
(ord(ch) - base + shift) % 26, withbase=ord("a")orord("A"), and leave non-letters alone. - Why does decoding with a negative shift work in Python? Python's
%with a positive divisor always returns 0..25, even for negative numbers (-1 % 26is 25). In C or Java it would be -1. - Is the caesar cipher secure? No: there are only 26 keys, so trying them all (a brute-force attack) breaks it instantly. Real encryption uses algorithms like AES with huge keys.
- How do you check if
bis a rotation ofa?len(a) == len(b) and b in a + a. Every rotation ofais a substring ofa + a; the length check rules out shorter substrings. - Why not
sorted(a) == sorted(b)? That's an anagram check; it ignores the order."acbd"has the same letters as"abcd"but isn't a rotation. - What's the complexity of the a + a check? O(n) to build
a + a, plus the substring search, which is linear in practice; KMP guarantees O(n).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Immutable | Can't be changed after it's made; "changing" it makes a new object | strings, ints, tuples |
| Mutable | Can be changed in place | lists, dicts, sets |
+= on a string |
Builds a new string from the old one plus the piece | s += "x" |
str.join(iterable) |
Glues the strings of an iterable with the separator between them | "-".join(["a", "b"]) → 'a-b' |
| Separator | The string join is called on; it goes between the pieces |
", " in ", ".join(...) |
list.append(x) |
Adds one item at the end of a list | lines.append("chai 10") |
| Amortised O(1) | O(1) on average over many operations, even if one is sometimes slower | append |
time.perf_counter() |
A clock for timing short pieces of code | time.perf_counter() - start |
| O(n), O(n²) | Work that grows like n, or like n × n | join; += in a loop |
| Quadratic | O(n²): double the input, four times the work | 50k → 100k lines: 0.25 s → 1.3 s |
| CPython | The standard Python implementation, written in C | what python3 usually runs |
| PyPy | Another Python implementation, with a just-in-time compiler | |
id() / is |
An object's identity / whether two names point to the same object | a is b |
| Generator expression | (f(x) for x in items): makes items one at a time |
str(w) for w in words |
str(x) |
Turns a value into text | str(10) → '10' |
TypeError |
An operation the types don't support | "".join([10]) |
| Caesar cipher | Shift every letter by a fixed number of places | shift 3: abc → def |
| Shift / key | How many places each letter moves | 3 |
| Encode / decode | Turn a message into code / back into the message | caesar(s, 3) / caesar(s, -3) |
| Unicode code point | The number of a character | a is 97, A is 65 |
ord(ch) |
The code point of one character | ord("a") → 97 |
chr(n) |
The character with code point n | chr(100) → 'd' |
| Position in the alphabet | ord(ch) - ord("a"): 0 for a, 25 for z |
ord("x") - 97 → 23 |
| Base | The code point of the first letter of the range | ord("a") or ord("A") |
% (modulo) |
The remainder after division; in Python, same sign as the divisor | 28 % 26 → 2, -1 % 26 → 25 |
| Wrap around | Going past the end and starting again at the beginning | z + 1 → a |
islower() / isupper() |
True for a lowercase / capital letter | "Z".isupper() → True |
continue |
Skip the rest of this loop step | |
string.ascii_lowercase |
The text 'abcdefghijklmnopqrstuvwxyz' |
|
str.maketrans / translate |
Build a character-for-character table / apply it | the caesar one-liner |
| ROT13 | A caesar shift of 13; applying it twice gives the original | codecs.encode(s, "rot13") |
| Brute-force attack | Trying every possible key | 26 shifts |
| Vigenère cipher | A caesar shift that changes with each letter of a key word | key lemon |
| Rotation | Cut a string and swap the two parts | "cdab" from "abcd" |
| Cut point | Where the string is cut for a rotation | a[i:] + a[:i] |
| Substring | A part of a string with no gaps | "bc" in "abcd" |
in (strings) |
True if one string is a substring of another | "bc" in "abcd" |
str.find(sub) |
The index where sub starts, or -1 |
"abcdabcd".find("cdab") → 2 |
| Anagram | The same letters in any order | "acbd" and "abcd" |
| Short-circuit | and / or stop as soon as the answer is known |
len(a) == len(b) and b in a + a |
| KMP | Knuth-Morris-Pratt: a substring search that is always O(n + m) | DSA course |
casefold() |
A stronger lower() for comparing text |
"Chai".casefold() → 'chai' |
| Edge case | An unusual input that often breaks code | "", "xyz", "bc" |
Summary
+=vsjoin: strings are immutable, so+=in a long loop copies the whole string every time: O(n²), and doubling the input made it about four times slower (1.3 s for 100,000 lines). Append the pieces to a list and"".jointhem once: O(n), a few milliseconds.joinonly accepts strings: convert withstr()first, or you getTypeError: sequence item 2: expected str instance, int found.- Caesar cipher:
ordturns a letter into a number andchrturns it back. Shifting the number directly runs pastz(xyz→{|}). Use the position in the alphabet and wrap with% 26:chr(base + (ord(ch) - base + shift) % 26), withbaseord("a")orord("A"), leaving non-letters alone. Decode with-shift; Python's%keeps it in 0..25. - Rotation: sorting ignores order (
"acbd"→True), and trying every cut is O(n²) (2.4 s for 200,000 letters). Every rotation ofais insidea + a, solen(a) == len(b) and b in a + adoes it in O(n); without the length check,"bc"passes.
Next episode: Dictionary questions: inverting a dictionary when values repeat, merging dictionaries (| and a deep merge), and safely getting a nested value by a path like "a.b.c".