home
›
cheatsheets
›
computer_science
›
arrays_strings_hashing
Free to read Every card and diagram, and Quiz me
2
Free account Star cards. Your Quiz me marks are kept, so next time you drill just what you missed
3
Pro All 85 answers on this sheet, My sheet across every topic, and PDFs
A free account keeps your stars and Quiz me marks. Pro adds all 85 answers on this sheet, My sheet across every topic, and PDFs.
/
Read
Quiz me
Comfortable
Compact
0
Click any code to copy it
Done 0 /0
To review 0
On this sheet
01 Arrays in memory02 Dynamic arrays03 Strings04 Hash maps & sets05 Hash functions06 Collisions07 Keys & equality08 Load factor & resizing09 Attacks & concurrency10 Hashing at scale
The model An array is one contiguous block of same-size slots. base + i * size finds any slot in one step, so indexing is O(1). An insert in the middle shifts every later element, so it's O(n). When a dynamic array fills up, it copies everything into a block a constant factor bigger, often 1.5x or 2x. That append is O(n), but copies get rarer as it grows, so appends average O(1). That is amortized O(1). A string is an array of characters. Java, Python and JavaScript make it immutable, so every edit builds a new string. That's why += in a loop is O(n^2). A hash table is an array plus a hash function that turns each key into a slot index. Lookups average O(1). Collisions and a crowded table push them toward O(n). The hash only picks the bucket, and equality confirms the key. So equal keys must hash the same, and a stored key must never change. A lookup hashes the key, picks a slot, jumps there in O(1) and checks the key. A collision tries the next entry. Growing rehashes every key in O(n).
Arrays in memory why reads by index are fast and inserts are slow How an array sits in memory Say how an array is stored One contiguous block of same-size slots, with no gaps or pointers.
Find element i's address base + i * size Same cost at any index.
Weigh an array's strengths and costs Fast reads by index and in order. Slow inserts in the middle.
Tip The block is one piece. You usually can't grow it in place, because the memory after it may be taken.
Array operation costs Add to the end a.append(x) Amortized O(1). Nothing has to shift.
Insert or delete in the middle a.insert(k, x) del a[k] O(n). Everything after k shifts.
Check whether an array holds a value x in a O(n). It checks slot by slot.
Delete when order doesn't matter a[k] = a[-1] a.pop() O(1). The last element fills the gap.
Tip If you check membership often, copy the values into a set once. Each check then averages O(1).
Trap Swap-remove moves the last element to a new index. Anything holding its old index is now wrong.
Zero-based indexes and bounds Explain why indexes start at zero An index is an offset from the start. In C, a[i] means *(a + i).
Index past the end in Java or Python Java throws ArrayIndexOutOfBoundsException . Python raises IndexError.
Read or write past the end in JavaScript A read returns undefined. A write grows the array.
Index past the end in C or C++ Undefined behavior. It may read garbage, crash or seem to work.
Trap In C, a write past the end can overwrite nearby data. Attackers use these buffer overflows to run their own code.
Arrays and the CPU cache Explain why arrays scan fast Each cache line holds several elements, and the prefetcher reads ahead.
Choose an array or a linked list An array, unless you splice often at a node you already hold.
Loop over a 2D grid Rows outer, columns inner. Most languages store it row by row.
Trap Looping column by column jumps a whole row each step. On a large grid, nearly every read misses the cache.
Dynamic arrays how a list grows, and what one append costs Grow a dynamic array Tell a static array from a dynamic one A static array's size is fixed. A dynamic one, like list, resizes.
Tell length from capacity Length counts stored elements. Capacity counts allocated slots.
Append to a full array Copy everything to a bigger block. That one append is O(n).
Explain amortized O(1) append Doubling makes resizes rare. All the copying adds up to under 2n.
Tip When you know the count, presize with new ArrayList<>(n) in Java or v.reserve(n) in C++.
Grow and shrink the capacity Grow by 2x Fewer copies, but up to half the memory can sit unused.
Grow by 1.5x Less waste, but more copies. Java's ArrayList grows by half.
Grow by a fixed amount, like 10 slots Resizes stay frequent, so n appends copy O(n^2) in total.
Decide when to shrink Halve the capacity once it's a quarter full, not half.
Trim spare capacity in Java list.trimToSize() ArrayList never shrinks on its own.
Tip With 2x, a new block is bigger than all the freed ones combined, so the allocator can't reuse them. With 1.5x it can.
Trap If you shrink at half full, adding and removing one element at that boundary resizes every time.
Arrays near a billion elements Estimate a resize's memory peak Old and new buffers coexist. A billion 8-byte items peak near 24 GB.
Spot the index overflow A 32-bit index overflows past about two billion elements.
Allocate one huge block Free memory may be split into gaps that are all too small.
Scan an array of objects Slots point all over the heap, so reads miss the cache.
Tip Past this scale, use chunked structures, not one flat array. For hot scans, store plain values.
Strings why edits copy, and what a length counts Immutable strings Change or append to a string s[:i] + c + s[i+1:] It builds a new string, O(n).
Say why strings are immutable Lock-free sharing between threads, and a hash you compute once.
Copy a large string or array cheaply Copy-on-write. Copies share a buffer until the first write.
Tip Java, Python, JavaScript, C# and Go strings are immutable. C++ std::string and Rust's String are mutable.
Trap Under copy-on-write, a loop of small edits can copy the whole buffer on nearly every step.
Build a string in a loop Append with += in a loop s += c O(n^2). Each += copies the string so far.
Build a string in Python "".join(parts) O(n). Join once at the end.
Build a string in Java sb.append(c) sb.toString() O(n) in total.
Edit the middle of a huge text A rope, a tree of chunks. O(log n) edits, slower scans.
Tip For two or three fixed pieces, plain + is fine.
Trap V8 hides the += cost by linking pieces into a rope. Other runtimes copy, so don't count on it.
Length, bytes and encoding Count a string's bytes in UTF-8 len(s.encode("utf-8")) 1 to 4 per code point. "café" is 5.
Read s.length in JavaScript It counts UTF-16 code units. Many emoji count as 2.
Get a C string's length strlen(s) O(n). It scans for the zero byte. A stored length is O(1).
Trap Cutting by bytes or code units can split a character and corrupt the text.
Compare and hash strings Compare two strings for equality O(n). A long shared prefix means a full scan.
Skip the full comparison Unequal lengths or cached hashes prove a mismatch fast.
Avoid rehashing a long key Hashing is O(k). Cache the result, since strings never change.
Substrings, interning and short strings Take a substring without copying A view is O(1), but it keeps the whole parent alive.
Intern a string sys.intern(s) Equal text shares one object, so equality is a pointer check.
Store a short string without a heap allocation Small-string optimization, up to 15 or 22 bytes inline.
Tip Small-string optimization costs a bigger object and a branch on every access.
Trap Interning mostly unique strings only grows the pool. In .NET, interned strings usually live until the process exits.
Hash maps & sets store and find by key in O(1) on average Hash map basics Insert, update or delete a key d[k] = v del d[k]
Look up a key d.get(k) k in d d[k] raises KeyError if missing.
Explain average O(1) lookup The hash leads to one bucket, which holds about one entry.
Name a hash map's costs No order, memory on empty slots, and a slow insert on resize.
Tip Use a hash map first for "seen it before?" checks and "how many of each?" counts.
Solve problems with sets and maps Choose a set or a map A set holds keys only. A map also holds a value for each key.
Remove duplicates and keep the order list(dict.fromkeys(xs)) O(n). set(xs) loses the order.
Find two numbers that add up to a target One pass. Look up target-x among values seen so far.
Check whether two words are anagrams Counter(a) == Counter(b) O(n). Sorting is O(n log n).
Trap Broken equality lets duplicates into a set, and crafted keys can make one pass O(n^2).
Iteration order Loop over a plain hash map Expect no order. Python's dict and JavaScript's Map keep insertion order.
Keep insertion order in Java new LinkedHashMap<>() It links the entries in order, at two extra pointers each.
Build an LRU cache in Java new LinkedHashMap<>(16, 0.75f, true) true turns on access order. Evict in removeEldestEntry .
Change a Java map while you loop over it The next step throws ConcurrentModificationException .
Trap Code that relies on hash map order has a silent bug. A resize or a random seed can reorder it.
Hash map or tree map Query a key range or the nearest key tm.subMap(lo, hi) tm.higherKey(x) A tree map like TreeMap, O(log n).
Tip A tree map also guarantees O(log n) with hostile keys. For plain lookups by key, a hash map is faster.
Hash functions how a key becomes a bucket number From key to bucket Turn a key into a bucket index hash(key) % n Hash it, then take the remainder by the bucket count.
Explain why collisions happen Far more keys than buckets, so some must share. That's the pigeonhole principle.
Tell a hash function from a hash table The function makes a number. The table stores the entries.
Trap The same key must always give the same hash, or you can't find what you stored.
Write a simple hash function def sum_hash(key, size): ignores order return sum(ord(c) for c in key) % size def poly_hash(key, size): order counts h = 0 for c in key: h = 31 * h + ord(c) as in Java's String.hashCode return h % size
Spot the flaw in summing character codes It ignores letter order, so "cat" and "act" always collide.
Good hash, bad hash Name what makes a hash function good An even spread, cheap to compute, and the same output for the same key.
Size the table to a power of two hash(key) & (n - 1) A fast mask, but it keeps only the low bits. Mix the hash first.
Size the table to a prime hash(key) % p It hides a weak hash, but division is slower.
Trap Real keys aren't random. Sequential IDs or similar strings can push a naive hash toward O(n).
What hashing is for Say what hashing is Data of any size in, a short fixed-size value out. Same input, same hash.
Tell hashing from encryption Hashing has no key to decrypt with, and SHA-256 can't be reversed.
Name where hashing is used Maps, caches, duplicate checks, checksums, Git, passwords.
Estimate when 64-bit hashes collide After about 2^32, or four billion keys. That's the birthday bound.
Trap Lookup hashes are easy to collide on purpose. Use a keyed or cryptographic hash for attacker input.
Collisions what a table does when two keys share a bucket Chaining or open addressing 0 1 2 cat act chaining act lands in bucket 1 with cat and joins that bucket's list.hash(act) cat dog act probing act hashes to cat's slot, steps past dog, and lands in the next free slot.Resolve collisions by chaining Each bucket holds a list. A lookup walks it, comparing keys.
Resolve collisions by open addressing Every entry lives in the array. A taken slot sends the key on.
Store more entries than buckets Only chaining can. Open addressing needs a load factor below 1.
Delete from an open-addressed table Leave a tombstone, or later lookups stop too early.
Tip Java's HashMap chains. Python's dict uses open addressing.
Trap Tombstones count as full while probing. They pile up until a rehash clears them.
Probe sequences Probe linearly (h(k) + i) % m The cache-friendly default.
Probe quadratically (h(k) + i * i) % m Keys with the same home slot share a path.
Probe with double hashing (h(k) + i * h2(k)) % m The best spread. h2 must never be 0.
Explain primary clustering Filled slots merge into runs. A key that lands in a run walks to its end.
Trap Quadratic probing can skip empty slots. Use a prime table size and keep it under half full.
How each scheme uses memory and cache Compare chaining and open addressing on memory Chaining pays a pointer per entry. Open addressing leaves 30 to 50% of slots empty.
Explain why open addressing is often faster Probes stay in one array, while chain hops can miss the cache.
Estimate probes at a high load factor About 1/(1-a) at load a. 2 probes at 0.5, 10 at 0.9, 100 at 0.99.
Tip Below about 0.7 load, open addressing usually wins on lookups.
Robin Hood, cuckoo and perfect hashing Even out probe lengths Robin Hood hashing. A key that has probed farther takes the slot.
Guarantee O(1) lookups in the worst case Cuckoo hashing. Each key has two slots, and a lookup checks only those.
Look up a fixed key set with no collisions A minimal perfect hash. n keys fill n slots, but any change means a rebuild.
Trap A cuckoo insert can evict keys in a loop and force a rebuild. Two tables stall near 50% full.
Keys & equality the hash picks a bucket, and equality finds the key hashCode and equals Tell apart two keys in one bucket The map compares them with equals. The hash only picks the bucket.
State the hashCode and equals contract Equal objects need equal hash codes. The reverse isn't required.
Override equals in Java return Objects.hash(name, id); Also override hashCode from the same fields.
Change a key after storing it It now hashes elsewhere, so lookups miss the entry. Nothing throws.
Trap Override equals without hashCode, and equal objects get different default hashes. A lookup for one misses the other.
Write a hash map's put def put(self, key, val): b = self.table[hash(key) % len(self.table)] for pair in b: if pair[0] == key: equality confirms the key pair[1] = val; return b.append([key, val]); self.size += 1 if self.size > 0.75 * len(self.table): self.grow() double, then rehash all
Write get and delete Walk the same bucket, comparing keys. Delete unlinks the match.
List the design decisions Collision scheme, resize threshold, bucket count and a seeded hash.
Load factor & resizing when a table grows, and what growing costs Load factor Work out the load factor entries / buckets 6 entries in 8 buckets is 0.75.
Say when Java's HashMap grows Past 0.75 load. It doubles and rehashes every entry.
Say when Python's dict grows At two thirds full. It roughly doubles too.
Set the limit for open addressing Lower, often 0.5 to 0.7. Probe runs get long fast.
Tip At 0.75, most buckets hold zero or one entry. Java's docs call it a good tradeoff between time and space.
Resize a hash table Pay for one resize O(n) for that insert, but doubling keeps it rare. Average stays O(1).
Resize without a long pause Keep both tables and move a few buckets per operation, like Redis.
Grow without rehashing every key Extendible or linear hashing. Each step splits just one bucket.
Trap Amortized means on average. The one insert that triggers a resize still stalls, and latency-sensitive systems feel it.
Attacks & concurrency keep O(1) under hostile keys and many threads When O(1) becomes O(n) Name what makes lookups O(n) A poor hash, a table left too full, or an attacker's colliding keys.
Spot a hash-flooding attack Crafted keys share one bucket, so n inserts cost O(n^2).
Defend with a keyed hash Use SipHash with a secret per-process seed.
Tip Java 8+ turns a long chain into a tree, so a flooded bucket of comparable keys costs O(log n).
Trap A leaked seed lets attackers precompute collisions again. Keep it secret and unique to each process.
Share arrays and maps across threads Make a hash map fast under many threads new ConcurrentHashMap<>() Per-bin locks and lock-free reads.
Make a dynamic array thread-safe Lock it, or swap buffers atomically and free old ones after readers leave.
Spot false sharing Threads write neighbors on one cache line, which bounces between cores.
Fix false sharing Pad each thread's hot data onto its own cache line.
Trap One global lock is safe, but every reader waits in line behind it.
Hashing at scale keys across servers, and sets too big to store Spread keys over servers Move few keys when a node joins or leaves Consistent hashing. A node change moves about 1/N of keys, not nearly all.
Even out load on the ring Give each server many ring positions, called virtual nodes.
Move a key range to a new node Stream that range while the old and new owners both serve reads.
Tip A key goes to the first server clockwise from it on the ring.
Trap Consistent hashing doesn't fix a hot key. One popular key still overloads one shard.
Bloom filters and HyperLogLog Test membership in a fraction of the memory A Bloom filter. No means absent and yes means maybe, at a few bits per key.
Count distinct items without storing them HyperLogLog. A few kilobytes estimate a billion items within about 2%.
Count distinct items across shards Merge the per-shard sketches. Nothing is counted twice.
Trap Past its planned size, a Bloom filter's false-positive rate climbs. A basic one can't delete keys.
Nothing matches. Try a shorter word, or clear the search.
Practice Guided practice One question at a time, with the ones you miss coming back. Practice 85 interview questions Full answers, from beginner to expert.
Found this useful? Pass it on.
Share on LinkedIn
Share on X
Copy link
This sheet stays free. With Pro , you can:
Every answer on this sheet. Read the full answer to all 85 questions it links, not just the 11 free ones.My sheet. The cards you star and the ones you miss in Quiz me, from every sheet, on one page to quiz and print.PDFs. Download this sheet and My sheet, laid out for A4, with every question a link to its answer.The rest of Pro. Every answer in the question library, and 1,000 AI credits a month.
