Category B · 8 Problems

String & Text Processing

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 11 Coding Problem Medium
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).
Example
group_anagrams(["eat","tea","tan","ate","nat","bat"]) → [["ate","eat","tea"], ["nat","tan"], ["bat"]]
sorted(word) as keydefaultdict(list) sort by len descendinginner sort alphabetically
Solution
from collections import defaultdict from typing import List def group_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 descending return sorted( [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 12 Coding Problem Medium
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".
Example
rle_encode("aaabbbccddddee") → "3a3b2c4d2e" rle_decode("3a3b2c4d2e") → "aaabbbccddddee" rle_encode("abc") → "1a1b1c"
itertools.groupbylist(g) to consume group str parsing with indexisdigit() while loop index walk
Solution
import itertools def rle_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) def rle_decode(s: str) -> str: result = [] i = 0 while 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 character return "".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 13 Coding Problem Easy
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 email set for deduplicationstr.lower() sorted()
Solution
import re from typing import List def extract_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 output return sorted(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 14 Coding Problem Easy
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.
Example
sort_versions(["1.10.2", "1.9.0", "2.0.0", "1.10.0", "0.9.9"]) → ["0.9.9", "1.9.0", "1.10.0", "1.10.2", "2.0.0"]
str.split('.')tuple of ints as sort key sorted() with key=lambda + map
Solution
from typing import List def sort_versions(versions: List[str]) -> List[str]: # Convert each "1.10.2" to (1, 10, 2) for numeric comparison return sorted( 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 15 Coding Problem Medium
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 tokenisationCounter set lookup O(1)sorted with tuple key str.lower()
Solution
import re from collections import Counter from typing import List, Tuple, Set def top_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 16 Coding Problem Easy
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.
Example
longest_common_prefix(["flower","flow","flight"]) → "fl" longest_common_prefix(["dog","racecar","car"]) → "" longest_common_prefix(["abc"]) → "abc" longest_common_prefix([]) → ""
zip(*words) to transposeset() for unique check early exit on mismatchedge case handling
Solution
from typing import List def longest_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 behaviour for char_column in zip(*words): if len(set(char_column)) == 1: prefix.append(char_column[0]) else: break # first mismatch — stop here return "".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 17 Coding Problem Medium
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.
Example
is_balanced("()[]{}") → True is_balanced("([{}])") → True is_balanced("([)]") → False is_balanced("{[}") → False is_balanced("") → True
stack (list)dict for bracket matching early exit on mismatchempty stack check at end
Solution
def is_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 brackets elif ch in matching: # Closing bracket: stack must have the matching opener on top if not stack or stack[-1] != matching[ch]: return False stack.pop() # If stack is empty, all brackets were matched return len(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 18 Coding Problem Medium
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 descending string slicing with offsetsf-string tag wrapping
Solution
from typing import List, Dict def apply_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 repeatedly def apply_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 = 0 for 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 span return "".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.
← Category A: Log Parsing Category C: Dict & Counting →