Arrays, Strings, and Hashing Questions
Manipulating arrays and strings using the standard toolkit for entry-level coding-interview problems: two-pointer and sliding-window techniques, in-place modification (reversal, rotation, partitioning, deduplication), prefix sums, and hash-map or hash-set based techniques used to solve array or string problems in optimal time (frequency counting, lookup-based pairing such as two-sum, duplicate detection, grouping by a computed key such as anagram grouping). Hashing appears in this topic only as an applied technique for solving an array or string problem faster: how hash tables work internally (hash functions, collision resolution, load factor, resizing) and hash-based structures that are not array or string shaped (Bloom filters, HyperLogLog) belong to the separate hashing and hash tables topic, not this one. Covers the most frequent entry-level coding-interview problem shapes and the trade-offs between time, space, and readability. The default warm-up surface for any coding interview.
Find all start indices of p's anagrams in s. Given strings s and p, return a list of starting indices of p's anagrams in s. Example: s = 'cbaebabacd', p = 'abc' -> [0,6]. Implement in Python using sliding window + frequency arrays in O(n) time. Explain applications for substring pattern detection in tokenized text.
Sample Answer
Direct answer
Slide a fixed-size window of length len(p) across s, tracking the window's contents with two fixed-size frequency arrays (as the question specifies), one for p's required counts and one for the current window, indexed directly by character rather than through hashing. Updating the window incrementally (increment the entering character's slot, decrement the exiting character's slot) rather than rebuilding and comparing a fresh count every position is what makes this O(n) instead of O(n * |p|). Space is O(alphabet size): for lowercase English letters, that is a fixed 26 integers regardless of how long s or p are.
Algorithm
- Build
need, a length-26 array ofp's character counts (need[ord(ch) - ord('a')] += 1for each character inp). - Initialize
windowas the length-26 count array ofs's firstlen(p)characters. - If
window == need(array-to-array comparison), index 0 is a match. - Slide the window one character at a time: increment the slot of the character entering on the right, decrement the slot of the character leaving on the left, and compare
window == needagain after each slide.
def find_anagrams(s: str, p: str) -> list:
len_s, len_p = len(s), len(p)
if len_p > len_s:
return []
def index_of(ch):
return ord(ch) - ord("a")
need = [0] * 26
window = [0] * 26
for ch in p:
need[index_of(ch)] += 1
for ch in s[:len_p]:
window[index_of(ch)] += 1
result = []
if window == need:
result.append(0)
for i in range(len_p, len_s):
incoming, outgoing = s[i], s[i - len_p]
window[index_of(incoming)] += 1
window[index_of(outgoing)] -= 1
if window == need:
result.append(i - len_p + 1)
return result
Using a fixed-size array indexed directly by ord(ch) - ord('a'), rather than a hash map keyed by the character, is exactly what "frequency array" means here: no hashing, no key deletion bookkeeping (a count naturally sits at 0 in an untouched slot, so there is nothing to clean up the way there would be with a dict-based count map), and the window == need comparison is a fixed-length list comparison, always exactly 26 elements, regardless of the alphabet actually observed in a given window. This assumes a known, bounded alphabet (lowercase English letters, size 26 here); for Unicode or an unbounded alphabet, a hash map keyed by character is the structure that scales with distinct characters actually seen instead of the size of the declared alphabet, at the cost of per-key hashing overhead.
Applications for substring pattern detection in tokenized text
The same fixed-size-window-plus-count-comparison technique applies directly to detecting "this window of tokens is a rearrangement of a target token multiset," which comes up in tasks like flagging text spans that contain exactly the same word multiset as a suspicious phrase (word-order-scrambled plagiarism or obfuscation detection) or matching a fixed-size set of required tags in a tokenized log line regardless of their order. The technique is identical, only the "character" unit changes to "token."
Worked example
def brute_force_find_anagrams(s, p):
len_p = len(p)
target = sorted(p)
result = []
for i in range(len(s) - len_p + 1):
if sorted(s[i:i+len_p]) == target:
result.append(i)
return result
tests = ["cbaebabacd", "abab", "aaaaaaaaaa"]
patterns = ["abc", "ab", "aaa"]
for s, p in zip(tests, patterns):
fast = find_anagrams(s, p)
brute = brute_force_find_anagrams(s, p)
print(f"find_anagrams({s!r}, {p!r}) = {fast} (brute-force agrees: {fast == brute})")
Output (verified by execution, and cross-checked against an O(n * k log k) brute-force reference that sorts every window directly, so the fast result's correctness is independently confirmed rather than assumed):
find_anagrams('cbaebabacd', 'abc') = [0, 6] (brute-force agrees: True)
find_anagrams('abab', 'ab') = [0, 1, 2] (brute-force agrees: True)
find_anagrams('aaaaaaaaaa', 'aaa') = [0, 1, 2, 3, 4, 5, 6, 7] (brute-force agrees: True)
Tracing s='cbaebabacd', p='abc' (need = {a:1, b:1, c:1}): the window at index 0 is "cba", whose counts exactly match need, so index 0 is recorded. Sliding to index 1 gives "bae", which introduces 'e' (not in need at all) so it fails to match. The window keeps sliding until index 6, "bac" (b,a,c), which again matches need exactly, giving the second recorded index. No other window in between matches because each contains either a repeated letter with the wrong count or a letter ('e', 'd') that need doesn't have at all.
Trade-offs and pitfalls
- Comparing two full 26-length arrays on every slide is itself O(alphabet size) per comparison, not O(1), so even though the alphabet here is small and fixed, this is not free; a common refinement is to track a single integer "how many of the 26 positions currently match between the two arrays" (the same trick used in minimum-window-substring problems), updated incrementally as each slide changes at most two positions, which turns the check into O(1) instead of O(26) per step.
- The frequency-array approach assumes a known, bounded alphabet. It is the right choice here (lowercase English letters) precisely because the question specifies it; for Unicode text or an unbounded token vocabulary, a hash map keyed by the actual character or token is what scales with distinct values seen, and switching to one is a straightforward substitution of the counting structure without changing the sliding-window logic itself.
- This is a fixed-size window, unlike minimum-window-substring's variable-size window: the window length here is always exactly
len(p), which is simpler (no shrink/grow decision needed) but means the technique doesn't generalize to "smallest window containing X" problems without the additional grow/shrink logic those require. - Edge cases:
plonger thans(no window can exist, return empty immediately),pempty (depends on the problem's intended contract, typically treated as matching every position or explicitly disallowed), and heavily repeated characters ins(as in the'aaaaaaaaaaaa'/'aaa'case above), which stress-test that the sliding update (not a full rebuild) is genuinely being used, since a naive re-slice-and-recount implementation would still pass correctness tests here but silently lose its performance advantage.
You receive a log line in this format (single line):
2025-12-06T12:00:00Z service=auth pid=1234 level=ERROR msg='Failed login for user bob: invalid password'
Write a Python parser that extracts timestamp, service, pid (int), level, and msg into a dict. Handle missing or quoted messages safely. Discuss performance considerations when parsing millions of lines per hour.
Sample Answer
Direct answer
Parse the line as a leading timestamp token followed by a run of key=value tokens, where a value is either a bare token or a quoted string that can itself contain spaces or an escaped quote. Scan it manually, character by character, rather than with one big anchored regular expression: a single anchored pattern matches the whole line or fails the whole line, and "handle missing fields safely" specifically means a missing field should leave that one key unset, not blow up the entire parse.
Structured elaboration
Tokenizing approach. Read the leading whitespace-delimited token as the timestamp (an ISO 8601 style stamp, 2025-12-06T12:00:00Z, though the parser does not need to validate that format, only extract it). Then repeatedly: skip whitespace, read a key up to =, and read the value either as a bare token (up to the next space) or, if the next character is a quote, as everything up to the matching unescaped quote, unescaping any \' along the way.
Safe field handling. Every expected key (timestamp, service, pid, level, msg) starts at None in the result dict. A key that never appears in the line simply stays None; a malformed pid (not all digits) is caught with a try/except around the int() conversion and also left as None, instead of raising and losing the whole line. That is the concrete meaning of "handle missing or quoted messages safely" here: partial, defensive results instead of an exception.
Performance at millions of lines per hour. The scan itself is a single O(n) pass per line, O(1) extra space beyond the output dict, no backtracking. The throughput number matters for scale: 1,000,000 / 3600 ≈ 277.8 lines per second, a modest rate for a single-threaded O(n)-per-line parse. The parsing technique's job at that rate is to not add avoidable overhead: avoid rebuilding the same intermediate list-and-rejoin structure that line.split() plus manual reassembly would need, and avoid a regex whose quantifiers could backtrack badly on adversarial input (many repeated escaped quotes inside msg). Everything past that (batching, buffering, multiple worker processes) is an ingestion-pipeline design question, a different skill from the array/string parsing technique this question is actually testing.
Worked example
def parse_log_line(line: str) -> dict:
result = {"timestamp": None, "service": None, "pid": None, "level": None, "msg": None}
n = len(line)
i = 0
# 1. timestamp is the leading whitespace-delimited token
while i < n and line[i] == ' ':
i += 1
start = i
while i < n and line[i] != ' ':
i += 1
if i > start:
result["timestamp"] = line[start:i]
# 2. remaining key=value tokens, respecting quoted values
while i < n:
while i < n and line[i] == ' ':
i += 1
if i >= n:
break
key_start = i
while i < n and line[i] != '=' and line[i] != ' ':
i += 1
if i >= n or line[i] != '=':
while i < n and line[i] != ' ':
i += 1
continue
key = line[key_start:i]
i += 1 # skip '='
if i < n and line[i] in ("'", '"'):
quote = line[i]
i += 1
val_start = i
while i < n:
if line[i] == '\\' and i + 1 < n and line[i + 1] == quote:
i += 2
continue
if line[i] == quote:
break
i += 1
raw_val = line[val_start:i]
value = raw_val.replace('\\' + quote, quote)
if i < n:
i += 1 # skip closing quote
else:
val_start = i
while i < n and line[i] != ' ':
i += 1
value = line[val_start:i]
if key in result:
result[key] = value
if result["pid"] is not None:
try:
result["pid"] = int(result["pid"])
except ValueError:
result["pid"] = None
return result
test_lines = [
"2025-12-06T12:00:00Z service=auth pid=1234 level=ERROR msg='Failed login for user bob: invalid password'",
"2025-12-06T12:00:01Z service=auth level=INFO msg='pid missing on this line'",
"2025-12-06T12:00:02Z service=auth pid=5678 level=WARN msg='He said \\'hi\\' twice'",
"2025-12-06T12:00:04Z service=auth pid=notanumber level=INFO msg='bad pid value'",
]
for t in test_lines:
print(repr(t))
print(parse_log_line(t))
print("1,000,000 lines/hour =", round(1_000_000 / 3600, 1), "lines/second")
Output, run against the sample line plus edge cases:
"2025-12-06T12:00:00Z service=auth pid=1234 level=ERROR msg='Failed login for user bob: invalid password'"
{'timestamp': '2025-12-06T12:00:00Z', 'service': 'auth', 'pid': 1234, 'level': 'ERROR', 'msg': 'Failed login for user bob: invalid password'}
"2025-12-06T12:00:01Z service=auth level=INFO msg='pid missing on this line'"
{'timestamp': '2025-12-06T12:00:01Z', 'service': 'auth', 'pid': None, 'level': 'INFO', 'msg': 'pid missing on this line'}
"2025-12-06T12:00:02Z service=auth pid=5678 level=WARN msg='He said \\'hi\\' twice'"
{'timestamp': '2025-12-06T12:00:02Z', 'service': 'auth', 'pid': 5678, 'level': 'WARN', 'msg': "He said 'hi' twice"}
"2025-12-06T12:00:04Z service=auth pid=notanumber level=INFO msg='bad pid value'"
{'timestamp': '2025-12-06T12:00:04Z', 'service': 'auth', 'pid': None, 'level': 'INFO', 'msg': 'bad pid value'}
1,000,000 lines/hour = 277.8 lines/second
Every field from the question (timestamp, service, pid as int, level, msg) is produced, a missing pid and a missing quoted value both degrade to None instead of raising, and the escaped-quote case (\'hi\') is correctly unescaped to a literal quote inside the message.
Trade-offs and pitfalls
A single anchored regex (^(?P<timestamp>\S+)\s+service=...) is more compact to write, but it is all-or-nothing: reorder the fields, drop one, or add an unexpected key, and the whole line fails to match instead of degrading field by field. If you do reach for a regex per field, keep quantifiers bounded (avoid nested .* inside the quoted-value group) so a message packed with escaped quotes cannot trigger catastrophic backtracking.
Swallowing a bad pid to None is the right behavior for a pipeline that must never crash on one bad line, but silently doing nothing else is its own risk: track a counter of how many lines failed to parse a given field, or a silent upstream format change (a service starts emitting pid as a hex string, say) goes unnoticed indefinitely.
Real log files are commonly UTF-8; if you are reading raw bytes rather than already-decoded text, quote and escape detection has to run on the decoded string, not the raw byte sequence, or a multi-byte character could be split mid-character by a byte-oriented scan.
Write a function in Python to determine whether two strings are anagrams of each other in a Unicode-aware way. Consider normalization, casefolding, and handling of combining marks. Aim for O(n) time and O(k) extra space where k is the distinct character count. Discuss trade-offs between sorting-based and counting-based approaches when the alphabet is large.
Sample Answer
Direct answer
Normalize both strings to a canonical Unicode form (NFC: compose combining marks into precomposed characters wherever a composed form exists), then casefold them (a Unicode-aware, more aggressive relative of .lower()), and finally compare character frequency counts using a hash map. Two strings are anagrams exactly when their normalized, casefolded character-count maps are equal. This is O(n) time and O(k) extra space, where k is the number of distinct characters actually present, not the size of the whole alphabet.
Structured elaboration
Why raw codepoint comparison fails on Unicode text. The same visible character can be represented by different codepoint sequences: an accented letter like an e with an acute accent can be one precomposed codepoint, or two codepoints (the base letter plus a separate combining acute-accent mark). Two strings that look identical to a human, and that a user would absolutely expect to be treated as anagrams of each other, can fail a naive character-by-character or Counter-based comparison if one uses the composed form and the other the decomposed form, because they are literally different sequences of codepoints.
Normalization (NFC) before comparison. Running both strings through Unicode Normalization Form C (NFC) converts any decomposed base-plus-combining-mark sequence into its precomposed equivalent wherever one exists, so that two visually-identical strings become byte-for-byte identical at the codepoint level before any counting happens. Normalization must happen before counting, not after, since counting decomposed and precomposed forms separately would treat them as different characters.
Casefolding, not just lowercasing. Python's .casefold() is used instead of .lower() because casefolding is defined specifically for caseless string matching and handles cases .lower() doesn't, most famously the German sharp s (ß), which casefolds to the two-character sequence ss (matching how ß and ss are treated as equivalent in caseless comparisons) while .lower() leaves it unchanged. This means casefolding can change a string's length, which matters for the next step.
Order of operations for the length check. The length check (len(s) != len(t) as a fast rejection before doing full character counting) must be performed on the normalized-and-casefolded strings, never on the raw input, precisely because casefolding can change length. Checking the raw lengths first, as a shortcut before normalization, is a subtle but real bug: it would incorrectly reject valid Unicode-aware anagram pairs whose raw lengths differ only because casefolding expands one of them.
Sorting-based versus counting-based comparison, and the large-alphabet trade-off. A sorting-based approach (sort both normalized/casefolded strings, compare for equality) costs O(n log n) time but only O(1) extra space if sorting can be done on a mutable copy in place (or O(n) if the language's sort isn't in-place), and it never needs a hash map at all, which matters when the character alphabet is enormous, since a sort never allocates space proportional to the alphabet size, only to the string length. A counting-based approach (build a frequency map, compare maps) is O(n) time but pays O(k) space for the map, where k is the number of distinct characters seen; for a small, fixed alphabet like lowercase ASCII, that map is trivially small and counting wins outright on speed, but for full Unicode text (over a million possible codepoints, even though any single string only uses a tiny fraction of them), a hash-map-based counter is still the right call because k is bounded by the input length itself, not by the alphabet size, since a Python dict/Counter only allocates entries for characters that actually appear.
Worked example
Full runnable code with pinned test cases, including the composed-versus-decomposed accented-character case and the German sharp-s casefold case (a genuine subtlety, not a contrived one):
import unicodedata
from collections import Counter
def normalize_for_compare(s):
"""NFC-normalize then casefold. Length check must happen AFTER this,
never on the raw string (see the STRASSE case below)."""
return unicodedata.normalize("NFC", s).casefold()
def is_anagram(s, t):
"""O(n) time, O(k) extra space where k is the distinct-character count,
counting-based rather than sorting-based."""
s_norm = normalize_for_compare(s)
t_norm = normalize_for_compare(t)
if len(s_norm) != len(t_norm):
return False
return Counter(s_norm) == Counter(t_norm)
if __name__ == "__main__":
# Built from explicit codepoint escapes so the composed/decomposed
# distinction is unambiguous regardless of source-file encoding.
precomposed = "caf" + "\u00e9" # c a f e-acute (1 codepoint, U+00E9)
decomposed = "caf" + "e" + "\u0301" # c a f e + combining acute (U+0301)
print("raw codepoint lengths (decomposed vs precomposed):", len(decomposed), len(precomposed))
print("raw equal (no normalization)?", decomposed == precomposed)
print("NFC-normalized equal?", unicodedata.normalize("NFC", decomposed) == unicodedata.normalize("NFC", precomposed))
reordered_precomposed = "\u00e9" + "fac" # e-acute f a c (reordered anagram)
strasse_lower = "stra" + "\u00df" + "e" # stra-sharp_s-e
tests = [
("listen", "silent", True),
("Listen", "Silent", True),
(precomposed, decomposed + "x", False),
(precomposed, reordered_precomposed, True),
(decomposed, reordered_precomposed, True),
("STRASSE", strasse_lower, True), # casefold('ss') == casefold('\u00df')
("ab", "abc", False),
]
for a, b, expected in tests:
result = is_anagram(a, b)
print(f"is_anagram({a!r}, {b!r}) = {result} (expected {expected})")
print("raw len(strasse_lower) =", len(strasse_lower), " raw len('STRASSE') =", len("STRASSE"))
print("casefold(strasse_lower) =", strasse_lower.casefold())
print("casefold('STRASSE') =", "STRASSE".casefold())
Output (actual run):
raw codepoint lengths (decomposed vs precomposed): 5 4
raw equal (no normalization)? False
NFC-normalized equal? True
is_anagram('listen', 'silent') = True (expected True)
is_anagram('Listen', 'Silent') = True (expected True)
is_anagram('café', 'caféx') = False (expected False)
is_anagram('café', 'éfac') = True (expected True)
is_anagram('café', 'éfac') = True (expected True)
is_anagram('STRASSE', 'straße') = True (expected True)
is_anagram('ab', 'abc') = False (expected False)
raw len(strasse_lower) = 6 raw len('STRASSE') = 7
casefold(strasse_lower) = strasse
casefold('STRASSE') = strasse
The STRASSE / straße case is the one to walk through out loud in an interview: the raw strings have different lengths (7 versus 6 codepoints), so a fast-reject on raw length would wrongly report "not an anagram." But ß casefolds to the two characters ss, so both strings casefold to the same 7-character string strasse, and they are correctly identified as an anagram pair. This is exactly why the length check must run on the normalized-and-casefolded strings.
Trade-offs and pitfalls
- Comparing raw strings, or even lowercasing with
.lower()instead of.casefold(), silently fails on real internationalized input like theß/sscase above;.lower()alone leavesßunchanged and would reportSTRASSEandstraßeas not anagrams, which is wrong under Unicode caseless matching rules. - Checking length before normalizing (a tempting micro-optimization to avoid normalizing strings that "obviously" can't match) is a genuine bug source, not a harmless shortcut, precisely because casefolding and normalization can both change apparent length.
- Sorting-based comparison is the right call when the alphabet is small and fixed (interview-classic lowercase-English anagram checks) since it avoids hash-map overhead entirely; counting-based comparison is the right call once the input might be full Unicode text, since a hash map's cost scales with how many distinct characters actually appear in this particular input, not with the size of the Unicode codepoint space.
- Grapheme-cluster-level correctness (treating an emoji-with-modifier sequence, or a base character plus multiple combining marks, as a single user-perceived "character") is a further layer beyond codepoint-level NFC normalization; this answer normalizes and compares at the codepoint level, which is sufficient for the vast majority of real anagram-style interview questions, but a fully grapheme-aware comparison would need a dedicated segmentation library, which is depth beyond what this question is testing.
- NFC (compose) rather than NFD (decompose) is used here because it produces the more compact, more widely-used-as-a-default form; either would work correctly as long as it's applied consistently to both strings before comparison, since the point is only that both strings land on the same normalized form, not which specific form is chosen.
Implement remove_element(nums, val) in-place in Python or Java: remove all occurrences of val from nums and return the new length. This is part of a backend cleanup job where payload arrays must be compacted before storage. Explain how to move elements and whether order must be preserved.
Sample Answer
Direct answer
Use a read/write two-pointer: walk the array once with a read index, and every time you see a value that isn't val, copy it into the next open slot tracked by a write index. The write index at the end is the new length. Whether order must be preserved decides which of two variants you use: the read/write copy above preserves the original relative order in O(n) writes; if order doesn't matter, you can instead swap a matching element with the current last element and shrink the array, which does fewer writes when val is rare.
Approach
- Order-preserving (read/write two-pointer):
writestarts at 0. For eachreadindex in order, ifnums[read] != val, copy it tonums[write]and advancewrite. Every kept element lands in its original relative order, one slot earlier than or at its original position. - Order-not-preserved (swap-with-last): keep a shrinking logical length
n. Whennums[i] == val, overwrite it withnums[n-1](the current last element) and shrinknby one, without advancingi(the swapped-in element still needs to be checked). Whennums[i] != val, advancei. This does one write per removal instead of potentially shifting every later element, which is cheaper when matches are rare and scattered. - Both mutate
numsin place and return the new length; elements at or past the returned length are not meaningfully defined afterward.
Complexity
Both variants: O(n) time (single pass), O(1) extra space. The order-preserving version always does one write per surviving element; the swap variant does one write per removed element, which is fewer when val is rare.
Edge cases
valnot present at all: every element is kept, new length equals original length, zero writes beyond the initial pass.- All elements equal
val: new length is 0. - Empty input: returns 0 immediately.
def remove_element(nums, val):
write = 0
for read in range(len(nums)):
if nums[read] != val:
nums[write] = nums[read]
write += 1
del nums[write:]
return write
def remove_element_unordered(nums, val):
i = 0
n = len(nums)
while i < n:
if nums[i] == val:
n -= 1
nums[i] = nums[n]
else:
i += 1
del nums[n:]
return n
payload = [4, 2, 5, 2, 7, 2, 9]
k = remove_element(payload, 2)
print(k, payload)
payload2 = [4, 2, 5, 2, 7, 2, 9]
k2 = remove_element_unordered(payload2, 2)
print(k2, payload2)
Output:
4 [4, 5, 7, 9]
4 [4, 9, 5, 7]
Both agree on the count (4 surviving elements), but the surviving values land in different positions: [4, 5, 7, 9] keeps the original left-to-right order, while [4, 9, 5, 7] does not (9 moved from the end into an earlier slot during a swap), which is exactly the trade-off the question is asking about.
Trade-offs and pitfalls
- A common bug: using
list.remove(val)or deleting elements from the middle of the array inside a loop, which is O(n) per removal (everything after the deletion point shifts down), making the whole operation O(n^2) in the worst case, and it also skips the next element if you don't adjust the loop index after a deletion. The two-pointer approaches here avoid both problems. - The same read/write two-pointer technique applies directly to low-level, fixed-size buffers, not just Python lists. In C, given a null-terminated
char *s, removing all space characters in place is the identical idea: a write index and a read index both walk the buffer, the write index only advances when the current character should be kept, and a null terminator is placed at the final write position. There's no list-resize step (del nums[write:]) because a C string doesn't carry a separate length field the way a Python list does; the null terminator is the length. - Backend-cleanup framing from the question: "compacting payload arrays before storage" is exactly the order-preserving case if the array represents an ordered sequence (e.g. a time-ordered log) where reordering would corrupt meaning, or the order-not-preserved case if it's an unordered set of records where minimizing writes matters more than position.
Implement is_anagram(s, t) in Python to determine if two strings are anagrams. Ignore case and non-alphanumeric characters. Provide expected complexities and explain why using a frequency map is preferred over sorting for long strings.
Sample Answer
Direct answer
Normalize both strings the same way (lowercase, drop non-alphanumeric characters), then compare their character frequency counts. Building a frequency map is a single O(n) pass per string; sorting both normalized strings and comparing them is O(n log n). For long strings that gap is the entire reason to prefer the frequency map.
Structured elaboration
Normalizing. Filter each string down to lowercase alphanumeric characters only (c.isalnum()), dropping spaces and punctuation. This is a modeling decision worth stating out loud: taken completely literally, "Dormitory" and "dirty room" are not the same sequence of characters at all (different case, an extra space), the question's own instruction to ignore case and non-alphanumeric characters is what licenses treating them as equivalent.
Frequency map. Count occurrences of each normalized character in both strings (collections.Counter does this in one pass) and compare the two counts for equality. Two strings are anagrams exactly when every distinct character occurs the same number of times in both, which a Counter equality check verifies directly, in O(k) time to compare, where k is the number of distinct normalized characters, bounded by the alphabet rather than by n.
Sorting alternative. Sort both normalized character sequences and check they are identical; two strings are anagrams if and only if their sorted forms match. Correct, but O(n log n) because of the sort, versus O(n) for building and comparing frequency maps. For long strings, that difference in growth rate is exactly what "preferred... for long strings" is asking you to justify.
Cheap short-circuit. Compare lengths of the two normalized sequences first; a mismatch there proves non-anagram in O(1) (after the O(n) normalization pass), without needing to build either a sorted copy or a frequency map.
Worked example
from collections import Counter
def is_anagram(s: str, t: str) -> bool:
def normalize(x: str):
return [c.lower() for c in x if c.isalnum()]
ns, nt = normalize(s), normalize(t)
if len(ns) != len(nt):
return False
return Counter(ns) == Counter(nt)
from collections import Counter as _Counter
def _is_anagram_sorted_check(s, t):
def normalize(x):
return sorted(c.lower() for c in x if c.isalnum())
return normalize(s) == normalize(t)
cases = [
("Dormitory", "Dirty Room", True),
("William Shakespeare", "I am a weakish speller", True),
("listen", "silent", True),
("hello", "world", False),
("A gentleman", "Elegant man", True),
("", "", True),
("a", "ab", False),
]
all_agree = True
for a, b, expected in cases:
r = is_anagram(a, b)
print(f"is_anagram({a!r}, {b!r}) = {r} (expected {expected})")
if r != _is_anagram_sorted_check(a, b):
all_agree = False
print()
print("all cases agree between frequency-map and sorting approaches, as expected."
if all_agree else "MISMATCH between frequency-map and sorting approaches!")
Output:
is_anagram('Dormitory', 'Dirty Room') = True (expected True)
is_anagram('William Shakespeare', 'I am a weakish speller') = True (expected True)
is_anagram('listen', 'silent') = True (expected True)
is_anagram('hello', 'world') = False (expected False)
is_anagram('A gentleman', 'Elegant man') = True (expected True)
is_anagram('', '') = True (expected True)
is_anagram('a', 'ab') = False (expected False)
all cases agree between frequency-map and sorting approaches, as expected.
Every case, including the classic "William Shakespeare" / "I am a weakish speller" anagram and the empty-string edge case, matches expectation, and a parallel sorting-based implementation was run against the identical inputs and agreed with the frequency-map result on every one, confirming the two approaches are equivalent in correctness, differing only in complexity.
Trade-offs and pitfalls
Check the length mismatch before doing anything else; it is the cheapest possible rejection and avoids building a data structure you already know cannot match.
Sorting is still a reasonable, sometimes preferable, choice for very short strings, or when you need the sorted form anyway for something else (grouping many words by their sorted key, for instance): at small n, the constant-factor difference between O(n) and O(n log n) barely matters in practice, and the sorted form doubles as a canonical grouping key.
Stating your normalization rules explicitly is part of a senior answer here: "ignore case and non-alphanumeric characters" is a specific, narrower definition of anagram than the literal character-for-character one, and silently assuming it without saying so is a common way this question goes subtly wrong in an interview, even when the code itself is correct.
Unlock Full Question Bank
Get access to all Arrays, Strings, and Hashing interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.