SyntaxPilot
Courses/Python Coding Questions/Lesson 6
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python Coding Questions · Lesson 6 of 30

List questions II

reverse in placerotate by k (slicing and k larger than n)remove duplicates keeping order (dict.fromkeys vs a listO(n) vs O(n²))

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, nums is 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 in list(...) to see them.
  • .reverse() changes the list in place and returns None. So coaches = coaches.reverse() reverses the list, then moves the name coaches to None. 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, i and j: 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']
  • same is 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. Compare coaches = ..., which only moves the name.
  • list(reversed(coaches)) and coaches[::-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):

  1. Reverse the whole list: 5 4 3 2 1
  2. Reverse the first k: 4 5 | 3 2 1
  3. 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 first n slots 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: the id is 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

  1. 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.
  2. 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. Use nums[:] = nums[::-1], nums.reverse() or swaps.
  3. reversed(x) vs x.reverse() vs x[::-1]? reversed() returns a lazy iterator; .reverse() reverses in place and returns None; [::-1] returns a new reversed list.
  4. How do you rotate when k is larger than the list? k %= n (only the remainder matters), after checking for an empty list to avoid ZeroDivisionError.
  5. Rotate in O(1) extra space? Three reversals: whole list, first k, the rest. O(n) time.
  6. Why is insert(0, x) in a loop slow? A list shifts every item to make room at the front: O(n) per insert. Use collections.deque (appendleft, rotate) for work at both ends.
  7. 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 result is 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() or nums[:] = nums[::-1]. nums = ... only moves a name, reversed() is an iterator, and .reverse() returns None.
  • Rotate by k: k %= n first (seven weeks = two weeks), guard the empty list (ZeroDivisionError), then nums[-k:] + nums[:-k]. Avoid insert(0, ...) in a loop (O(n·k)); use three reversals for O(1) space, or deque.rotate.
  • Remove duplicates keeping order: list(set(...)) loses the order (and for strings it changes every run); x not in result is 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).