Array and String Techniques Checkpoint
A review of this module. Skip it if you feel confident; the next module does not need it.
Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
This checkpoint mixes all five lessons. For each task, decide first which pattern fits, then write it, then say its time and space cost.
In place: swap and write pointer
A support queue holds closed tickets marked 0. Move them to the end while keeping the open ones in order, using one list and two indexes.
tickets = [0, 14, 0, 9, 21]write = 0for read in range(len(tickets)): if tickets[read] != 0: tickets[write], tickets[read] = tickets[read], tickets[write] write += 1print(tickets)One pass, O(n) time, O(1) extra space. The swap keeps the zeros at the back.
Reverse and rotate
A rotation is three reversals. Reverse everything, then the first k items, then the rest. Each reversal swaps from both ends.
def reverse(items, lo, hi): while lo < hi: items[lo], items[hi] = items[hi], items[lo] lo += 1 hi -= 1
data = [1, 2, 3, 4, 5]k = 2reverse(data, 0, 4)reverse(data, 0, k - 1)reverse(data, k, 4)print(data)Example 1 · Rotate then check
data = [10, 20, 30, 40, 50]k = 7 % len(data)rotated = data[-k:] + data[:-k]print(rotated, rotated[::-1])[40, 50, 10, 20, 30] [30, 20, 10, 50, 40]
What this code does
- 7 % 5 is 2, so the last two items move to the front.
- The second value is the same list reversed with a slice.
- Both are new lists: O(n) extra space.
Reduce k with k %= len(data) before the three calls when k can be large.
Merge, partition and Kadane
Sorted inputs call for a merge with two pointers. Values of three kinds call for three pointers. A best run of consecutive values calls for Kadane.
def kadane(nums): current = best = nums[0] for value in nums[1:]: current = max(value, current + value) best = max(best, current) return best
print(kadane([4, -10, 3, 3]))Example 2 · Best stretch of a week
change = [2, -1, 2, -6, 4, -1, 3]current = best = change[0]for value in change[1:]: current = max(value, current + value) best = max(best, current)print(best)6
What this code does
- The run 4, -1, 3 gives 6.
- The run 2, -1, 2 gives only 3, and -6 breaks it.
- One pass, O(1) extra space.
Each is one pass. Read the problem for the clue: sorted, few kinds of values, or a run of neighbours.
Strings: join, two pointers, counts
Build text with join, test symmetry with two pointers, and compare or count letters with Counter.
from collections import Counter
print(Counter("tea") == Counter("eat"))print(" ".join(["red", "green", "blue"][::-1]))Example 3 · Count each customer's orders
from collections import Counter
orders = ["asha", "ravi", "asha", "meena", "asha", "ravi"]for name, n in Counter(orders).most_common(): print(name, n)asha 3 ravi 2 meena 1
What this code does
- Counter counts every name in one pass.
most_common()without a number lists all names, highest count first.- Equal counts keep the order of first appearance.
Most string problems are one of these three patterns.
Module quiz
Questions from the whole module. Your first answer is your score.
Problems
Graded easy to hard, using everything from this module.
Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.
Exercise 1· Easy
Swap the first and last items of temps = [21, 25, 19, 30] in place and print the list.
[30, 25, 19, 21]
Exercise 2· Easy
Rotate [1, 2, 3, 4, 5, 6] right by 2 with slices and print the new list.
[5, 6, 1, 2, 3, 4]
Exercise 3· Easy
Print True if "Madam" is a palindrome when case is ignored, else False.
True
Exercise 4· Medium
Move every 0 of [0, 1, 0, 3, 12] to the end in place, keeping the order of the others. Print the list.
[1, 3, 12, 0, 0]
Exercise 5· Medium
Merge the sorted lists [1, 3, 5, 7] and [2, 3, 6] with two pointers and print the merged list.
[1, 2, 3, 3, 5, 6, 7]
Exercise 6· Medium
Print the maximum subarray sum of [-2, 1, -3, 4, -1, 2, 1, -5, 4].
6
Exercise 7· Hard
Sort [2, 0, 1, 2, 0, 1, 1] (values 0, 1, 2) in one pass with three pointers and print the list.
[0, 0, 1, 1, 1, 2, 2]
Exercise 8· Hard
Rotate [1, 2, 3, 4, 5, 6, 7] right by 4 in place with three reversals and print the list.
[4, 5, 6, 7, 1, 2, 3]
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: Array and String Techniques