Pattern matching, transforming, grouping, and searching through text. These problems test your command of Python's string toolkit and standard library.
Problems: 8
Difficulty: Easy – Medium
Key libs: re · itertools · collections · bisect
Pattern to recognise: String problems often hide a data-structure problem inside.
Grouping anagrams = dict with a sorted-word key. Frequency = Counter. Validation = stack.
Always ask: what is the natural key that groups identical things together?
P 11Coding ProblemMedium
Anagram Grouper
Given a list of words, group all anagrams together.
Return groups as a list of lists. Sort each group alphabetically.
Return the groups sorted by size descending (largest group first).
sorted(word) as keydefaultdict(list)sort by len descendinginner sort alphabetically
Solution
from collections import defaultdict
from typing import List
defgroup_anagrams(words: List[str]) -> List[List[str]]:
groups: dict = defaultdict(list)
for word in words:
# sorted("eat") → ['a','e','t'] → "aet" — same key for all anagrams
key = "".join(sorted(word))
groups[key].append(word)
# Sort each group alphabetically, then sort groups by size descendingreturnsorted(
[sorted(g) for g in groups.values()],
key=len, reverse=True
)
Key insight: Anagrams are the same word with letters rearranged.
So "".join(sorted(word)) produces the same canonical key for all anagrams.
sorted("eat") → ['a','e','t'] → "aet" — same as for "tea" and "ate".
This turns a string problem into a grouping-by-key problem.
Time complexity: O(n · k log k) where k is the average word length.
P 12Coding ProblemMedium
Run-Length Encoder & Decoder
Implement rle_encode(s) and rle_decode(s).
Encode: compress consecutive identical characters as count + char.
Decode: expand them back. Edge case: "abc" → "1a1b1c", not "abc".
itertools.groupbylist(g) to consume groupstr parsing with indexisdigit()while loop index walk
Solution
import itertools
defrle_encode(s: str) -> str:
if not s:
return""# groupby yields (char, group_iterator) for each run
parts = [
f"{len(list(g))}{ch}"for ch, g in itertools.groupby(s)
]
return"".join(parts)
defrle_decode(s: str) -> str:
result = []
i = 0while i < len(s):
# Collect all digit characters (handles counts > 9)
j = i
while j < len(s) and s[j].isdigit():
j += 1
count = int(s[i:j])
char = s[j]
result.append(char * count)
i = j + 1# skip past the characterreturn"".join(result)
Key insight:itertools.groupby is the perfect tool — it groups consecutive identical elements.
Note you must call list(g) or len(list(g)) to consume the group iterator before moving to the next group.
The decoder uses a two-pointer walk to handle multi-digit counts like "12a" correctly.
P 13Coding ProblemEasy
Email Extractor & Deduplicator
Given a large text blob, extract all email addresses using regex.
Lowercase them, deduplicate (same email in different cases counts once), and return a sorted list.
Example
text = "Contact Alice@Example.com or alice@example.com. Also bob@test.org."
extract_emails(text) → ["alice@example.com", "bob@test.org"]
re.findallregex pattern for emailset for deduplicationstr.lower()sorted()
Solution
import re
from typing import List
defextract_emails(text: str) -> List[str]:
# Standard email regex: local-part @ domain . tld
pattern = r"[a-zA-Z0-9._%+\-]+@[a-zA-Z0-9.\-]+\.[a-zA-Z]{2,}"
matches = re.findall(pattern, text)
# Lowercase + dedup with set + sort for deterministic outputreturnsorted(set(e.lower() for e in matches))
Key ideas:re.findall returns all non-overlapping matches as a list — no loop needed.
Lowercase before adding to the set so "Alice@Example.com" and "alice@example.com" collapse to one entry.
The set eliminates duplicates; sorted() gives deterministic output.
The regex is not perfect for all edge cases (RFC 5321 is complex) but is good enough for interviews.
P 14Coding ProblemEasy
Version String Sorter
Sort a list of semantic version strings like "1.10.2" correctly — not lexicographically.
Lexicographic sort would put "1.10.2" before "1.9.0" because "1" < "9", which is wrong.
str.split('.')tuple of ints as sort keysorted() with key=lambda + map
Solution
from typing import List
defsort_versions(versions: List[str]) -> List[str]:
# Convert each "1.10.2" to (1, 10, 2) for numeric comparisonreturnsorted(
versions,
key=lambda v: tuple(int(x) for x in v.split("."))
)
Key insight: Python compares tuples element by element — so (1, 10, 2) correctly comes after (1, 9, 0).
The key function converts each version string into a tuple of integers just for the sort comparison.
This is a classic "transform → sort → (optionally restore)" pattern. No external libraries needed.
P 15Coding ProblemMedium
Word Frequency with Stopwords
Count word frequency in a text string. Exclude words in a given stopword set (case-insensitive).
Return the top-N as (word, count) tuples, sorted by frequency descending.
Ties are broken alphabetically.
Example
text = "the cat sat on the mat the cat"
stopwords = {"the", "on"}
top_words(text, stopwords, top_n=2) → [("cat", 2), ("mat", 1)]
re.findall for word tokenisationCounterset lookup O(1)sorted with tuple keystr.lower()
Solution
import re
from collections import Counter
from typing import List, Tuple, Set
deftop_words(text: str, stopwords: Set[str], top_n: int) -> List[Tuple[str, int]]:
# Extract only alphabetic words, lowercase
words = re.findall(r"\b[a-z]+\b", text.lower())
# Filter out stopwords (set lookup is O(1))
counts = Counter(w for w in words if w not in stopwords)
# Sort: frequency desc, then alphabetically asc for ties
ranked = sorted(counts.items(), key=lambda x: (-x[1], x[0]))
return ranked[:top_n]
Key ideas:re.findall(r"\b[a-z]+\b", text.lower()) tokenises cleanly — handles punctuation, numbers, and mixed case in one step.
Filtering with a set is O(1) per lookup vs O(n) for a list.
The sort key (-count, word) is a classic trick: negate count for descending, word for ascending alphabetical tiebreak — all in one pass.
P 16Coding ProblemEasy
Longest Common Prefix
Given a list of strings, find the longest prefix string shared by all of them.
If there is no common prefix, return "".
Handle edge cases: empty list, single string, all strings identical.
zip(*words) to transposeset() for unique checkearly exit on mismatchedge case handling
Solution
from typing import List
deflongest_common_prefix(words: List[str]) -> str:
if not words:
return""
prefix = []
# zip(*words) → iterate character columns across all words in parallel# zip stops at the shortest word — correct behaviourfor char_column inzip(*words):
iflen(set(char_column)) == 1:
prefix.append(char_column[0])
else:
break# first mismatch — stop herereturn"".join(prefix)
Key insight:zip(*words) "transposes" the list of strings — it yields tuples of characters at each position across all words.
zip automatically stops at the shortest string, so you never index out of bounds.
Checking len(set(chars)) == 1 verifies all characters at that position are the same.
This is cleaner than comparing against words[0] character by character.
P 17Coding ProblemMedium
Balanced Bracket Checker
Given a string containing only ()[]{},
return True if every opening bracket has a corresponding closing bracket in the correct order.
Other characters should be ignored.
stack (list)dict for bracket matchingearly exit on mismatchempty stack check at end
Solution
defis_balanced(s: str) -> bool:
stack = []
# Map each closing bracket to its expected opening bracket
matching = {")": "(", "]": "[", "}": "{"}
for ch in s:
if ch in"([{":
stack.append(ch) # push opening bracketselif ch in matching:
# Closing bracket: stack must have the matching opener on topif not stack or stack[-1] != matching[ch]:
returnFalse
stack.pop()
# If stack is empty, all brackets were matchedreturnlen(stack) == 0
Key insight: A stack is the natural data structure here — the most recently opened bracket must be closed first (LIFO).
The dict matching maps each closer to its opener, making the check elegant: stack[-1] != matching[ch].
Two failure conditions: stack is empty when we see a closer (nothing to match), or top of stack doesn't match.
At the end, a non-empty stack means unclosed brackets remain.
P 18Coding ProblemMedium
Apply Markup by Offset — Right-to-Left Replacement
Given a text string and a list of {"start", "end", "tag"} spans, wrap each span with HTML-like tags.
Example: span {start:4, end:9, tag:"b"} on "The quick brown fox" → "The <b>quick</b> brown fox".
Spans are non-overlapping. Process them efficiently without rebuilding the whole string multiple times from scratch.
This is the generic version of the PII redaction offset problem — same trick, different use case.
Example
text = "The quick brown fox"
spans = [
{"start": 4, "end": 9, "tag": "b"},
{"start": 10,"end": 15, "tag": "em"},
]
apply_markup(text, spans)
→ "The <b>quick</b> <em>brown</em> fox"
right-to-left replacementsorted() by start descendingstring slicing with offsetsf-string tag wrapping
Solution
from typing import List, Dict
defapply_markup(text: str, spans: List[Dict]) -> str:
# Sort by start descending = right-to-left order# This preserves offsets for all unprocessed (left-side) spans
sorted_spans = sorted(spans, key=lambda s: s["start"], reverse=True)
for span in sorted_spans:
s = span["start"]
e = span["end"]
tag = span["tag"]
wrapped = f"<{tag}>{text[s:e]}</{tag}>"
text = text[:s] + wrapped + text[e:]
return text
# Alternative: build result from parts without mutating the string repeatedlydefapply_markup_v2(text: str, spans: List[Dict]) -> str:
# Sort by start ascending, then build the output in one pass
sorted_spans = sorted(spans, key=lambda s: s["start"])
parts = []
prev_end = 0for span in sorted_spans:
parts.append(text[prev_end : span["start"]]) # text before span
parts.append(f"<{span['tag']}>{text[span['start']:span['end']]}</{span['tag']}>")
prev_end = span["end"]
parts.append(text[prev_end:]) # text after last spanreturn"".join(parts)
Two approaches: v1 (right-to-left): Sort spans by start descending. Replace each span right-to-left. Each replacement only shifts text to the right — already done. O(n·m) due to repeated string creation.
v2 (single-pass builder): Sort spans by start ascending. Walk through, collecting the unchanged text between spans and the wrapped span text into a list. Join once at the end. O(n) time, O(n) space — far more efficient for large texts with many spans.
In interviews: mention both. Implement v2 if performance is a concern.