A string is a finite sequence of characters or encoded units treated as a single data value. In data structures, it is a sequence abstraction whose exact representation and available operations depend on the programming language and encoding.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Concept
A string commonly supports operations such as accessing an element by position, finding its length, searching, comparing, concatenating, and creating substrings. An empty string is valid and has length zero.
Many common implementations store elements in contiguous memory, allowing constant-time indexed access. However, contiguous storage is an implementation choice rather than a requirement of the abstract string data type. A text string may contain characters or Unicode code points, while a byte string contains octets.
Python String Representation
Python 3.12’s str type represents Unicode text and is immutable. Consequently, an assignment such as message[0] = "H" raises TypeError. A changed value must be created explicitly, for example with message = "H" + message[1:].
Python’s len() counts Unicode code points, not user-perceived characters or grapheme clusters. For example, precomposed "é" contains one code point, while decomposed "e\u0301" contains two. Unicode encoding is a separate concern: it maps Unicode text to a byte representation such as UTF-8.
For byte-oriented data, Python provides bytes and bytearray. A bytes value is immutable, while a bytearray is mutable. Indexing bytes or bytearray produces an integer byte value, whereas indexing str produces a one-character string.
Complexity
Let n and m be the lengths of two strings, k be a slice’s length, L be the total number of characters being joined, and p be the number of parts.
The table’s space values include auxiliary allocations and newly created results, but exclude the source input itself. The source inputs still occupy O(n) or O(n+m) storage. No recursion is involved, so recursion-stack space is O(1).
Operation
Time
Space
Reason
Read s[index]
O(1)
O(1)
A supported random-access representation retrieves the element directly
Get len(s)
O(1)
O(1)
The length is maintained as metadata
Compare strings
O(n) worst case
O(1)
Equal-length strings may require every element to be compared
Straightforward substring search
O(nm)
O(1)
Up to m elements may be checked at each possible starting position
Concatenate s + t
O(n + m)
O(n + m)
A new immutable result containing both strings is created
Slice s[start:end]
O(k)
O(k)
Slicing copies the selected elements
Build and join p parts
O(L + p)
O(L + p)
The list stores p references and the result stores L characters
Immutability and Performance
Because strings are immutable, repeatedly modifying one can be expensive. A loop using result += piece can repeatedly copy the growing string, resulting in O(n²) behavior in the general case for a total of n characters.
A better approach is to collect the pieces in a list and call " ".join(parts) once. Building the list and joining it takes O(L + p) time and O(L + p) additional space, including the list and final result. If the list already exists, the join operation alone takes O(L) time and creates an O(L)-space result.
Slicing also creates an independent copy: text[2:6] is not a view into the original string.
When to Use a String
Text processing: Use str for human-readable Unicode text.
Identifiers and protocols: Use strings for names, keys, URLs, JSON fields, and command-line arguments.
Binary data: Use bytes rather than str for images, compressed content, network packets, and other non-text data.
Mutable character data: Use bytearray, a list of characters, or another mutable collection when frequent in-place changes are required.
Common Pitfalls
Confusing characters and bytes: str stores Unicode text, while bytes stores octets and has different indexing behavior.
Ignoring Unicode normalization: Canonically equivalent text can have different code-point sequences and therefore different lengths.
Assuming substrings are views: Python slicing copies data and costs O(k) time and space.
Repeatedly concatenating in a loop: Build a list and use join to avoid potentially quadratic copying.
Using list.pop(0) or list.insert(0, value): Both shift the remaining elements and take O(n) time per operation. Use collections.deque when efficient front insertion or removal is required.
2
How do strings and character arrays differ?
KnownRevise
Strings are immutable, object-level sequences of characters, whereas character arrays are mutable, element-level sequences of characters that can be modified in place.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Key Definitions
String: A read-only sequence of characters treated as a single value. In Python 3.12, str is immutable and represents Unicode code points. Raw byte sequences must be represented by bytes/bytearray with an explicit encoding.
Character Array: In Python 3.12 the practical equivalent for in-place character edits is a list of single-character str objects, or a bytearray when strictly working with byte values. Each element can be accessed and reassigned independently. Treat these as different tools depending on whether you need Unicode code points or bytes.
Core Differences
Aspect
String (str)
Character Array (list of chars or bytearray)
Mutability
Immutable. Any modification creates a new str object.
Mutable. Elements can be reassigned/added/removed in place for the container (semantics differ for bytearray vs list).
Modification
Index assignment (e.g. s[0] = 'x') raises a TypeError.
Direct index assignment is allowed where the container is mutable.
Memory Behavior
Slicing creates a copy of the selected substring. Repeated += in a loop creates intermediate str objects (costly for large n).
Edits to existing elements do not require rebuilding the entire sequence to change those elements, but creating a new list by slicing or ''.join() still allocates new objects.
Identity vs Value
Often treated by value for equality (== compares the character/code-point sequence).
A mutable container: identity differs from another object even if element sequences are equal; compare elements explicitly.
Unicode Awareness
len(s) counts Unicode code points. Indexing returns a str for that code point. Use ord() and chr() for character arithmetic.
With a list of single-character str, the same Unicode code-point rule applies per element. With bytearray, you are dealing with byte values only — you must decode/encode with an explicit encoding and cannot assume 1 code point per byte.
Intended Use
Best for fixed textual data, keys/lookups, or values that must not be accidentally mutated.
Best for in-place transformations (swaps/reversals/permutations) where you intend to mutate elements before producing a final str with ''.join().
Complexity Notes
Apply the following to Python 3.12 for the operations most relevant to this distinction. “Input counted” here means: is the original input sequence counted in the stated space complexity (total) or is space counted as auxiliary/extras beyond the input?
Operation
Time (Big-O)
Space (Big-O)
Notes
String slicing s[i:j]
O(k) where k = j-i (best/avg/worst same here)
O(k). Input counted: yes for total if you count the new substring as output derived from input; treat as O(k) for the copy created.
Creates a new str copy of those code points.
s += c inside a loop (n appends)
O(n^2) in the worst/typical case for naive str concatenation in CPython (best case rare). Reason: str is immutable so each += may copy the entire current string to form a new one.
O(n) for the final string objects created over time. Input counted: the growing result is counted in total space; auxiliary copies are the cost.
Avoid in loops; prefer list + ''.join().
lst.append(c) / element reassignment in a list
O(1) amortized for append in the common case (worst case reallocation; say “amortized” where reallocation happens). Element assignment lst[i] = c is O(1).
O(1) auxiliary for the assignment/append action beyond the list storage; Input counted: the list elements are the working copy (if built from input) — state auxiliary vs total per use.
Amortized applies to dynamic array growth (append).
Build from list + ''.join(lst)
O(M) where M is the total number of characters/code points in the joined sequence (best/avg/worst typically O(M), linear).
O(M) for the result str and the list of parts. Input counted: count the final string as output; the list is working storage derived from/for the input.
Preferred for many concatenations; do not rely on list.pop(0) or list.insert(0, x) in loops (O(t) per operation).
Practical Implications
Transformations: To reverse a string in-place in effect, convert str to a mutable container (e.g. a list of single-character str), perform swaps, then ''.join() to produce a new str (the original str remains immutable).
Building Results: For building a large sequence over many iterations, use a list and ''.join() at the end rather than s += c in a loop.
Character Semantics: Unless explicitly stated, do not assume lowercase ASCII. Be explicit about Unicode code points vs bytes: use ord()/chr() intentionally, and only convert between bytes/str with an explicit encoding/decoding.
Edge Cases to Consider
Empty input: An empty str and an empty mutable container both have length 0, but mutability and allowed operations still differ.
One element: Mutability is the distinction even for length 1.
Duplicates: Affect equality, hashing keys and frequency-based logic regardless of representation.
Unicode characters: A human “character” may be a code point; len() counts code points. With bytearray there is no code-point guarantee.
Already “finalized” text: Treating text as immutable prevents accidental cross-reference mutation; converting to a mutable container creates a copy/workspace and does not retroactively change other references to the original str.
Common Pitfalls
Mutating a string: Attempting index assignment to a str raises a TypeError. Convert to a mutable container first if mutation is required.
Counting bytes instead of code points: Using len() without considering Unicode can be misleading. Use ord()/chr() intentionally when doing character arithmetic.
Inefficient concatenation: Using s += c in a loop instead of list + ''.join() is a frequent source of O(n^2) work.
Mixing bytes and str: Treating a byte sequence as text (or vice versa) is an encoding error. Only convert with an explicit encoding, and prefer bytearray only when byte-level mutation is truly required.
Forgetting immutability in references: Multiple variables can reference the same immutable str object; mutating a copied container will not affect the original str.
Interview follow-ups to expect: Be ready to justify when you’d choose a mutable container over str, explain the cost of ''.join(), state whether input is counted for the space you’re quoting, and point out the difference between mutability, copying, and Unicode code points vs bytes.
3
What does a null-terminated string represent in memory?
KnownRevise
A null-terminated string stores encoded character data followed by a null terminator, usually the byte 0x00, which marks where the string ends. The terminator is not part of the visible text; for example, "Hi" is stored in a byte buffer as H, i, 0x00.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
A program reads encoded bytes or code units sequentially until it encounters the null terminator:
Stored bytes
Visible text
String length
72 00
H
1
72 69 00
Hi
2
00
empty string
0
The terminator distinguishes the end of the string from any bytes that follow it in memory. A byte buffer containing "Hi" needs three bytes: two for the characters and one for 0x00.
This representation is commonly used by C and C++. Functions such as strlen, printf, and strcpy rely on null-terminated strings to identify their string boundaries. The terminator itself is not included in the visible string length.
Characters Versus Bytes
A null-terminated string is fundamentally a sequence of encoded bytes or code units, not an inherent sequence of Unicode characters:
ASCII: Each character occupies one byte.
UTF-8: A Unicode code point occupies between one and four bytes. A user-visible character can require multiple code points, such as when combining marks are used.
UTF-16: A Unicode code point is encoded as one or two 16-bit code units, and the terminator is typically the two-byte value 0x0000.
Embedded nulls: A byte sequence such as A\0B appears as "A" when interpreted as a conventional null-terminated string, even though B remains in memory.
Python’s built-in str is different. It is immutable, stores Unicode content, and is not represented as a conventional null-terminated character array. Python bytes objects may contain null bytes and can be passed to C APIs that accept byte strings, but a C API will generally interpret an embedded null as the end of the string.
Complexity
For a byte-oriented null-terminated string with n bytes before the terminator:
Best case:O(n) because the scan must inspect all n content bytes and the terminator.
Average case:O(n) for the same reason.
Worst case:O(n) for the same reason.
Empty string: The check is O(1) because the first byte is already the terminator.
Auxiliary space:O(1) for scanning. The input is not counted as auxiliary space; it occupies n + 1 bytes in a byte-oriented representation. In a fixed-width encoding such as UTF-16, the terminator may instead require multiple bytes.
If the length is stored separately, obtaining it is O(1).
Advantages and Limitations
Advantages: Simple representation, easy interoperability with C-style APIs, and straightforward use with memory-copying functions.
Limitations: The length is not inherently known, so scanning may be necessary. Embedded null bytes cannot appear as visible content in a conventional C string.
Buffer safety: A string must be large enough for its content and terminator. Writing beyond the allocated buffer causes undefined behavior in C and C++.
Encoding: Byte length and Unicode character count are not always equal for multibyte encodings such as UTF-8.
Common Pitfalls
Forgetting to allocate space for the terminator.
Assuming the terminator is included in the visible string length.
Confusing byte count with Unicode character count.
Using strlen or similar operations on a buffer that lacks a terminator.
Treating embedded null bytes as ordinary visible characters.
Assuming Python str objects use the same representation as C strings.
A common interview follow-up asks how the length of a null-terminated string is determined when it is not stored. The answer is to scan until the null terminator, which takes O(n) time.
4
How do mutable and immutable strings differ?
KnownRevise
Mutability determines whether a string’s existing contents can be changed after creation, while immutability means every modification produces a new string. In Python, str objects are immutable, so operations such as replacement or concatenation return new objects rather than altering the original.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Difference
A string’s mutability is a property of its type, not of the variable that references it.
Property
Mutable string
Immutable string
Modify existing contents
Allowed in place
Not allowed
Result of an update
The same object changes
Usually a new object is returned
Sharing between owners
Owners can observe changes
Owners continue seeing the original value
Thread-safety
Requires synchronization when shared and concurrently modified
Safe to share because values cannot change
Use as a dictionary key
Usually unsuitable if its contents affect equality
Suitable when hashable
Typical example
bytearray
str and bytes in Python
For example, if original and reference both refer to the Python string "hello", executing reference += " world" rebinds reference to a new string. It does not modify the original string, so original still contains "hello".
How Immutability Works in Python
Python’s str represents text as a sequence of Unicode code points. Common operations therefore behave as value transformations:
Indexing: text[0] returns a one-code-point string.
Slicing: text[start:end] returns a new string.
Replacement: text.replace(...) returns a new string.
Concatenation: text + suffix returns a new string.
Normalization: text.lower() returns a new string.
The original object remains unchanged in every case. Other languages differ: Java’s String is immutable, while StringBuilder is mutable; C++’s std::string is mutable.
Time and Space Complexity
For a string of length n and a slice of length k, the following complexities apply. Input storage is excluded from auxiliary space unless explicitly stated.
Operation
Best case
Average case
Worst case
Extra space
Reason
Access one code point
O(1)
O(1)
O(1)
O(1)
A code point can be located directly
Traverse the string
O(n)
O(n)
O(n)
O(1)
Every code point must be visited
Copy a slice of length k
O(k)
O(k)
O(k)
O(k)
The slice and its copy contain k code points
Concatenate strings of lengths n and m
O(n + m)
O(n + m)
O(n + m)
O(n + m)
A new result string must be allocated
Hash the entire string
O(n)
O(n)
O(n)
O(1)
All code points must be processed
Python caches a string’s hash after its first calculation, so subsequent calls to hash(text) are O(1). The immutability of str makes this caching safe.
Practical Implications
Safe sharing: Immutable strings can be passed between functions or threads without one caller unexpectedly changing another caller’s value.
Hashability: Immutable str objects can be dictionary keys and set members.
Simple reasoning: A string value effectively identifies a fixed sequence rather than a changing buffer.
Memory awareness: Repeated transformations can create temporary strings and increase memory usage.
Unicode awareness: Python str stores Unicode code points, so len(text) counts code points rather than encoded bytes. A user-perceived character, such as an emoji with multiple code points, may count as more than one.
Common Pitfalls
Rebinding is not mutation: text = text.upper() creates a new string and rebinds text; it does not modify the old object.
Repeated += can be quadratic: Building a string with += in a loop may repeatedly copy the growing result, giving O(n²) time in the worst case.
Use join for accumulation: Collect strings in a list and call "".join(parts). For total input length L, this takes O(L) time and O(L) space for the result.
Do not confuse text and bytes: str represents Unicode text, bytes represents immutable byte sequences, and bytearray is a mutable byte sequence.
Watch slicing costs: Slicing copies k code points and requires O(k) space; it is not a view into the original string.
5
How do programming languages represent and manipulate strings?
KnownRevise
Programming languages represent strings as sequences of encoded characters or bytes and provide operations for comparison, searching, slicing, concatenation, and encoding. The string representation—Unicode code points, UTF-16 code units, or raw bytes—determines indexing behavior, memory usage, and complexity.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Common Representations
Language
Logical unit
Mutability and encoding notes
Python 3.12
Unicode code points
str is immutable; compact internal storage uses ASCII or wider Unicode representations. bytes is separate.
Java 21
UTF-16 code units
String is immutable. A supplementary Unicode character, such as an emoji, occupies two char units.
JavaScript ES2023
UTF-16 code units
Strings are immutable. length counts code units rather than user-perceived characters.
C++20
Bytes in std::string
std::string is mutable and encoding-agnostic. std::u16string and std::u32string provide UTF-specific alternatives.
Internally, runtimes may use contiguous byte buffers, compact encodings, or tree-like structures such as ropes. These details affect performance but should not normally change observable behavior.
Characters, Code Units, and Bytes
A character is not represented identically everywhere:
Unicode code point: One value in the Unicode standard. In Python 3.12, len(str) counts code points.
UTF-16 code unit: A 16-bit value used by Java and JavaScript. Some characters require two units.
Byte: An 8-bit value. UTF-8 uses between one and four bytes per code point.
User-perceived character: What a reader considers one letter or symbol. It may consist of several code points.
For example, in text that contains "é", the number of code points, UTF-16 code units, and UTF-8 bytes can all differ depending on the encoding and representation used. Unicode normalization also matters: visually identical text can have different encodings. Python does not automatically normalize strings, so comparisons may require unicodedata.normalize() when the data producer does not guarantee a canonical form.
Operation Costs
Let n be the input length and k the length of a selected substring. Space complexity here is stated as auxiliary space excluding the input unless explicitly stated.
Operation
Time complexity
Space complexity
Reason
Access by a direct index to the representation’s fixed unit
O(1) best/average/worst
O(1) auxiliary (input not counted)
Only applies when units are fixed-width and directly addressable. For variable-width encodings (e.g. UTF-8) finding a specific code point by character index can require scanning and is not guaranteed O(1).
Iterate over all represented units
O(n) best/average/worst
O(1) auxiliary (input not counted)
Every represented unit is visited once.
Slice or extract a substring
O(k) best/average/worst
O(k) auxiliary for the new copy/output (input not counted)
With immutable strings, creating the selected substring produces a copy of those k units.
Concatenate two immutable strings
O(n + m) best/average/worst
O(n + m) auxiliary for the new string (input not counted)
A new string must contain both operands.
Encode or decode text
O(n) best/average/worst
O(n) auxiliary for the encoded/decoded output (input not counted)
The complete input is converted.
Append to a mutable builder
O(1) amortized
O(n) auxiliary for the buffer over time (input not counted)
Occasional buffer growth copies existing content.
These costs describe the logical operation. Particular runtimes may optimize concatenation or searching internally, but for immutable strings slicing still creates a copy.
Construction and Manipulation
Immutable strings: Operations return new objects. This simplifies sharing, caching, and safe use as dictionary keys.
Mutable buffers: StringBuilder in Java, StringBuffer in older APIs, and similar builders in other languages reduce repeated copying when constructing large strings.
Python concatenation: Repeated result += part inside a loop can take O(n²) total time because intermediate immutable strings are copied. Collect parts in a list and call "".join(parts) for linear construction.
Search and comparison: Built-in APIs are usually optimized and may use linear-time or pattern-based algorithms. Complexity therefore depends on the language and implementation rather than only on the source expression.
Unicode-aware APIs: Prefer casefold() over lower() for caseless comparisons, because Unicode case conversion can change text length and produce multiple characters.
Common Pitfalls
Confusing code points, code units, and bytes: Check what the language’s length property actually counts.
Assuming UTF-8 means one byte per character: Non-ASCII characters commonly require multiple bytes.
Ignoring Unicode normalization: Visually equal strings may not compare equal.
Repeated immutable concatenation: Use a builder or join rather than += in a Python loop.
Forgetting that slicing copies: Slicing an immutable string consumes time and space proportional to the copied length.
Off-by-one errors: Carefully define whether substring and range endpoints are inclusive or exclusive.
Integer overflow: In fixed-width languages, expressions such as left + right or n + m can overflow when calculating buffer sizes.
Unexpected mutation: Some C++ and buffer APIs modify their inputs, while Python, Java, and JavaScript string operations normally return new values.
Interviewers commonly follow up by asking how len() differs between bytes and text, why immutable concatenation can be expensive, or how UTF-8 handles characters outside the ASCII range.
6
Do character arrays improve password security compared with Strings?
KnownRevise
Character arrays can improve password security over immutable Strings because a mutable buffer can be overwritten before it is discarded. This provides better control over sensitive data, but it is defense in depth rather than a guarantee of secure memory handling.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Security Difference
Immutable String objects cannot be changed after creation. A password stored in a String may therefore remain in memory until it is garbage-collected, and temporary copies created during formatting, logging, or serialization may remain longer.
A mutable character array, such as Java’s char[] or .NET’s char[], can instead be cleared before it is discarded:
Overwrite every element with its zero value.
Drop the reference to the buffer afterward.
Avoid unnecessary copies while the password is being used.
In Python 3.12, the closest mutable byte-oriented equivalent is bytearray; both str and bytes are immutable. Converting an existing str or bytes value to bytearray creates a mutable copy but does not erase the original immutable object. A mutable buffer therefore improves erasure only when the password can be obtained without first creating an unnecessary immutable copy.
Time and Space Complexity
Let n be the number of characters or bytes in the password.
Operation
Best, Average and Worst Time
Space
Reason
Copying a password into a mutable buffer
O(n)
O(n)
Every character or byte is copied
Clearing a mutable buffer
O(n)
O(1) auxiliary
Every position is overwritten once
Creating an immutable string
O(n)
O(n)
A new object and its character storage are required
Processing the input for a password hash
O(n) for input scanning
O(n) plus algorithm-dependent working memory
The password must be read; the algorithm’s configured work factor and memory use determine the total cost
The table counts the destination or hashing-input buffer but not an already-existing source secret. Total password-hashing time is not necessarily O(n) because algorithms such as Argon2id, bcrypt, scrypt, and PBKDF2 deliberately include additional work.
Limitations and Caveats
Mutable does not mean automatically secure: The application must clear the array promptly and correctly.
Copies may survive: Logging, formatting, GUI components, serialization, exceptions, and temporary conversions can create copies that cannot be cleared.
Runtime behavior varies: Compilers, just-in-time runtimes, and garbage collectors may move, copy, or retain objects, so explicit zeroization is stronger but not a universal guarantee.
Storage is a separate concern: A character array addresses transient memory; it does not define how a password should be stored permanently.
Password hashing is still required: For persistent storage, use a salted, adaptive password hash such as Argon2id, bcrypt, scrypt, or PBKDF2 with appropriate parameters—not raw characters or an unsalted fast hash.
Best Practices
Minimize the password’s lifetime and the number of copies created.
When the platform supports it, use a mutable buffer and clear it in a finally block or equivalent cleanup path.
If an API requires an immutable string, use it only for as short a period as possible and never log it.
Do not assume converting a secret to bytearray erases a previously created str or bytes copy.
Use a reputable password-hashing library when storing passwords.
Treat zeroization as defense in depth rather than a substitute for secure coding and storage controls.
Common Pitfalls
Assuming that deleting a String immediately removes its contents from memory.
Clearing only the original array while leaving copies in logs, exceptions, or temporary objects.
Converting an immutable password to a mutable buffer while overlooking the original copy.
Using a character array as the permanent storage format for passwords.
Assuming every runtime guarantees that a compiler or garbage collector will erase secret memory promptly.
Forgetting that Java char[] stores UTF-16 code units, while Python str represents Unicode code points; use the platform’s documented encoding rules when comparing or transferring passwords.
7
How does indexing work in Python string operations?
KnownRevise
In Python 3.12, string indexing is zero-based and returns the character at a specified position, where each position represents one Unicode code point rather than necessarily one user-perceived character. Indexing supports fast direct access, but slicing and many whole-string operations create or scan new data, so their complexity depends on the operation and string length.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Indexing Model
Python strings are immutable and indexed with square brackets:
Zero-based indexing: The first character is at index 0.
Negative indexing: -1 refers to the final character, -2 to the second-to-last, and so on.
Bounds checking: An out-of-range index raises IndexError.
Immutability: Individual characters cannot be assigned, so text[0] = "J" raises TypeError.
Unicode code points: len counts code points, not bytes or grapheme clusters. For example, "é" has length 1, while "e\u0301" has length 2 because it contains two code points.
For text = "café":
Index
Character
0
c
1
a
2
f
3
é
bytes behave differently: indexing a bytes object returns an integer byte value, not a character, and len(bytes) counts bytes.
Effects on Common Operations
Indexing is especially useful when an algorithm needs to compare positions directly:
Two-pointer algorithms: Palindrome checks compare text[left] with text[right] while moving the pointers inward.
Sliding windows: A window is commonly represented by two indices, such as text[left:right + 1].
Character classification: ord(text[index]) obtains a code point’s numeric value, while chr(value) converts it back.
Searching: Methods such as find return an integer index or -1; index returns an integer index but raises ValueError when no match exists.
Slicing: text[start:end] creates a new string, unlike direct indexing, which does not copy the entire input.
Concatenation: Because strings are immutable, “changing” one character generally requires constructing another string. Repeated += in a loop can become quadratic in time and use O(n) peak space; use a list and "".join(parts) for O(n) time and O(n) space.
Iteration: for character in text visits code points, while enumerate(text) provides both the index and character.
Complexity
These bounds assume Python 3.12’s built-in str implementation and exclude the original input from the space calculation.
Operation
Best time
Average time
Worst time
Space
text[index]
O(1)
O(1)
O(1)
O(1)
len(text)
O(1)
O(1)
O(1)
O(1)
text[start:end]
O(k)
O(k)
O(k)
O(k) including the result; O(1) auxiliary excluding it
text[::-1]
O(n)
O(n)
O(n)
O(n) including the result; O(1) auxiliary excluding it
Direct iteration
O(n)
O(n)
O(n)
O(1)
Two-pointer palindrome check
O(n)
O(n)
O(n)
O(1)
Here, n is the number of code points and k is the number of code points in the slice. The palindrome implementation below uses no recursion, so there is no recursion-stack cost.
Code Example
def is_palindrome(text: str) -> bool:
"""Check whether text is a palindrome by Unicode code point."""
if len(text) < 2:
return True
# Compare the outermost pair, then move toward the center.
left, right = 0, len(text) - 1
while left < right:
if text[left] != text[right]:
return False
left += 1
right -= 1
return True
print(is_palindrome("level"))
# True
For "level", the algorithm proceeds as follows:
left = 0 and right = 4; compare l with l.
left = 1 and right = 3; compare e with e.
The pointers meet in the middle, so return True.
It handles empty strings and one-character strings, which are palindromes.
Common Pitfalls
Confusing code points with user-perceived characters: A family emoji or combining-character sequence may contain several code points, so this algorithm checks code-point symmetry rather than grapheme-cluster symmetry.
Assuming normalization changes case: "Level" and "level" remain different after Unicode normalization. Use casefold() or lower() for case-insensitive comparison, and strip() when surrounding whitespace should be removed.
Forgetting immutability: Do not attempt text[index] = value; create a modified string instead.
Using += inside a loop: Repeated concatenation can take O(n²) time. Collect fragments in a list and call "".join(parts).
Assuming slicing is free: A slice copies the selected code points and uses O(k) space for the result.
Overlooking index errors: Empty strings have no valid character index, and direct indexing must be bounds-checked when the input is user-controlled.
Likely interview follow-up: Ask how the same operations differ for bytes, non-ASCII text, and grapheme-cluster-aware processing.
8
What is a Pascal string in string handling?
KnownRevise
A Pascal string is a length-prefixed string: one or more bytes store the string’s length before the character data. Unlike a null-terminated C string, it does not require a trailing \0, and the length can be obtained directly from the prefix.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Format
A traditional Pascal string uses a single-byte unsigned length prefix, so its maximum payload length is 255 bytes. Its structure is [length byte][character data].
For example, the five-character ASCII string Hello is represented by the bytes 05 48 65 6C 6C 6F:
05 is the unsigned payload length in bytes.
48 65 6C 6C 6F contains the bytes for Hello.
No null terminator is required because the prefix identifies the payload’s end.
Why Length Prefixes Are Used
Fast length lookup: The number of bytes or other encoded units can be read without scanning the payload.
No terminator scanning: Finding the end does not require comparing every character with \0.
Binary-safe payloads: Embedded null bytes can be handled as ordinary data when the format permits them.
Easy serialization: Length and data can be written together without relying on a language-specific string representation.
Length-prefixed strings are useful in file formats, network protocols, serialized objects, and interfaces where strings cross language or system boundaries.
Relation to Pascal
The term commonly describes the Pascal-style length-prefixed representation, not necessarily every string type in every Pascal compiler.
In traditional Pascal implementations such as Turbo Pascal, a fixed-length string buffer reserves its first byte for the current length and permits at most 255 characters. Modern Pascal dialects may instead provide dynamically sized strings, length-prefixed records, or compiler-specific representations. For interoperability, Pascal-style length-prefixed string is therefore more precise than assuming every Pascal string has the same representation.
Complexity
Let n be the payload length in bytes or other stored code units. Assume a fixed-width prefix and contiguous storage. The best, average, and worst-case algorithmic times are the same for these operations.
Operation
Time
Space
Reason
Read the length
O(1)
O(1) auxiliary
A fixed-width prefix stores the length directly.
Access a stored byte or code unit by index
O(1)
O(1) auxiliary
Direct indexing is supported by contiguous storage.
Traverse the payload
O(n)
O(1) auxiliary, excluding input
Every payload unit must be visited.
Copy or extract the payload
O(n)
O(n) for the new output, excluding input
All n units must be copied.
Store a complete string
O(n)
O(n + 1) total storage
Storage is needed for the prefix and payload.
The auxiliary-space figures exclude the input and any returned output. In Python 3.12, slicing bytes creates a copy, so extracting the payload requires O(n) time and O(n) additional space.
Character Versus Byte Length
The prefix in the classic format counts bytes, not Unicode code points. For example, é uses two bytes in UTF-8 but is one Unicode code point. Python’s bytes length therefore matches the prefix count, while str length may not.
Use a UTF-8 byte length when serializing: "é" is one code point and two UTF-8 bytes. Always specify whether a length represents bytes or characters when designing a format. A four-byte prefix can support larger values, but its byte order and integer encoding must also be defined.
Common Pitfalls
Confusing Pascal with the format: Compiler-specific Pascal string types do not all use the same representation.
Ignoring the length limit: A one-byte prefix represents lengths from 0 through 255, but not larger values.
Handling the empty string: A zero-length payload is valid and is represented by a prefix of 0.
Assuming null termination: Searching for \0 as the string boundary is incorrect for a length-prefixed value.
Mixing bytes and characters: UTF-8 character count and encoded byte count differ for non-ASCII text.
Changing the prefix convention: Receivers must agree on prefix size, byte order for multi-byte prefixes, and whether the length includes the prefix itself.
Repeated concatenation: Building strings with += in a Python loop can become O(n²); collect fragments in a list and use ''.join() when constructing text dynamically.
9
How does string concatenation work and what is its complexity?
KnownRevise
String concatenation combines the characters of two or more strings into a new sequence. Because Python strings are immutable, concatenation generally creates a new string; repeated concatenation can therefore be expensive unless the implementation can efficiently reuse the existing storage.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
In Python, the + operator concatenates two strings. For example, combined = left + right preserves the order of all characters from left, followed by all characters from right.
Step
Result
Start with "str"
"str"
Concatenate "ing"
"string"
Concatenate " concat"
"string concat"
Concatenate "enation"
"string concatenation"
Python str objects represent sequences of Unicode code points. Therefore, len(text) counts code points, not encoded bytes. A character such as "é" occupies one position in a Python string but two bytes in UTF-8.
Concatenating a string with a non-string raises TypeError. Empty strings are valid operands, "".join([]) returns "", and duplicate parts are preserved in order.
Time and Space Complexity
Let:
n be the number of code points in the first string.
m be the number of code points in the second string.
q be the number of concatenation operations.
L be the total number of code points across all input parts.
Approach
Best time
Average time
Worst time
Space
One left + right
O(1) when one operand is empty
O(n + m)
O(n + m)
O(n + m) including the result
Repeated result = result + part
O(q + L)
O(qL)
O(qL)
O(L) including the current and new result
Repeated result += part
O(q + L) amortized when storage is reused
O(qL) without guaranteed reuse
O(qL)
O(L) including the current result
"".join(parts)
O(q + L)
O(q + L)
O(q + L)
O(q + L) including the result and temporary references
A single concatenation copies the characters into a new immutable string, except that CPython can reuse the non-empty operand when the other operand is empty. For repeated immutable concatenation, each operation may copy the entire accumulated result, so the total work can grow quadratically. When q is also Θ(L), the common worst case is O(L²).
CPython 3.12 can optimize some += patterns when it can reuse the destination’s storage, commonly for an exclusively referenced local string. This can produce an amortized O(q + L) total cost, but it is an implementation optimization rather than a portable guarantee.
The space figures include the newly created output but do not count the input strings or input collection. str.join can additionally use O(q) space for temporary references to its parts. There is no recursion stack, so its contribution is O(1).
Code Example
For multiple parts, str.join is preferred because it copies the characters into the final result once:
def concatenate_parts(parts: list[str]) -> str:
"""Join string parts in order without repeated immutable-string copying."""
return "".join(parts)
result = concatenate_parts(["str", "ing", " concat", "enation"])
print(result) # string concatenation
This function handles an empty list by returning "", preserves empty and duplicate parts, and returns the same content whether there is one part or many.
Best Practices
Use join for collections: Prefer "".join(parts) when combining an unknown number of strings.
Use + for a small fixed number of operands: A few direct concatenations are straightforward and generally efficient.
Avoid repeated += in loops: Although CPython may optimize some cases, repeated immutable-string concatenation can become O(L²).
Use str.join or io.StringIO for generated output: Both avoid repeatedly copying the entire accumulated result.
Count characters, not bytes: Python string complexity is usually measured in code points; encoded byte length depends on the encoding.
Remember that slicing copies: Extracting a substring with text[start:end] creates a new string and costs O(end - start) time and space.
Common Pitfalls
Assuming += is always constant-time because it resembles an append operation.
Ignoring quadratic copying when building a large string inside a loop.
Measuring UTF-8 byte size with len(text); len counts Unicode code points.
Forgetting to include output storage and temporary references when discussing space complexity.
Assuming empty parts or duplicate parts are removed—concatenation preserves them exactly.
Mutating strings character by character, which is impossible because Python strings are immutable.
10
What is the time complexity of substring search in strings?
KnownRevise
Substring search has no single time complexity: it depends on the matching algorithm. A naive search takes O(n × m) time in the worst case, while an optimal algorithm such as KMP takes O(n + m) time by avoiding repeated comparisons after a mismatch.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
Let:
n be the length of the text.
m be the length of the pattern.
A naive algorithm checks the pattern at every possible text position. Each alignment can require up to m character comparisons, giving O(n × m) worst-case time.
KMP uses a prefix function to determine how much of the pattern can be reused after a mismatch:
prefix[i] is the length of the longest proper prefix of pattern[:i + 1] that is also a suffix.
After a mismatch, the algorithm falls back to a valid shorter prefix instead of restarting the comparison.
Although an individual pattern character may be reconsidered after a failure, the total number of comparisons is amortized linear, producing O(n + m) time.
For example, searching for "ABABC" in "ABABABC":
The alignment starting at index 0 matches "ABAB".
At index 4, the text character A mismatches the pattern character C.
The prefix function identifies "AB" as the reusable prefix and suffix, so the search falls back to that alignment.
The pattern then matches from index 2 through index 6.
Complexity Comparison
Approach
Best case
Average case
Worst case
Auxiliary space
Naive search
O(n)
Distribution-dependent; O(n) for i.i.d. random characters
O(n × m)
O(1)
KMP
O(n + m)
O(n + m)
O(n + m)
O(m)
Rabin–Karp with hashing and verification
O(n + m)
Expected O(n + m) with a suitable random hash
O(n × m) with adversarial collisions
O(1)
KMP time: O(n + m) because prefix-function construction takes O(m) and scanning the text takes O(n).
KMP space: O(m) for the prefix table, excluding the input strings.
Naive space: O(1) auxiliary space for indices and a comparison counter.
Rabin–Karp space: O(1) auxiliary space for a rolling hash, excluding the inputs and any sliced result.
Python 3.12’s built-in in operator and str.find() use optimized implementations, but Python does not specify one universal time-complexity guarantee for them across all implementations.
Edge Cases
Empty pattern: By the usual convention, it matches at position 0 with a zero-length result.
Empty text: A nonempty pattern cannot match; an empty pattern still matches at position 0.
Pattern longer than the text: No match is possible.
One-element input: A match occurs only when the text and pattern contain the same character.
Duplicate occurrences: Searching for the first occurrence stops at its earliest starting position.
Unicode: Python strings represent Unicode code points, and len() counts code points. KMP compares code points rather than encoded bytes.
Common Pitfalls
Do not describe every substring search as O(n × m); that is the naive worst-case bound, not the optimal one.
Include pattern preprocessing in KMP’s analysis: it uses O(m) time and space in addition to scanning the text.
Do not claim a universal average case for naive search without specifying the input distribution.
Slicing text[start:end] creates an O(k) copy; returning indices avoids that output allocation.
Do not modify the input strings during the search; Python strings are immutable.
For byte-oriented data, use bytes or bytearray; their indexes represent bytes rather than Unicode code points.
11
How does a rope data structure organize large strings?
KnownRevise
A rope is a tree-based data structure for storing and manipulating large strings or character sequences. Instead of copying all characters during every concatenation, it stores text in chunks connected by internal concatenation nodes.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Representation
A rope is commonly implemented as a balanced tree:
Leaf nodes contain chunks of characters rather than necessarily storing one character per node.
Internal nodes represent the concatenation of their children.
Balancing keeps the height small, typically O(log n) for a balanced rope with n characters.
Weights or lengths stored at nodes let the implementation locate characters without scanning every preceding character.
For example, a rope representing "Hello, world!" might initially have one leaf. Concatenating it with " Welcome" can create another leaf and an internal parent without copying either original chunk.
Why It Exists
Python strings are immutable. Repeatedly executing text += "more" in a loop can therefore copy the growing string repeatedly, resulting in O(n²) total time in the worst case. A rope represents edits through small tree nodes and references, reducing copying.
Ropes are useful in editors, document-processing systems, and text buffers that perform many insertions, deletions, concatenations, or substring operations on large text.
Core Operations and Complexity
Let n be the total number of characters, k the length of a materialized substring, c the number of characters in a leaf chunk, h the tree height, and m the number of leaves. Space below is additional to the stored rope unless an output is explicitly noted.
Operation
Time
Additional space
Link two existing roots
O(1)
O(1)
Locate a character
O(h + c)
O(1)
Insert or delete using path copying and chunk splitting
O(h + c)
O(h + c)
Materialize a substring as a flat sequence
O(h + c + k)
O(k) output plus O(h) auxiliary space
Create a structural substring sharing existing chunks
O(h)
O(h)
Visit every character
O(n)
O(h) auxiliary space for an iterative traversal
Visit only chunk nodes
O(m)
O(h) auxiliary space
Best, average, and worst case with a maintained balanced invariant: indexed lookup and bounded-chunk edits are O(log n + c), including when c is constant.
Worst case with a degenerate tree: height can become O(n), making lookup and edits O(n + c).
Concatenation: creating the parent reference is always O(1). Maintaining the balance invariant is implementation-dependent; a straightforward full rebuild of m leaves takes O(m) time and O(m) space.
A flat substring must copy k characters, while a structural substring can share chunks and avoid that O(k) copy.
Including character storage and node metadata, a rope occupies O(n + m) = O(n) space.
Example Walkthrough
Suppose two ropes contain "Hello" and " world".
Each chunk is stored in a leaf node.
Concatenation creates an internal node referencing both leaves.
The root stores the combined length, 11.
Accessing index 6 follows subtree lengths to the second leaf and then scans within that leaf.
Inserting "there" splits or updates the affected leaf and reconnects the relevant ancestors.
The original chunks do not need to be copied merely to represent their concatenation.
Advantages and Limitations
Advantages: Fast structural concatenation, efficient indexed access, and reduced copying during edits.
Limitations: More metadata than a flat string, a more complicated implementation, and balancing costs.
A rope is most beneficial for large, frequently edited text; short strings or strings with few edits are usually simpler and faster as flat immutable strings.
Ropes operate on characters, not necessarily bytes. Python’s len counts Unicode code points, whereas a byte-oriented implementation indexes bytes.
Common Pitfalls and Interview Tips
Do not claim that every rope operation is O(1); only linking two existing roots is inherently constant-time.
Account for scanning within a multi-character leaf when discussing indexed lookup.
Distinguish a copied flat substring from a structural substring that shares chunks.
Mention that balancing is essential for logarithmic lookup performance.
Python’s standard library does not expose a built-in rope implementation; list followed by ''.join(...) is the usual way to avoid quadratic immutable-string concatenation.
Common follow-ups ask about balancing, locating characters, sharing nodes during edits, and comparing ropes with immutable strings or gap buffers.
12
What are the key advantages and limitations of ropes?
KnownRevise
A rope is a tree-based data structure for representing strings as a sequence of smaller string chunks. It is especially useful when large strings are repeatedly concatenated, split, or edited, because it can avoid copying the entire string for every operation.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How Ropes Work
A rope typically has:
Leaf nodes: Contain small chunks of text.
Internal nodes: Represent concatenation and are usually kept balanced.
Structural sharing: Multiple ropes can refer to the same unchanged chunks.
For example, concatenating "hello" and "world" can create a new internal node pointing to the two existing chunks instead of copying all characters into a new string. Python’s built-in str does not provide this behavior directly; rope implementations are generally provided by specialized libraries or custom code.
Key Advantages
Efficient concatenation: Joining two balanced ropes generally requires logarithmic tree work rather than copying all characters.
Efficient splitting: A rope can be divided at a position without duplicating the unchanged portions.
Localized updates: Editing one section can create new nodes along the path to that section while sharing the rest.
Good fit for large documents: Text editors, compilers, and version-control systems often need to manipulate large strings incrementally.
Persistent or copy-on-write designs: Existing rope versions can remain unchanged while a new version shares most of their structure.
Flexible chunking: Chunks can be split, combined, compressed, or sourced from different storage mechanisms.
Limitations
Higher memory overhead: Every chunk and internal node requires metadata, so a rope can use more memory than a flat string.
Slower random access: Finding an individual character usually requires traversing the tree, whereas indexing a Python str is effectively constant time.
More complex implementation: Balancing, sharing, splitting, and garbage collection are substantially harder to implement correctly than ordinary string concatenation.
Small-string overhead: For short strings or applications dominated by ordinary operations, a flat string is often simpler and faster.
Mutation costs depend on the design: In a persistent rope, each edit may allocate new nodes. In a mutable rope, updates can be cheaper but may reduce the benefits of version sharing.
Unicode and encoding complexity: Chunks must respect the intended character or byte boundaries. Python strings represent Unicode code points, while byte-oriented languages may use different indexing rules.
Complexity
For a balanced rope with n total characters:
Operation
Best
Average
Worst
Reason
Concatenate
O(log n)
O(log n)
O(log n)
Creates or adjusts logarithmic tree nodes
Split
O(log n)
O(log n)
O(log n)
Locates the boundary and separates tree paths
Character lookup
O(log n)
O(log n)
O(log n)
Descends through the chunk tree
Read k characters
O(log n + k)
O(log n + k)
O(log n + k)
Tree traversal plus output traversal
Build from a flat string
O(n)
O(n)
O(n)
Every character must be inspected and stored
Traverse or flatten
O(n)
O(n)
O(n)
Every character is visited
These bounds assume the rope remains balanced. An incorrectly balanced implementation can degrade toward O(n) for operations that should be logarithmic. Space usage is typically O(n) for the rope’s nodes and chunk contents. Structural sharing can reduce newly allocated space for a derived rope to approximately O(log n) nodes, but the original chunks remain retained as long as they are referenced. Auxiliary space is O(log n) for traversal stacks in typical implementations; the input rope itself is not counted as auxiliary space.
Common Pitfalls and Interview Tips
Do not claim that rope character lookup is O(1); that advantage belongs to flat, contiguous string representations.
Distinguish a rope operation that changes the tree from one that materializes a flat copy. Flattening the entire rope costs O(n).
Mention the assumptions behind logarithmic complexity: the tree must be balanced and operations must use structural sharing appropriately.
Explain that ropes are most beneficial for large, repeatedly edited strings, while normal str values are usually preferable for small or read-mostly text.
Edge cases include an empty rope, a rope containing one chunk, edits at chunk boundaries, and Unicode text whose chunk boundaries must not split invalidly. A rope library should handle these cases consistently.
13
Where are rope data structures used in practical applications?
KnownRevise
A rope is a tree-based representation of a character sequence that supports efficient concatenation, splitting, insertion, and deletion without repeatedly copying the entire string. It is useful when applications manipulate large documents or other long text buffers frequently.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How Ropes Work
A rope divides text into smaller string chunks, called leaves, and connects them through internal nodes. Internal nodes represent the concatenation of their children, often storing the total character length.
For example:
"abc" and "def" are stored as separate leaves.
Their parent represents "abcdef" without copying either leaf into one contiguous buffer.
Splitting at position 4 locates the boundary and creates subtrees representing "abcd" and "ef".
This structure is especially effective for large text because operations can share unchanged chunks instead of copying them.
Typical Complexities
The following assumes a balanced, eagerly rebalanced rope with cached subtree lengths. Under this implementation, the best-, average-, and worst-case time bounds have the same asymptotic forms.
Operation
Time
Space
Character lookup by index
O(log n)
O(1) auxiliary
Concatenation with rebalancing
O(log n)
O(log n) auxiliary
Split
O(log n + k)
O(log n + k), including new nodes and copied characters
Insertion or deletion
O(log n + k)
O(log n + k), including new nodes and copied characters
Substring extraction
O(log n + k)
O(log n + k), including copied output and path or stack space
Full flattening
O(n)
O(n) output plus O(log n) recursion stack
Full traversal
O(n)
O(log n) recursion stack
Here, n is the total number of characters and k is the number of characters copied or materialized. Auxiliary space excludes the existing input rope; copied output and newly allocated nodes are included where indicated. A fully materialized rope or contiguous string requires O(n) total space, including character data.
A lazy concatenation wrapper can make the immediate join O(1) in time and auxiliary space, but it defers balancing. Its eventual rebalancing cost depends on the implementation and accumulated imbalance, so it does not provide the same immediate concatenation bound as the eagerly rebalanced case.
Practical Applications
Text editors: Large documents can be edited without copying the entire file for every insertion or deletion.
Code editors and IDEs: Source files, project files, and search results are often represented as large text buffers that benefit from chunked editing.
Document-processing systems: Word processors, publishers, and note-taking applications can use ropes to support long documents and structural operations efficiently.
Collaborative editing: Chunked representations make it easier to reuse unchanged portions of a document when applying edits or generating versions.
Log viewers and file browsers: Large log files can be split into chunks for selective loading, display, and searching.
Diff and patch tools: Chunk-level text representations can reduce copying when comparing or modifying similarly structured documents.
Version-control and archival systems: Tree-structured text can help represent snapshots while sharing unchanged content, although systems such as Git commonly use additional mechanisms such as delta encoding rather than relying on a single rope implementation.
Rope Versus a Flat String
Property
Rope
Flat immutable string
Concatenation
Efficiently shares existing chunks
May copy the entire sequence
Insertion and deletion
Avoids copying unaffected text
Often requires rebuilding the sequence
Character lookup
Usually O(log n)
Usually O(1)
Contiguous access
Requires flattening
Directly available
Memory overhead
Higher for nodes and metadata
Lower for one flat buffer
Best fit
Large, frequently edited text
Small strings and simple read-only access
In Python 3.12, ordinary strings are immutable. Repeatedly using text += chunk in a loop can therefore become quadratic in the general case; the usual alternative is to collect chunks in a list and call "".join(chunks). A rope is a more advanced solution when the application needs both efficient editing and large text.
Common Pitfalls and Interview Tips
Do not assume every operation is cheap: lookup and editing may be logarithmic, but flattening the entire rope into one string costs O(n).
Clarify Unicode semantics: Python len counts Unicode code points, while byte-oriented systems count bytes. The rope must preserve the intended character model.
Mention balancing: Complexity guarantees depend on a balanced structure and cached subtree lengths; an unbalanced or poorly implemented tree can degrade toward linear behavior.
Protect shared data: Treat shared leaves as immutable or use copy-on-write, otherwise an edit could affect another branch or version.
Check boundary positions: split and substring positions are commonly zero-based and must be validated against the rope length.
Common follow-up questions: Compare ropes with str, explain substring extraction, discuss thread safety, and identify when a simple list of chunks is sufficient.
14
How do Ropes compare with StringBuilders?
KnownRevise
A rope is a tree-like data structure optimized for efficient concatenation, insertion, deletion, and substring operations, while a StringBuilder is a mutable linear buffer optimized for appending characters and producing a final string. Ropes trade additional structural overhead for better large-scale editing, whereas StringBuilders are usually simpler and faster for sequential construction.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Differences
Rope: Represents text as a balanced tree of character chunks or leaves. Operations can avoid copying unaffected portions of the text, and persistent implementations can share unchanged chunks between versions.
StringBuilder: Stores characters in a contiguous, growable buffer. It supports efficient appending and can be converted to an immutable string once construction is complete.
Typical StringBuilder implementation: Java’s StringBuilder and .NET’s StringBuilder are mutable and are not intended for concurrent mutation without external synchronization.
Python consideration: Python strings are immutable and there is no built-in StringBuilder equivalent. For repeated construction, collect pieces in a list and use ''.join(parts).
Complexity Comparison
The table assumes n total characters involved, m characters added, and k characters copied into a result. Rope bounds assume a balanced persistent tree with O(log n) height and bounded-size leaf chunks. Unless otherwise stated, best, average, and worst cases have the same bound under these assumptions.
Operation
StringBuilder
Rope
Append one constant-size unit
Best O(1), average O(1) amortized, worst O(n) during buffer growth
O(log n) to update the tree
Append an m-character chunk
Best O(m), average O(m) amortized, worst O(n + m)
O(m + log n) to copy the chunk and update the tree
Concatenate two texts
O(n) because the characters are copied into a contiguous result
O(log n) to join or rebalance tree pieces
Random character access
O(1)
O(log n)
Insert m characters in the middle
O(n) because existing characters are shifted
O(log n + m)
Delete a range
O(n) because remaining characters are shifted
O(log n) when deleted content is not copied
Create a substring
O(k) because the result is copied
O(log n) for a view; O(log n + k) when materialized
Flatten to one string
O(n)
O(n) to traverse and copy the leaves
StringBuilder appends are amortized O(1) for constant-size units: occasional buffer growth copies the buffer, but that cost is spread across many appends. Copying a longer chunk still costs at least O(m).
Space and Memory Behavior
StringBuilder: Uses O(n) buffer capacity, excluding the immutable final result, which may require another O(n) space.
Rope: Uses O(n) character storage plus O(r) metadata, where r is the number of tree nodes; r is O(n) in the worst case when leaves contain only a few characters.
Persistent edits: A small persistent edit typically adds O(log n) tree nodes plus the inserted characters because unchanged subtrees are shared.
Input counting: The original input text is excluded from additional-space figures. Materializing the final contiguous string adds O(n) output space.
Cache locality: A StringBuilder’s contiguous buffer generally has better cache locality than a rope’s tree of chunks.
When to Use Each
Use a StringBuilder when:
Characters or pieces are added mostly from left to right.
The final text is produced once and then read frequently.
Random access or tight memory overhead matters.
The algorithm does not perform repeated middle insertions or deletions.
Use a rope when:
Text is assembled from many large pieces.
Substrings, insertions, deletions, or concatenation occur repeatedly.
A persistent implementation can share unchanged text rather than copying it.
The text is eventually flattened or traversed as a whole.
For example, building a report from many independent sections may benefit from a rope if sections are repeatedly rearranged. Building the same report once from small append operations is usually simpler and faster with a StringBuilder.
Common Pitfalls
Assuming every rope has O(1) concatenation: The bound depends on tree height, balancing, and implementation.
Ignoring copied chunk lengths: Appending m characters costs at least O(m) even when the structure provides amortized constant-time appends for single units.
Ignoring flattening cost: A rope can delay copying, but producing the final contiguous string still takes O(n).
Choosing a rope for simple append-only work: Tree overhead may outweigh the benefits when edits are rare.
Confusing characters and bytes: Complexities usually count characters or bytes consistently; UTF-8 storage size may differ from the number of Unicode code points.
Mutating input unexpectedly: StringBuilder operations modify the builder. If multiple versions are needed, copy or preserve the original text deliberately.
Forgetting thread safety: A mutable StringBuilder is generally not safe for unsynchronized concurrent modification.
15
How do Strings and Ropes differ in performance?
KnownRevise
Strings are typically flat, immutable sequences, whereas ropes represent text as a balanced tree of chunks. Strings provide fast indexed access, while ropes make repeated structural operations such as concatenation, insertion, and splitting much more efficient.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Representation
A conventional string stores its native units in one contiguous allocation. It is simple and cache-friendly, but modifying it creates a new value.
A rope represents text hierarchically:
Leaves contain chunks of text.
Internal nodes combine or describe child chunks.
Metadata such as subtree length and sometimes cached hashes is stored at nodes.
Persistent implementations can share unchanged subtrees between versions.
Ropes are not a standard Python feature. Some text editors and JavaScript engines use similar tree-based techniques internally.
Performance Comparison
Let n and m be the input lengths and k the substring length. The bounds below assume a height-balanced rope. Unless noted, the time bounds are the same in the best, average, and worst cases.
Operation
Flat immutable string
Balanced rope
Read one indexed unit
Θ(1) time, Θ(1) auxiliary space
Θ(log n) time, Θ(1) auxiliary space
Get length
Θ(1) time and space
Θ(1) time and space when lengths are cached
Concatenate
Θ(n + m) time and Θ(n + m) new output space
Θ(log(n + m)) time and new-node space
Create substring
Θ(k) time and Θ(k) output space for a copying API
Θ(log n) time and space for a lazy view; Θ(log n + k) to materialize
Insert or remove
Θ(n) time and new output space
Θ(log n) time and new-node space
Traverse all units
Θ(n) time, Θ(1) auxiliary space
Θ(n) time, Θ(log n) traversal-stack space with depth-first traversal
Flatten
Already flat
Θ(n) time, Θ(n) output space, plus Θ(log n) traversal stack
Comparing two sequences takes up to Θ(n) time in the worst case without memoized subtree comparisons; unequal lengths or an early mismatch can finish in Θ(1). Equality can be O(1) in the best case when both references identify the same object, and a rope can shortcut identical shared subtrees.
Computing an uncached content hash takes Θ(n) time. A rope can cache hashes at nodes, making subsequent root-hash retrieval O(1); caching a hash at every node requires Θ(n) additional storage.
These space bounds count newly created output and auxiliary storage but not the original input unless it is replaced.
When Ropes Perform Better
Ropes are useful for large documents that are repeatedly edited or combined:
Concatenation creates a small tree of nodes instead of copying all characters.
Insertion and deletion update only a path through the tree.
Splitting can create views that share existing chunks.
Persistent versions can share almost all their storage, supporting undo, history, and collaborative editing.
These logarithmic bounds require balanced trees. An unbalanced rope can degrade toward linear-time access or editing.
Python 3.12 Behavior
Python’s str is immutable and represents a sequence of Unicode code points. Compact internal representations allow one, two, or four bytes per code point depending on the characters, but len counts code points rather than bytes or grapheme clusters.
Python slicing creates a copy, so text[start:end] takes Θ(k) time and output space. Repeated immutable concatenation can take Θ(n²) total time in implementations that copy the growing result on every update; CPython can optimize some local += patterns, but applications should not depend on that optimization.
For predictable linear behavior, collect fragments in a list and join them once. Joining fragments with total length L takes Θ(L) time and Θ(L) output space. Python provides no built-in rope.
Advantages and Trade-offs
Strings: constant-time indexed access, simple APIs, good cache locality, and straightforward comparison and hashing.
Ropes: efficient concatenation, splitting, persistent editing, and structural sharing, at the cost of slower random access and greater implementation complexity.
Use ordinary strings for typical application text with infrequent edits. Ropes are advantageous for large, frequently edited, or versioned documents.
Common Pitfalls
Do not assume rope indexing is constant time.
Do not treat rope concatenation as allocation-free; creating balanced nodes still costs Θ(log n) time and space.
Include materialized output and recursion or traversal-stack space in complexity claims.
Distinguish bytes, Unicode code points, and user-perceived grapheme clusters.
Do not assume Python provides a built-in rope.
A common follow-up asks why repeated immutable concatenation can become Θ(n²): each update may copy the growing result, whereas a rope shares existing chunks.
16
How does Boyer-Moore string search work?
KnownRevise
Boyer–Moore is a string-search algorithm that compares characters from right to left and skips alignments that cannot produce a match. The complete algorithm combines a bad-character rule with a good-suffix rule to achieve linear worst-case search time.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
Given text and pattern, the algorithm keeps a possible starting position in the text called an alignment.
Compare the pattern’s last character with the corresponding text character.
Continue comparing leftward while the characters match.
On a mismatch, use the bad character to calculate a safe positive shift.
Move the alignment by that amount and repeat.
Return the alignment when every pattern character matches.
For the bad-character rule, let the mismatch occur at pattern index j and the unmatched text character be c:
If c previously appeared at pattern index i < j, shift by j - i. This aligns the earlier c with the unmatched text character.
Otherwise, shift by j + 1.
The full Boyer–Moore algorithm adds a good-suffix rule. When a suffix of the pattern has already matched, it uses the pattern’s borders or overlaps to shift without unnecessarily repeating comparisons.
Example Walkthrough
For text = "ABABC" and pattern = "ABC":
Alignment
Right-to-left comparison
Action
0
C versus B
Mismatch at pattern index 2; shift by 1
1
C versus B
Mismatch at pattern index 2; shift by 1
2
C = C, B = B, A = A
Match found at index 2
Code Example
This implementation demonstrates the core bad-character-only Boyer–Moore variant. It returns the first match or -1 if none exists.
from bisect import bisect_left
from collections import defaultdict
def boyer_moore_search(text: str, pattern: str) -> int:
"""Return the first index of pattern in text, or -1 if absent."""
text_length = len(text)
pattern_length = len(pattern)
if pattern_length == 0:
return 0
if pattern_length > text_length:
return -1
occurrences: defaultdict[str, list[int]] = defaultdict(list)
for index, character in enumerate(pattern):
occurrences[character].append(index)
alignment = 0
while alignment <= text_length - pattern_length:
mismatch_index = pattern_length - 1
# Compare from right to left.
while (
mismatch_index >= 0
and text[alignment + mismatch_index] == pattern[mismatch_index]
):
mismatch_index -= 1
if mismatch_index < 0:
return alignment
bad_character = text[alignment + mismatch_index]
positions = occurrences.get(bad_character, [])
# Find the closest occurrence strictly before mismatch_index.
insertion_point = bisect_left(positions, mismatch_index)
if insertion_point > 0:
previous_position = positions[insertion_point - 1]
shift = mismatch_index - previous_position
else:
shift = mismatch_index + 1
alignment += shift
return -1
print(boyer_moore_search("ABABC", "ABC")) # 2
Complexity
Let n be the text length, m the pattern length, and σ the alphabet size.
Approach
Best
Average
Worst
Auxiliary Space
Bad-character-only code
O(m)
O(n) on typical inputs
O(nm)
O(m)
Full Boyer–Moore
O(m)
O(n) overall
O(n+m)
O(m + σ)
Best case, O(m): all pattern characters match at the first alignment.
Bad-character worst case, O(nm): alignments may advance by one while many characters are compared.
Full worst case, O(n + m): adding the good-suffix rule prevents repeated quadratic work.
The code stores one occurrence-list entry per pattern position, so it uses O(m) auxiliary space, excluding the input strings.
The implementation is iterative and uses no recursion stack.
Preprocessing takes O(m) expected time because it uses a hash-based dictionary.
Edge Cases
Empty pattern: the function returns 0, following the common convention that it matches at the beginning.
Empty text: a nonempty pattern returns -1.
Single-character input: a matching one-character pattern returns 0; otherwise, the result is -1.
Pattern longer than text: returns -1 immediately.
Duplicate characters: handled through sorted occurrence lists.
Unicode: Python str characters are Unicode code points; len counts code points, not encoded bytes.
No match: the alignment eventually moves beyond the final valid starting position.
Common Pitfalls
Comparing left to right eliminates most of Boyer–Moore’s skipping advantage.
Confusing the previous occurrence with the next occurrence produces invalid shifts.
Claiming that the bad-character-only implementation has O(n) worst-case time; only the full algorithm with the good-suffix rule has a linear worst-case guarantee.
Forgetting the empty-pattern and pattern-longer-than-text cases.
Interviewers commonly follow up by asking how the good-suffix rule works, why the shifts are safe, and how Boyer–Moore compares with KMP.
17
How do Knuth-Morris-Pratt, Boyer-Moore, and Rabin-Karp string search compare?
KnownRevise
Knuth-Morris-Pratt (KMP) guarantees linear-time matching, Boyer-Moore can be very fast in practice because it skips positions, and Rabin-Karp compares rolling hashes. Their trade-offs involve preprocessing, worst-case behavior, probabilistic guarantees, and use of extra space.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Ideas
KMP: Preprocesses the pattern into a prefix-function table. On a mismatch, it uses that table to determine how much of the already matched prefix can be reused without moving backward.
Boyer-Moore: Aligns the pattern with the text and compares characters from the pattern’s end. A mismatch allows it to skip several text positions using bad-character and good-suffix rules.
Rabin-Karp: Assigns numeric hashes to the pattern and each text window. A rolling hash updates the current window’s hash in constant time, so most comparisons require only hash-equality checks.
Naive search: Restarts after every mismatch. It is simple but can repeatedly compare the same characters.
Complexity Comparison
Let n be the text length, m the pattern length, and Σ the alphabet size. Extra space excludes the input strings; standard iterative implementations use constant recursion-stack space.
Algorithm
Preprocessing
Best Time
Average Time
Worst Time
Extra Space
Naive
O(1)
O(m)
O(nm)
O(nm)
O(1)
KMP
O(m)
O(n+m)
O(n+m)
O(n+m)
O(m)
Boyer-Moore
O(m +
Σ
)
O(n)
Typically O(m + n/m)
O(nm)
O(m +
Σ
)
Rabin-Karp
O(m)
O(n+m)
Expected O(n+m)
O(nm)
O(1) with a rolling hash
KMP is deterministically linear because the text pointer never moves backward.
Boyer-Moore commonly performs around O(n/m) character comparisons, although preprocessing costs O(m). Its bad-character and good-suffix shifts do not guarantee linear worst-case time without an additional rule such as Galil’s rule.
Rabin-Karp is expected linear when suitable randomized hashing makes collisions sufficiently rare. With a fixed hash, linear time is not guaranteed; if every window collides and every candidate is verified character by character, its worst case becomes O(nm).
Hash arithmetic is conventionally treated as constant time. Very large arbitrary-precision integers can introduce bit-complexity considerations.
When to Use Each Algorithm
KMP: Choose it when deterministic worst-case linear time is important or when the pattern is searched repeatedly in long texts.
Boyer-Moore: Choose it for typical single-pattern searches where practical speed matters more than a deterministic linear-time guarantee.
Rabin-Karp: Choose it for exact matching when a rolling-hash implementation and expected linear behavior are suitable. For many static patterns, Aho-Corasick is usually preferable, although a set of pattern hashes can support a smaller multiple-pattern workload.
Naive search: Use it only for very short patterns, small inputs, or educational purposes.
Approximate matching: Use a specialized fuzzy-matching algorithm or an explicitly modified Rabin-Karp variant; ordinary Rabin-Karp only detects exact matches.
Small KMP Walkthrough
For pattern ABAB, the prefix function is:
Index
Character
Prefix-function value
0
A
0
1
B
0
2
A
1
3
B
2
When scanning ABABABC:
A matches, so the matched-prefix length becomes 1.
B matches, making it 2.
A matches, making it 3.
B matches, making it 4; the complete pattern is found at index 3.
The prefix table allows KMP to recover efficiently after later mismatches.
Common Pitfalls
Empty pattern: Define its behavior explicitly—many implementations return 0 immediately.
Pattern longer than text: Return no match without attempting unnecessary comparisons.
Off-by-one errors: Carefully track whether match positions are zero-based or one-based.
Hash collisions: Rabin-Karp should verify hash matches before accepting them; otherwise it can report false positives.
Unicode versus bytes: Python’s len counts Unicode code points, while encoded byte searches operate on bytes. State the representation being searched.
Case sensitivity: Normalize the strings or specify a case-insensitive comparison policy before searching.
Preprocessing cost: For repeated searches of the same pattern, KMP or Boyer-Moore preprocessing is amortized by reusing the pattern tables.
18
How do you implement pattern searching with the Z-algorithm?
KnownRevise
The Z-algorithm finds every occurrence of a pattern in linear time by computing how many characters match at each position. For pattern searching, the pattern and text are combined with a unique separator, and matching Z-values identify the pattern’s starting positions.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
For a sequence s, the Z-array stores z[i], the length of the longest common prefix between s and the suffix beginning at i.
For example, given s = "ABABAB":
z[0] = 0 by convention.
z[2] = 4 because "ABAB" matches the first four characters.
z[1] = 0 because the suffix "BABAB" starts with a different character.
To search for a pattern, the implementation constructs:
pattern + unique_separator + text
If the pattern has length m, a Z-value of m at a position in the text means a complete match occurs there. Python’s None is used as the separator because it cannot equal any character in a str.
The algorithm maintains a matching interval [left, right). When a position lies inside that interval, its previously calculated Z-value provides an initial comparison length, avoiding repeated character comparisons.
Complexity
Let n be the text length and m the pattern length.
Approach
Best time
Average time
Worst time
Auxiliary space
When to use
Brute-force comparison
O(n)
O(n) for random inputs
O(nm)
O(1)
Very short patterns or simple implementations
Z-algorithm
O(n + m)
O(n + m)
O(n + m)
O(n + m)
Guaranteed linear-time pattern searching
Time: O(n + m) in all cases for the Z-algorithm. The right boundary advances at most n + m times, while failed comparisons add only linear overhead.
Space: O(n + m) auxiliary space for the combined sequence and Z-array, excluding the returned matches. The input itself is not counted, although the algorithm internally copies its characters into a combined sequence.
Recursion stack: None; the implementation is iterative.
Output space: O(k), where k is the number of matches. Since k ≤ n + 1, total additional space remains O(n + m).
Empty pattern: Returns all n + 1 boundary positions in O(n) time, using the convention that an empty pattern matches at every boundary.
Pattern longer than the text: Returns an empty list in O(1) time.
Example Walkthrough
For text = "ABABAB" and pattern = "ABAB", the combined sequence is conceptually:
ABAB#ABABAB
The text starts at index 5.
Text start
Text suffix
Matching prefix length
Match
0
ABABAB
4
Yes
1
BABAB
0
No
2
ABAB
4
Yes
3
BAB
0
No
4
AB
0
No
The returned starting indices are [0, 2].
Code Example
from collections.abc import Sequence
def _z_array(sequence: Sequence[object]) -> list[int]:
"""Return the Z-value for every position in the sequence."""
length = len(sequence)
z_values = [0] * length
left = right = 0 # Current matching interval is [left, right)
for index in range(1, length):
if index < right:
mirrored_index = index - left
z_values[index] = min(
right - index,
z_values[mirrored_index],
)
while (
index + z_values[index] < length
and sequence[z_values[index]]
== sequence[index + z_values[index]]
):
z_values[index] += 1
if index + z_values[index] > right:
left = index
right = index + z_values[index]
return z_values
def z_pattern_search(text: str, pattern: str) -> list[int]:
"""Return every starting index where pattern occurs in text."""
if not pattern:
return list(range(len(text) + 1))
if len(pattern) > len(text):
return []
# None is a separator that cannot occur inside a Python string.
sequence: list[object] = [*pattern, None, *text]
z_values = _z_array(sequence)
text_start = len(pattern) + 1
pattern_length = len(pattern)
return [
index - text_start
for index in range(text_start, len(sequence))
if z_values[index] == pattern_length
]
print(z_pattern_search("ABABAB", "ABAB")) # [0, 2]
Common Pitfalls
Off-by-one errors: Treat right as an exclusive boundary and subtract the text offset from each global match position.
Separator collisions: A textual separator can occur inside the input. None avoids this problem entirely.
Overlapping matches: Do not advance past a match by the pattern length. The implementation correctly reports overlapping occurrences.
Unicode assumptions: Python str indexing operates on Unicode code points, so len counts code points rather than encoded bytes.
Unnecessary input mutation: The algorithm does not modify either string.
Common follow-up questions: Interviewers may ask how Z-algorithm differs from KMP, how to search for multiple patterns, or how the algorithm would be adapted to a streaming input.
19
How does the BNDM algorithm work for string matching?
KnownRevise
BNDM (Backward Nondeterministic DAWG Matching, Navarro and Raffinot) finds a pattern of length m by reading each text window from right to left and tracking, in one bit mask, every position where the characters read so far appear as a substring of the pattern. When that set becomes empty it skips ahead, often by almost m characters, so on typical text it reads only a fraction of the input. It combines Boyer-Moore-style backward scanning with bit-parallel simulation of a suffix automaton, and is fast for short patterns that fit in a machine word.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Preprocessing
For each character c, build a mask B[c] with bit m - 1 - i set when pattern[i] == c. Pattern "abab" gives:
Character
Positions in pattern
B[c]
a
0, 2
1010
b
1, 3
0101
anything else
none
0000
This costs O(m + σ) time and O(σ) space, where σ is the alphabet size (only characters in the pattern need entries if you use a dictionary).
Searching a Window
For the window starting at pos:
Set state to all ones (every pattern position is still possible) and j = m.
Read text[pos + j - 1], the next character from the right, and set state &= B[c].
Decrement j. If the top bit of state is set, the characters read so far are a prefix of the pattern. If j > 0, remember last = j, the safe shift. If j == 0, the whole window equals the pattern: report a match.
Shift state left by one (masked to m bits) and repeat while state is non-zero.
Move the window by last. The shift is safe because any earlier start would need a pattern prefix that the scan did not see.
Code Example
def bndm_search(text: str, pattern: str) -> list[int]:
"""Return every start index of pattern in text using BNDM."""
m = len(pattern)
n = len(text)
if m == 0:
return list(range(n + 1))
masks: dict[str, int] = {}
for i, character in enumerate(pattern):
masks[character] = masks.get(character, 0) | (1 << (m - 1 - i))
full = (1 << m) - 1
high_bit = 1 << (m - 1)
matches: list[int] = []
pos = 0
while pos <= n - m:
j = m
last = m
state = full
while state:
state &= masks.get(text[pos + j - 1], 0)
j -= 1
if state & high_bit:
if j > 0:
last = j
else:
matches.append(pos)
break
state = (state << 1) & full
pos += last
return matches
print(bndm_search("abcabab", "abab")) # [3]
print(bndm_search("aaaa", "aa")) # [0, 1, 2]
Walkthrough
Text "abcabab", pattern "abab" (m = 4):
Window pos
j after read
Character
state
Note
0
3
a
1010
top bit set: a is a prefix, last = 3
0
2
c
0000
c is not in the pattern, stop
shift by 3
3
3
b
0101
3
2
a
1010
prefix ab seen, last = 2
3
1
b
0100
3
0
a
1000
j == 0 with top bit: match at 3
Complexity
Algorithm
Preprocessing
Search best
Search average
Search worst
Extra space
Naive
none
O(n)
O(n)
O(n·m)
O(1)
KMP
O(m)
O(n)
O(n)
O(n)
O(m)
Boyer-Moore-Horspool
O(m + σ)
O(n/m)
about O(n/m)
O(n·m)
O(σ)
BNDM
O(m + σ)
O(n/m)
O(n·log_σ(m) / m)
O(n·m)
O(σ)
These figures assume m is at most the word size w (64), so each mask operation is O(1). For longer patterns each operation costs O(m/w); Python’s unbounded integers hide this but do not remove it. The output list is O(occ) extra. The best case occurs when the last character of each window is absent from the pattern, so each window costs one read and shifts by m. The worst case, such as text "aaaa…" and pattern "aa…a", reads every window fully. The search is iterative, so there is no recursion stack.
Interview Tips
Explain the meaning of state: bit k set means “the characters read so far from the right occur in the pattern at one specific position”. That one sentence shows you understand the bit-parallel trick.
Compare with Shift-Or, which scans forward with the same kind of masks but never skips characters.
Mention when not to use it: patterns much longer than a machine word lose the bit-parallel advantage, and for everyday code the library’s str.find (a tuned Horspool-style search that switches to the two-way algorithm for long patterns) is the better choice.
Pitfalls to avoid: forgetting to mask the shift to m bits, using the wrong bit order in B[c], and forgetting overlapping matches ("aa" in "aaaa" has three).
20
How to check balanced parentheses in linear time and constant space?
KnownRevise
A string has balanced parentheses when every closing parenthesis ) has a preceding unmatched opening parenthesis (, and no opening parentheses remain unmatched. For strings containing only these two characters, a single counter is sufficient, giving O(n) time and O(1) auxiliary space.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
Maintain an open_count counter:
Opening parenthesis (: increment open_count.
Closing parenthesis ): decrement open_count.
If open_count becomes negative, return False immediately because a closing parenthesis appeared without a matching opening one.
After scanning the string, return open_count == 0.
The implementation ignores non-parenthesis characters and checks only the parentheses they contain.
Example Walkthrough
For the string "(()":
Step
Character
open_count
Result
1
(
1
Continue
2
(
2
Continue
3
)
1
Continue
The final count is 1, so the string is not balanced.
Complexity
Let n be the number of characters in the input.
Case
Time
Reason
Best
O(n)
The scan still examines every character in the worst-case input shape
Average
O(n)
Each character is processed once
Worst
O(n)
Each character is processed once
Auxiliary space: O(1), because only one integer counter is used.
The input string is not copied or modified, so the input itself is not counted as auxiliary space.
There is no recursion stack.
Code Example
def is_balanced_parentheses(text: str) -> bool:
"""Check whether the parentheses in text are balanced."""
open_count = 0
for character in text:
if character == "(":
open_count += 1
elif character == ")":
open_count -= 1
if open_count < 0:
return False
return open_count == 0
print(is_balanced_parentheses("(()())")) # True
Common Pitfalls
Checking only at the end: "())" has a final count of 0, but it is invalid because the second ) appears too early. The negative-count check must happen during the scan.
Empty input: By the standard convention, an empty string is balanced, so the function returns True.
Single parentheses: Both "(" and ")" are unbalanced.
Multiple bracket types: A counter works for only ( and ). Mixed types such as (), [], and {} require a stack, which uses O(n) space in the worst case.
Unexpected characters: This implementation ignores them. If only ( and ) are valid input, validate that requirement separately.
21
How do you remove the fewest parentheses to balance a string?
KnownRevise
Minimum-parentheses removal produces a valid balanced string by deleting the minimum number of parentheses while preserving the order of all remaining characters. The greedy approach removes unmatched closing parentheses from left to right, then unmatched opening parentheses from right to left.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Idea
A parentheses string is valid when:
The number of ( equals the number of ).
In every prefix, the number of ( is at least the number of ).
Use two directional scans:
Scan from left to right, matching each ) with an available earlier (.
If a ) has no available (, mark it for removal.
Scan the remaining characters from right to left, matching each ( with an available later ).
If an ( has no available ), mark it for removal.
This greedy matching maximizes the number of matched pairs, so the number of deleted parentheses is minimal.
Let n be the input length and p the number of parentheses:
Approach
Time
Space
When to use
Brute force: try every subset of parentheses
O(n · 2^p)
O(n) working space
Tiny inputs or generating candidates one at a time
Greedy two-pass matching
O(n)
O(n) auxiliary space
Producing one minimum-removal result efficiently
The brute-force working-space figure excludes the input and any candidates retained by the caller.
Example Walkthrough
For ())(():
Step
Action
Result
1
Scan left to right
The first ) matches the first (
2
The next ) has no available (
Mark it for removal
3
Scan the remaining string from right to left
The final ) matches the preceding (
4
The remaining earlier ( has no available closing parenthesis remaining to its right
Mark it for removal
5
Join the unmarked characters
()()
Two parentheses were removed, which is minimal.
Complexity
Let n be the length of the input string.
Case
Time
Space
Best
O(n)
O(n) auxiliary
Average
O(n)
O(n) auxiliary
Worst
O(n)
O(n) auxiliary
The algorithm performs two linear scans and one final join. Auxiliary space is O(n) because it stores removal flags and constructs the result; the input string itself is not counted. Including the returned string, total space remains O(n). There is no recursion stack.
Code Example
def remove_min_parentheses(text: str) -> tuple[str, int]:
"""Remove the fewest parentheses needed to make the parentheses balanced."""
remove = [False] * len(text)
# Match closing parentheses with opening parentheses to their left.
available_opens = 0
for index, character in enumerate(text):
if character == "(":
available_opens += 1
elif character == ")":
if available_opens == 0:
remove[index] = True
else:
available_opens -= 1
# Match opening parentheses with closing parentheses to their right.
available_closes = 0
for index in range(len(text) - 1, -1, -1):
if remove[index]:
continue
character = text[index]
if character == ")":
available_closes += 1
elif character == "(":
if available_closes == 0:
remove[index] = True
else:
available_closes -= 1
result = "".join(
character
for index, character in enumerate(text)
if not remove[index]
)
return result, sum(remove)
balanced, removed = remove_min_parentheses("())(()")
print(balanced) # Expected: ()()
print(removed) # Expected: 2
The function preserves non-parenthesis characters and uses ''.join(...) rather than repeatedly concatenating strings with +=, which could become quadratic.
Common Pitfalls
Empty input: Returns ("", 0).
One element: Removes the unmatched parenthesis, if applicable.
Only opening parentheses: Removes all of them.
Only closing parentheses: Removes all of them.
Already balanced input: Returns the original string with 0 removals.
Duplicate or repeated parentheses: Handles them through the same matching process.
Negative or unrelated characters: Treats them as ordinary characters; only parentheses affect validity.
Unicode: Python indexes and len() count Unicode code points, while only the ASCII characters ( and ) are treated as parentheses.
Common mistake: Removing parentheses without preserving their original order can produce a different result; always retain the unmarked characters in sequence.
Common follow-up: Ask how to return all distinct valid strings, which typically requires backtracking rather than this greedy solution.
22
How do you reverse a string using a stack?
KnownRevise
A stack reverses a string by pushing each character onto the stack and then popping characters in last-in, first-out (LIFO) order. Because each popped character is the last one pushed, the resulting sequence is the reverse of the original string.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
Create an empty stack.
Push characters from left to right into the stack.
Pop characters from the stack one at a time.
Join the popped characters into a new string.
For "hello":
Operation
Stack after operation
Output so far
Push h
h
—
Push e
h, e
—
Push l
h, e, l
—
Push l
h, e, l, l
—
Push o
h, e, l, l, o
—
Pop o
h, e, l, l
o
Pop l
h, e, l
ol
Pop l
h, e
oll
Pop e
h
olle
Pop h
empty
olleh
In Python, strings are immutable, so the implementation uses a list as the stack and joins the popped characters at the end. Python string indexing and len() count Unicode code points, so this reverses code points rather than user-perceived grapheme clusters such as an emoji with multiple code points.
Complexity
Let n be the number of characters in the input string.
Time:O(n) — every character is pushed once and popped once.
Space:O(n) — the stack and the output list each store up to n characters. The input string is not counted as additional space.
Code Example
class CharacterStack:
"""A LIFO stack for storing individual characters."""
def __init__(self) -> None:
self._items: list[str] = []
def push(self, character: str) -> None:
"""Add a character to the top of the stack."""
self._items.append(character)
def pop(self) -> str:
"""Remove and return the top character."""
if not self._items:
raise IndexError("pop from empty stack")
return self._items.pop()
def is_empty(self) -> bool:
"""Return whether the stack contains no characters."""
return not self._items
def reverse_string(text: str) -> str:
"""Return the characters of text in reverse order using a stack."""
stack = CharacterStack()
for character in text:
stack.push(character)
reversed_characters: list[str] = []
while not stack.is_empty():
reversed_characters.append(stack.pop())
return "".join(reversed_characters)
print(reverse_string("hello")) # olleh
Common Pitfalls
Using += in a loop: Repeatedly appending to an immutable Python string can lead to O(n²) behavior. Use a list and ''.join(...) instead.
Using pop(0): Removing the first element from a list is O(n) because the remaining elements must shift. Pop from the end instead.
Assuming bytes and characters are identical: In Python, bytes stores byte values, while str stores Unicode code points. The code above reverses str characters.
Forgetting empty input: The implementation handles "" by returning an empty string. One-character strings, duplicates, and whitespace are preserved in reversed order.
Unicode display concerns: Reversing code points may not always reverse a user-perceived grapheme cluster. Applications that require grapheme-aware reversal need a Unicode grapheme-segmentation library.
23
How do you solve the String Compression problem?
KnownRevise
Run-length encoding compresses consecutive equal characters by replacing each run with the character followed by its count. For example, "aaabccddd" becomes "a3b1c2d3".
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Approach
Scan the string once while tracking:
run_char: The character currently being counted.
run_length: How many times it has appeared consecutively.
parts: Compressed fragments stored for a final join.
When the next character differs from run_char, append the completed run and start a new one. This compresses only consecutive repetitions, not every occurrence of a character across the entire string.
Complexity
Let n be the number of Unicode code points in the input.
Case
Time
Space
Best
O(n)
O(n)
Average
O(n)
O(n)
Worst
O(n)
O(n)
Time: Every character is visited once, and constructing the output is linear in its size.
Space: O(n) additional space for the fragment list and returned string. The input is not counted, and there is no recursion stack.
Empty input: Returns in O(1) time and uses O(1) space.
One-character input: Returns the character followed by 1, such as "a1".
Duplicates: Consecutive duplicates form one run, while nonconsecutive occurrences belong to separate runs.
Walkthrough
For "aaabccddd":
Read three a characters and append "a3".
Read one b character and append "b1".
Read two c characters and append "c2".
Read three d characters and append "d3".
Join the fragments into "a3b1c2d3".
Code Example
def compress_string(text: str) -> str:
"""Compress consecutive character runs as character plus count."""
if not text:
return ""
parts: list[str] = []
run_char = text[0]
run_length = 1
for index in range(1, len(text)):
char = text[index]
if char == run_char:
run_length += 1
else:
parts.append(f"{run_char}{run_length}")
run_char = char
run_length = 1
# Include the final run.
parts.append(f"{run_char}{run_length}")
return "".join(parts)
print(compress_string("aaabccddd")) # a3b1c2d3
Best Practices
Use join(): Build fragments in a list and join them once. Repeatedly using result += fragment in a loop can become O(n²).
Consider Unicode: Python strings represent Unicode code points, so len(text) counts code points, not encoded bytes or user-perceived characters.
Check whether compression helps: Run-length encoding can make short or nonrepetitive strings longer; omit counts of 1 if the goal is to minimize output size.
Common Pitfalls
Off-by-one errors: The final run must be appended after the loop.
Quadratic string building: Appending to an immutable string in a loop may repeatedly copy the accumulated result.
Incorrect grouping: The algorithm compresses consecutive runs, not all occurrences of a character.
Mutating the input: Strings are immutable; a non-mutating implementation avoids unnecessary copies.
Ambiguous output: Formats such as "a1112" can be difficult to decode when original characters are digits. If decoding is required, define separators or another unambiguous encoding.
Interviewers may follow up by asking for a decoder, an “original length versus compressed length” comparison, or a variant that only emits a count when it saves space.
24
How do I find the longest palindromic substring in Python 3.12?
KnownRevise
The longest palindromic substring is the longest contiguous sequence of characters that reads identically forward and backward. Manacher’s algorithm finds it in linear time by reusing previously computed palindrome radii instead of expanding independently around every possible center.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Approach
Manacher’s algorithm transforms the string so that odd- and even-length palindromes both have a single-character center:
text = "abba" becomes #a#b#b#a#.
radius[center] records the maximum palindrome radius around that position.
center and right track the palindrome whose right boundary currently reaches farthest.
If the current position is inside that palindrome, its mirrored position provides an initial radius.
Expansion continues only as needed to determine the exact radius.
The separator is represented by None, so it cannot accidentally match a character in the input.
Approach
Time
Auxiliary space
When to use
Check every substring
O(n³)
O(1)
Educational or very short strings
Expand around every center
O(n²)
O(1)
Simple implementation with modest input sizes
Manacher’s algorithm
O(n)
O(n)
Large inputs or interview optimization
Why It Works
Every palindrome has a center, whether its length is odd or even. The separator transformation represents both cases uniformly.
When a position lies inside the known palindrome, symmetry guarantees that its initial radius is at least the mirrored radius. If that radius reaches the known boundary, further expansion is required to find the exact maximum. Expanding from that point therefore computes the correct radius for every center.
The transformed radius of the largest palindrome equals the number of original characters in that palindrome, so the maximum radius identifies the answer.
Complexity
For a string of length n:
Best-case time: O(n). The transformed array, radius array, and initial setup require linear work.
Average-case time: O(n). Successful expansions extend the known boundary, which can happen only O(n) times overall.
Worst-case time: O(n). Repeated characters do not make the algorithm quadratic because mirrored information is reused.
Auxiliary space: O(n) for the transformed sequence and radius array, excluding the input and returned substring.
Output space: O(k), where k is the answer’s length.
Total space including input and output: O(n).
Recursion stack: O(1), because the implementation is iterative.
Code Example
def longest_palindromic_substring(text: str) -> str:
"""Return the longest contiguous palindromic substring of text."""
if not text:
return ""
# Separators make odd- and even-length palindromes use one center model.
transformed: list[str | None] = [None] * (2 * len(text) + 1)
transformed[1::2] = text
radii = [0] * len(transformed)
center = 0
right = 0
best_center = 0
best_radius = 0
for position in range(len(transformed)):
if position < right:
mirror = 2 * center - position
radii[position] = min(right - position, radii[mirror])
# Expand beyond the mirrored or initially known radius.
while (
position - radii[position] - 1 >= 0
and position + radii[position] + 1 < len(transformed)
and transformed[position - radii[position] - 1]
== transformed[position + radii[position] + 1]
):
radii[position] += 1
if position + radii[position] > right:
center = position
right = position + radii[position]
if radii[position] > best_radius:
best_center = position
best_radius = radii[position]
start = (best_center - best_radius) // 2
return text[start:start + best_radius]
print(longest_palindromic_substring("abba")) # "abba"
Walkthrough and Edge Cases
For "abba":
The transformed sequence is #a#b#b#a#.
At the separator between the two b characters, the radius expands through matching b, #, a, and # pairs.
The maximum radius is 4, corresponding to four original characters.
The start index is (4 - 4) // 2 = 0, so the result is "abba".
Relevant edge cases:
Empty input: Returns "".
One character: Returns that character.
Duplicate characters: Handled normally; for example, "aaaa" returns "aaaa".
Multiple answers: Returns the first maximum encountered because the implementation updates only for a strictly larger radius.
Unicode: Python str indexes Unicode code points, so palindrome comparisons use code points rather than bytes or user-perceived grapheme clusters.
Negative numbers, sorted input, disconnected graphs, and cycles are not applicable to this substring problem.
Common Pitfalls
Off-by-one errors: Carefully distinguish the transformed radius, original start index, and original substring length.
Character versus byte confusion:len(text) counts Unicode code points for str; bytes instead counts bytes.
Repeated concatenation: Avoid building large strings with += inside loops because Python strings are immutable. Use ''.join(parts) when multiple pieces must be combined.
Slicing cost: Python slicing creates a new string and costs O(k) time and space.
Unnecessary mutation: The algorithm does not modify the input.
Common follow-up: Distinguish a palindromic substring, which must be contiguous, from a palindromic subsequence, which may skip characters.
25
How to verify if a string reads the same forward and backward?
KnownRevise
A palindrome reads the same forward and backward. Verify one by comparing characters at symmetric positions with two pointers, stopping immediately at the first mismatch.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
Initialize pointers: Set left to 0 and right to len(text) - 1.
Compare symmetric positions: Compare text[left] with text[right].
Stop on a mismatch: If they differ, the string is not a palindrome.
Move inward: Otherwise, increment left and decrement right.
Finish: If left >= right, every symmetric pair matched, so the string is a palindrome.
This approach does not create a reversed copy and does not mutate the input.
Time and Space Complexity
Best-case time:O(1) when the first compared pair differs.
Average-case time:O(n) under the conventional interview assumption that a linear-length matching prefix may be examined; a tighter expected bound depends on the character distribution.
Worst-case time:O(n) when every symmetric pair matches.
Extra space:O(1), excluding the input itself. Only two integer pointers are used, and there is no recursion stack.
Here, n is the number of Unicode code points in the Python string.
Edge Cases to Consider
Empty input: Returns True because there are no mismatching positions.
One element: Returns True because the single character matches itself.
Duplicates: Repeated characters do not change the algorithm; "abba" is a palindrome, while "abca" is not.
Negative numbers: A minus sign is an ordinary character; "-121" is not a palindrome, while "-121-" is.
Already sorted input: Sorting is irrelevant to palindrome detection.
Disconnected graphs or cycles: Not applicable to strings.
Unicode: Python str indexing and len() operate on Unicode code points. The algorithm does not compare user-perceived grapheme clusters.
Step-by-Step Walkthrough
For "racecar":
left = 0, right = 6: compare 'r' with 'r'; they match.
left = 1, right = 5: compare 'a' with 'a'; they match.
left = 2, right = 4: compare 'c' with 'c'; they match.
left = 3, right = 3: the pointers meet, so return True.
Code Example
def is_palindrome(text: str) -> bool:
"""Return whether text is an exact palindrome by Unicode code point."""
left: int = 0
right: int = len(text) - 1
while left < right:
if text[left] != text[right]:
return False
left += 1
right -= 1
return True
print(is_palindrome("racecar")) # Expected output: True
Common Pitfalls
Off-by-one errors: Use left < right so the middle character of an odd-length string is not compared twice.
Normalization: Do not ignore case, spaces, or punctuation unless the question explicitly requires it.
String construction: Python strings are immutable, and repeated += in a loop can take O(n²) time. The two-pointer solution avoids constructing another string.
Slicing cost:text == text[::-1] is concise, but text[::-1] creates an O(n) copy, so it does not have O(1) extra space.
Recursion: The iterative solution avoids recursion-depth concerns.
26
How can you generate all permutations of a string?
KnownRevise
Backtracking generates every permutation by selecting one unused character at each level and recursively exploring that choice. The default implementation returns distinct permutations in lexicographic order; unique=False returns all positional permutations, including duplicate strings.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
Sort the characters so identical characters are adjacent and distinct results are generated lexicographically.
Track which character positions have been used.
Add one unused character to the current path and backtrack.
When the path contains every character, join it into a completed permutation.
For distinct results, skip a repeated character when an earlier identical character is still unused. This prevents equivalent choices at the same recursion level.
The used array tracks positions rather than characters, so repeated characters are handled correctly.
Example Walkthrough
For "aab", the distinct results are:
Selected path
Completed result
a → a → b
"aab"
a → b → a
"aba"
b → a → a
"baa"
The second "a" is skipped when the first "a" is available at the same recursion level, preventing duplicate results such as "aab" from appearing twice.
Code Example
def string_permutations(text: str, *, unique: bool = True) -> list[str]:
"""Return all permutations of text, optionally removing duplicate strings."""
characters = sorted(text)
used = [False] * len(characters)
path: list[str] = []
results: list[str] = []
def backtrack() -> None:
if len(path) == len(characters):
results.append("".join(path))
return
for index, character in enumerate(characters):
if used[index]:
continue
# Skip equivalent choices at the same recursion level.
if (
unique
and index > 0
and characters[index] == characters[index - 1]
and not used[index - 1]
):
continue
used[index] = True
path.append(character)
backtrack()
path.pop()
used[index] = False
backtrack()
return results
print(string_permutations("aab"))
# ['aab', 'aba', 'baa']
Complexity
Let n be the number of characters and P the number of returned strings.
Sorting:O(n) in the best case for already sorted input and O(n log n) in the average and worst cases.
Generation with unique=False:P = n!, and the time is Θ(n × n!), including traversal and joining the outputs.
Generation with unique=True: The number of distinct results is P = n! / (c₁! × c₂! × ... × cₖ!), where each cᵢ is the frequency of one repeated character. A safe, though not always tight, output-sensitive upper bound for this implementation is O(n²P): there can be O(nP) prefix states, and each scans up to n candidates. The worst case across all length-n inputs is Θ(n × n!), attained when all characters are distinct.
Best, average, and worst generation costs: For a fixed character multiset, these are identical because traversal depends on character frequencies rather than the original ordering. Only sorting has different best and average/worst costs.
Auxiliary space:O(n), including the sorted character list, used array, current path, and recursion stack. This excludes the input and returned results.
Output space:O(nP) for storing every completed string.
Total space including input and output:O(n + nP).
Common Pitfalls
Empty input: The function returns [""], representing the single permutation of an empty sequence.
One character: The result contains that character once.
Duplicate characters: The default avoids duplicate strings; unique=False includes permutations arising from different positions.
Already sorted input: The input is copied into a sorted list, but all permutations are still generated.
Recursion depth: The stack depth is O(n). For lengths near Python’s recursion limit, use an explicit stack or carefully raise the limit.
String construction: Avoid repeatedly using result += character; repeated immutable-string concatenation can become O(n²). A list plus "".join(...) is more efficient.
Unicode: Python str iteration works with Unicode code points, not bytes. A visible character such as an emoji may consist of multiple code points.
Mutation: The original string is never modified.
27
How do you check whether two strings are anagrams?
KnownRevise
Two strings are anagrams when they contain the same characters with the same frequencies, regardless of order. A hash map can count characters in the first string and subtract those in the second.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
If the strings have different lengths, they cannot be anagrams.
Count each character in the first string.
For each character in the second string, decrement its count.
The strings are anagrams exactly when every remaining count is zero.
This assumes comparison is case-sensitive and whitespace and punctuation are significant. For case-insensitive comparison, normalize both strings with casefold() before counting.
Complexity
Let n and m be the lengths of the two strings, and let k be the number of distinct characters.
Best case:O(1) when the lengths differ; otherwise O(n + m).
Average case:O(n + m), because each character requires a constant-time average hash-map operation.
Worst case:O((n + m)^2) in a theoretical hash-table model with adversarial collisions; under the usual assumption of constant-time dictionary operations, this is O(n + m).
Auxiliary space:O(k) for the character-count map, excluding the input strings. No recursion stack is used. Including the inputs, total space is O(n + m).
Code Example
def are_anagrams(first: str, second: str) -> bool:
"""Return whether two strings contain identical character frequencies."""
if len(first) != len(second):
return False
counts: dict[str, int] = {}
for character in first:
counts[character] = counts.get(character, 0) + 1
for character in second:
remaining = counts.get(character, 0) - 1
if remaining < 0:
return False
counts[character] = remaining
return True
print(are_anagrams("listen", "silent")) # True
print(are_anagrams("hello", "world")) # False
Example Walkthrough
For "listen" and "silent":
After processing "listen", the counts are: text {'l': 1, 'i': 1, 's': 1, 't': 1, 'e': 1, 'n': 1}
Processing "silent" decrements each corresponding count once.
Every count reaches zero, so the result is True.
The function also handles empty strings, one-element strings, duplicate characters, and strings containing different characters.
Interview Tips
Clarify whether comparison should be case-sensitive.
Decide explicitly whether spaces and punctuation are included.
Mention that Python len() counts Unicode code points, not encoded bytes.
For Unicode text, consider normalization and casefold() when the problem expects locale-independent matching.
A Counter can implement the same idea more concisely, but a manual dictionary makes the hashing logic explicit.
Common Pitfalls
Ignoring multiplicity:"aab" and "abb" have the same length but are not anagrams.
Using character sets instead of counts: A set detects which characters appear, not how many times they appear.
Changing only one string’s case: Both strings must use the same normalization rules.
Treating bytes and characters as identical: In Python, str operates on Unicode code points, while bytes operates on byte values.
Mutating the inputs: The implementation above creates a separate count map and does not modify either string.
28
How do you find the longest repeating subsequence in a string?
KnownRevise
The longest repeating subsequence (LRS) is the longest character sequence that appears at least twice as a subsequence, with corresponding characters taken from different positions. It can be found using an LCS-style dynamic program that compares the string with itself while forbidding a match at the same index.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
Let dp[i][j] represent the LRS length between the prefixes text[:i] and text[:j].
If text[i - 1] == text[j - 1] and i != j, the characters can be matched: dp[i][j] = dp[i - 1][j - 1] + 1.
Otherwise, discard one of the two candidates: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).
The i != j restriction is essential. Without it, the program could incorrectly match each character with itself.
After filling the table, backtracking from dp[n][n] reconstructs one longest repeating subsequence.
Unlike a substring, an LRS does not need contiguous characters. For example, "abd" is a repeating subsequence of "aabebcdd".
Complexity and Alternatives
Approach
Time
Auxiliary space
When to use
Generate every pair of subsequences and compare them
O(n × 4ⁿ)
O(n)
Very small inputs or conceptual understanding
LCS-style dynamic programming
O(n²)
O(n²)
Standard efficient solution
For the dynamic-programming solution:
Best, average and worst-case time: O(n²), because every cell in an n × n table is computed.
Auxiliary space: O(n²) for the table, plus O(n) for reconstruction.
Recursion stack: O(1), because reconstruction is iterative.
The input string is not counted in auxiliary space. Counting the returned string does not change the O(n²) overall space bound.
If only the LRS length is required, rolling rows can reduce auxiliary space to O(n), but retaining the full table makes reconstruction straightforward.
Walkthrough
For "aabebcdd", one longest repeating subsequence is "abd":
Character
First occurrence
Second occurrence
a
0
1
b
2
4
d
6
7
The occurrences preserve their order, although characters between them may be skipped. The corresponding indices differ, so the result satisfies the LRS definition.
Code Example
def longest_repeating_subsequence(text: str) -> str:
"""Return one longest repeating subsequence of text."""
length = len(text)
if length < 2:
return ""
# dp[i][j] is the LRS length for text[:i] and text[:j].
dp = [[0] * (length + 1) for _ in range(length + 1)]
for left in range(1, length + 1):
for right in range(1, length + 1):
if text[left - 1] == text[right - 1] and left != right:
dp[left][right] = dp[left - 1][right - 1] + 1
else:
dp[left][right] = max(
dp[left - 1][right],
dp[left][right - 1],
)
# Reconstruct one optimal subsequence.
characters: list[str] = []
left, right = length, length
while left > 0 and right > 0:
if text[left - 1] == text[right - 1] and left != right:
characters.append(text[left - 1])
left -= 1
right -= 1
elif dp[left - 1][right] >= dp[left][right - 1]:
left -= 1
else:
right -= 1
return "".join(reversed(characters))
print(longest_repeating_subsequence("aabebcdd")) # abd
Common Pitfalls
Using ordinary LCS without the index restriction: LCS of the string with itself can match every position with itself and incorrectly return the entire string.
Confusing subsequence and substring: A subsequence may skip characters; a substring must be contiguous.
Off-by-one errors: The table uses prefix lengths 0..n, while string positions are 0..n-1.
Unicode assumptions: Python str indexing and len() operate on Unicode code points, not bytes or user-perceived grapheme clusters.
Edge cases: Empty and one-character inputs return ""; repeated characters are handled by the same recurrence. Negative numbers, sorted numeric inputs, disconnected graphs and cycles are not applicable to this string problem.
Common follow-up: Interviewers may ask for the LRS length using O(n) space, the actual subsequence, or a comparison with the longest repeating substring.
29
How do you find the shortest palindrome by prepending characters?
KnownRevise
Shortest palindrome construction depends on finding the longest palindromic prefix of the input string. If that prefix has length L, prepend the reverse of the remaining len(s) - L characters.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
For a string s, write it as:
s = palindromic_prefix + remaining_suffix
The result is:
reverse(remaining_suffix) + s
Choosing the longest palindromic prefix minimizes the number of characters added at the beginning.
We can find that prefix in linear time using the KMP prefix function:
Build s + separator + reverse(s).
Use a separator that cannot occur in the input.
Compute the prefix function.
The final prefix-function value is the length of the longest palindromic prefix of s.
The prefix function pi[i] stores the length of the longest proper prefix of sequence[:i+1] that is also its suffix. Because the separator occurs only once, the final value cannot incorrectly cross the boundary between s and reverse(s).
Approach Comparison
Approach
Time
Auxiliary space
When to use
Test every prefix for being a palindrome
O(n²)
O(1)
Small inputs or conceptual explanation
KMP prefix function
O(n)
O(n)
General interview solution
Walkthrough
For s = "aacecaaa":
reverse(s) is "aaacecaa".
The combined sequence is "aacecaa" + separator + "aaacecaa".
The final KMP prefix value is 7, so the longest palindromic prefix is "aacecaa".
The remaining suffix is "a".
Prepending its reverse produces "a" + "aacecaaa" = "aaacecaaa".
Only one character was added, and the result is a palindrome.
Code Example
def shortest_palindrome(text: str) -> str:
"""Return the shortest palindrome formed by prepending characters to text."""
if not text:
return ""
# A unique object avoids collisions with any character in text.
separator = object()
sequence: list[str | object] = [
*text,
separator,
*reversed(text),
]
prefix_function = [0] * len(sequence)
matched = 0
for index in range(1, len(sequence)):
while matched > 0 and sequence[index] != sequence[matched]:
matched = prefix_function[matched - 1]
if sequence[index] == sequence[matched]:
matched += 1
prefix_function[index] = matched
longest_palindromic_prefix = prefix_function[-1]
remaining_suffix = text[longest_palindromic_prefix:]
return remaining_suffix[::-1] + text
# Expected output: "aaacecaaa"
print(shortest_palindrome("aacecaaa"))
Complexity and Edge Cases
Let n = len(text).
Best-case time: O(n), because the sequence construction and prefix-function computation are linear.
Average-case time: O(n), with no dependence on character distribution.
Worst-case time: O(n), since each prefix-function comparison is amortized constant time.
Auxiliary space: O(n) for the combined sequence and prefix-function array. The input string is not counted; the returned string also occupies O(n) space.
Recursion stack: O(1), because the implementation is iterative.
Empty input: Returns "".
One character: Returns the original string.
Already palindromic input: Returns the original string without additions.
Duplicate characters: Work normally; for example, "aaaa" is already a palindrome.
Unicode: Python str and len operate on Unicode code points, not bytes or necessarily user-perceived grapheme clusters.
Numeric values, sortedness, disconnected graphs and cycles are not applicable to this string problem.
Common Pitfalls
Using the wrong prefix: The required prefix is palindromic, whereas many classic problems find a longest palindromic suffix.
Choosing an unsafe delimiter: A literal separator such as "#" could already occur in the input. A unique object avoids that collision.
Incorrect slicing: After obtaining L, the characters to prepend come from text[L:], not text[:-L].
Repeated string concatenation: Avoid result += character inside a loop because immutable Python strings can make that O(n²). Use a list and ''.join(...) when many pieces must be combined.
Interview follow-ups: Be ready to explain the prefix function, distinguish this problem from longest palindromic substring, state the complexity, and discuss why Unicode normalization can affect palindrome semantics.
30
Reverse the order of words in a string.
KnownRevise
To reverse the order of words (not the characters inside them), split the string into words, reverse that list and join it with single spaces: "the sky is blue" becomes "blue is sky the". In Python that is " ".join(reversed(text.split())), which is O(n). In an interview, also show the classic reverse-everything-then-each-word trick, which runs in O(1) extra space on a mutable character array.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Two Ideas
Scan and collect: walk the string from right to left, skip spaces, and slice out each word. Joining the slices gives the answer and naturally collapses repeated, leading and trailing spaces.
Double reversal: reverse the whole character array ("eulb si yks eht"), then reverse each word back ("blue is sky the"). Every character moves twice and no second array is needed. This is the answer for C, C++ or Java char[], where strings can be edited in place.
Approaches
Approach
Time
Extra space
When to use
" ".join(reversed(text.split()))
O(n)
O(n)
Idiomatic Python
Right-to-left scan with slices
O(n)
O(n) for the result
When asked not to use split()
Double reversal on a list[str]
O(n)
O(1) beyond the list
Mutable character arrays, “in place” requirement
Prepending each word with +
O(n²)
O(n)
Never; each concatenation copies the result so far
Python strings are immutable, so any Python answer builds a new string of size O(n). The in-place version works on a list of characters that the caller already owns. Best, average and worst case are the same: every character is visited a constant number of times. Neither function recurses.
Code Example
def reverse_words(text: str) -> str:
"""Return the words of text in reverse order, separated by single spaces."""
words: list[str] = []
end = len(text)
while end > 0:
while end > 0 and text[end - 1].isspace():
end -= 1
start = end
while start > 0 and not text[start - 1].isspace():
start -= 1
if start < end:
words.append(text[start:end])
end = start
return " ".join(words)
def reverse_words_in_place(chars: list[str]) -> None:
"""Reverse word order in a list of characters whose words are separated by single spaces."""
def reverse(left: int, right: int) -> None:
while left < right:
chars[left], chars[right] = chars[right], chars[left]
left += 1
right -= 1
reverse(0, len(chars) - 1)
start = 0
for i in range(len(chars) + 1):
if i == len(chars) or chars[i] == " ":
reverse(start, i - 1)
start = i + 1
print(reverse_words(" the sky is blue ")) # blue is sky the
letters = list("the sky is blue")
reverse_words_in_place(letters)
print("".join(letters)) # blue is sky the
Walkthrough of the Double Reversal
Step
Character array
Start
the sky is blue
Reverse all
eulb si yks eht
Reverse word 1
blue si yks eht
Reverse word 2
blue is yks eht
Reverse word 3
blue is sky eht
Reverse word 4
blue is sky the
Edge Cases
Empty string or only spaces:reverse_words returns "".
One word: returned unchanged (without surrounding spaces).
Multiple, leading or trailing spaces: collapsed by the scan; the in-place version assumes single spaces, so normalise first if the input may contain more.
Punctuation: stays attached to its word ("hello, world" → "world hello,"), which is usually what the problem expects; say so.
Unicode:isspace() also recognises tabs, newlines and non-breaking spaces; the in-place version only checks " ".
Common Pitfalls
Reversing characters instead of words (text[::-1] gives "eulb si yks eht").
text.split(" ") instead of text.split(): the former keeps empty strings for repeated spaces, so the output gets extra spaces.
Building the result with result = word + " " + result in a loop, which is O(n²).
Off-by-one errors in the word loop: the final word has no space after it, which is why the loop runs to len(chars) inclusive.
Common follow-ups: keep the original spacing, reverse words in place with O(1) extra space, or rotate a sentence by k words using the same reversal trick.
31
How do you reverse every word in a sentence while preserving whitespace?
KnownRevise
Reverse each contiguous sequence of non-whitespace characters without changing the word order or the original whitespace. The two-pointer approach processes each word from both ends while preserving every space, tab, and newline in its original position.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
Collect the characters of the current word into a list.
When whitespace is encountered, append the word’s characters in reverse order, then append the whitespace unchanged.
Reverse any remaining word after processing the final character.
Join the result into a string.
Because Python strings are immutable, accumulating characters in a list and calling join() avoids the potentially quadratic cost of repeated string concatenation.
Complexity
Let n be the number of characters in the sentence.
Time: O(n) — each character is processed and copied only a constant number of times.
Auxiliary space: O(n) — the result list, current-word list, and final joined string store up to O(n) characters. The input string is not counted.
Best, average, and worst case: O(n) in all cases.
Code Example
def reverse_words_preserving_whitespace(sentence: str) -> str:
"""Reverse each word while preserving all whitespace and word order."""
result: list[str] = []
word: list[str] = []
for character in sentence:
if character.isspace():
result.extend(reversed(word))
word.clear()
result.append(character)
else:
word.append(character)
result.extend(reversed(word))
return "".join(result)
example = "one two\tthree\nfour"
print(repr(reverse_words_preserving_whitespace(example)))
# Output: 'eno owt\teerht\nruof'
Example Walkthrough
For "one two":
Step
Input character
Result so far
Current word
1
o
""
o
2
n
""
on
3
e
""
one
4
space
"eno "
""
5
space
"eno "
""
6
t
"eno "
t
7
w
"eno "
tw
8
o
"eno "
two
The final word is reversed when the loop ends, producing "eno owt".
Edge Cases
Empty input: Returns an empty string.
Whitespace-only input: Returns the original whitespace unchanged.
One word: Reverses its characters without adding whitespace.
Repeated spaces: Preserves the exact number and positions of spaces.
Tabs and newlines: Preserved because str.isspace() recognizes them as whitespace.
Unicode: Characters are reversed by Unicode code point; combining marks may not form a visually reversed grapheme cluster.
Common Pitfalls
Do not use sentence.split() and " ".join() if exact whitespace must be preserved; that approach collapses repeated whitespace and removes leading or trailing whitespace.
Do not reverse the entire sentence, because that would also reverse word order.
Avoid repeated result += character in a loop: Python strings are immutable, so this can become O(n²). Use a list and join().
Interviewers may ask how the solution handles consecutive whitespace, Unicode, or an empty string.
32
What is the minimum append/delete cost to transform one string into another?
KnownRevise
The longest common subsequence (LCS) determines the minimum number of insertion/deletion operations when a character may be inserted at any position and another may be deleted at any position. If the source and target lengths are n and m, and the LCS length is L, the minimum cost is n + m - 2L.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Idea
Characters that are not deleted must remain in the same relative order in both strings. Therefore, the characters preserved during the transformation form a common subsequence. To minimize deletions and insertions, preserve an LCS.
The LCS recurrence is:
If the current source and target characters match, extend the LCS of the preceding prefixes by one.
Otherwise, take the better result from skipping either the current source character or the current target character.
For example, with source = "abc" and target = "adc":
Step
Operation
Result
1
Find an LCS
"ac"
2
Delete "b"
"ac"
3
Insert "d" between "a" and "c"
"adc"
Here, L = 2, so the cost is 3 + 3 - 2 * 2 = 2.
Why the Formula Is Optimal
Any valid transformation preserves some common subsequence of the two strings. If the preserved subsequence has length k, the transformation must delete at least n - k characters and insert at least m - k characters. Its total cost is therefore at least:
n + m - 2k
This bound is minimized when k is the LCS length. Keeping an LCS and deleting or inserting the remaining characters achieves that bound.
Complexity
For source length n and target length m, the standard rolling-row LCS dynamic program has the following bounds:
Case
Time
Extra space
Reason
Best
O(nm)
O(min(n, m))
It examines the character pairs regardless of their distribution.
Average
O(nm)
O(min(n, m))
Runtime does not depend on the input distribution.
Worst
O(nm)
O(min(n, m))
Every pair of positions may require a comparison.
Two DP rows are live at once, each containing O(min(n, m)) entries. The input strings are not counted as extra space, and no recursion stack is used.
Common Pitfalls
Wrong operation model: Ordinary edit distance may also replace characters. Here, replacement is not allowed, so replacing one character requires one deletion plus one insertion.
Empty input: An empty source requires len(target) insertions, while an empty target requires len(source) deletions.
One-element input: Equal one-character strings cost 0; different one-character strings cost 2 because replacement is unavailable.
Duplicates: The LCS recurrence handles repeated characters correctly and does not assume unique characters.
Character versus byte semantics: Python str indexes Unicode code points, and len counts code points—not bytes or user-perceived grapheme clusters.
Appending only at the end: If insertion is restricted to the end, the LCS formula does not apply. The permitted operation model must be stated explicitly.
Interview follow-ups: Common follow-ups include reconstructing the actual edit sequence, handling very long strings, and comparing this approach with ordinary edit distance.
33
How to reverse a string in place without extra buffer space?
KnownRevise
In-place string reversal uses two pointers to swap characters from opposite ends until they meet. It requires a mutable character sequence; Python’s built-in str is immutable, so reversing a Python string directly without additional storage is not possible.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Key Idea
For a mutable sequence such as a character array or list:
Place left at the first character.
Place right at the last character.
Swap characters[left] and characters[right].
Move left forward and right backward until left >= right.
This modifies the existing sequence without allocating another sequence proportional to its size.
Complexity
Representation
Best, Average, and Worst Time
Auxiliary Space
Existing mutable character list
O(n) because approximately n / 2 pairs are swapped
O(1), excluding the mutable input list; there is no recursion, so the recursion stack is O(1)
Python str converted with list(s)
O(n) for conversion, swapping, and joining
O(n) for the temporary list; the returned string also occupies O(n) space
The original Python string is not counted as auxiliary space, but the copied character list must be counted.
Edge Cases and Walkthrough
Empty sequence: No swaps are required.
One character: The character remains unchanged.
Duplicates: Every occurrence is preserved, although its position may change.
Negative-number text:"-123" becomes "321-" because every character is reversed.
Already sorted or palindromic input: The same swaps are still performed because the algorithm does not need to inspect whether the sequence is symmetric.
Unicode: Python string indexing operates on Unicode code points (including any isolated surrogate code points). Reversing code points does not necessarily preserve user-perceived grapheme clusters, which can consist of multiple code points.
For ['a', 'b', 'c', 'd']:
Step
Action
Result
1
Swap indices 0 and 3
['d', 'b', 'c', 'a']
2
Swap indices 1 and 2
['d', 'c', 'b', 'a']
3
Stop because the pointers have crossed
['d', 'c', 'b', 'a']
Code Example
def reverse_characters_in_place(characters: list[str]) -> None:
"""Reverse a mutable character list in place using two pointers."""
left = 0
right = len(characters) - 1
while left < right:
characters[left], characters[right] = (
characters[right],
characters[left],
)
left += 1
right -= 1
characters = list("abcd")
reverse_characters_in_place(characters)
print("".join(characters)) # Output: dcba
Common Pitfalls
Python string immutability:text[0] = "x" is invalid. Converting the string to a list permits swapping, but that conversion requires O(n) space.
Incorrect space accounting: Do not describe list(s) as constant space merely because it replaces the result-building buffer.
Off-by-one error: Use left < right. Using left <= right swaps the middle character with itself unnecessarily, although that alone does not change the result.
Slicing:s[::-1] returns a new string and uses O(n) space; it is not an in-place operation.
Repeated concatenation: Building a result with += in a loop can take O(n²) time because Python strings are immutable.
Recursion: The iterative implementation has no recursion-depth risk.
34
Why is string sorting different, and how can it be optimized?
KnownRevise
String sorting differs mainly because strings are variable-length sequences whose comparisons may inspect a long common prefix and whose ordering can depend on Unicode or locale-specific rules. Optimization therefore requires choosing the correct comparison key and algorithm while accounting for both key construction and character-comparison costs.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Why String Sorting Is Different
Variable-cost comparisons: Comparing fixed-width numbers is O(1), while comparing strings can require examining their entire common prefix. For strings of maximum length L, one comparison costs up to O(L). Arbitrary-precision integer comparisons similarly depend on the number of digits.
Lexicographic ordering: Characters are compared from left to right. If one string is a prefix of another, the shorter string normally comes first.
Multiple ordering definitions: Python’s default order compares Unicode code points, but applications may require case-folded, locale-aware, normalized, or byte-level ordering.
Immutable strings: Changing or extending a string creates a new string value. Repeated operations such as text += item in a loop can therefore become O(n²). Sorting itself only reorders references to the immutable strings.
Memory sensitivity: Long keys, temporary slices, and copied substrings can consume substantial space even when the comparison algorithm is efficient.
Choosing the Correct Ordering
Requirement
Recommended approach
Important detail
Exact code-point order
sorted(values)
Case-sensitive and deterministic
Case-folded order
sorted(values, key=str.casefold)
casefold() handles more Unicode cases than lower()
Locale-aware human ordering
locale.strxfrm as the key
The process locale, specifically LC_COLLATE, must first be configured correctly
Byte-level ordering
Sort bytes values
Byte order is not the same as Unicode character order
Case folding can expand a string—for example, "ß" becomes "ss"—and may cause otherwise different strings to compare as equal. Python’s stable sort preserves their original relative order.
Time and Space Complexity
Let n be the number of strings, L the maximum key length, and σ the alphabet size.
Approach
Best case
Average case
Worst case
Auxiliary space
Built-in lexicographic sort
O(nL)
O(nL log n)
O(nL log n)
O(n)
Sort with str.casefold keys
O(nL)
O(nL log n)
O(nL log n)
O(n) references plus up to O(nL) key data
Fixed-alphabet radix sort
O(nL + σL)
O(nL + σL)
O(nL + σL)
O(n + σL) for per-level buckets
The logarithmic factors come from the number of comparisons, while L accounts for character inspection. The radix-sort bound assumes a straightforward implementation over a fixed-width alphabet, such as bytes.
The input itself is not counted in auxiliary space. Python’s built-in sort uses O(n) temporary references and an O(log n) internal merge stack; computed key data is also auxiliary space.
Optimization Strategies
Use sorted or list.sort: Python uses Timsort, which is stable and performs well on already sorted, reversed, or partially ordered data.
Compute keys once: A key function is evaluated once per element, avoiding repeated expensive transformations during comparisons.
Prefer stable sorting: It makes duplicate handling predictable and preserves input order for equal keys.
Avoid unnecessary copies: Slicing a string creates an O(k) copy. Do not create substrings as keys unless the substring defines the required ordering.
Consider radix sorting selectively: It can approach O(nL) when the alphabet is small and the format is fixed, but Python’s built-in sort is usually simpler and often faster in practice.
Do not build strings with += in a loop: Collect fragments in a list and use ''.join(parts).
Choose the correct mutation behavior: list.sort() rearranges the list in place, whereas sorted() returns a new list.
Optimization Example
For a case-folded ordering of "pear", "Apple", "apple", and "fig":
The original values are "pear", "Apple", "apple", and "fig".
Their case-folded keys are "pear", "apple", "apple", and "fig".
Sorting by those keys places the two equal-key values first, followed by "fig" and "pear".
Stability keeps "Apple" before "apple".
Key construction costs O(nL). The total cost is O(nL) when already ordered and O(nL log n) on average and in the worst case. Empty input produces an empty result; one-element input is unchanged; duplicates retain their input order; and empty strings remain valid keys that precede longer strings sharing their prefix.
Common Pitfalls
Assuming string comparison is always O(1).
Using lower() when full Unicode case folding is required.
Ignoring locale configuration when using locale.strxfrm.
Normalizing strings without deciding whether visually equivalent Unicode sequences should compare equally.
Building strings through repeated concatenation.
Assuming equal sort keys should be reordered; stable sorting preserves their original order.
Confusing Python code-point ordering with byte ordering.
Using list.sort() when the original list must remain unchanged.
35
What is the longest common prefix algorithm and where is it used?
KnownRevise
The longest common prefix (LCP) is the longest string that appears at the beginning of every input string. The standard algorithm checks characters at the same position across all strings and stops at the first mismatch.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
Two common strategies are vertical scanning and horizontal pairwise scanning. The following steps describe vertical scanning:
Find the length of the shortest string, since the common prefix cannot be longer than it.
Compare the character at index 0 across every string.
Continue comparing characters at index 1, 2, and so on.
Stop at the first index where the characters do not all match.
Return the matching prefix.
For example:
Index
flower
flow
flight
Result
0
f
f
f
Continue
1
l
l
l
Continue
2
o
o
i
Stop
The answer is "fl".
Relevant edge cases include:
Empty collection: Return "".
Any empty string: Return "".
One string: Return that string.
Duplicate strings: They are handled normally.
Unicode: Python string indexing operates on Unicode code points, not bytes or user-perceived characters.
Applications
Autocomplete and typeahead systems: Filter candidates that begin with the user’s current input.
File and directory hierarchies: Identify the deepest lexically shared path among several locations.
Batch processing: Find a common naming prefix before applying a transformation to related records.
String grouping: Group records by a shared prefix, such as product families or geographic regions.
Trie implementations: During insertion, matching characters can reuse an existing trie path. In a compressed or radix trie, two keys share an explicit path segment that ends where their edges diverge.
Version and configuration management: Detect shared prefixes in configuration keys or versioned names.
Complexity
Let:
n be the number of strings.
m be the length of the shortest string.
L be the length of the returned prefix.
S be the total number of characters across all strings.
P be the number of matching positions before the algorithm stops.
For more than one string:
Best-case time: O(n): Finding the shortest length and detecting a mismatch at the first character require linear work in the number of strings.
Average-case time: O(n(1 + E[P])): The exact average depends on the input distribution. For comparable-length strings with long shared prefixes, this is commonly summarized as O(nm).
Worst-case time: O(n(m + 1)): Every string shares the entire shortest string. This is O(nm) when m >= 1 and O(n) when the shortest string is empty.
Overall upper bound: O(n + S): The minimum-length pass costs O(n), while character comparisons are bounded by the available input characters.
Auxiliary space: O(1), excluding the input and returned string. There is no recursion stack.
Output space: O(L) when Python slicing is used to construct the returned prefix. The input itself is not counted.
Common Pitfalls
Off-by-one errors: Only indices below the shortest string’s length can be examined.
Confusing bytes with characters: Python len counts Unicode code points, while UTF-8 storage size is measured in bytes.
Repeated concatenation: Avoid building the result with prefix += character in a loop because immutable strings can make that O(L²). Construct the substring once instead.
Assuming equal-length inputs: Use the shortest string as the upper bound.
Mutating the input: A read-only LCP implementation does not modify the supplied strings.
Common follow-up question: Interviewers may ask about finding the LCP of two strings, many strings, or using the result to implement autocomplete with a trie.
36
How do you group anagrams in an array of strings?
KnownRevise
A character-frequency signature groups strings efficiently: two Python strings are anagrams when they contain the same Unicode code points with the same multiplicities. Store each signature as a key in a dictionary whose value contains all matching strings.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Approach
For each string:
Count the occurrences of each character with Counter.
Convert the character-count mapping into a hashable frozenset of (character, count) pairs.
Append the string to the group associated with that signature.
For example, the character counts {"e": 1, "a": 1, "t": 1} become:
frozenset({("e", 1), ("a", 1), ("t", 1)})
A frozenset is independent of iteration order, so equivalent frequency mappings produce equal keys.
Approach
Time
Space Including Output
When to Use
Pairwise frequency comparisons
O(n²(L + 1))
O(n + A)
Very small inputs
Sorted-character signatures
O(n + C log(L + 1))
O(n + C)
A simple canonical representation is preferred
Frequency-signature hash map
O(n + C) average
O(n + C)
Efficient grouping of general strings
Here, n is the number of strings, C is the total number of characters, L is the maximum string length, and A is the maximum number of distinct characters in one string.
Example Walkthrough
For ["eat", "tea", "tan", "ate", "nat", "bat"]:
String
Character Counts
Group
eat
{e: 1, a: 1, t: 1}
1
tea
{e: 1, a: 1, t: 1}
1
tan
{t: 1, a: 1, n: 1}
2
ate
{e: 1, a: 1, t: 1}
1
nat
{t: 1, a: 1, n: 1}
2
bat
{b: 1, a: 1, t: 1}
3
The result is [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]].
Code Example
from collections import Counter
def group_anagrams(words: list[str]) -> list[list[str]]:
"""Group strings with identical character frequencies."""
groups: dict[frozenset[tuple[str, int]], list[str]] = {}
for word in words:
# Exact, order-independent representation of the character counts.
signature = frozenset(Counter(word).items())
# Preserve duplicates and original relative order.
groups.setdefault(signature, []).append(word)
return list(groups.values())
words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(words))
# Expected output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
Complexity
Best time: O(n + C), assuming no significant hash-map collisions.
Average time: O(n + C). Counting and signature construction are linear in the input size, while dictionary lookups have expected constant-time behavior.
Worst time: O(C + n²A) under pathological hash collisions, a loose bound where each lookup may compare against O(n) signatures and each comparison may inspect O(A) character-count pairs.
Output space: O(n) string references; the original string contents are not copied.
Recursion stack: O(1), because the implementation is iterative.
Common Pitfalls
Empty input: An empty list correctly returns [].
One element: A one-element list returns a group containing that string.
Duplicates: Equal strings are valid anagrams and should remain in the result. This implementation preserves them.
Empty strings: All empty strings share the empty signature and are grouped together.
Unicode normalization: Python strings contain Unicode code points. Canonically equivalent forms such as "é" and "e\u0301" are not grouped unless both are normalized first.
Case sensitivity:"Listen" and "silent" are not grouped because uppercase and lowercase characters are distinct.
Numeric-looking strings: Characters such as - and digits are compared normally, so "-1" and "1-" are anagrams.
Input mutation and ordering: The function does not modify the input. Groups appear in first-seen order, and strings within each group retain their input order; an already sorted input does not change this behavior.
37
How do you compare version number strings in Python?
KnownRevise
For dotted numeric versions, perform component-wise numeric comparison rather than comparing the complete strings lexicographically. This ensures that "1.10" is correctly considered newer than "1.2".
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Comparison Rules
Split each version on ., then compare corresponding components from left to right.
The first unequal numeric component determines the result.
If all shared components are equal, the longer version is greater unless its extra components are zero.
This implementation treats missing trailing components as zero, so "1.2" and "1.2.0" compare as equal.
Approach
Example
Result
Raw string comparison
"1.10" versus "1.2"
Incorrect: "1.10" < "1.2"
Component-wise numeric comparison
"1.10" versus "1.2"
Correct: "1.10" > "1.2"
SemVer-aware comparison
"1.0.0-alpha" versus "1.0.0"
Prerelease is lower
The function below implements a dotted-numeric convention rather than strict SemVer. Under SemVer 2.0.0, a release has exactly three numeric core components, and leading zeroes are forbidden except for zero itself. A prerelease ranks below the corresponding release. Prerelease identifiers are compared from left to right: all-numeric identifiers compare numerically, non-numeric identifiers compare in ASCII lexicographic order, and a numeric identifier ranks below a non-numeric identifier. If all preceding identifiers are equal, a prerelease with more identifiers has higher precedence. Build metadata does not affect precedence.
Complexity
Let L be the total number of characters in both versions.
Best, average and worst-case time:O(L). Splitting, validation, normalization and comparison scan each component a constant number of times.
Extra space:O(L) for the split components and normalized values. There is no recursion, so the call stack uses O(1) space, and the input strings are not counted.
Total space including input:O(L).
Code Example
The implementation normalizes leading zeros and compares decimal strings directly. This avoids integer-conversion limits for exceptionally long numeric components.
def compare_version_strings(left: str, right: str) -> int:
"""Return -1, 0, or 1 for two dotted numeric version strings."""
def parse(version: str) -> list[str]:
if not version:
raise ValueError("version must not be empty")
components: list[str] = []
for component in version.split("."):
# Only non-negative ASCII integers are supported.
if (
not component
or not component.isascii()
or not component.isdecimal()
):
raise ValueError(
"version components must be non-negative integers"
)
# Remove leading zeros while preserving one zero for "0".
components.append(component.lstrip("0") or "0")
return components
left_components = parse(left)
right_components = parse(right)
component_count = max(len(left_components), len(right_components))
for index in range(component_count):
left_component = (
left_components[index]
if index < len(left_components)
else "0"
)
right_component = (
right_components[index]
if index < len(right_components)
else "0"
)
# More digits means a larger non-negative integer.
if len(left_component) != len(right_component):
return -1 if len(left_component) < len(right_component) else 1
# Equal-length decimal strings can be compared lexicographically.
if left_component != right_component:
return -1 if left_component < right_component else 1
return 0
result = compare_version_strings("1.10.2", "1.9.9")
print(result) # 1
The example proceeds as follows:
Split the versions into ["1", "10", "2"] and ["1", "9", "9"].
Compare the first components: "1" equals "1", so continue.
Compare the second components: "10" has more digits than "9", so it is larger.
Return 1, indicating that the left version is newer.
SemVer assumptions: Missing components are not universally equivalent to zero. Strict SemVer requires exactly three numeric core components.
Invalid input: Empty versions, empty components such as "1..2", negative values and nonnumeric labels are rejected by this implementation.
Leading zeros: This dotted-numeric implementation considers "01" equal to "1", although strict SemVer forbids leading zeroes.
Edge cases: One-component versions work correctly, and duplicate components compare normally. Sortedness is irrelevant, while graph concepts such as connectivity and cycles do not apply.
Follow-up question: Interviewers may ask how prerelease labels such as alpha, beta and rc should be ordered, which requires a SemVer-aware comparison strategy.
38
How do you encode and decode strings with Run-Length Encoding?
KnownRevise
Run-Length Encoding (RLE) compresses consecutive repeated characters by replacing each run with its count and character. A delimiter such as # can separate the count from the character, making the format unambiguous even when the original string contains digits.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
For an input such as aaabbcddd, identify each maximal run:
aaa becomes 3#a
bb becomes 2#b
c becomes 1#c
ddd becomes 3#d
The encoded result is:
3#a2#b1#c3#d
To decode, repeatedly:
Read the decimal count.
Read the # delimiter.
Read the character following the delimiter.
Repeat that character count times.
The implementation below uses Python str characters, which are Unicode code points rather than bytes. Therefore, len(text) counts code points, not encoded byte length.
Complexity
Let:
n be the number of characters in the original string.
m be the length of the encoded string.
k be the length of the encoded output.
r be the number of runs.
Operation
Best case
Average case
Worst case
Reason
Encode
O(n)
O(n)
O(n)
Every input character is examined once
Decode
O(m + n)
O(m + n)
O(m + n)
Parsing takes O(m), and producing the output takes O(n)
Uncompressed copy
O(n)
O(n)
O(n)
Every character is copied without compression
Encoding uses O(k) space for the generated fragments and output, excluding the input string. Decoding uses O(n) space for the reconstructed output, excluding the encoded input. Neither implementation uses recursion, so there is no recursion-stack cost.
RLE is most effective when the input contains long consecutive runs, such as repeated spaces, repeated status characters, or simple bitmap-like data. It can make already varied data larger.
Edge Cases
Empty input: encode_rle("") and decode_rle("") both return "".
One character: "a" becomes "1#a".
Duplicates: Consecutive duplicates are combined, while separated duplicates remain separate runs.
Negative numbers: Counts are never negative; malformed encoded counts raise ValueError.
Digits in the original text: The # delimiter allows characters such as "7" to be encoded and decoded correctly.
Malformed input: Missing counts, missing delimiters, invalid characters, or non-positive counts are rejected.
Unicode: Characters are counted as Python code points; combining marks and emoji sequences may represent multiple code points visually.
Code Example
def encode_rle(text: str) -> str:
"""Encode consecutive characters as count#character runs."""
if not text:
return ""
parts: list[str] = []
run_character = text[0]
run_length = 1
for index in range(1, len(text)):
character = text[index]
if character == run_character:
run_length += 1
else:
parts.append(f"{run_length}#{run_character}")
run_character = character
run_length = 1
parts.append(f"{run_length}#{run_character}")
return "".join(parts)
def decode_rle(encoded: str) -> str:
"""Decode a count#character run-length encoded string."""
if not encoded:
return ""
parts: list[str] = []
index = 0
while index < len(encoded):
count = 0
has_digit = False
# Parse the count without creating a slice of the encoded string.
while index < len(encoded) and encoded[index] != "#":
digit_character = encoded[index]
if digit_character not in "0123456789":
raise ValueError("Encoded count must contain only decimal digits")
count = count * 10 + (ord(digit_character) - ord("0"))
has_digit = True
index += 1
if not has_digit:
raise ValueError("Missing run count")
if index >= len(encoded):
raise ValueError("Missing '#' delimiter")
index += 1 # Skip the delimiter.
if index >= len(encoded):
raise ValueError("Missing encoded character")
character = encoded[index]
index += 1
if count <= 0:
raise ValueError("Run count must be positive")
parts.append(character * count)
return "".join(parts)
print(encode_rle("aaabbcddd")) # Expected: 3#a2#b1#c3#d
print(decode_rle("3#a2#b1#c3#d")) # Expected: aaabbcddd
Common Pitfalls
Incorrect run boundaries: A new run starts whenever the current character differs from the previous one; nonconsecutive duplicates must not be combined.
Off-by-one errors: The final run must be emitted after the scan, and the decoder must verify that a character exists after every #.
Ambiguous formats: A format such as 3a2b can be difficult to parse when the original text contains digits. A delimiter or escaping mechanism avoids ambiguity.
Mutating or repeatedly concatenating strings: Python strings are immutable. Using result += piece in a loop can become O(n²); accumulate fragments in a list and use "".join(parts).
Forgetting validation: Production decoders should reject malformed input rather than silently producing incorrect output.
Interview follow-up: Be ready to explain why RLE is suitable for repetitive data, how Unicode differs from byte-oriented encoding, and how you would add an escape mechanism if the delimiter itself could conflict with the chosen format.
39
How do you implement a Caesar cipher and evaluate its security?
KnownRevise
A Caesar cipher encrypts text by shifting each ASCII letter by a fixed number of positions in the alphabet, wrapping around after Z or z. It is useful for learning substitution ciphers, but it is not secure for protecting real data.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
Shift: The number of positions each letter moves. A shift of 3 maps A to D.
Wrapping: Modular arithmetic handles transitions such as X shifting to A.
Case preservation: Uppercase and lowercase letters are shifted independently.
Non-letters: This implementation leaves spaces, punctuation, digits, and Unicode characters unchanged.
Decryption: Subtract the same shift, equivalent to using (26 - shift) % 26.
Code Example
def caesar_encrypt(text: str, shift: int) -> str:
"""Encrypt ASCII letters using a Caesar shift from 0 through 25."""
if not 0 <= shift <= 25:
raise ValueError("shift must be between 0 and 25")
encrypted: list[str] = []
for character in text:
if "A" <= character <= "Z":
base = ord("A")
offset = ord(character) - base
encrypted.append(chr(base + (offset + shift) % 26))
elif "a" <= character <= "z":
base = ord("a")
offset = ord(character) - base
encrypted.append(chr(base + (offset + shift) % 26))
else:
encrypted.append(character)
return "".join(encrypted)
print(caesar_encrypt("Attack at dawn!", 3)) # Tdfwh df gdzq!
Using a list and join avoids repeated string concatenation. Repeated text += character can take O(n²) time because immutable strings must be copied.
Example Walkthrough
For "abc XYZ!" with a shift of 3:
Input
Operation
Output
a
Shift forward three letters
d
b
Shift forward three letters
e
c
Shift forward three letters
f
X
Wrap after Z
A
Y
Wrap after Z
B
Z
Wrap after Z
C
!
Leave unchanged
!
The result is "def ABC!".
Security Assessment
The implementation defines 26 possible shifts, 0 through 25; if the identity shift is excluded, there are only 25 nontrivial shifts. An attacker can try every shift, so brute-force decryption takes O(25n), which is O(n) for the fixed alphabet. A dictionary or known-plaintext attack is also effective.
Security property
Caesar cipher behavior
Consequence
Keyspace
26 possible shifts, including the identity shift
Trivial brute force
Letter frequencies
Preserved
Frequency analysis can reveal plaintext
Repeated patterns
Preserved
Known phrases help identify the shift
Determinism
Equal plaintexts produce equal ciphertexts
Patterns remain visible
Integrity
No protection against modification
Ciphertext can be tampered with undetected
Modern cryptography
No authenticated encryption
Unsuitable for sensitive data
It should therefore be treated as encoding or obfuscation, not real encryption. For actual applications, use a vetted cryptography library with AES-GCM or ChaCha20-Poly1305, a securely generated key, and a unique nonce for every encryption under the same key.
Complexity
For a string containing n Unicode code points:
Best case: O(n) — every character must be inspected.
Average case: O(n) — each character requires constant work.
Worst case: O(n) — all characters may be letters and require shifting.
Space: O(n) for the character list and resulting string; no recursion stack is used. The input string itself is not counted, although including it still gives O(n) total space.
Common Pitfalls
Edge cases: Empty input returns ""; one-character inputs and duplicate characters are handled independently; negative shifts and shifts above 25 raise ValueError.
Off-by-one errors: Shift 25 and shift 0 are valid; shifts outside 0..25 are rejected by this implementation.
Incorrect wrapping: Use % 26 when moving forward and (26 - shift) % 26 when decrypting.
Unicode assumptions: len counts Unicode code points, not bytes or grapheme clusters. This implementation intentionally changes only ASCII letters.
Inefficient concatenation: Avoid result += character in a loop; collect characters in a list and call "".join.
False sense of security: A Caesar cipher is intentionally simple and must not be used for passwords, financial data, private messages, or other sensitive information.
40
What challenges do Unicode encoding and decoding create for strings?
KnownRevise
Unicode encoding maps Unicode code points to bytes, while decoding performs the reverse mapping using a particular encoding. The main challenges arise because code points, code units, bytes, and user-perceived characters are different units, and Unicode can represent the same text in multiple forms.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Concepts
Unicode separates text representation into several layers:
Code point: A number assigned to a Unicode character, such as U+00E9 for é.
Code unit: A fixed-size storage unit used by some encodings. Java and JavaScript primarily use 16-bit UTF-16 code units.
Byte: An 8-bit unit used by physical storage and most modern text encodings.
Grapheme cluster: A user-perceived character, which may contain multiple code points. For example, the flag of France contains two regional-indicator code points.
Consequently, these lengths can differ:
Python len("é") is 1 code point.
The UTF-8 representation of "é" is 2 bytes.
Java "😀".length() is 2 UTF-16 code units.
A single visible character such as "é" may require multiple code points or bytes.
Main Challenges
Variable-length representations: UTF-8 uses one to four bytes per code point. Code must not split a multi-byte character in the middle.
Invalid byte sequences: Arbitrary bytes may not form valid UTF-8. Decoders can raise an exception, replace invalid data, or ignore it, but these policies have different safety implications.
Missing encoding metadata: A Python bytes object does not remember how it was encoded. The application must know whether the bytes represent UTF-8, UTF-16, Latin-1, or something else.
Canonical equivalence: Unicode has canonically equivalent sequences such as precomposed "é" (U+00E9) and decomposed "é" (U+0065 U+0301). They may look identical but have different byte representations.
Normalization versus encoding: Normalization changes the internal code-point sequence; encoding converts text into bytes. str.encode() does not automatically perform Unicode normalization.
Legacy encodings: Shift_JIS has lead/trailing-byte structure and vendor-extension compatibility issues, while legacy code pages such as GBK use different byte mappings. Neither should be assumed interchangeable with UTF-8, which is usually preferable for interchange.
Security concerns: Normalization differences, homoglyphs, mixed scripts, and invalid decoding can enable visually misleading text or bypass application-level validation.
Language Approaches
Language
String representation
Typical encoding boundary
Python 3.12
str stores Unicode code points; bytes stores raw bytes
Explicit encode() and decode()
Java 21
String represents UTF-16 code units
Charset APIs and byte arrays
JavaScript ES2023
Strings use UTF-16 code units
Web APIs provide TextEncoder and TextDecoder; TextEncoder always emits UTF-8, while TextDecoder defaults to UTF-8 and can support other encodings in Web environments
Languages generally separate Unicode text from encoded bytes, and conversion occurs at I/O boundaries, either explicitly or inside an I/O API. Strict-error policies are available in many APIs, although their defaults differ. Support for grapheme clusters also varies; iteration over code points or code units does not necessarily match user-visible characters.
Complexity
Let n be the number of Unicode code points and m the number of encoded bytes.
Operation
Best
Average
Worst
Space
UTF-8 encoding
O(n)
O(n)
O(n)
O(n) bytes including output
UTF-8 decoding
O(m)
O(m)
O(m)
O(k) including output, where k ≤ m
Strict byte validation
O(m)
O(m)
O(m)
O(1) auxiliary space
UTF-8 encoding is linear because each code point produces at most four bytes. UTF-8 decoding and validation process each input byte a constant number of times. These bounds do not differ between best, average, and worst cases. Space includes the returned object; the input is not counted, and the auxiliary space excluding that output is O(1).
Common Pitfalls
Do not use byte length as character length or assume one code point equals one visible character.
Do not decode with the wrong encoding, especially when handling HTTP data, files, or command-line arguments.
Prefer strict decoding at trust boundaries. Replacement-character policies can silently corrupt data and hide attacks.
Normalize identifiers with a documented canonical form when semantic equality matters. Normalization alone is not a complete security control because homoglyphs and mixed scripts can remain.
Never slice UTF-8 bytes at arbitrary indices; operate on decoded text or code-point-aware boundaries.
In interviews, expect follow-up questions about UTF-8 versus UTF-16, malformed input, canonical equivalence, grapheme clusters, and why a bytes object must carry encoding information separately.
41
How are Regular Expressions used for string pattern matching and validation?
KnownRevise
A regular expression (regex) is a small pattern language that describes a set of strings. You use it in three ways: validate that a whole string has the expected shape (fullmatch), find or extract parts of a larger string (search, finditer, capture groups), and transform text (sub, split). Regex checks form, not meaning: it can confirm that 2026-02-30 looks like a date, but only a real date parser can reject it.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Building Blocks
Element
Meaning
Example
Literal
Matches itself
cat
Character class
One character from a set
[A-Za-z], d, s, w
Quantifier
Repetition
*, +, ?, {2,4}
Lazy quantifier
Match as little as possible
.*?
Anchor
Position, not a character
^, $, b
Group
Capture a part
(d+), (?P<year>d{4})
Lookahead
Condition without consuming
(?=.*d)
Alternation picks one of several options: (?:jpg|png) accepts either extension, and (?:...) groups without capturing.
Matching Functions in Python
re.fullmatch(p, s): the whole string must match. Use it for validation.
re.match(p, s): matches only at the start; trailing junk is allowed.
re.search(p, s): first match anywhere.
re.finditer / re.findall: every non-overlapping match.
re.sub and re.split: replace or split on matches.
re.compile(p): build the pattern once and reuse it in loops.
Code Example
import re
from datetime import date
DATE_RE = re.compile(r"(?P<year>\d{4})-(?P<month>\d{2})-(?P<day>\d{2})", re.ASCII)
PAIR_RE = re.compile(r"(\w+)=(\w+)")
def parse_iso_date(text: str) -> date | None:
"""Validate YYYY-MM-DD with a regex, then check the calendar with datetime."""
match = DATE_RE.fullmatch(text)
if match is None:
return None
try:
return date(int(match["year"]), int(match["month"]), int(match["day"]))
except ValueError:
return None
print(parse_iso_date("2026-02-28")) # 2026-02-28
print(parse_iso_date("2026-02-30")) # None
print(parse_iso_date("2026-02-28 junk")) # None
print(dict(PAIR_RE.findall("user=ana role=admin"))) # {'user': 'ana', 'role': 'admin'}
print(re.sub(r"\s+", " ", "too many\tspaces")) # too many spaces
The date example shows the usual split of work: the regex rejects anything that is not shaped like a date, and datetime rejects February 30. The re.ASCII flag matters because in Python 3 \d also matches digits from other scripts, such as Arabic-Indic ٣.
How the Engine Matches
Python’s re is a backtracking engine. It tries the pattern left to right and, when a branch fails, backs up and tries the next option (another alternative, or one fewer repetition).
Engine type
Examples
Time guarantee
Extra features
Backtracking
Python re, Java, PCRE, JavaScript
Usually O(n) for simple patterns; exponential worst case
Backreferences, lookaround
Automaton (DFA/NFA simulation)
RE2, Rust regex, Go regexp
O(n·m) or linear in the text
No backreferences
Here n is the text length and m the pattern size. Compiling costs O(m) and is cached by re. Matching usually needs O(1) to O(m) extra state, plus O(k) for each extracted group or result list.
Catastrophic Backtracking
A pattern like (a+)+$ against "aaaaaaaaaaaaaaaaaaaaaaaab" explores an exponential number of ways to split the a run before it fails. This is the basis of ReDoS (regular-expression denial of service) when users control the input. Defences:
Avoid nested quantifiers over the same characters ((a+)+, (.*)*).
Cap input length before matching.
Use atomic groups (?>...) or possessive quantifiers a++ (supported in Python 3.11+).
Use a linear-time engine for untrusted patterns or inputs.
Common Pitfalls
Validating with match or search, which accept a valid-looking prefix or substring. Use fullmatch.
Relying on ^…$: $ also matches before a trailing newline, so "abc\n" passes ^abc$.
Forgetting raw strings, so "\b" becomes a backspace instead of a word boundary.
Greedy .* swallowing too much (<.*> on <a><b> matches the whole string; <.*?> matches <a>).
Using regex for nested structures such as HTML or balanced brackets; use a parser.
Interviewers often ask you to explain the difference between match, search and fullmatch, and why a regex for email or dates should be combined with a real check.
42
How can I write a regular expression to validate email addresses?
KnownRevise
A regular expression can validate the common syntactic form of an email address, such as alice@example.com. The pattern below supports an ASCII local part, dot-separated domain labels, common special characters, and basic length limits; it does not verify that the mailbox actually exists.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Pattern Requirements
The regular expression validates these components:
Local part: One or more letters, digits, or common special characters. Dots may separate local-part segments, but cannot appear consecutively or at the beginning or end.
Domain: One or more labels separated by dots. Labels may contain letters, digits, and internal hyphens, but cannot begin or end with a hyphen.
Top-level domain: Two to 63 ASCII letters.
Length limits: The local part is limited to 64 characters, the domain to 253 characters, and the complete address to 254 characters.
This is a practical validation pattern, not a complete implementation of every form allowed by RFC 5322.
How It Works
The pattern uses these regular-expression features:
+: Requires one or more characters.
*: Allows zero or more repetitions.
?: Makes the preceding group optional.
(?:...): Groups alternatives without capturing them.
[A-Za-z0-9-]: Matches an allowed character inside a domain label.
fullmatch(): Ensures that the entire input matches, not merely a prefix.
For alice.smith@example.com, the match proceeds as follows:
The local-part pattern consumes alice.
The optional dot-separated group consumes .smith.
The literal @ matches the separator.
The domain pattern consumes example. as a domain label and com as the top-level domain.
fullmatch() succeeds because the entire address matches.
By contrast, alice..smith@example.com and alice@-example.com are rejected.
Complexity
Let n be the length of the candidate address.
Best case: O(1) time for empty input or an input rejected immediately.
Average case: O(n) time for a typical address, because the input is scanned and matched.
Worst case: O(n^2) as a conservative bound for Python’s backtracking regular-expression engine on adversarial input. The implementation limits matching to addresses of at most 254 characters, so practical work is bounded.
Auxiliary space: O(1) for the surrounding Python code, excluding the input string. The regex engine may use O(n) backtracking state. There is no recursion stack. If the input itself is counted, total storage is O(n).
Code Example
import re
EMAIL_RE = re.compile(
r"[A-Za-z0-9!#$%&'*+/=?^_`{|}~-]+"
r"(?:\.[A-Za-z0-9!#$%&'*+/=?^_`{|}~-]+)*"
r"@"
r"(?:[A-Za-z0-9](?:[A-Za-z0-9-]{0,61}[A-Za-z0-9])?\.)+"
r"[A-Za-z]{2,63}"
)
def is_valid_email(email: str) -> bool:
"""Validate a practical ASCII email address."""
if len(email) > 254:
return False
local_part, separator, domain = email.partition("@")
if not separator:
return False
if len(local_part) > 64 or len(domain) > 253:
return False
return EMAIL_RE.fullmatch(email) is not None
print(is_valid_email("alice@example.com")) # True
print(is_valid_email("alice..smith@example.com")) # False
Common Pitfalls
Using match() instead of fullmatch(): match() can accept a valid-looking prefix while ignoring invalid trailing characters.
Using only ^ and $: $ can match before a trailing newline. fullmatch() is safer for validation.
Assuming regex validates deliverability: A syntactically valid address may not exist, may be disabled, or may reject mail.
Ignoring Unicode: The pattern is ASCII-only. Internationalized domains generally need IDNA/punycode conversion, and Unicode local parts require additional rules.
Expecting full RFC 5322 support: Quoted local parts, comments, IP literals, and other specialized formats are intentionally excluded from this practical pattern.
Testing only typical addresses: Include empty input, missing @, repeated dots, leading or trailing dots, invalid domain hyphens, long local parts, and long domains in test cases.
43
How do I implement full-string wildcard regex matching with . and *?
KnownRevise
A dynamic-programming wildcard matcher checks whether the entire input string matches a pattern where . represents one character and * represents zero or more occurrences of the immediately preceding literal character or .. This implements a restricted, regex-style wildcard syntax rather than the complete syntax supported by Python’s re module.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Pattern Semantics
.: Matches exactly one character.
*: Applies to the immediately preceding literal character or . and allows zero or more occurrences.
Full match: The pattern must consume the entire string, not merely a substring.
Literal characters: Every character other than . and * is matched literally.
Invalid pattern: A * without a preceding literal character or . raises ValueError.
For example, a*b matches b, ab, and aab, while .* matches every string, including an empty string.
Dynamic Programming
Let D[i][j] mean that the first i characters of the text match the first j characters of the pattern.
Literal or .: The current characters must match, and the preceding prefixes must also match: D[i][j] = D[i-1][j-1] and pattern[j-1] matches text[i-1].
*: Either the preceding character occurs zero times, or it matches the current text character while the pattern prefix remains active: D[i][j] = D[i][j-2] or (pattern[j-2] matches text[i-1] and D[i-1][j]).
The implementation stores only the previous and current pattern states, reducing memory from a full table to two rows.
Complexity and Approach Comparison
Let n be the text length and m the pattern length.
Approach
Best time
Average time
Worst time
Auxiliary space
When to use
Recursive backtracking
O(n+m)
Input-dependent; O((n+1)^m) is an upper bound
O((n+1)^m)
O(m) recursion stack
For explanation or a simple prototype
Dynamic programming
O(m(n+1))
O(m(n+1))
O(m(n+1))
O(n+1)
For predictable performance and production use
Recursive backtracking can repeatedly explore the zero-occurrence and consume-one-character branches of starred tokens, causing exponential work on ambiguous inputs; its stack holds at most one frame per pattern position. Dynamic programming scans the text once per pattern token, so its best, average, and worst times are the same. Its two Boolean rows require O(n+1) auxiliary space. Input storage is not included in these space figures.
Edge Cases and Walkthrough
An empty pattern matches only an empty string.
An empty string matches patterns such as "", a*, and .*.
A one-character text and pattern are handled normally.
Repeated characters require no special treatment.
Python strings are Unicode sequences, so len() counts Unicode code points; . matches one code point, not necessarily one displayed grapheme.
For text aab and pattern a*b, where dp[j] indicates whether text[:j] matches the processed pattern:
Initially: [True, False, False, False].
After processing a*: [True, True, True, False].
After processing b: [False, False, False, True] (dp[0] becomes False because a literal cannot match an empty prefix).
The final state is True, so the entire text matches.
Code Example
def is_match(text: str, pattern: str) -> bool:
"""Return whether text fully matches a wildcard pattern containing '.' and '*'."""
text_length = len(text)
dp = [False] * (text_length + 1)
dp[0] = True
pattern_index = 0
while pattern_index < len(pattern):
pattern_char = pattern[pattern_index]
if pattern_char == "*":
raise ValueError("'*' must follow a literal character or '.'")
if pattern_index + 1 < len(pattern) and pattern[pattern_index + 1] == "*":
# Process a literal followed by '*' as one pattern token.
next_dp = [False] * (text_length + 1)
next_dp[0] = dp[0]
for text_index in range(1, text_length + 1):
character_matches = (
pattern_char == "." or pattern_char == text[text_index - 1]
)
# Zero occurrences use dp; one more occurrence uses next_dp.
next_dp[text_index] = dp[text_index] or (
character_matches and next_dp[text_index - 1]
)
dp = next_dp
pattern_index += 2
else:
# Update backward so dp[text_index - 1] still represents
# the state before processing the current literal.
for text_index in range(text_length, 0, -1):
dp[text_index] = dp[text_index - 1] and (
pattern_char == "." or pattern_char == text[text_index - 1]
)
dp[0] = False
pattern_index += 1
return dp[text_length]
print(is_match("aab", "a*b")) # True
Common Pitfalls
Partial matching: Returning success when only a prefix matches is incorrect.
Invalid stars: A leading * or consecutive * characters lack a valid operand.
Off-by-one errors: The empty-prefix state must remain initialized correctly.
Unicode assumptions: len() counts code points rather than bytes or user-perceived characters.
Library confusion: Python’s re.fullmatch() supports much richer syntax, including character classes and other quantifiers. Use it when those features are required rather than when this restricted custom matcher is sufficient.
44
How do multilingual strings affect data storage and manipulation?
KnownRevise
Multilingual text should be represented as Unicode, with explicit policies for encoding, normalization, character boundaries, collation, and locale-sensitive behavior. In Python 3.12, str objects contain Unicode code points, whereas bytes objects contain arbitrary byte sequences; they are not interchangeable.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Unicode and Character Boundaries
A multilingual string is not necessarily a sequence of the characters users perceive.
Code point: A numeric Unicode code point. Python’s len() counts code points, including any surrogate code points that may occur in an internally constructed string.
Unicode scalar value: A code point excluding surrogate values. Valid UTF-8 contains scalar values, not lone surrogates.
Grapheme cluster: A user-perceived character that may contain multiple code points. For example, é can be one code point (U+00E9) or two (e followed by U+0301).
Encoded bytes: The representation used for storage or transmission. UTF-8 encodes each Unicode scalar value in one to four bytes.
Consequently, lengths differ depending on whether code points, grapheme clusters, or encoded bytes are measured. Indexing and slicing a Python string operate on code points, not necessarily user-visible characters. Case conversion can also change length, such as when ß becomes SS under upper().
Storage and Data Integrity
Store text with a declared encoding: UTF-8 is a common storage and interchange format because it preserves the Unicode code-point sequence and is self-synchronizing. Other encodings may be required by external systems, but the encoding must be recorded.
Define a decoding policy: Strict decoding rejects malformed byte sequences with UnicodeDecodeError. If replacement behavior is required, use an explicit error handler and account for possible data loss.
Normalize at boundaries: Apply NFC during ingestion and before comparison or indexing when canonically equivalent representations such as Café and Café should be treated identically. NFKC is useful for compatibility matching but can erase distinctions between compatibility variants.
Define uniqueness rules: Normalize before inserting into a uniqueness constraint or creating an exact-match index if canonically equivalent values must not be stored separately.
Choose collation deliberately: Binary ordering, code-point ordering, and locale-aware linguistic ordering are different. Database sorting also depends on the database, encoding, and configured collation.
Avoid fixed-byte character assumptions: Use text or Unicode-aware database types rather than assuming one character occupies a fixed number of bytes.
Preserve originals when necessary: Keeping the original and normalized forms is useful for auditing, but the two representations must remain semantically consistent.
Manipulation and Complexity
Python strings are immutable, so concatenation creates a value and slicing creates a copy. Let n and m be string lengths, k be a slice’s length, and N be the total size of all parts. Extra space excludes the original input but includes newly allocated output; no recursion stack is involved.
Operation
Best time
Average time
Worst time
Extra space
Reason
len(text)
O(1)
O(1)
O(1)
O(1)
Python stores the string length
Iterate over text
O(n)
O(n)
O(n)
O(1)
Each code point is visited once
left + right
O(n + m)
O(n + m)
O(n + m)
O(n + m)
A new immutable string is allocated
text[start:end]
O(1) for an empty/full-slice special case
O(k)
O(k)
O(k)
A partial slice copies k code points
Repeated text += value with copying on every append
O(N)
O(N²)
O(N²)
O(N) peak
Cumulative lengths may be copied repeatedly; runtimes may optimize some cases
"".join(parts)
O(N)
O(N)
O(N)
O(N)
The parts are copied once into the result
For Unicode-safe processing:
Use ord() and chr() for code-point arithmetic.
Use str.casefold() for caseless comparison when appropriate, while remembering that it is Unicode-wide rather than fully locale-aware.
Use unicodedata.normalize() for canonically equivalent text.
Use a dedicated grapheme-segmentation library when processing depends on user-perceived characters.
Build large strings with a list and join() rather than relying on repeated +=.
Common Pitfalls and Interview Tips
Assuming len() counts visible characters: It counts code points; grapheme-cluster counting requires another approach.
Comparing raw strings without normalization: Canonically equivalent inputs can compare unequal.
Slicing at code-point offsets: An offset that appears correct visually may split a grapheme cluster.
Using repeated string concatenation: Copying can produce quadratic time; use a list and join() for predictable performance.
Ignoring collation and bidirectional text: Correctly stored text can still be searched, sorted, or displayed incorrectly.
Mutating input unexpectedly: Transformations should generally return new values while preserving the original when required.
Interviewers commonly follow up by asking how to count user-perceived characters, compare accented text, select a database encoding, or make Unicode processing safe across an API boundary.
45
How does locale-specific sorting affect string comparison?
KnownRevise
Locale-specific sorting orders strings according to linguistic rules for a particular language and region rather than by raw Unicode code point. These rules can affect case, accents, normalization, contractions, and the relative order of characters.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Locale-Aware Versus Code-Point Ordering
A locale-sensitive comparison uses a collation defined by settings such as language, region, and tailoring. By contrast, direct code-point ordering compares the numeric values of characters.
String behavior
Code-point ordering
Locale-aware ordering
Case
Uses code-point values
May place lowercase before uppercase
Accents
Always distinguishes é from e
May treat them as equal at a lower comparison strength
Normalization
Requires pre-normalization
Usually handles equivalent representations
Character order
Fixed by Unicode
Can differ by locale
Linguistic contractions
Not interpreted
May use locale-specific contraction rules
For example, Python compares str values by Unicode code point, not by locale:
"A" < "a" # True
A collation for English can instead consider a and A equal except at a tertiary level. Likewise, composed "é" (é) and decomposed "é" (e followed by a combining accent) may compare differently by code point but equal under a normalized collator.
What Locale Settings Change
A locale commonly includes language, country, and optional tailoring rules. Collation behavior may also depend on:
Case level: Whether uppercase and lowercase letters are equivalent.
Strength: Which differences are considered primary, secondary, or tertiary.
Tailoring: Custom rules for a language, organization, or product.
The result can be either a simple ordering result or several comparison levels. For example, a collator might report that two strings are equal at the accent level but different at the case level.
Effects on Algorithms
Locale-aware comparison changes both the result and potentially the cost of an algorithm. For strings of length at most k:
Operation
Time complexity
Extra space
Code-point comparison
O(k)
O(1)
Typical locale-aware comparison
O(k)
Usually O(1)
Generate one sort key per string
O(nk) typical
Up to O(nk) for stored keys
Standard comparison-based sort
O(kn log n) best, average, worst
O(n) plus stored keys
The space figures exclude the original input. Exact collator complexity depends on the locale and implementation; some also maintain temporary state.
For a standard merge sort, the number of comparisons is O(n log n) in the best, average, and worst cases. An adaptive sort can have an O(n) best case for comparison count, but locale-key generation still takes O(nk).
Precomputing sort keys is often preferable to invoking a full collator during every comparison. Each string is transformed once, and the sort can then compare the resulting keys. This works only when the collation provides a consistent ordering and independent keys.
Other algorithms are affected as follows:
Binary search: Safe only if comparisons use the same total ordering used to build the collection. With locale comparisons taking O(k), search takes O(k log n).
Deduplication: Locale-aware equality may group strings that are not identical by code point, such as case variants.
Set and map keys: Choosing a locale-sensitive key can intentionally merge different spellings, but it may surprise callers expecting exact string identity.
Substring searches: A pattern can match according to linguistic rules rather than exact code-point sequences.
Swedish Collation Example
Consider these strings:
ä, å, a, z, ö
Code-point ordering compares the Unicode values and produces:
a, z, ä, å, ö
Under standard Swedish collation, å, ä and ö are separate letters that come after z in that order, producing:
a, z, å, ä, ö
This demonstrates why a result can be correct for one locale but incorrect for another. Changing only the locale changes the comparator’s ordering.
Common Pitfalls
Using raw Unicode order for user-facing lists: Users often expect locale-aware ordering, especially for names.
Changing locale during an operation: Sorting, searching, and deduplication must use a consistent collation.
Ignoring normalization: Equivalent Unicode representations can behave differently without normalization.
Assuming Python’s str comparison is locale-aware: Python uses code-point ordering. The locale module provides limited strxfrm support, but behavior depends on the operating system’s locale facilities; full Unicode collation generally requires an ICU-based implementation.
Applying locale sorting to identifiers: Stable code-point ordering is usually better for identifiers, database keys, and protocols.
Breaking search assumptions: A comparator must provide a consistent total preorder; inconsistent case or accent rules can cause binary search and sorting to fail.
46
How can you minimize memory usage with large strings?
KnownRevise
Minimizing memory usage requires incremental processing: scan or transform data in bounded chunks, avoid unnecessary copies, and stream results instead of retaining every intermediate value. Python strings are immutable, so techniques that appear to modify a string in place usually create another string.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Techniques
Process in chunks: Read or examine a fixed number of characters at a time. This keeps temporary working memory bounded even when the total data is very large.
Use generators: A generator yields one result at a time, allowing callers to process data without storing a complete collection.
Avoid unnecessary conversions: Operations such as upper(), lower(), split(), strip(), and regular-expression findall() create new objects and may consume substantial memory.
Avoid repeated concatenation: Building a string with text += part in a loop can take O(n^2) time because strings are immutable. Collect fragments in a list and use ''.join(parts).
Be careful with slicing: text[start:end] creates a copy of the selected characters, requiring O(k) space for a slice of length k.
Stream large outputs: Write processed data incrementally rather than accumulating a large final string, especially when the output is sent to a file or network stream.
For truly large data, reading from a file line by line or in fixed-size blocks is usually better than first loading the entire file into one string.
Memory and Time Complexity
The following complexities distinguish auxiliary memory from the memory occupied by the original input:
Approach
Time
Auxiliary space
When to use
One direct character scan
O(n)
O(1)
The complete string already exists in memory
Chunked processing
O(n)
O(k)
Temporary working memory must be bounded
split() or findall()
O(n)
O(n)
The result set or tokens fit comfortably in memory
Building with repeated +=
O(n^2) worst case
O(n)
Avoid this pattern
Building fragments then join
O(n)
O(n) including output
A complete final string is required
Here, n is the number of characters and k is the chunk size. If the input string itself is counted, total space is O(n+k) for chunked processing and O(n) for a direct scan. Best, average, and worst-case running time are all O(n) for a complete scan because every character may need to be examined.
Unicode and Character Boundaries
Python str values represent Unicode text, and len(text) counts Unicode code points, not bytes or user-perceived characters. An emoji may consist of multiple code points, while its UTF-8 encoding may occupy several bytes.
A str chunk size is measured in code points.
A bytes chunk size is measured in bytes.
Slicing a str never splits an individual code point, but it may split a multi-code-point grapheme cluster.
When decoding byte chunks, use codecs.getincrementaldecoder() so a multi-byte UTF-8 character split across chunk boundaries is decoded correctly.
Code Example
This implementation counts words using bounded chunks while preserving state across chunk boundaries:
from collections.abc import Iterator
def iter_chunks(text: str, chunk_size: int = 64_000) -> Iterator[str]:
"""Yield bounded-size chunks of a string."""
if chunk_size <= 0:
raise ValueError("chunk_size must be positive")
for start in range(0, len(text), chunk_size):
yield text[start:start + chunk_size]
def count_words(text: str, chunk_size: int = 64_000) -> int:
"""Count whitespace-separated words without storing all tokens."""
word_count = 0
inside_word = False
for chunk in iter_chunks(text, chunk_size):
for character in chunk:
if character.isspace():
inside_word = False
elif not inside_word:
word_count += 1
inside_word = True
return word_count
print(count_words("alpha beta gamma", chunk_size=6)) # 3
For chunk_size=6, the example is processed as follows:
Chunk
Characters
Words found
Total
1
"alpha "
alpha
1
2
" beta "
beta
2
3
"gamma"
gamma
3
The inside_word flag prevents duplicate counting for consecutive whitespace and handles words that cross chunk boundaries.
Common Pitfalls
Repeated concatenation: Do not build a large result with text += fragment; use a list with ''.join(fragments) or stream the output.
Accidental copies: Slicing, splitting, regular-expression findall(), and case conversion allocate additional strings.
Ignoring Unicode boundaries: Code-point, grapheme, and byte boundaries are different; chunking bytes requires safe incremental decoding.
Dropping boundary state: Track continuation state such as whether a word is still open when processing chunks.
Trying to mutate strings: Python strings are immutable; create a new value or use a mutable buffer only when appropriate.
Assuming zero-copy everywhere: memoryview can avoid copying byte data, but it does not provide a mutable text string or understand Unicode boundaries.
47
How does the Flyweight Pattern reduce memory usage for strings?
KnownRevise
The Flyweight Pattern shares one canonical string object among many consumers instead of storing separate copies of identical text. This is especially effective for large datasets containing repeated values such as status labels, category names, or error messages.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
The pattern separates string data into two parts:
Intrinsic state: immutable content shared by every occurrence, such as "ACTIVE".
Extrinsic state: information that differs between occurrences, such as a record’s position, formatting, or language.
A flyweight factory maintains a pool of canonical objects. When a caller requests a string, the factory returns the existing object if equivalent content is already present.
For example, if one million records contain the label "ACTIVE", all records can reference the same string while storing their record-specific information separately. Because Python strings are immutable, sharing them cannot cause one consumer’s changes to affect another.
Memory and Complexity
Let:
n be the number of input strings.
S be their total number of characters.
U be the number of unique strings.
L be the maximum string length.
Approach
Time complexity
Space complexity
When to use
Store every occurrence separately
O(S) to construct
O(S)
Every value is unique or duplication is small
Canonicalize with a flyweight factory
Best/average O(S + n)
O(S_unique + n + U)
Many repeated strings share the same content
For the flyweight approach:
Best and average time: O(S + n) because hashing examines the characters, and dictionary operations take average O(1) time after hashing.
Worst time: O(S + nUL) under adversarial hash collisions, when multiple keys may be compared and each comparison can examine up to L characters.
Space: O(S_unique + n + U), counting the canonical content, result references, and factory table, but not the original input.
If the original input remains alive, total memory is O(S + n + U); the saving is realized only after duplicate input strings can be released.
Code Example
def canonicalize_strings(values: list[str]) -> list[str]:
"""Return references to one canonical object for each distinct string."""
pool: dict[str, str] = {}
result: list[str] = []
for value in values:
canonical = pool.setdefault(value, value)
result.append(canonical)
return result
canonical = canonicalize_strings(["ACTIVE", "ACTIVE", "DRAFT"])
print(canonical[0] is canonical[1]) # True
The factory dictionary maps each unique value to its canonical object. Duplicate inputs then reuse the first equal object.
Common Pitfalls
Unbounded pools: Interning unique values such as UUIDs or request-specific messages can increase memory usage rather than reduce it.
Assuming all equal Python strings are already shared: Python may intern identifiers and some constant strings, but dynamically constructed strings are not guaranteed to share storage.
Confusing characters and bytes: Python str represents Unicode text, while bytes represents raw bytes; len(str) counts Unicode code points, not encoded bytes.
Ignoring the retained input: Duplicate strings are not freed until references to the original copies are released.
Sharing mutable wrapper state: Only immutable content should be shared. Record-specific state must remain outside the shared object.
Interview Tips
Explain that the Flyweight Pattern trades a small lookup cost for reduced object allocation and memory pressure. In Python, sys.intern can canonicalize selected strings, but it should be used selectively rather than for every dynamically generated value.
Common follow-up questions include how to bound the pool, how to handle Unicode normalization, whether equal strings are guaranteed to use the same object, and how the pattern differs from ordinary object pooling. The key distinction is that flyweights share immutable intrinsic state, while a general object pool can reuse mutable objects whose state must be reset.
48
Detect if a string has any duplicate characters without using additional data structures.
KnownRevise
Without a set or dictionary there are three classic answers: compare every pair of characters (O(n²) time, O(1) space), sort and compare neighbours (O(n log n) time, in place only where strings are mutable), or, when the input is limited to a small alphabet such as lowercase a–z, use one integer as a bit vector (O(n) time, O(1) space). State which constraint you are assuming before you code.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Approaches
Approach
Time
Extra space
When to use
Hash set (for comparison)
O(n) average
O(k)
When extra structures are allowed
Nested loops over all pairs
O(n²)
O(1)
Any character set, strict “no extra memory” rule
Sort, then compare neighbours
O(n log n)
O(1) in C++/Java char arrays; O(n) in Python
Mutable character arrays
Bit vector in one integer
O(n), at most 27 steps for a–z
O(1)
Input known to be lowercase ASCII
Python strings are immutable, so “sort in place” is not possible: sorted(text) builds a new list of n characters. That is why the Python answer is either the nested loop or the bit vector. The input itself is not counted in these space figures, and neither approach recurses.
How the Bit Vector Works
Map each letter to an offset: ord(character) - ord("a") gives 0 for a and 25 for z.
Bit offset of the integer seen records whether that letter has appeared.
seen & (1 << offset) tests the bit; seen |= 1 << offset sets it.
26 letters fit in one machine word in any language, so the “structure” is a single integer.
By the pigeonhole principle, a lowercase string longer than 26 characters must contain a duplicate, so the loop never runs more than 27 times. The bit-vector check is therefore O(min(n, 26)), which is O(1) for that alphabet.
Code Example
def has_duplicates_lowercase(text: str) -> bool:
"""Bit-vector check for strings made only of lowercase ASCII letters a-z."""
seen = 0
for character in text:
offset = ord(character) - ord("a")
if not 0 <= offset < 26:
raise ValueError("expected lowercase ASCII letters only")
bit = 1 << offset
if seen & bit:
return True
seen |= bit
return False
def has_duplicates_any(text: str) -> bool:
"""Pairwise check for any characters, using O(1) extra space."""
for i in range(len(text)):
for j in range(i + 1, len(text)):
if text[i] == text[j]:
return True
return False
print(has_duplicates_lowercase("interview")) # True
print(has_duplicates_lowercase("python")) # False
print(has_duplicates_any("Ab-1b")) # True
Walkthrough
has_duplicates_lowercase("abca"), showing the low four bits of seen:
Step
Character
Offset
Bit tested
seen after
Result
1
a
0
not set
0001
continue
2
b
1
not set
0011
continue
3
c
2
not set
0111
continue
4
a
0
set
0111
True
Complexity by Case
Nested loops: best case O(1) when the first two characters match; worst case O(n²) when all characters are distinct, since every pair is compared (n(n−1)/2 comparisons).
Bit vector: best case O(1); worst case 27 iterations for valid input, then the 27th letter must repeat.
Sort and scan: O(n log n) in every case for a comparison sort.
Edge Cases
Empty string and one character: no duplicates; both functions return False.
Case:"Aa" has no duplicate under exact comparison. Lowercase the input first only if the problem says case does not matter.
Characters outside a–z: the bit-vector version raises instead of giving a silently wrong answer; use the nested loop for general text.
Unicode:ord() returns code points up to 0x10FFFF, so a bit vector for all of Unicode would need up to 1.1 million bits, which is no longer “no extra space”.
Common Pitfalls
Starting the inner loop at j = 0, which compares a character with itself.
Calling sorted() in Python and claiming O(1) space.
Using a bit vector without stating the alphabet assumption.
Overflow in Java or C++ when the alphabet exceeds 32 or 64 letters: switch to a long, an array of words, or the nested loop.
A common follow-up: “what if the input is a stream you cannot store?” Then a bit vector or set is the only option, because you cannot revisit earlier characters.
49
Check for an Isomorphic String relationship between two given strings.
KnownRevise
Two strings are isomorphic when you can replace characters in the first to get the second, where the mapping is one-to-one: each character always maps to the same character, and no two characters map to the same one. "egg" and "add" are isomorphic (e→a, g→d); "foo" and "bar" are not, because o would need to map to both a and r. The standard solution uses two hash maps, one in each direction, and runs in O(n).
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Why Two Maps
One map (source → target) catches a character mapping to two different targets. It does not catch two characters mapping to the same target:
"badc" and "baba": the forward map b→b, a→a, d→b, c→a has no conflict, yet b and d both map to b.
The backward map (target → source) catches this: b was already claimed by b, so d cannot claim it.
Both directions must stay consistent for the strings to be isomorphic. A different-length pair is never isomorphic.
Approaches
Approach
Time
Extra space
When to use
Compare every pair of positions (i, j)
O(n²)
O(1)
Only to explain the definition
Two dictionaries (forward and backward)
O(n)
O(k)
Standard interview answer
Compare first-occurrence patterns
O(n)
O(n)
When you want a canonical “shape” to group many strings
k is the number of distinct characters, bounded by the alphabet size (O(1) for ASCII). Dictionary operations are O(1) on average, so the scan is O(n). The input is not counted in the space figure, and there is no recursion. Best, average and worst case differ only in when the loop exits early: a mismatch at index 0 stops in O(1).
Code Example
def is_isomorphic(source: str, target: str) -> bool:
"""Return True if a one-to-one character mapping turns source into target."""
if len(source) != len(target):
return False
forward: dict[str, str] = {}
backward: dict[str, str] = {}
for left, right in zip(source, target):
if forward.setdefault(left, right) != right:
return False
if backward.setdefault(right, left) != left:
return False
return True
def shape(text: str) -> tuple[int, ...]:
"""Pattern of first-occurrence indexes; isomorphic strings share a shape."""
first_seen: dict[str, int] = {}
return tuple(first_seen.setdefault(character, len(first_seen)) for character in text)
print(is_isomorphic("egg", "add")) # True
print(is_isomorphic("foo", "bar")) # False
print(is_isomorphic("badc", "baba")) # False
print(shape("paper"), shape("title")) # (0, 1, 0, 2, 3) (0, 1, 0, 2, 3)
setdefault stores the mapping the first time a character appears and returns the existing value afterwards, so one call both records and checks.
Walkthrough
is_isomorphic("badc", "baba"):
Step
Pair
forward after
backward after
Result
1
b, b
{b: b}
{b: b}
consistent
2
a, a
{b: b, a: a}
{b: b, a: a}
consistent
3
d, b
{…, d: b}
b already maps to b, not d
False
Edge Cases
Empty strings: two empty strings are isomorphic (the loop never runs).
One character each: always isomorphic.
Different lengths: rejected before the loop.
Repeated characters: handled by the maps, which is the whole point of the check.
Identical strings: isomorphic through the identity mapping.
Unicode: the maps work on code points, so accented letters and emoji are handled; a character built from several code points is compared code point by code point.
Common Pitfalls
Using only one map, which wrongly accepts "badc" and "baba".
Comparing len(set(source)) == len(set(target)) alone. It is necessary but not sufficient: "aab" and "abb" both have two distinct characters, yet they are not isomorphic.
Using fixed 256-element arrays in Python without saying the input is assumed ASCII.
Follow-ups interviewers ask: group a list of words by isomorphism (use shape() as a dictionary key), or the related “word pattern” problem, where the target is a list of words instead of characters.
50
Implement a string tokenizer that splits a string on multiple delimiters.
KnownRevise
A multi-delimiter tokenizer scans the string once and cuts a token every time it meets any delimiter from a given set. When delimiters can be longer than one character (->, ::), it must try the longest delimiter first at each position, so -> is not read as - followed by >.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
How It Works
Remove duplicate delimiters and sort them by length, longest first.
Keep two indexes: start (where the current token began) and i (the scan position).
At each i, check whether any delimiter starts there with text.startswith(delimiter, i).
On a match, emit text[start:i] as a token, jump i past the delimiter and set start = i.
With no match, advance i by one character.
At the end, emit the remaining text[start:].
A keep_empty flag decides what happens between two adjacent delimiters ("a,,b"): keep an empty token like str.split(",") does, or skip it like str.split() does for whitespace.
Approaches
Approach
Time
Extra space
When to use
Replace every delimiter with one, then split()
O(n·d) plus a new string per pass
O(n) per pass
Quick scripts with a few single-character delimiters
Single scan, longest delimiter first
O(n·d·L) worst case
O(n) for the tokens
Interviews, multi-character delimiters, full control over empties
re.split with an escaped alternation
O(n·d·L) typical
O(n)
Production code where a regex is acceptable
Here n is the text length, d the number of delimiters and L the longest delimiter. With only single-character delimiters held in a set, the scan is O(n). Space counts the output tokens, which together hold up to n characters; the input is not counted. There is no recursion.
Code Example
import re
def tokenize(text: str, delimiters: list[str], keep_empty: bool = False) -> list[str]:
"""Split text on any of the delimiters, trying the longest delimiter first."""
if not delimiters or any(not delimiter for delimiter in delimiters):
raise ValueError("delimiters must be a non-empty list of non-empty strings")
ordered = sorted(set(delimiters), key=len, reverse=True)
tokens: list[str] = []
start = 0
i = 0
while i < len(text):
match = next((delimiter for delimiter in ordered if text.startswith(delimiter, i)), None)
if match is None:
i += 1
continue
if keep_empty or i > start:
tokens.append(text[start:i])
i += len(match)
start = i
if keep_empty or start < len(text):
tokens.append(text[start:])
return tokens
def tokenize_regex(text: str, delimiters: list[str]) -> list[str]:
"""Same result as tokenize(keep_empty=False), using re.split."""
ordered = sorted(set(delimiters), key=len, reverse=True)
pattern = "|".join(re.escape(delimiter) for delimiter in ordered)
return [token for token in re.split(pattern, text) if token]
print(tokenize("a, b;;c->d", [",", " ", ";", "->"])) # ['a', 'b', 'c', 'd']
print(tokenize("a,,b", [","], keep_empty=True)) # ['a', '', 'b']
print(tokenize_regex("a, b;;c->d", [",", " ", ";", "->"])) # ['a', 'b', 'c', 'd']
re.escape matters: without it a delimiter such as . or | would be read as regex syntax.
Walkthrough
tokenize("a, b;;c->d", [",", " ", ";", "->"]):
i
Character
Delimiter found
Token emitted
New start
1
,
,
a
2
2
space
space
none (empty)
3
4
;
;
b
5
5
;
;
none (empty)
6
7
-
->
c
9
end
d
Edge Cases
Empty input: returns [], or [''] with keep_empty=True (the same as "".split(",")).
Only delimiters:",,," returns [] when empties are skipped.
Leading or trailing delimiters: produce empty tokens only when keep_empty=True.
Overlapping delimiters:- and -> both listed; longest first picks ->.
Duplicates in the delimiter list: removed by set().
Unicode: indexes count code points, so a multi-code-point emoji is never a delimiter unless listed exactly.
Common Pitfalls
Checking short delimiters before long ones, which splits -> into two cuts.
Building each token with += one character at a time; slice text[start:i] once instead.
Forgetting the last token after the loop ends.
Passing raw delimiters to re.split without re.escape.
Interviewers often follow up with quoted fields ("a,b",c), which need a small state machine that ignores delimiters inside quotes, or with streaming input, where a delimiter can be split across two chunks.