Skip to content

Arrays, Strings, Hash Maps, and Sets

Arrays, strings, hash maps, and sets appear in almost every interview because they are the building blocks behind larger algorithms and everyday backend code. The important skill is not memorizing that a list is fast or a map is constant time. It is choosing a representation that makes the required operations cheap while preserving the correct semantics.

Start with one question: which operations must this solution perform, how often, and on what kind of input? The answer determines whether you need indexed access, ordered traversal, duplicate detection, frequency counts, or fast key lookup. It also exposes constraints that Big-O alone cannot show, such as Unicode text, memory growth, hash-key stability, and language-specific behavior.

1. Translate the problem into operations

Before choosing a data structure, write down:

  • The input size and whether it can grow without a fixed upper bound.
  • Whether order and duplicate values must be preserved.
  • Which operations dominate: indexing, scanning, insertion, deletion, membership, or grouping.
  • Whether keys are immutable and have stable equality and hash behavior.
  • Whether text is ASCII, arbitrary Unicode, normalized, or user-visible.
  • How much additional memory is acceptable.

A single scan with a hash map may beat repeated array scans, but adds memory, hashing work, and collision risk.

2. Arrays and dynamic arrays

An array stores elements in indexed order. With a conventional contiguous array, accessing element i is constant time because the address can be calculated from the base address and element width. Searching for an arbitrary value is linear unless the data is sorted or another index is maintained.

Most interview languages expose a dynamic-array abstraction:

Language Common type Important detail
Python list Resizable sequence of object references
Go []T slice A view described by a pointer, length, and capacity over a backing array
Java ArrayList<T> Resizable array of references; primitive arrays avoid boxing

The usual costs are:

Operation Typical cost Reason
Read or replace by index O(1) Direct position lookup
Scan for a value O(n) May inspect every element
Append Amortized O(1) Most appends use spare capacity; occasional growth copies elements
Insert or remove near the front O(n) Later elements must shift
Copy or slice into a new array O(k) The selected elements are copied

Amortized constant time does not mean every append is constant time. A growth operation can copy the existing elements, but geometric capacity growth spreads that cost across many appends. If the final size is known, preallocating capacity can reduce reallocations; it does not change the cost of inserting in the middle.

Go slices deserve special attention. Assigning a slice copies its small header, not its backing array. Two slices can therefore refer to the same storage. An append may reuse that storage or allocate a new backing array when capacity is insufficient. Code that keeps aliases to a slice must not assume that appending through one alias is invisible to the other. When ownership matters, copy deliberately.

Use a dynamic array when iteration order and indexed access matter. Do not use it for repeated membership checks on a large unsorted collection: membership in a list is linear in the number of elements. A set or map is often the better representation for that operation.

3. Strings are sequences with encoding rules

Strings are usually immutable sequences. Building a new string from repeated concatenation can copy an increasingly large prefix each time, making a loop quadratic. Prefer a builder or collect-and-join approach when assembling many fragments:

parts = ["order", "-", "created"]
message = "".join(parts)

The word character is ambiguous in software. A string may be measured as bytes, Unicode code points, or grapheme clusters (roughly, user-perceived characters). These are not interchangeable:

Language String model What a basic length or index means
Python Immutable sequence of Unicode code points len(s) counts code points
Go Immutable sequence of bytes, conventionally UTF-8 for text len(s) counts bytes; range decodes code points and reports byte offsets
Java Immutable UTF-16 sequence length() counts UTF-16 code units; codePoints() iterates code points

A code point is still not necessarily one displayed character. A letter plus a combining mark can be two code points but one grapheme cluster. Emoji sequences can contain several code points joined into one grapheme cluster. If a product requirement says “limit a display name to 20 characters,” decide whether that means bytes, code points, or grapheme clusters. Enforce a separate byte limit when storage or transport size must be bounded.

Text comparison also needs a policy. Canonically equivalent text can have different code-point sequences, and case conversion can be locale-sensitive or expand one code point into several. Normalize when the product requires canonical equivalence, choose locale-aware or Unicode case-folding rules deliberately, and never assume lowercasing is a universal identity function. Preserve the original text when it is needed for display or audit.

For algorithm questions, state the unit being processed. Python iteration visits code points. Go's range visits decoded code points, but its index is a byte offset. Java's charAt returns a UTF-16 code unit; use codePoints() when the algorithm is defined over code points. Grapheme-aware processing requires a Unicode segmentation implementation rather than any of these basic loops.

4. Hash maps: trade memory for lookup speed

A hash map stores key-value pairs. It applies a hash function to a key, uses the result to locate a candidate bucket or probe sequence, then uses equality to identify the matching key. Collisions are normal: different keys can produce the same hash. A correct implementation resolves them rather than assuming hashes are unique.

For a well-distributed hash function, lookup, insertion, and deletion are typically expected O(1). This is an average-case model, not a worst-case guarantee. Heavy collisions can make operations approach O(n), and resizing can make an individual insertion expensive even though insertion is amortized constant time. Maps also consume more memory than a compact array because they maintain spare capacity and indexing metadata.

The key contract matters more than the syntax:

  • If two keys compare equal, they must produce equal hashes.
  • A key's equality and hash behavior must remain stable while it is stored.
  • Hashing and equality should be deterministic, bounded, and inexpensive.
  • Never treat a hash value as a unique identifier or security token.

A mutable key is dangerous when a mutation changes fields used by hashing or equality. The entry may remain in the bucket chosen by its old hash while future lookups calculate a different hash. Prefer immutable value keys.

Language rules differ. Python dictionaries preserve insertion order, but that does not make every dictionary operation ordered by value. Go map iteration order is unspecified, and map key types must be comparable. Java HashMap makes no iteration-order guarantee; its keys must obey the equals/hashCode contract. Do not write portable logic that relies on the iteration order of a hash map.

5. Sets: model membership and uniqueness directly

A set is a collection of distinct values. It is useful when the question is “have I seen this value?” rather than “what value belongs to this key?” Membership, insertion, and deletion are typically expected O(1), with the same hashing caveats as maps.

Common set operations include:

  • Union: values present in either set.
  • Intersection: values present in both sets.
  • Difference: values present in the first set but not the second.
  • Symmetric difference: values present in exactly one set.

A set does not preserve the input sequence's order as a general contract. If stable output order is required, pair a set for membership with a list for output:

def stable_unique(values):
    seen = set()
    result = []
    for value in values:
        if value not in seen:
            seen.add(value)
            result.append(value)
    return result

This takes expected O(n) time and O(u) additional space, where u is the number of distinct values. It requires hashable values. If elements are unhashable or equality is expensive, choose a different key or accept a different complexity.

6. Patterns worth recognizing

Frequency counting. Count occurrences in one pass with a map. This supports anagram checks, majority candidates, inventory summaries, and event aggregation. The time is expected O(n); space is O(k), where k is the number of distinct keys.

counts = {}
for value in values:
    counts[value] = counts.get(value, 0) + 1

First unique value. Build a frequency map in one pass, then scan the original sequence again and return the first index whose count is one. The second pass is necessary because an early value cannot be known to be unique until the full input has been counted. This takes expected O(n) time and O(k) space, where k is the number of distinct values.

Stable deduplication. Use a set to answer membership and a list to preserve first-seen order. Do not convert directly to a set when the result order is part of the contract.

Grouping by key. Map each key to a collection of matching records. In a backend batch job, grouping events by tenant or status can be done in one pass. The map gives expected O(1) group lookup, but the grouped values still consume O(n) memory. For data larger than the process budget, stream or partition the work rather than loading every record into one map.

The tested implementations use the same stable-deduplication and first-unique-index contracts in all three languages:

7. Complexity and correctness

For these structures, state both the cost and the assumption:

Task Typical time Extra space
Scan an array of n elements O(n) O(1)
Count frequencies for k distinct values O(n) expected O(k)
First unique value with a frequency map O(n) expected O(k)
Stable deduplication of n values O(n) expected O(u)
Compare two strings of length n O(n) Usually O(1) extra for comparison
Count Unicode code points in UTF-8 text O(n) bytes O(1) if streamed

These are common implementation costs, not universal language guarantees. For example, Python's published built-in complexity estimates describe CPython; the Go specification defines map and slice semantics without promising a particular lookup complexity, while Java's HashMap documents constant-time basic operations under a suitable hash distribution.

When giving a complexity answer, define n, k, and u. Separate auxiliary space from the input and output. If a hash map is involved, say expected or average-case and acknowledge the collision worst case. If a string operation copies data, include the copied length in the cost.

Correctness needs an invariant, not just a complexity table. For first-unique lookup, the frequency map is complete before the second scan begins; returning the first count-one value therefore preserves input order. For stable deduplication, the output contains each value exactly once, in the order of its first occurrence in the input.

8. Production considerations

These structures also appear on request paths, in caches, parsers, and batch processors. A few interview shortcuts become production bugs if their assumptions are left unstated:

  • Unbounded cardinality: a map keyed by user-controlled IDs can grow until the process runs out of memory. Bound its size or lifetime, or use a durable store with an explicit retention policy.
  • Hash flooding: adversarial keys can increase collision work. Use runtime protections, validate input size, and bound CPU and memory exposure; randomized hashing is not a substitute for resource limits.
  • Wrong uniqueness boundary: an in-memory set deduplicates only within that process and its lifetime. It cannot enforce uniqueness across replicas or restarts. Use a database unique constraint or another shared atomic mechanism for durable invariants.
  • Unicode mismatch: two visually identical identifiers may compare differently if normalization policy is absent. Define normalization and case rules at the boundary, and apply them consistently to lookup and uniqueness.
  • Aliasing and concurrency: a Go slice may share backing storage, and mutable collections in any language need an ownership or synchronization policy when shared between goroutines or threads.
  • Premature optimization: a hash map can use substantially more memory than a compact sorted array. For small inputs or read-mostly data, a scan or sort-and-search approach may be simpler and faster in practice. Measure with representative data.

A database index is not the same thing as an in-memory hash map. The database index has durability, concurrency control, query planning, and transaction semantics that an application collection does not provide. Use the collection to solve an algorithmic problem inside one computation; use the database to enforce shared data invariants.

9. Interview questions with reasoned answers

Q1. Why is dynamic-array append amortized O(1), not worst-case O(1)?

Most appends use spare capacity. When capacity is exhausted, the implementation allocates a larger backing array and copies existing elements, which costs O(n). Geometric growth spreads that occasional cost across many appends, so the average cost per append over a sequence is constant.

Q2. When would you choose a set instead of a list?

Choose a set when uniqueness or repeated membership checks dominate and order is irrelevant. Choose a list when order, positional access, or duplicates matter. If both membership and stable output order matter, use a set plus a list.

Q3. Is hash-map lookup guaranteed O(1)?

No. It is typically expected O(1) under suitable hash distribution and bounded key operations. Collisions can degrade performance, and resizing can make an individual operation expensive. State the average-case assumption and the worst-case risk.

Q4. Why must equal keys have equal hashes?

The map uses the hash to choose where to search. If equal keys can produce different hashes, the lookup may search a different location and fail to find an existing equal key. The reverse is not required: unequal keys may share a hash.

Q5. Why can a mutable object be a bad map key?

If a field used by hashing or equality changes after insertion, the key's lookup behavior changes while the stored entry remains in its original location. Use immutable keys or remove and reinsert after a controlled change.

Q6. What is the difference between a Unicode code point and a user-perceived character?

A code point is a Unicode scalar value. A grapheme cluster is a sequence that text segmentation treats as one user-perceived character. Combining marks and emoji sequences can contain multiple code points in one grapheme cluster. Choose the unit required by the product.

Q7. Why does len mean different things for Python, Go, and Java strings?

Python counts code points. Go counts UTF-8 bytes. Java counts UTF-16 code units. None of these automatically counts grapheme clusters. The algorithm must choose its unit explicitly.

Q8. Can an in-memory set enforce a unique username across multiple service replicas?

No. Each process has independent memory, and its contents disappear on restart. Enforce the invariant in a shared durable system, typically with a database unique constraint, and handle the conflict atomically.

Practical checklist

  • Identify the operations and input constraints before choosing a structure.
  • Use arrays for ordered indexed data; account for shifting and copying.
  • Treat Go slices as views over backing arrays, not independent arrays.
  • Define whether string processing uses bytes, code points, or grapheme clusters.
  • Use maps for key lookup and frequency counts; state expected-case assumptions.
  • Use sets for membership and uniqueness; preserve order separately when required.
  • Keep hash keys immutable and equality/hash behavior consistent.
  • Bound memory and input cardinality in production.
  • Test empty input, duplicates, negative values, Unicode, and all-duplicate cases.
  • Explain correctness invariants as well as time and auxiliary space.

References