What are binary-heap insertion, root-removal and root-peek costs?

O(log n), O(log n) and O(1), respectively, when no array resize is needed. A resize can cost O(n).

How do path compression, union by rank and union by size differ?

Path compression redirects visited nodes to the root. Rank links a lower-rank root below a higher-rank root; size links the smaller set below the larger. Rank need not equal the current height.

What are pre-order, in-order and post-order traversal orders for a binary tree?

Pre-order: node → left → right. In-order: left → node → right. Post-order: left → right → node.

For nonnegative functions f and g, what does f(n) ∈ O(g(n)) mean?

There are constants c > 0 and n₀ ≥ 0 such that f(n) ≤ c·g(n) for every n ≥ n₀.

What answers can an insertion-only Bloom filter give?

A negative result means the item was not inserted; a positive result means it may have been. Hashes set bits in a bit array, so false positives are possible but false negatives are not if the state is intact.

How does separate chaining resolve hash collisions?

Each bucket holds a collection of entries with that bucket index, often a linked list. Distinct keys sharing a bucket remain separate entries.

What does in-order traversal of a BST with distinct keys produce?

All keys in strictly increasing order, visiting n nodes in O(n) time.

Why can a doubly linked list delete a given node in O(1)?

Its previous and next links let it reconnect the neighbors directly. Update head/tail when needed; no search for the predecessor is required.

Order these growth rates from slowest to fastest as n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n.

1 < log n < n < n log n < n² < 2ⁿ < n! asymptotically.

What is the amortized cost of union/find with path compression and union by rank?

O(α(n)) per operation, where α is the inverse Ackermann function and n is the number of elements. Initialization is O(n); the bound concerns a sequence, not a constant worst-case cost for every call.

What is a trie, and when is lookup of an L-character key O(L)?

A prefix tree stores keys along character paths, with markers for complete keys. Lookup is O(L) when each next-character transition takes O(1).

What two properties define a binary min-heap?

It is a complete binary tree, and every parent key is no greater than its child keys. Thus the root holds a minimum.

What ordering invariant defines a BST with distinct keys?

At every node, all keys in the left subtree are smaller and all keys in the right subtree are larger. The rule applies recursively.

Why is indexed access in a fixed-size array O(1)?

Equal-sized slots are contiguous, so address(i) = base + i·slot_size. This assumes constant-time address arithmetic.

How do linear and quadratic probing differ in open addressing?

Entries stay in the array. For table size m and initial index h, probes use (h+i) mod m or (h+c₁i+c₂i²) mod m, respectively. Quadratic probing needs suitable parameters.

How do BST search, insertion and deletion depend on tree height h?

They take O(h) time. A balanced tree has h = O(log n); a chain has h = O(n). Expected O(log n) requires assumptions such as random insertion order.

How is an AVL left-right insertion imbalance repaired?

First rotate the left child left; then rotate the unbalanced node right.

How does a circular array queue avoid shifting after dequeue?

Front and rear indices wrap around modulo capacity. Dequeue advances the front index, so freed slots can be reused without moving other elements.

In a zero-indexed heap array of length n, where are node i’s parent and children?

Parent: ⌊(i−1)/2⌋ for i>0. Children: 2i+1 and 2i+2, only if those indices are below n. Index 0 has no parent.

What properties should a hash function have for table lookup?

It must be deterministic and distribute the expected keys well. Hashing fixed-size keys can be O(1); hashing a new L-character string is typically O(L).

What are a queue’s access rule and typical operation costs?

FIFO: enqueue at the rear and dequeue at the front. Both are O(1) with head/tail links or a fixed-capacity circular buffer; shifting an array makes dequeue O(n).

What are the expected and worst-case operation costs for a separate-chaining hash table?

With bounded load, well-distributed hashes and constant-cost key operations, lookup/deletion are expected O(1). Insertions with geometric growth are expected amortized O(1). A chain of n colliding keys can make an operation O(n).

How does level-order traversal visit a binary tree?

Use a FIFO queue to visit one depth level at a time. Enqueue each node’s left child before its right child to obtain left-to-right order.

What is the AVL balance condition?

At every node, height(left) − height(right) ∈ {−1, 0, 1}. The tree also satisfies the BST ordering invariant.

How do O, Ω and Θ differ?

They give asymptotic upper, lower and tight bounds, respectively. They describe a specified cost function; O does not itself mean worst case.

Compare head insertion and indexed access in a singly linked list and a dynamic array.

List: O(1) head insertion and O(n) indexed access. Array: O(n) head insertion and O(1) indexed access; front insertion shifts elements.

Which color rules keep a red-black BST balanced?

Nodes are red or black; the root and NIL leaves are black. Red nodes have no red children. Every path from a node to a descendant NIL leaf has the same number of black nodes. These rules bound height by O(log n).

What do find and union do in a disjoint-set structure?

find(x) returns the representative of x’s set. union(x,y) merges their sets if they differ; if they are already together, the partition is unchanged.

How does a stack work, and when are its operations O(1)?

LIFO: the most recently pushed item is popped first. At a linked-list head, push, pop and peek take O(1); array resizing can make a single push O(n).

What is the cost of bottom-up heap construction from n items?

O(n). Most nodes are near the leaves and need little sifting; summing work by node height gives a linear total.

What is a hash table’s load factor, and why may it resize?

α = n/m: n stored entries and m buckets or slots. Crossing an implementation’s threshold may trigger a larger table and rehashing; 0.75 is not universal.

With capacity doubling, what is the amortized cost of appending to a dynamic array?

O(1) per append. A resize can cost O(n), but n appends from an empty array cost O(n) in total.

Data Structures, Arrays, Hash Maps, Trees & Big-O Complexity

Undergraduate review requiring basic programming: 32 cards on arrays, lists, hashing, trees, heaps, tries, Union–Find, Bloom filters and complexity.

Level: basic
Languages: en → en
Cards: 32
Markdown: Data Structures, Arrays, Hash Maps, Trees & Big-O Complexity (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	What are binary-heap insertion, root-removal and root-peek costs?	O(log n), O(log n) and O(1), respectively, when no array resize is needed. A resize can cost O(n).
2	How do path compression, union by rank and union by size differ?	Path compression redirects visited nodes to the root. Rank links a lower-rank root below a higher-rank root; size links the smaller set below the larger. Rank need not equal the current height.
3	What are pre-order, in-order and post-order traversal orders for a binary tree?	Pre-order: node → left → right. In-order: left → node → right. Post-order: left → right → node.
4	For nonnegative functions f and g, what does f(n) ∈ O(g(n)) mean?	There are constants c > 0 and n₀ ≥ 0 such that f(n) ≤ c·g(n) for every n ≥ n₀.
5	What answers can an insertion-only Bloom filter give?	A negative result means the item was not inserted; a positive result means it may have been. Hashes set bits in a bit array, so false positives are possible but false negatives are not if the state is intact.
6	How does separate chaining resolve hash collisions?	Each bucket holds a collection of entries with that bucket index, often a linked list. Distinct keys sharing a bucket remain separate entries.
7	What does in-order traversal of a BST with distinct keys produce?	All keys in strictly increasing order, visiting n nodes in O(n) time.
8	Why can a doubly linked list delete a given node in O(1)?	Its previous and next links let it reconnect the neighbors directly. Update head/tail when needed; no search for the predecessor is required.
9	Order these growth rates from slowest to fastest as n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n.	1 < log n < n < n log n < n² < 2ⁿ < n! asymptotically.
10	What is the amortized cost of union/find with path compression and union by rank?	O(α(n)) per operation, where α is the inverse Ackermann function and n is the number of elements. Initialization is O(n); the bound concerns a sequence, not a constant worst-case cost for every call.
11	What is a trie, and when is lookup of an L-character key O(L)?	A prefix tree stores keys along character paths, with markers for complete keys. Lookup is O(L) when each next-character transition takes O(1).
12	What two properties define a binary min-heap?	It is a complete binary tree, and every parent key is no greater than its child keys. Thus the root holds a minimum.
13	What ordering invariant defines a BST with distinct keys?	At every node, all keys in the left subtree are smaller and all keys in the right subtree are larger. The rule applies recursively.
14	Why is indexed access in a fixed-size array O(1)?	Equal-sized slots are contiguous, so address(i) = base + i·slot_size. This assumes constant-time address arithmetic.
15	How do linear and quadratic probing differ in open addressing?	Entries stay in the array. For table size m and initial index h, probes use (h+i) mod m or (h+c₁i+c₂i²) mod m, respectively. Quadratic probing needs suitable parameters.
16	How do BST search, insertion and deletion depend on tree height h?	They take O(h) time. A balanced tree has h = O(log n); a chain has h = O(n). Expected O(log n) requires assumptions such as random insertion order.
17	How is an AVL left-right insertion imbalance repaired?	First rotate the left child left; then rotate the unbalanced node right.
18	How does a circular array queue avoid shifting after dequeue?	Front and rear indices wrap around modulo capacity. Dequeue advances the front index, so freed slots can be reused without moving other elements.
19	In a zero-indexed heap array of length n, where are node i’s parent and children?	Parent: ⌊(i−1)/2⌋ for i>0. Children: 2i+1 and 2i+2, only if those indices are below n. Index 0 has no parent.
20	What properties should a hash function have for table lookup?	It must be deterministic and distribute the expected keys well. Hashing fixed-size keys can be O(1); hashing a new L-character string is typically O(L).
21	What are a queue’s access rule and typical operation costs?	FIFO: enqueue at the rear and dequeue at the front. Both are O(1) with head/tail links or a fixed-capacity circular buffer; shifting an array makes dequeue O(n).
22	What are the expected and worst-case operation costs for a separate-chaining hash table?	With bounded load, well-distributed hashes and constant-cost key operations, lookup/deletion are expected O(1). Insertions with geometric growth are expected amortized O(1). A chain of n colliding keys can make an operation O(n).
23	How does level-order traversal visit a binary tree?	Use a FIFO queue to visit one depth level at a time. Enqueue each node’s left child before its right child to obtain left-to-right order.
24	What is the AVL balance condition?	At every node, height(left) − height(right) ∈ {−1, 0, 1}. The tree also satisfies the BST ordering invariant.
25	How do O, Ω and Θ differ?	They give asymptotic upper, lower and tight bounds, respectively. They describe a specified cost function; O does not itself mean worst case.
26	Compare head insertion and indexed access in a singly linked list and a dynamic array.	List: O(1) head insertion and O(n) indexed access. Array: O(n) head insertion and O(1) indexed access; front insertion shifts elements.
27	Which color rules keep a red-black BST balanced?	Nodes are red or black; the root and NIL leaves are black. Red nodes have no red children. Every path from a node to a descendant NIL leaf has the same number of black nodes. These rules bound height by O(log n).
28	What do find and union do in a disjoint-set structure?	find(x) returns the representative of x’s set. union(x,y) merges their sets if they differ; if they are already together, the partition is unchanged.
29	How does a stack work, and when are its operations O(1)?	LIFO: the most recently pushed item is popped first. At a linked-list head, push, pop and peek take O(1); array resizing can make a single push O(n).
30	What is the cost of bottom-up heap construction from n items?	O(n). Most nodes are near the leaves and need little sifting; summing work by node height gives a linear total.
31	What is a hash table’s load factor, and why may it resize?	α = n/m: n stored entries and m buckets or slots. Crossing an implementation’s threshold may trigger a larger table and rehashing; 0.75 is not universal.
32	With capacity doubling, what is the amortized cost of appending to a dynamic array?	O(1) per append. A resize can cost O(n), but n appends from an empty array cost O(n) in total.