How Python Interviews Work 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.
Put the whole module together: one mock answer, a test table, and a choice between a library call and the manual version.
One question, answered in full
Take "find the first character in a word that appears only once". Clarify it, give a plain answer, improve it, then test it.
def first_unique(text): for i, ch in enumerate(text): if text.count(ch) == 1: return ch return NoneExample 1 · First unique character: three levels
from collections import Counter
def first_unique_slow(text): for ch in text: if text.count(ch) == 1: return ch return None
def first_unique(text): counts = Counter(text) for ch in text: if counts[ch] == 1: return ch return None
for word in ["level", "aabb", "", "x"]: print(repr(word), first_unique_slow(word), first_unique(word))'level' v v 'aabb' None None '' None None 'x' x x
What this code does
- The slow version is O(n squared) time and O(1) space; the counted version is O(n) time and O(k) space for k distinct characters.
- Both agree on all four inputs, including the empty string, which has no answer.
This plain version calls text.count inside a loop, so it is O(n squared). Say so, then offer one counting pass followed by one scan, which is O(n).
Test with a table
Write your own cases as pairs of input and expected result, run them in a loop, and include the edge cases.
cases = [("level", "v"), ("aabb", None), ("", None), ("x", "x")]for text, expected in cases: result = first_unique(text) print("PASS" if result == expected else "FAIL", repr(text))Example 2 · A test table that reports PASS or FAIL
def second_highest(marks): distinct = sorted(set(marks), reverse=True) return distinct[1] if len(distinct) > 1 else None
cases = [([78, 91, 85, 91], 85), ([50, 50], None), ([], None), ([-4, -9, -1], -4)]for marks, expected in cases: got = second_highest(marks) print("PASS" if got == expected else f"FAIL {marks}: got {got}")PASS PASS PASS PASS
What this code does
- Every case passes, so the output is four PASS lines. If one failed, the message would name the input and the wrong answer.
- Saying "I will test empty, one item, repeats and negatives" and then doing it is what the testing signal looks like.
A table makes it easy to add one more case when you think of it. repr shows the empty string clearly as two quotes.
Library or by hand, and the cost
For a frequency question, Counter is a fine first answer. Say what it costs and offer the manual version if asked.
from collections import Counter
def top_words(words, k): counts = Counter(words) return sorted(counts, key=lambda w: (-counts[w], w))[:k]Example 3 · Top words: Counter and a careful key
from collections import Counter
def top_words(words, k): counts = Counter(words) return sorted(counts, key=lambda w: (-counts[w], w))[:k]
sample = "to be or not to be to go".split()print(top_words(sample, 2))print(top_words([], 3))['to', 'be'] []
What this code does
- The key
(-counts[w], w)sorts by count from high to low and breaks ties alphabetically, so the result is fully defined. - Asking "what should happen on a tie?" before coding is the clarifying step this key depends on.
The sort key puts the highest count first and breaks ties by the word itself. Time is O(n + m log m) for n words and m distinct ones.
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
Write first_unique(text) that returns the first character appearing once, or None. Use Counter. Print it for "level", "aabb" and "".
v None None
Exercise 2· Easy
Write a test table for abs: for each pair (input, expected) in [(-3, 3), (0, 0), (5, 5)] print PASS or FAIL, one per line.
PASS PASS PASS
Exercise 3· Medium
Write most_frequent(values) that returns the value that appears most often, and the first one seen on a tie, or None if the list is empty. Print it for [3, 1, 3, 1, 2], [7] and [].
3 7 None
Exercise 4· Medium
Write is_anagram(a, b) by hand with a dictionary and no imports. Print the result for ("listen", "silent"), ("abc", "abd") and ("", "").
True False True
Exercise 5· Medium
Write merge_sorted(a, b) that merges two sorted lists into one sorted list with two pointers, no sorted. Print it for ([1, 4, 9], [2, 3, 10]), ([], [5]) and ([2, 2], [2]).
[1, 2, 3, 4, 9, 10] [5] [2, 2, 2]
Exercise 6· Medium
Write is_balanced(text) that checks (), [] and {} are balanced, using a list as a stack. Print it for "{[()]}", "([)]", "((" and an empty string.
True False False True
Exercise 7· Hard
Write top_k_words(words, k) returning the k most frequent words, ties broken alphabetically. Print it for the words of "to be or not to be to go" with k = 2 and for an empty list with k = 3.
['to', 'be'] []
Exercise 8· Hard
Write longest_unique_run(text) returning the length of the longest part of text with no repeated character, using a window and a dictionary of last positions. Print it for "abcabcbb", "bbbb", "" and "pwwkew".
3 1 0 3
Interview questions
Questions interviewers ask on this topic.
What's next
You finished the preview of How Python Interviews Work
Python Programming has 21 sections, 110 modules and 609 lessons. An account opens every lesson and saves your progress.
Finish up
Mark complete & continue
Next: Python Basics and How It Runs: Interview Questions