These are the notes for Python Coding Questions, episode 6, the second list episode. Three questions interviewers love: reverse a list in place, rotate a list by k steps, and remove duplicates while keeping the order. Each one has a trap that gives a wrong answer without any error: a name that moves instead of a list that changes, a slice that quietly does nothing when k is bigger than the list, and a set that throws the order away.
Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real; timings depend on the machine, so compare them, don't copy them.
Q1: Reverse a list in place
Real-life example: a train goes from Delhi to Jaipur: Engine, A1, B1, B2, GS (the general coach). For the return journey the order must flip. But there is no spare yard to build a second train, so you swap the two end coaches, then the next two, moving inward. That's what in place means: change the same list, using no second list.
| Input | Output (the same list, changed) |
|---|---|
["Engine", "A1", "B1", "B2", "GS"] |
["GS", "B2", "B1", "A1", "Engine"] |
[1, 2, 3, 4] |
[4, 3, 2, 1] |
[7] |
[7] |
[] |
[] |
The obvious attempts: a reversed slice, reversed(), and x = x.reverse()
def reverse_list(nums):
nums = nums[::-1]
coaches = ["Engine", "A1", "B1", "B2", "GS"]
reverse_list(coaches)
print(coaches)
print(reversed(coaches))
coaches = coaches.reverse()
print(coaches)
Output:
['Engine', 'A1', 'B1', 'B2', 'GS']
<list_reverseiterator object at 0x7f2cadc9aec0>
None
(The 0x... address is different on every run.)
Why it's wrong: three surprises, and not one error message.
- The list didn't change. Inside the function,
numsis just a name (a name tag) stuck on the caller's list.nums = nums[::-1]builds a brand new reversed list and moves the tag to it. This is called rebinding the name. The caller's list is never touched, and the new list is thrown away when the function ends.=moves a name; it never changes a list. reversed()gives an iterator, a lazy object that hands out the items one by one when asked. Printing it shows the object, not the items. Wrap it inlist(...)to see them..reverse()changes the list in place and returnsNone. Socoaches = coaches.reverse()reverses the list, then moves the namecoachestoNone. We lost our list.
The fix: two pointers
A pointer here is just an index. i starts at the front, j at the back. Swap nums[i] and nums[j], then move i one step right and j one step left. Stop when they meet; in an odd-length list the middle item stays where it is.
def reverse_in_place(nums):
i, j = 0, len(nums) - 1
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
for coaches in [["Engine", "A1", "B1", "B2", "GS"], [1, 2, 3, 4], [7], []]:
before = id(coaches)
reverse_in_place(coaches)
print(coaches, id(coaches) == before)
Output:
['GS', 'B2', 'B1', 'A1', 'Engine'] True
[4, 3, 2, 1] True
[7] True
[] True
Why it works: nums[i] = ... changes a slot of the list itself, not the name, so the caller sees the change. nums[i], nums[j] = nums[j], nums[i] swaps with one tuple assignment (no temporary variable). id() gives the identity number of an object: the same id before and after means it is the same list, changed in place. For [7], i and j are both 0, so the loop never runs; for [], j is −1 and the loop never runs either. No crash.
- About n/2 swaps: time O(n).
- Only two extra variables,
iandj: space O(1).
Follow-up: the built-in tools
coaches = ["Engine", "A1", "B1", "B2", "GS"]
same = coaches # a second name, same list
coaches.reverse() # in place, returns None
print(same)
coaches[:] = coaches[::-1] # slice assignment: also in place
print(same)
print(list(reversed(coaches)), coaches[::-1]) # new lists
Output:
['GS', 'B2', 'B1', 'A1', 'Engine']
['Engine', 'A1', 'B1', 'B2', 'GS']
['GS', 'B2', 'B1', 'A1', 'Engine'] ['GS', 'B2', 'B1', 'A1', 'Engine']
sameis a second name on the same list. It changed both times, so both were in place:.reverse()flipped it, and the slice assignment flipped it back.- Slice assignment,
coaches[:] = ..., replaces the contents of the existing list. Comparecoaches = ..., which only moves the name. list(reversed(coaches))andcoaches[::-1]build new reversed copies (O(n) extra space); the original stays as it is.- The difference matters when other code holds the same list (another name, an argument, an item inside another list).
In an interview, write the two-pointer loop first to show you understand it, then mention list.reverse(). Time O(n), space O(1).
Q2: Rotate a list to the right by k
Real-life example: a hostel has a cleaning-duty roster with five names. Every week, the last name moves to the top: that's a rotation to the right by 1. After five weeks the roster is back where it started, so seven weeks is the same as two weeks. Only the remainder matters: k % n.
| Input | Output |
|---|---|
["Asha", "Ravi", "Meena", "Kabir", "Zoya"], k = 2 |
["Kabir", "Zoya", "Asha", "Ravi", "Meena"] |
| same, k = 7 (7 weeks later) | ["Kabir", "Zoya", "Asha", "Ravi", "Meena"] |
| same, k = 5 or k = 0 | unchanged |
[], k = 3 |
[] |
Attempt 1: slicing
The last k items, nums[-k:], plus everything before them, nums[:-k].
def rotate(nums, k):
return nums[-k:] + nums[:-k]
duty = ["Asha", "Ravi", "Meena", "Kabir", "Zoya"]
print(rotate(duty, 2))
print(rotate(duty, 7)) # 7 weeks later
print(rotate(duty, 0))
Output:
['Kabir', 'Zoya', 'Asha', 'Ravi', 'Meena']
['Asha', 'Ravi', 'Meena', 'Kabir', 'Zoya']
['Asha', 'Ravi', 'Meena', 'Kabir', 'Zoya']
Why it's wrong: k = 2 and k = 0 are correct, but seven weeks later the roster didn't move at all. With five names, nums[-7:] just means the whole list, and nums[:-7] is empty. Slices never complain about going past the end (only indexing, like nums[10], raises IndexError). Whole list plus nothing: no rotation, and no error to warn us. (k = 0 only works by luck: nums[-0:] is nums[0:], the whole list, and nums[:-0] is nums[:0], empty.)
Attempt 2: k %= len(nums)
def rotate(nums, k):
k %= len(nums)
return nums[-k:] + nums[:-k]
duty = ["Asha", "Ravi", "Meena", "Kabir", "Zoya"]
for k in [2, 7, 5, 0, -1]:
print(k, rotate(duty, k))
print(rotate([], 3))
Output:
2 ['Kabir', 'Zoya', 'Asha', 'Ravi', 'Meena']
7 ['Kabir', 'Zoya', 'Asha', 'Ravi', 'Meena']
5 ['Asha', 'Ravi', 'Meena', 'Kabir', 'Zoya']
0 ['Asha', 'Ravi', 'Meena', 'Kabir', 'Zoya']
-1 ['Ravi', 'Meena', 'Kabir', 'Zoya', 'Asha']
Traceback (most recent call last):
File "main.py", line 8, in <module>
print(rotate([], 3))
~~~~~~^^^^^^^
File "main.py", line 2, in rotate
k %= len(nums)
ZeroDivisionError: integer modulo by zero
Why it's wrong: k = 2 and k = 7 now agree, 5 is a full circle, 0 is unchanged. But modulo divides, and the length of an empty list is 0: ZeroDivisionError: integer modulo by zero.
The fix: guard the empty list first
def rotate(nums, k):
if not nums:
return []
k %= len(nums)
return nums[-k:] + nums[:-k]
duty = ["Asha", "Ravi", "Meena", "Kabir", "Zoya"]
for k in [2, 7, 5, 0, -1]:
print(k, rotate(duty, k))
print(rotate([], 3), 7 % 5, -1 % 5)
Output:
2 ['Kabir', 'Zoya', 'Asha', 'Ravi', 'Meena']
7 ['Kabir', 'Zoya', 'Asha', 'Ravi', 'Meena']
5 ['Asha', 'Ravi', 'Meena', 'Kabir', 'Zoya']
0 ['Asha', 'Ravi', 'Meena', 'Kabir', 'Zoya']
-1 ['Ravi', 'Meena', 'Kabir', 'Zoya', 'Asha']
[] 2 4
Why it works: if not nums catches the empty list before the modulo. Look at k = −1: one step to the left, Ravi first. Python's % always gives a result from 0 to n − 1 when n is positive, so -1 % 5 is 4, and a right rotation by 4 is a left rotation by 1.
- Time O(n): each item is copied once.
- Space O(n): it builds a new list. That's the clean answer.
Follow-up: insert(0, pop()) k times vs slicing (the timing race)
Many people rotate by moving one item at a time. It's correct for any k, but:
import time
def rotate_slow(nums, k):
for _ in range(k):
nums.insert(0, nums.pop()) # last one to the front
def rotate_slice(nums, k):
if nums:
k %= len(nums)
nums[:] = nums[-k:] + nums[:-k]
for f in [rotate_slow, rotate_slice]:
nums = list(range(200_000))
start = time.perf_counter()
f(nums, 20_000)
print(f.__name__, nums[:3], f"{time.perf_counter() - start:.3f} s")
Output (one run; your times will differ):
rotate_slow [180000, 180001, 180002] 0.790 s
rotate_slice [180000, 180001, 180002] 0.003 s
Same answer, but the loop took over a hundred times longer.
Why: a Python list is a row of slots in memory. pop() from the end is cheap, O(1). insert(0, x) shifts every other item one slot to the right: O(n). Done k times, that's O(n·k). Slicing copies each item once: O(n). Note that rotate_slice uses slice assignment, nums[:] = ..., so it changes the caller's list in place like rotate_slow does.
Follow-up: rotate in place with three reversals, and deque.rotate
To rotate with O(1) extra space, reuse the two-pointer reverse three times. For [1, 2, 3, 4, 5] with k = 7 (so k = 2):
- Reverse the whole list:
5 4 3 2 1 - Reverse the first k:
4 5 | 3 2 1 - Reverse the rest:
4 5 | 1 2 3
def reverse(nums, i, j):
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i, j = i + 1, j - 1
def rotate(nums, k):
n = len(nums)
if n == 0:
return
k %= n
reverse(nums, 0, n - 1) # 5 4 3 2 1
reverse(nums, 0, k - 1) # 4 5 | 3 2 1
reverse(nums, k, n - 1) # 4 5 | 1 2 3
seats = [1, 2, 3, 4, 5]
rotate(seats, 7)
print(seats)
from collections import deque
d = deque([1, 2, 3, 4, 5])
d.rotate(2)
print(list(d))
Output:
[4, 5, 1, 2, 3]
[4, 5, 1, 2, 3]
Why it works: reversing the whole list puts the last k items at the front, but backwards; the two smaller reversals put each part back in its own order. Each item is touched about twice: time O(n), space O(1). When k is 0, reverse(nums, 0, -1) does nothing and the other two reversals undo each other.
collections.deque (a double-ended queue) is built for adding and removing at both ends, and has rotate(k) built in (negative k rotates left). Use it when you rotate often.
In an interview: k % n first, guard the empty list, slicing for the clean version, three reversals if they want it in place.
Q3: Remove duplicates, keeping the order
Real-life example: a family is making a wedding guest list. Three aunties send names, and some names repeat. The order matters: it's who confirmed first. If someone shuffles the cards to remove repeats, the repeats are gone, but so is the order. The right way: go down the list and keep each name the first time you see it.
| Input | Output |
|---|---|
["Riya", "Aman", "Riya", "Zoya", "Kabir", "Aman"] |
["Riya", "Aman", "Zoya", "Kabir"] |
[3, 1, 3, 2, 1] |
[3, 1, 2] |
[] |
[] |
Attempt 1: list(set(...))
guests = ["Riya", "Aman", "Riya", "Zoya", "Kabir", "Aman"]
print(list(set(guests)))
Output (two runs of the same program):
['Riya', 'Kabir', 'Zoya', 'Aman']
['Aman', 'Zoya', 'Riya', 'Kabir']
Why it's wrong: four names, no repeats, but not in the guests' order, and the order changes from run to run. Your run will very likely show yet another order. A set keeps no order. For strings, Python also randomises the hashing every time the program starts (a security feature), so the order of a set of strings can differ on every run. Never trust the order of a set.
Attempt 2: if x not in result
import time, random
def dedupe_slow(items):
result = []
for x in items:
if x not in result: # scans result every time
result.append(x)
return result
guests = ["Riya", "Aman", "Riya", "Zoya", "Kabir", "Aman"]
print(dedupe_slow(guests))
random.seed(7)
big = [random.randint(1, 20_000) for _ in range(40_000)]
start = time.perf_counter()
out = dedupe_slow(big)
print("slow:", len(out), f"{time.perf_counter() - start:.3f} s")
Output (one run):
['Riya', 'Aman', 'Zoya', 'Kabir']
slow: 17266 1.438 s
Why it's wrong (for big lists): the order is right, but 40,000 items took well over a second. x not in result checks the list one item at a time. The result grows to about 17,000 numbers, so each check can scan thousands of items. n checks, each O(n): O(n²). (random.seed(7) makes the "random" numbers the same on every run, so the test can be repeated.)
The fix: dict.fromkeys
A dictionary's keys are unique, a dictionary remembers insertion order (guaranteed since Python 3.7), and finding a key is O(1) on average. dict.fromkeys(items) makes each item a key the first time it appears; repeats are ignored. Adding this to the end of the program above:
start = time.perf_counter()
out = list(dict.fromkeys(big))
print("fast:", len(out), f"{time.perf_counter() - start:.3f} s")
Output of the whole program (one run; your times will differ):
['Riya', 'Aman', 'Zoya', 'Kabir']
slow: 17266 1.734 s
fast: 17266 0.002 s
Why it works: the same count, and hundreds of times faster: O(n²) down to O(n) time, with O(n) extra space for the dictionary. list(...) of a dictionary gives its keys, in insertion order.
Follow-up: by hand, with a seen set and a key function
Interviewers often want it by hand. Keep a set called seen for fast checks and a list for the order. A key function decides what counts as a duplicate.
def dedupe(items, key=lambda x: x):
seen = set()
result = []
for x in items:
k = key(x)
if k not in seen: # a set lookup: O(1) on average
seen.add(k)
result.append(x)
return result
emails = ["riya@mail.com", "Aman@mail.com", "RIYA@mail.com", "aman@mail.com"]
print(dedupe(emails))
print(dedupe(emails, key=str.lower))
print(list(dict.fromkeys([[1, 2], [1, 2], [3]])))
Output:
['riya@mail.com', 'Aman@mail.com', 'RIYA@mail.com', 'aman@mail.com']
['riya@mail.com', 'Aman@mail.com']
Traceback (most recent call last):
File "main.py", line 14, in <module>
print(list(dict.fromkeys([[1, 2], [1, 2], [3]])))
~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^
TypeError: unhashable type: 'list'
- Without a key, all four emails stay: they are different strings.
- With
key=str.lower,"RIYA@mail.com"and"riya@mail.com"give the same key, so we keep the first Riya and the first Aman, in order, with their original spelling. - The last line crashed:
TypeError: unhashable type: 'list'. Set items and dictionary keys must be hashable: their value can't change, so Python can store them by a hash number. Lists can change, so they are not hashable. Convert each list to a tuple first (see practice question 3). - Time O(n), extra space O(n) for the set. Same idea as
dict.fromkeys, but you control the key.
Common mistakes (and what you really see)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
nums = nums[::-1] in a function |
the caller's list is unchanged, no error | = rebinds a local name |
swap in place, nums.reverse() or nums[:] = nums[::-1] |
print(reversed(x)) |
<list_reverseiterator object at 0x...> |
reversed() returns an iterator |
list(reversed(x)) |
reversed(x)[0] |
TypeError: 'list_reverseiterator' object is not subscriptable |
an iterator has no indexes | x[-1], or list(reversed(x))[0] |
x = x.reverse() |
None; later AttributeError: 'NoneType' object has no attribute 'append' |
.reverse() returns None |
x.reverse() on its own line |
nums[-k:] + nums[:-k] with k > n |
k = 7, n = 5: nothing moves, no error | slices clip silently | k %= len(nums) first |
k %= len([]) |
ZeroDivisionError: integer modulo by zero |
the length is 0 | if not nums: return [] |
insert(0, pop()) k times |
~0.8 s vs ~0.003 s (200,000 items, k = 20,000) | insert(0) shifts every item: O(n·k) |
slicing, three reversals or deque.rotate |
list(set(items)) |
order lost, and different on each run for strings | a set has no order | list(dict.fromkeys(items)) |
if x not in result |
~1.5 s for 40,000 items | in on a list is O(n): O(n²) total |
a seen set or dict.fromkeys, O(n) |
dict.fromkeys / set on lists |
TypeError: unhashable type: 'list' |
lists can change | tuple(row) as the key |
Your turn: remove duplicates from a SORTED list, in place (solution)
[1, 1, 2, 3, 3, 3, 4] → [1, 2, 3, 4], with no set and no new list: two pointers, O(1) space.
Solution
Because the list is sorted, duplicates sit next to each other. Use two pointers: r reads every item, w is where the next new value is written. An item is new if it differs from the last value written, nums[w - 1]. Return the new length w; then either use nums[:w] or truncate the list in place with del nums[w:].
def remove_sorted_dupes(nums):
if not nums:
return 0
w = 1 # next free slot for a new value
for r in range(1, len(nums)): # r reads every item
if nums[r] != nums[w - 1]: # a new value
nums[w] = nums[r]
w += 1
return w
for nums in [[1, 1, 2, 3, 3, 3, 4], [5, 5, 5], [1, 2, 3], [7], []]:
before = id(nums)
n = remove_sorted_dupes(nums)
print(n, nums[:n], nums)
del nums[n:] # truncate in place
print(" after del:", nums, id(nums) == before)
Output:
4 [1, 2, 3, 4] [1, 2, 3, 4, 3, 3, 4]
after del: [1, 2, 3, 4] True
1 [5] [5, 5, 5]
after del: [5] True
3 [1, 2, 3] [1, 2, 3]
after del: [1, 2, 3] True
1 [7] [7]
after del: [7] True
0 [] []
after del: [] True
- Before
del, the firstnslots hold the answer and the rest is leftover junk (3, 3, 4). This is how the LeetCode version ("return k") works. del nums[n:]removes the tail from the same list: theidis unchanged.- Time O(n) (one pass), extra space O(1).
- This only works on a sorted list. For an unsorted list, use the seen set from Q3.
Practice questions (with solutions)
1. Rotate left by k (["Asha", "Ravi", "Meena", "Kabir", "Zoya"], k = 2 → Meena first).
Solution
A left rotation by k takes the first k items to the end: nums[k:] + nums[:k]. Same guards as before.
def rotate_left(nums, k):
if not nums:
return []
k %= len(nums)
return nums[k:] + nums[:k]
duty = ["Asha", "Ravi", "Meena", "Kabir", "Zoya"]
for k in [1, 2, 7, 0]:
print(k, rotate_left(duty, k))
print(rotate_left([], 3))
from collections import deque
d = deque(duty)
d.rotate(-2) # negative = left
print(list(d))
Output:
1 ['Ravi', 'Meena', 'Kabir', 'Zoya', 'Asha']
2 ['Meena', 'Kabir', 'Zoya', 'Asha', 'Ravi']
7 ['Meena', 'Kabir', 'Zoya', 'Asha', 'Ravi']
0 ['Asha', 'Ravi', 'Meena', 'Kabir', 'Zoya']
[]
['Meena', 'Kabir', 'Zoya', 'Asha', 'Ravi']
Left by k is the same as right by n − k (or right by −k). O(n) time, O(n) space; the three-reversal trick also works (reverse the first k, reverse the rest, then reverse the whole list).
2. Is one list a rotation of another? ([1, 2, 3, 4, 5] and [4, 5, 1, 2, 3] → True.)
Solution
Same length, and some left rotation of a equals b.
def is_rotation(a, b):
if len(a) != len(b):
return False
if not a:
return True
n = len(a)
for k in range(n): # try every shift
if a[k:] + a[:k] == b:
return True
return False
print(is_rotation([1, 2, 3, 4, 5], [4, 5, 1, 2, 3]))
print(is_rotation([1, 2, 3, 4, 5], [4, 5, 2, 1, 3]))
print(is_rotation([1, 2], [1, 2, 1]))
print(is_rotation([], []))
Output:
True
False
False
True
Each try builds and compares a list of n items, and there are n tries: O(n²) time in the worst case, O(n) space. Fine for an interview answer; mention that for strings the classic trick is len(a) == len(b) and b in a + a.
3. Dedupe a list of lists ([[1, 2], [3], [1, 2], [2, 1], [3]] → [[1, 2], [3], [2, 1]]).
Solution
Lists are unhashable, tuples are hashable: use the tuple as the key.
rows = [[1, 2], [3], [1, 2], [2, 1], [3]]
# 1. tuples are hashable, so dict.fromkeys works on them
print([list(t) for t in dict.fromkeys(map(tuple, rows))])
# 2. a seen set with key=tuple, keeping the original lists
def dedupe(items, key=lambda x: x):
seen = set()
result = []
for x in items:
k = key(x)
if k not in seen:
seen.add(k)
result.append(x)
return result
print(dedupe(rows, key=tuple))
Output:
[[1, 2], [3], [2, 1]]
[[1, 2], [3], [2, 1]]
[1, 2] and [2, 1] are different (order inside a row matters). To treat them as the same, use key=lambda r: tuple(sorted(r)). O(n) time (times the row length), O(n) space.
Quick quiz
What does this print?
a = [1, 2, 3, 4]
b = a
a = a[::-1]
b.reverse()
print(a == b, a is b)
(A) True False (B) True True (C) False False (D) False True
Answer
(A). a = a[::-1] makes a new list [4, 3, 2, 1] and moves the name a to it. b still names the old list, and b.reverse() flips it in place to [4, 3, 2, 1]. Equal contents, so == is True; two different objects, so is is False.
True False
Interview questions
- What does "in place" mean? Changing the same list object instead of building a new one; usually with O(1) extra space. The
id()stays the same. - Why does
nums = nums[::-1]inside a function not change the caller's list?=rebinds the local name to a new list; the caller's list is untouched. Usenums[:] = nums[::-1],nums.reverse()or swaps. reversed(x)vsx.reverse()vsx[::-1]?reversed()returns a lazy iterator;.reverse()reverses in place and returnsNone;[::-1]returns a new reversed list.- How do you rotate when k is larger than the list?
k %= n(only the remainder matters), after checking for an empty list to avoidZeroDivisionError. - Rotate in O(1) extra space? Three reversals: whole list, first k, the rest. O(n) time.
- Why is
insert(0, x)in a loop slow? A list shifts every item to make room at the front: O(n) per insert. Usecollections.deque(appendleft,rotate) for work at both ends. - Remove duplicates keeping order, in O(n)?
list(dict.fromkeys(items)), or a seen set plus a result list (which also allows a key function).list(set(items))loses the order;x not in resultis O(n²).
Glossary
| Term | Meaning | Example |
|---|---|---|
| In place | Changing the same object, not building a new one | nums.reverse() |
| Two pointers | Two indexes moving through a list, often from both ends | i from the left, j from the right |
| Pointer (here) | Just an index into the list | i = 0 |
| Name | A label that refers to an object; several names can share one object | same = coaches |
| Rebinding | Moving a name to a different object with =; the old object is unchanged |
nums = nums[::-1] |
| Swap | Exchange two values with one tuple assignment | a[i], a[j] = a[j], a[i] |
| Iterator | A lazy object that hands out items one by one, and is used up after one pass | reversed(coaches) |
None |
Python's "no value"; what .reverse() returns |
x = x.reverse() → None |
id() |
The identity number of an object; same id = same object | id(coaches) == before |
is / == |
Same object / equal contents | a == b, a is b |
| Slice | A part of a list, nums[start:stop:step]; never raises IndexError |
nums[-k:], nums[::-1] |
| Slice assignment | Replaces the contents of the same list | nums[:] = nums[::-1] |
del nums[n:] |
Removes the tail of the same list | truncating after dedupe |
| Rotate right by k | The last k items move to the front | nums[-k:] + nums[:-k] |
| Rotate left by k | The first k items move to the end | nums[k:] + nums[:k] |
Modulo % |
The remainder after division; in Python from 0 to n − 1 for positive n | 7 % 5 → 2, -1 % 5 → 4 |
ZeroDivisionError |
Raised when dividing or taking modulo by zero | 3 % len([]) |
IndexError |
Raised for an index outside the list | [1, 2][10] |
deque |
collections.deque, a double-ended queue: fast at both ends |
deque([1, 2, 3]).rotate(1) |
insert(0, x) / pop() |
Add at the front (O(n), shifts everything) / remove from the end (O(1)) | nums.insert(0, nums.pop()) |
| Hash / hashable | A number computed from a value / a value that can't change, so it can be a set item or dict key | str, int, tuple yes; list no |
TypeError: unhashable type |
Raised when a list (or other changeable value) is used as a key | set([[1, 2]]) |
| Set | Unordered collection of unique, hashable items; O(1) average lookup | seen = set() |
| Hash randomisation | Python changes string hashing on each start, so set order can change between runs | list(set(guests)) |
| Dictionary key | Unique, hashable; a dict keeps keys in insertion order | {"Riya": None} |
dict.fromkeys |
Builds a dict from items as keys (repeats ignored) | list(dict.fromkeys(xs)) |
| Insertion order | The order in which keys were first added (guaranteed since Python 3.7) | first-seen wins |
| Key function | A function that turns each item into the value used for comparing | key=str.lower |
str.lower |
Returns a lowercase copy of a string | "RIYA".lower() → "riya" |
| Tuple | An unchangeable sequence; hashable if its items are | tuple([1, 2]) → (1, 2) |
random.seed() |
Makes "random" numbers repeatable | random.seed(7) |
time.perf_counter() |
High-resolution stopwatch | timing the race |
| O(n) | Time grows in step with the input size | one pass |
| O(n²) | Time grows with the square of the size: double n, about four times the time | x not in result in a loop |
| O(n·k) | n work done k times | insert(0) k times |
| O(1) space | Only a fixed number of extra variables, whatever n is | i, j |
| O(n) space | Extra memory that grows with the input | a new list, a seen set |
Summary
- Reverse in place: two pointers swapping from both ends, O(n) time, O(1) space; in real code,
nums.reverse()ornums[:] = nums[::-1].nums = ...only moves a name,reversed()is an iterator, and.reverse()returnsNone. - Rotate by k:
k %= nfirst (seven weeks = two weeks), guard the empty list (ZeroDivisionError), thennums[-k:] + nums[:-k]. Avoidinsert(0, ...)in a loop (O(n·k)); use three reversals for O(1) space, ordeque.rotate. - Remove duplicates keeping order:
list(set(...))loses the order (and for strings it changes every run);x not in resultis O(n²);list(dict.fromkeys(items))or a seen set is O(n). Use a key function for "same" by your own rule, and tuples for lists. - For a sorted list, two pointers (read and write) remove duplicates in place with O(1) space.
Next episode: List questions III: the missing number (sum and XOR), frequency count (Counter), and the majority element (Boyer-Moore voting).