Difficulty: Beginner to Intermediate | Prerequisites: Functions, loops, and basic operations
Strings and lists are the two data structures you will work with most in CS124. This set of notes covers how to inspect, transform, filter, and combine them: checking palindromes, counting characters, reversing words, removing duplicates, merging sorted lists, finding pairs, and more. Master these patterns and most exam problems become variations of the same handful of moves.
String
An immutable sequence of characters, defined with quotes ('hello' or "hello"). Because strings are immutable, you cannot change a character in place; you create a new string instead.
List
An ordered, mutable collection of items, defined with square brackets ([1, 2, 3]). Lists can hold any type, including other lists (nested lists). Think of it as a row of numbered slots you can read from, write to, and resize.
Index
The position of an element in a sequence, starting at 0. my_list[0] is the first element. Negative indices count from the end: my_list[-1] is the last element.
Slicing
Extracting a subsequence with sequence[start:stop:step]. The stop index is excluded. s[::-1] reverses a string or list. In simple terms, slicing lets you grab a chunk of a sequence without a loop.
in operator
Tests membership. 'a' in 'apple' returns True. Works on strings, lists, tuples, sets, and dictionaries (checking keys).
split() and join()
str.split() breaks a string into a list of words (splitting on whitespace by default). ' '.join(lst) does the reverse, joining a list of strings with a space. These two are the standard way to manipulate words within a sentence.
List comprehension
A concise way to build a new list by transforming or filtering an existing one: [x for x in lst if x > 0] returns only the positive elements. Think of it as a one-line loop that collects results into a list.
Set
An unordered collection of unique elements, created with set() or {1, 2, 3}. Useful for removing duplicates (list(set(my_list))) and for fast membership checks.
sorted()
A built-in function that returns a new sorted list from any iterable. Does not modify the original. Contrast with list.sort(), which sorts in place and returns None.
Palindrome check
Compare the string to its reverse: s == s[::-1].
For case-insensitive checks, convert to lowercase first: s.lower().
This is one of the most common introductory string questions.
Reversing words in a sentence
Split the sentence into a list of words with s.split().
Reverse the list (slicing [::-1] or .reverse()).
Join back into a string with ' '.join(reversed_list).
Counting vowels
Loop through each character, check if it is in 'aeiouAEIOU', increment a counter.
Alternatively, use a generator expression: sum(1 for c in s if c.lower() in 'aeiou').
Checking if two strings are anagrams
Two strings are anagrams if they contain the same characters in the same quantities.
Sort both strings and compare: sorted(s1.lower()) == sorted(s2.lower()).
A more efficient approach uses a dictionary (or collections.Counter) to count character frequencies.
Most frequent character
Build a dictionary mapping each character to its count.
Loop through the dictionary to find the key with the highest value.
Or use max(s, key=s.count), though this is O(n^2) because .count traverses the string each time.
Removing punctuation
Use string.punctuation (after import string) which contains all standard punctuation characters.
Build a new string keeping only characters that are not in string.punctuation.
Checking for all unique characters
Compare len(s) to len(set(s)). If they match, every character is unique.
Alternatively, loop through and add each character to a set, returning False the moment you see a duplicate.
Filtering a list (e.g. positive numbers only)
List comprehension: [x for x in lst if x > 0].
Or loop and append to a new list. Both are standard patterns.
Removing duplicates
list(set(lst)) removes duplicates but does not preserve order.
To preserve order, loop through and add each element to a new list only if it is not already there, or use dict.fromkeys(lst) in Python 3.7+.
Sorting without sort()
Implement a simple sorting algorithm manually: selection sort, insertion sort, or bubble sort.
Selection sort: repeatedly find the minimum of the unsorted portion and swap it to the front.
This tests whether you understand what sorting actually does, rather than relying on a built-in.
Merging two sorted lists
Use two pointers, one for each list. Compare the elements at both pointers, append the smaller one, advance that pointer. When one list is exhausted, append the remainder of the other.
This is the merge step of merge sort.
Finding the second-largest element
Track both the largest and second-largest as you loop through the list.
Initialise both to negative infinity (or the first two elements, sorted).
Update second-largest whenever you find a new largest, and update largest when you find something bigger than it.
Flattening a nested list
Use recursion: for each element, if it is a list, recursively flatten it; otherwise, append it to the result.
This is a natural problem for practising recursion on data structures.
Rotating a list by k positions
Slicing approach: lst[-k:] + lst[:-k] rotates right by k.
Handle the case where k is larger than the list length by taking k % len(lst).
Finding pairs that sum to a target
Brute force: two nested loops, checking every pair. O(n^2).
Efficient: use a set to track seen values. For each element, check if target - element is in the set.
Intersection of two lists
Convert both to sets and use the & operator: list(set(a) & set(b)).
Or loop through one list and check membership in the other.
Finding the longest word
Loop through the list, track the longest word seen so far by comparing len(word) to your current maximum.
Transpose of a 2D matrix
The transpose swaps rows and columns: element at [i][j] moves to [j][i].
Using list comprehension: [[row[i] for row in matrix] for i in range(len(matrix[0]))].
Or use list(zip(*matrix)) for a concise one-liner (returns tuples, wrap in list() and map if you need lists).
Students often try to modify a string in place (e.g. s[0] = 'H'). Strings are immutable in Python. You must create a new string instead.
Confusing sort() and sorted(). lst.sort() sorts the list in place and returns None. sorted(lst) returns a new sorted list and leaves the original unchanged. Assigning result = lst.sort() gives you None, which is a common bug.
Off-by-one errors with slicing. lst[1:3] gives you elements at index 1 and 2, not 1, 2, and 3. The stop index is always excluded.
Assuming set() preserves order. Sets are unordered. If you need to remove duplicates and keep the original order, loop through the list manually.
⚠️ Palindrome and anagram checks appear frequently. Know both the slicing approach and the sorted-comparison approach.
⚠️ Expect a question requiring you to write a sorting algorithm from scratch (without sort() or sorted()). Selection sort or bubble sort are the simplest to implement under time pressure.
⚠️ List comprehensions are tested both as "write one" and "read one and predict its output." Be comfortable with the syntax.
⚠️ The two-pointer merge pattern (merging two sorted lists) appears in multiple forms. It is also the foundation for understanding merge sort.
⚠️ Know how split() and join() work together. Word-counting and word-reversing questions rely on them.
True or False: 'racecar'[::-1] == 'racecar' evaluates to True. (Answer: True. "racecar" is a palindrome.)
Fill in the blank: To split the sentence 'hello world' into ['hello', 'world'], you call 'hello world'.______(). (Answer: split)
True or False: [1, 2, 3, 2].count(2) returns 1. (Answer: False. It returns 2, because the value 2 appears twice.)
Fill in the blank: len(set('aabbc')) evaluates to ______. (Answer: 3, because the unique characters are a, b, c.)
True or False: list.sort() returns the sorted list. (Answer: False. It returns None and sorts the list in place.)
Q: Write a Python function that determines if a string is a palindrome.
A: Convert to lowercase with s.lower(), then return s == s[::-1]. For stricter checks, strip spaces and punctuation first.
Q: Given a list of integers, return a new list with only the positive numbers.
A: return [x for x in lst if x > 0]. This filters out zero and negatives.
Q: Write a Python function that reverses the order of words in a sentence.
A: return ' '.join(s.split()[::-1]). Split into words, reverse the list, join back with spaces.
Q: Given a list of names, sort them alphabetically without using the sort() method.
A: Implement selection sort. On each pass, find the smallest unsorted name and swap it into position.
Q: Implement a function that takes a list and returns a new list without duplicates.
A: To preserve order: loop through and append each element to a new list only if it is not already there. To ignore order: return list(set(lst)).
Q: Write a Python function that merges two sorted lists into a single sorted list.
A: Use two index variables (i and j), compare elements at each, append the smaller one to the result, and advance that index. After the loop, extend the result with whichever list has remaining elements.
Q: Write a function that determines if two strings are anagrams.
A: return sorted(s1.lower()) == sorted(s2.lower()). Sorting both strings puts their characters in the same order if and only if they are anagrams.
Q: Implement a Python function to return the second-largest element in a list.
A: Initialise first and second to negative infinity. Loop through the list: if the current element is larger than first, shift first to second and update first. Otherwise, if it is larger than second (and not equal to first), update second.
Q: Write a function that takes a string and returns the character that appears most frequently.
A: Build a frequency dictionary, then return the key with the maximum value. max(freq, key=freq.get) gives you the character with the highest count.
Q: Write a Python function to rotate a list to the right by k positions.
A: k = k % len(lst) to handle k larger than the list. Then return lst[-k:] + lst[:-k].
Q: Implement a function to flatten a nested list.
A: Define a recursive function. For each element, if isinstance(element, list), recursively flatten it and extend the result. Otherwise, append the element.
Q: Implement a function to check if a string has all unique characters.
A: return len(s) == len(set(s)). If the set (which drops duplicates) is the same length as the original, all characters are unique.
Q: Implement a Python function that returns the transpose of a given 2D matrix.
A: return [[row[i] for row in matrix] for i in range(len(matrix[0]))]. Each new row is built from column i of the original.
String and list manipulation patterns are the raw material for every algorithm topic that follows. Sorting without sort() connects directly to the sorting algorithms unit. The two-pointer merge technique reappears in merge sort. Flattening a nested list is an exercise in recursion, covered in the next set of notes.
Set operations (intersection, uniqueness checks) reappear in database concepts and later in data structures courses. The frequency-counting dictionary pattern is a stepping stone to hash maps.
Python strings, Python lists, palindrome, anagram, string reversal, word reversal, split join, list comprehension, filtering, removing duplicates, set, sorted vs sort, merging sorted lists, two pointers, second largest, flatten nested list, rotate list, list intersection, transpose matrix, unique characters, most frequent character, punctuation removal, selection sort, bubble sort, CS124, UIUC, Intro to Computer Science I