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 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.

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.

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.

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).

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.

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.

How is an AVL left-right insertion imbalance repaired?

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

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).

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 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.

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).

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.

What is the AVL balance condition?

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

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).

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.

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 does in-order traversal of a BST with distinct keys produce?

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

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.

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.

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 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 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.

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.

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.

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 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 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 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).

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.

Data Structures, Complexity Analysis (Big-O) & Core Algorithms

Foundational computer science review for AI engineering: 32 cards on arrays, linked lists, hash tables, binary search trees, heaps, tries, Union–Find, Bloom filters, and asymptotic Big-O complexity.

Level: basic
Languages: en → en
Cards: 32
Markdown: Data Structures, Complexity Analysis (Big-O) & Core Algorithms (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	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.
2	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.
3	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.
4	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.
5	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).
6	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.
7	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.
8	How is an AVL left-right insertion imbalance repaired?	First rotate the left child left; then rotate the unbalanced node right.
9	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).
10	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₀.
11	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.
12	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).
13	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.
14	What is the AVL balance condition?	At every node, height(left) − height(right) ∈ {−1, 0, 1}. The tree also satisfies the BST ordering invariant.
15	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).
16	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.
17	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.
18	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.
19	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.
20	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.
21	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.
22	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).
23	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.
24	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.
25	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.
26	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.
27	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.
28	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.
29	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).
30	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).
31	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.
32	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.