Data Structures Flashcards

Question

What is the **Multiset / Bag ADT**?

Answer 1

A set that allows duplicates, but still doesn’t care about order. ## Footnote Multisets track the frequency of elements.

Answer 2

* `add(x)` * `removeOne(x)` * `count(x)` ## Footnote These operations manage the multiplicity of elements in the multiset.

Answer 3

Key → value mapping, where keys are (usually) unique. ## Footnote Maps allow retrieval of values based on unique keys.

Answer 4

* `put(k, v)` / `insert` / `update` * `get(k)` * `remove(k)` * `containsKey(k)` ## Footnote These operations manage key-value pairs in the map.

Answer 5

average O(1) ## Footnote This indicates that hash maps provide average constant time complexity for these operations.

Answer 6

A collection where each element has a priority and you always remove the **extremal** one first (min or max). ## Footnote Priority queues manage elements based on their priority rather than their order of arrival.

Answer 7

* `insert(x, priority)` * `findMin` / `findMax` * `extractMin` / `extractMax` ## Footnote These operations manage elements based on their priority.

Answer 8

O(log n) ## Footnote This indicates logarithmic time complexity for inserting elements into the priority queue.

Answer 9

Structure that maintains a partition of elements into **disjoint groups**, with fast `findWhichGroup(x)` and `mergeGroups(x, y)`. ## Footnote This structure is useful for managing connectivity in graphs.

Answer 10

* `makeSet(x)` * `find(x)` * `union(x, y)` ## Footnote These operations manage the groups and their relationships.

Answer 11

Amortized nearly O(1) per op ## Footnote This indicates very efficient operations for managing disjoint sets.

Answer 12

Nodes with parent-child relationships; often used as a **search** or **hierarchical** ADT. ## Footnote Trees are useful for representing hierarchical data.

Answer 13

* `insert(k, v)` * `delete(k)` * `find(k)` * traversals: inorder, preorder, postorder ## Footnote These operations manage the elements and structure of the tree.

Answer 14

Vertices + edges; general relationships, not just trees. ## Footnote Graphs are used to model complex relationships between elements.

Answer 15

* Add/remove vertex/edge * `neighbors(v)` ## Footnote These operations manage the vertices and edges in the graph.

Answer 16

Structures designed to answer **geometric / range queries** efficiently. ## Footnote These structures are optimized for spatial data and queries.

Answer 17

Structures that support queries like sets/maps, but with controlled errors for huge scale. ## Footnote These structures are useful in big data contexts where exact answers are less critical.

Answer 18

Backtracking, 'last thing done next' ## Footnote Stacks are used for operations where the last element added is the first to be removed.

Answer 19

Fair scheduling / pipelines / BFS ## Footnote Queues are essential for managing tasks in a first-in-first-out manner.

Answer 20

Membership, uniqueness, set ops ## Footnote Sets are used to store unique elements and perform operations like union and intersection.

Answer 21

Membership + multiplicity (counts) ## Footnote Multisets allow for the storage of duplicate elements with counts.

Answer 22

Key → value lookup ## Footnote Maps are used for associating keys with values for efficient retrieval.

Answer 23

Always handle 'best/cheapest/urgent' first ## Footnote Priority queues are used in scenarios where certain tasks need to be prioritized over others.

Answer 24

Groups/connected-components under merges ## Footnote Disjoint-sets are useful for tracking a set of elements partitioned into disjoint subsets.

Answer 25

Sorted keys + range queries + log-time operations ## Footnote Trees allow for efficient searching, insertion, and deletion operations.

Answer 26

Arbitrary relationships, paths, connectivity ## Footnote Graphs are used to model pairwise relationships between objects.

Answer 27

Nearest neighbors, range queries in multi-dimensional space ## Footnote Spatial indexes optimize queries related to spatial data.

Answer 28

Huge-scale membership/count/frequency with bounded errors ## Footnote Approximate structures are used when exactness is less critical than performance.

Answer 29

* Linear * Hierarchical * General graph ## Footnote These topologies help in understanding how elements are connected and the types of relationships that can be efficiently queried.

Answer 30

* Elements in a single line * Each element (except ends) has one predecessor and one successor ## Footnote Examples include arrays, linked lists, stacks, and queues.

Answer 31

* Sequential processing * Index-based access * FIFO / LIFO disciplines ## Footnote They are simple and have low overhead, especially contiguous arrays.

Answer 32

* Cannot represent branching relationships * Insert/delete costs are O(n) for arrays * Search operations are O(n) unless sorted ## Footnote These limitations affect their expressiveness and efficiency.

Answer 33

* When you mostly scan data * When you push/pop from ends * When you need fast contiguous access ## Footnote They are not suitable for complex relationships or frequent middle insertions.

Answer 34

* Rooted hierarchy * One root, zero or more children per node * No cycles ## Footnote Examples include binary trees, heaps, and tries.

Answer 35

* Hierarchical relationships * Ordered data & range queries * Priority operations ## Footnote They efficiently manage parent-child relationships and allow for logarithmic search operations.

Answer 36

* More complex invariants * Pointer-heavy implementations * Single-parent constraint ## Footnote These factors can impact performance and memory usage.

Answer 37

* When you care about sorted order * When you need logarithmic insert/delete/search * When you require range queries ## Footnote They are suitable for natural hierarchies like organizational charts.

Answer 38

* Vertices (nodes) + edges (connections) * Directed/undirected edges * Can have cycles and arbitrary connections ## Footnote Trees are a special case of graphs.

Answer 39

* Arbitrary relationships * Topology-aware algorithms * Modeling real-world systems ## Footnote They are useful for complex networks and systems with many-to-many connections.

Answer 40

* Highest representational overhead * Algorithmic complexity depends on both V and E * More complex reasoning required ## Footnote These factors can complicate implementation and analysis.

Answer 41

* When you care about connectivity and paths * When there are multiple relationships between entities * When you need non-hierarchical topologies ## Footnote They are ideal for complex systems like social networks.

Answer 42

O(n) ## Footnote This reflects the time taken to process each element in a linear structure.

Answer 43

O(log n) ## Footnote This efficiency is due to the hierarchical nature of trees.

Answer 44

O(V + E) ## Footnote This complexity accounts for both vertices and edges in the graph.

Answer 45

Best cache locality, minimal overhead ## Footnote This makes them ideal for performance-sensitive applications.

Answer 46

Easiest: trivial invariant, simple index arithmetic ## Footnote This simplicity aids in implementation.

Answer 47

* Next in line? → Linear * Natural hierarchy? → Tree * Many-to-many relationships? → Graph ## Footnote These questions guide the selection of the appropriate data structure.

Answer 48

How the bytes are laid out and linked together ## Footnote Different strategies massively change performance, memory use, and complexity.

Answer 49

* Access time * Insert/delete behavior * Cache / memory behavior * Overhead & complexity * Typical use cases ## Footnote These axes help evaluate the efficiency and suitability of various storage strategies.

Answer 50

* Elements stored in one continuous block of memory * Dynamic versions over-allocate and resize when needed ## Footnote Examples include C arrays, std::vector, Java ArrayList, and Python list.

Answer 51

O(1) ## Footnote Access is calculated using the formula: addr = base + i * size.

Answer 52

* Best cache locality * Very simple implementation * Ideal for hot inner loops and dense collections ## Footnote Contiguous storage is efficient for scenarios requiring fast indexed access.

Answer 53

* Expensive insert/delete in the middle * Need to occasionally reallocate & copy * Hard to share subranges without copying ## Footnote These limitations can affect performance in certain use cases.

Answer 54

* Each element lives in its own node allocated separately * Nodes have pointers to neighbors/children ## Footnote Examples include singly/doubly linked lists and pointer-based trees.

Answer 55

O(n) ## Footnote Access requires traversal through the nodes.

Answer 56

* Cheap structural changes * Flexible shapes (trees, graphs) * Can grow/shrink without moving existing nodes ## Footnote This flexibility is beneficial for dynamic data structures.

Answer 57

* Slow iteration compared to arrays * More complex memory management * Easier to produce fragmentation and pointer bugs ## Footnote These issues can lead to performance degradation.

Answer 58

* Use the key directly as an index into an array * Domain must be small and dense enough ## Footnote Examples include boolean visited arrays and simple lookups on small integer keys.

Answer 59

O(1) worst-case ## Footnote This allows for very fast lookups.

Answer 60

* Fastest possible lookup * Simple and predictable ## Footnote Direct-address tables are efficient for small, dense integer keys.

Answer 61

* Not scalable if key space is large * Wastes memory for unused slots ## Footnote These limitations restrict their applicability.

Answer 62

* Uses hash functions to map keys to indices * Two main bucket strategies: separate chaining and open addressing ## Footnote Hash tables are widely used for efficient key-based lookups.

Answer 63

O(1) ## Footnote This assumes a good hash function and load factor.

Answer 64

* Very fast expected time for key lookups * Go-to for membership and dictionaries ## Footnote Hash-based structures are efficient for many applications.

Answer 65

* Quality of hash function matters * Resizing and load-factor tuning add complexity * Poor range/query support ## Footnote These factors can complicate implementation and performance.

Answer 66

* Elements stored in nodes arranged to maintain a search invariant * Each node stores keys and child pointers ## Footnote Examples include balanced trees and B-trees.

Answer 67

O(log n) ## Footnote This allows for efficient operations on sorted data.

Answer 68

* Naturally sorted storage * Efficient range queries * More predictable worst-case than hash tables ## Footnote These features make trees suitable for many applications.

Answer 69

* More complex implementation * Slightly higher constant factors for random lookups * Pointer-heavy versions have poorer cache behavior ## Footnote These drawbacks can impact performance.

Answer 70

* Data grouped into blocks/pages * Minimize I/O operations rather than CPU cycles ## Footnote This strategy is essential for external memory systems.

Answer 71

Measured in page reads/writes ## Footnote This focuses on I/O complexity.

Answer 72

* Essential when data doesn’t fit in RAM * Yields huge performance gains over naive storage ## Footnote Proper use of this strategy can significantly improve efficiency.

Answer 73

* More complex design and tuning * Latency dominated by disks/SSDs ## Footnote These factors can complicate implementation.

Answer 74

* Store data in tightly packed or compressed form * Save memory and improve cache behavior ## Footnote Examples include bitsets and columnar storage.

Answer 75

* Great for huge datasets * Useful for analytics and bitmap indexes ## Footnote This strategy is effective for memory and bandwidth constraints.

Answer 76

* More complex to modify in-place * Harder to implement than plain arrays ## Footnote These challenges can limit usability.

Answer 77

* Expose handles instead of raw pointers * Store objects in arrays or pools ## Footnote This method is common in performance-critical systems.

Answer 78

* Encapsulates storage * Good locality & fewer pointer bugs ## Footnote This approach enhances safety and performance.

Answer 79

* Extra level of indirection * Need to manage handle lifecycle ## Footnote These factors can complicate implementation.

Answer 80

* In-memory: Tuned for CPU and caches * On-disk: Tuned for I/O pattern minimization * Hybrid: Structures in memory mirror disk-backed structures ## Footnote Each type has its own performance characteristics and use cases.

Answer 81

Must rehash when load factor passes a threshold ## Footnote This operation is O(n) but amortized.

Answer 82

Positional / Random Access (by index) ## Footnote This strategy answers the question: *“What’s the element at position i?”*

Answer 83

* Arrays * Dynamic arrays (e.g., `vector`, `ArrayList`, Python `list`) * Fixed-size buffers ## Footnote These structures allow for true random access.

Answer 84

O(1) ## Footnote This indicates true random access efficiency.

Answer 85

* Ideal for numerical work * Excellent cache behavior * Fast sequential scans ## Footnote This access strategy is particularly effective for dense sequences and time series.

Answer 86

* Arbitrary index semantics * O(n) for insert/delete in the middle * Not good for membership checks without extra indexing ## Footnote These weaknesses limit its use in certain scenarios.

Answer 87

Sequential Access (iteration-only) ## Footnote This strategy answers the question: *“Give me the next element, then the next…”*

Answer 88

* Linked lists * Streams * Iterators * File handles ## Footnote These structures support iteration without random access.

Answer 89

O(i) ## Footnote This indicates that accessing elements by index is inefficient.

Answer 90

* Works well with streaming data * Supports iterable-only interfaces ## Footnote This access strategy is beneficial for lazy structures.

Answer 91

* Poor random access * Limited ability for binary search ## Footnote These limitations affect its efficiency in certain applications.

Answer 92

Associative / Keyed Access (by key) ## Footnote This strategy answers the question: *“What is the value associated with key k?”*

Answer 93

* Hash maps * Tree maps * Dictionaries * Symbol tables ## Footnote These structures allow for efficient key-based lookups.

Answer 94

O(1) ## Footnote This indicates average-case efficiency for lookups.

Answer 95

* Natural for configurations and caches * Directly ask for items without scanning ## Footnote This access strategy simplifies lookups.

Answer 96

* No natural order * Poor support for range queries ## Footnote These weaknesses can limit its use in ordered data scenarios.

Answer 97

Membership Access (set-style) ## Footnote This strategy answers the question: *“Is x in this collection?”*

Answer 98

* Sets * Hash sets * Tree sets * Bitsets * Bloom filters ## Footnote These structures are optimized for membership checks.

Answer 99

O(1) ## Footnote This indicates efficient membership verification.

Answer 100

* Fast membership checks * Uniqueness enforcement ## Footnote This access strategy is ideal for deduplication tasks.

Answer 101

* No positional semantics * Not optimized for retrieving ordered elements ## Footnote These limitations affect its utility in certain contexts.

Answer 102

Ordered / Range Access ## Footnote This strategy answers questions like: *“What’s the smallest/largest element?”*

Answer 103

* Balanced BST (AVL, Red–Black) * B-trees * Sorted arrays ## Footnote These structures support ordered queries and range searches.

Answer 104

O(log n) ## Footnote This indicates efficient operations in balanced trees.

Answer 105

* Enables range queries * Supports sorted traversals ## Footnote This access strategy is essential for databases and ordered data.

Answer 106

* More complex than hash sets/maps * Slower for point lookups compared to hash maps ## Footnote These weaknesses can impact performance in certain scenarios.

Answer 107

Priority / Extremal Access ## Footnote This strategy answers the question: *“What’s the highest/lowest-priority element right now?”*

Answer 108

* Heaps (binary heap, Fibonacci heap) * Specialized priority queues ## Footnote These structures are designed for priority management.

Answer 109

O(log n) ## Footnote This indicates efficient priority operations.

Answer 110

* Natural for schedulers and event queues * Avoids full sorts for next best elements ## Footnote This access strategy is useful in pathfinding algorithms.

Answer 111

* Does not allow easy access to arbitrary elements * Not built for general-purpose storage ## Footnote These limitations restrict its application in some contexts.

Answer 112

Hierarchical / Structural Access ## Footnote This strategy answers questions like: *“What are this node’s children/parent?”*

Answer 113

* Trees (DOM, scene graphs, org charts) * File hierarchies ## Footnote These structures naturally express hierarchies.

Answer 114

* Naturally expresses hierarchies and containment * Good for recursive algorithms ## Footnote This access strategy is effective for tree traversals.

Answer 115

* No direct O(1) access by ID unless indexed * Performance depends on tree shape ## Footnote These weaknesses can affect efficiency in certain scenarios.

Answer 116

Graph / Neighbor Access ## Footnote This strategy answers questions like: *“What are the neighbors of this node?”*

Answer 117

* Adjacency lists * Adjacency matrices * Edge lists ## Footnote These structures represent relationships between nodes.

Answer 118

O(V + E) ## Footnote This indicates the efficiency of graph traversal algorithms.

Answer 119

* Represents arbitrary relationships * Supports rich topology queries ## Footnote This access strategy is essential for network analysis.

Answer 120

* More expensive operations than simple maps/sets/lists * Harder to reason about ## Footnote These limitations can complicate implementation.

Answer 121

Spatial / Range-in-Space Access ## Footnote This strategy answers questions like: *“What’s near this point?”*

Answer 122

* k-d trees * Quadtrees * R-trees ## Footnote These structures are optimized for spatial queries.

Answer 123

* Critical for physics engines and GIS * Efficient for collision detection ## Footnote This access strategy is vital for spatial analysis.

Answer 124

* Complex invariants and tuning * Sensitive to skewed distributions ## Footnote These limitations can affect performance in certain applications.

Answer 125

Approximate / Probabilistic Access ## Footnote This strategy answers questions like: *“Is x probably in this set?”*

Answer 126

* Bloom filters * Counting Bloom filters * HyperLogLog ## Footnote These structures provide memory-efficient approximations.

Answer 127

O(1) ## Footnote This indicates efficient operations for large datasets.

Answer 128

* Tiny memory usage * Suitable for big data applications ## Footnote This access strategy is effective for streaming analytics.

Answer 129

* Inexact results * Not suitable for exactness-required scenarios ## Footnote These limitations can restrict its use in certain contexts.

Answer 130

* No defined iteration order * Implementation detail * Must not rely on iteration order ## Footnote Examples include Abstract Set ADT and hash-based sets/maps.

Answer 131

* Fast membership / lookup * Spatial locality / hashing tricks * Free to change layout without breaking callers ## Footnote This allows for efficient implementations focused on membership checks.

Answer 132

* Cannot depend on iteration order for correctness * Cannot do smallest element without extra structure * Cannot do range queries or sorted operations directly ## Footnote These limitations affect how data can be processed.

Answer 133

* Elements come out in the order they were logically inserted * Removing an element preserves the relative order of others ## Footnote Examples include queues and ordered hash maps.

Answer 134

* Intuitive semantics reflecting time of arrival * Great for logs, history lists, task queues ## Footnote This makes it suitable for scenarios where order of arrival matters.

Answer 135

* Extra bookkeeping required * Not sorted by key or value ## Footnote Maintaining insertion order in hash-based structures can increase memory usage.

Answer 136

* Structure assigns each element a position/index * Order defined by those positions ## Footnote Examples include arrays and general lists.

Answer 137

* Simple mental model * Great for random access by index * Useful for dynamic programming tables ## Footnote This allows for efficient access to specific elements.

Answer 138

* Costly insert/remove at arbitrary positions * Index numbers can change after insertions ## Footnote This can complicate the management of data structures.

Answer 139

* Comparison relation defines order * Guarantees iteration in sorted order ## Footnote Examples include sorted arrays and balanced search trees.

Answer 140

* Find min/max easily * Perform range queries * Find predecessor/successor ## Footnote This order allows for efficient querying of data.

Answer 141

* Enables range scans and order statistics * Predictable O(log n) operations in balanced trees ## Footnote This makes it suitable for database-like indexing.

Answer 142

* Maintaining sorted order is costly * Slower for pure key-value lookups than hash maps ## Footnote This can affect performance in certain scenarios.

Answer 143

* Only some elements are ordered relative to others * Typically know the extremal element (min or max) ## Footnote Example includes heaps or priority queues.

Answer 144

* Efficient for needing the best next item * Simpler and faster than full sorted structures ## Footnote This is useful in scheduling and event queues.

Answer 145

* Not good for full sorted iteration * Cannot access arbitrary elements by priority rank directly ## Footnote This limits the flexibility of data access.

Answer 146

* Order defined by how you traverse the structure * Includes depth-first and breadth-first orders ## Footnote Examples include tree and graph traversals.

Answer 147

* Derives different meaningful orders from the same structure * Useful when structural relations matter more ## Footnote This is applicable in scenarios like AST processing and dependency resolution.

Answer 148

* Order is algorithm-dependent * Not a property of the ADT itself ## Footnote This can complicate the understanding of data structure behavior.

Answer 149

* Guaranteed and specified in documentation * Users can rely on it for correctness ## Footnote This ensures reproducible behavior in applications.

Answer 150

* Implementation has some order, but docs say 'don’t rely on it' * Might change in future versions ## Footnote This can lead to brittle bugs if relied upon.

Answer 151

* Some hash maps randomize iteration order * Avoids predictable hashing attacks ## Footnote This discourages reliance on unspecified order.

Answer 152

* Keeps equal keys in their original order * Important for multi-field sort keys ## Footnote Stability affects reproducibility and interpretability in analytics.

Answer 153

* Unordered: No defined iteration order * Insertion order: Reflects time of arrival * Positional: Order = position index * Sorted: Order defined by comparator * Partial: Only extremal elements ordered * Structural: Defined by traversal strategy ## Footnote Each type has its own guarantees, use cases, and limitations.

Answer 154

* Primitive / foundational data structures * Abstract containers / library collections * Composite / engineered data structures * Domain-specific / application-level structures ## Footnote These levels represent a stack of abstraction from raw building blocks to domain-specific constructs.

Answer 155

* Arrays * Dynamic arrays * Linked lists * Basic trees (binary tree, general tree) * Basic graphs (adjacency list/matrix) * Simple stacks/queues ## Footnote These structures live at the lowest level of abstraction and are close to memory representation.

Answer 156

* Live at the lowest level of abstraction * Close to memory representation * Often language/runtime primitives ## Footnote Examples include C arrays, Rust slices, and pointer-based nodes.

Answer 157

* Implement higher-level containers * Used in systems-level or performance-critical code * Control allocation strategy and growth policy ## Footnote Common in embedded systems, OS kernels, and high-performance computing.

Answer 158

* Maximum performance and control * Minimal overhead * Easy to reason about at the CPU/memory level ## Footnote They provide a high degree of efficiency.

Answer 159

* Easy to get wrong (bounds, lifetime, aliasing) * Little semantic information * Lots of boilerplate if used directly everywhere ## Footnote They require careful handling to avoid errors.

Answer 160

* std::vector * std::list * std::map * std::unordered_map * Java List, Set, Map, Queue * Python list, dict, set, deque ## Footnote These collections abstract away implementation details and focus on ADT roles.

Answer 161

* Abstract away implementation details * Provide well-defined semantics * Used at every layer, especially application and business logic ## Footnote They allow developers to think in terms of abstract data types.

Answer 162

* Reuse them instead of re-implementing * Choose container type based on access strategy, order semantics, and complexity needs ## Footnote They are commonly used in general application code.

Answer 163

* Huge productivity gain * Communicate intent clearly * Usually optimized and debugged by experts ## Footnote They simplify development and improve code clarity.

Answer 164

* Less control over internal behavior * May not be tuned for extreme performance * Sometimes need different semantics than offered ## Footnote This can lead to the need for composite structures.

Answer 165

* LRU cache * Indexed priority queues * Multi-index collections * Interval trees * Segment trees * Versioned/persistent structures ## Footnote These structures are built from basic containers to fulfill more complex roles.

Answer 166

* Data-structure-level but not generic enough to be primitive * Encode a compound set of invariants * Typically implemented in libraries or performance-sensitive infrastructure ## Footnote They are tailored to specific performance and semantic requirements.

Answer 167

* Created when standard containers don’t meet access/complexity requirements * Used in backend infrastructure, game/graphics engines, compilers ## Footnote They address specific needs that standard containers cannot fulfill.

Answer 168

* Tailored to specific performance and semantic requirements * Reusable within an organization or domain * Simplify upper layers of application code ## Footnote They provide clear abstractions for application logic.

Answer 169

* More complex to design, implement, and test * Risk of re-inventing buggy versions of known patterns * Misuse can introduce hidden complexity ## Footnote Careful design and documentation are essential.

Answer 170

* Order book in a trading system * Scene graph in a game engine * AST in a compiler * Dependency graph in a build system * Workflow/state machine models * ECS (Entity–Component–System) ## Footnote These structures encode specific problem domains.

Answer 171

* Highly semantics-rich * Designed to answer domain-specific queries efficiently ## Footnote They align closely with domain concepts and improve application logic clarity.

Answer 172

* Exposed directly in the application’s core logic * API is domain-oriented ## Footnote They facilitate clear manipulation of domain concepts.

Answer 173

* Align perfectly with domain concepts * Make application logic much clearer * Highly optimized for specific queries ## Footnote They enhance clarity and efficiency in application development.

Answer 174

* Easy to bake in too much policy or assumptions * Harder for new team members to reason about * May be tightly coupled to one system’s needs ## Footnote Proper documentation is crucial for maintainability.

Answer 175

| Level | Who uses it directly? | Abstraction focus | Typical examples | | ------------------------------------- | ------------------------------------- | --------------------------------- | ------------------------------------------------------------ | | Primitive / foundational | Low-level / performance-critical code | Memory layout, raw operations | arrays, nodes, adjacency lists, raw trees | | Abstract containers / collections | Most general application code | ADT roles (list, set, map) | `vector`, `list`, `dict`, `set`, `TreeMap`, `PriorityQueue` | | Composite / engineered structures | Infra/engine/library devs | Combined invariants & performance | LRU cache, multi-index tables, segment trees, indexed PQs | | Domain-specific structures | Core domain logic / product features | Domain semantics, domain queries | ASTs, order books, scene graphs, ECS stores, workflow graphs | ## Footnote This comparison highlights the differences in usage and focus across the levels.

Answer 176

* Understanding performance and memory behavior * Using collections as a default toolbox * Designing composite structures when needed * Modeling problem space explicitly with domain-level structures ## Footnote Engineers should adapt their approach based on the specific needs of their applications.

Answer 177

collection ## Footnote This indicates a lack of good composite or domain-level structures.

Answer 178

primitive ## Footnote This suggests missing opportunities for reuse and clarity.

Answer 179

* LIFO structure * Interact only with the top * Last thing put on is the first taken off ## Footnote The core idea of a stack is that it follows the Last In, First Out principle.

Answer 180

* `push(x)` * `pop()` * `peek()` / `top()` * `isEmpty()` * Sometimes: `size()` ## Footnote These operations define how you interact with a stack.

Answer 181

* `push`: O(1) * `pop`: O(1) * `peek`: O(1) * `isEmpty`: O(1) * `size`: O(1) ## Footnote All key operations should ideally be constant-time.

Answer 182

O(n) ## Footnote Space complexity can vary based on implementation, typically being array-based or linked list.

Answer 183

* Excellent cache locality * Very small overhead per element * Simple and fast ## Footnote Array-based stacks are the most common in practice.

Answer 184

* Need resizing or fixed capacity * Less flexible for arbitrary growth ## Footnote These limitations can affect performance and usability.

Answer 185

* Conceptually unbounded * Push/pop always O(1) without reallocation ## Footnote Linked-list stacks do not require resizing.

Answer 186

* More memory overhead * Worse cache behavior * More allocation/GC pressure ## Footnote These factors can impact performance and efficiency.

Answer 187

* Creates stack frames on function calls * Stores return address, parameters, local variables * Frames are stored in contiguous memory ## Footnote The call stack is a runtime structure that manages function calls and returns.

Answer 188

* Each recursive call adds a frame * Deep recursion can cause stack overflow ## Footnote Understanding stack depth and limits is crucial for avoiding errors.

Answer 189

* The stack: managed by runtime/OS, stores activation records * A stack: logical structure, can be implemented in various memory types ## Footnote Terminology can be confusing; clarity is important.

Answer 190

* Expression evaluation & parsing * Backtracking * Iterative DFS * Undo/redo systems * Monotonic stacks ## Footnote Recognizing these patterns is essential for software engineering.

Answer 191

Popping or peeking an empty stack ## Footnote Implementations must handle underflow situations appropriately.

Answer 192

Pushing when the stack is full ## Footnote This can occur in fixed-capacity stacks or due to deep recursion.

Answer 193

* Stack: LIFO * Queue: FIFO ## Footnote Stacks are used for nested scopes and backtracking, while queues are used for scheduling and pipelines.

Answer 194

* Explain stacks clearly * Implement a stack * Use stacks for various algorithms * Transform recursion to explicit stack * Debug stack issues * Understand call stack behavior * Recognize advanced patterns ## Footnote Mastery of these skills is crucial for effective software engineering.

Answer 195

A **FIFO** structure: **First In, First Out** ## Footnote You add elements at the back (tail) and remove them from the front (head).

Answer 196

* `enqueue(x)` / `push(x)` / `offer(x)` – add to back * `dequeue()` / `pop()` / `poll()` – remove and return from front * `front()` / `peek()` – see the first element without removing it * `isEmpty()` / `empty()` – check if queue has no elements * Optional: `size()` ## Footnote These operations define how elements are added and removed from the queue.

Answer 197

* `enqueue` → O(1) * `dequeue` → O(1) * `front` / `peek` → O(1) * `empty` / `size` → O(1) ## Footnote This indicates that all core operations can be performed in constant time.

Answer 198

O(n) ## Footnote This reflects the amount of memory required to store the elements in the queue.

Answer 199

* Fixed-size array `A` with capacity `C` * Two indices: `head` (next element to dequeue) and `tail` (next element to enqueue) ## Footnote It allows efficient use of space and time for enqueue and dequeue operations.

Answer 200

* Great cache locality * Minimal overhead per element * Perfect for fixed-capacity, high-throughput systems ## Footnote These advantages make circular buffers suitable for performance-critical applications.

Answer 201

* Fixed capacity unless resizing is implemented * Complexity in handling resizing and index remapping ## Footnote These limitations can affect the flexibility of the queue.

Answer 202

* Struct `Node { value; Node* next; }` * Keep `Node* head` (front) and `Node* tail` (back) ## Footnote This implementation allows for dynamic sizing but has different performance characteristics.

Answer 203

* Conceptually unbounded * Pure O(1) enqueue/dequeue without resizing ## Footnote This allows for flexibility in the number of elements in the queue.

Answer 204

* Heap allocation per node → overhead and fragmentation * Poor cache locality * More GC/allocator pressure ## Footnote These factors can lead to performance issues in certain scenarios.

Answer 205

* **Queue**: FIFO – first in, first out * **Stack**: LIFO – last in, first out ## Footnote This distinction defines their respective use cases in programming.

Answer 206

* **Queue**: fixed roles for ends (enqueue at back, dequeue from front) * **Deque**: can push/pop from both ends ## Footnote Deques provide more flexibility in how elements can be added or removed.

Answer 207

* **Queue**: Order = time of arrival * **Priority queue**: Order = priority; highest/lowest priority served first ## Footnote This affects how tasks are processed based on their urgency.

Answer 208

* One or more producers enqueue tasks * One or more consumers dequeue tasks and process them ## Footnote This pattern is fundamental in concurrent programming and task management.

Answer 209

* BFS uses a queue to explore nodes level by level * Enqueue neighbors as discovered, dequeue to explore in order ## Footnote This algorithm is commonly used in graph traversal.

Answer 210

* `put(x)` – blocks if the queue is full * `take()` – blocks if the queue is empty ## Footnote This behavior is important for managing flow in concurrent systems.

Answer 211

* **Utilization** = λ / μ * **Average queue length** * **Average waiting time** ## Footnote These metrics help in analyzing the performance of queue systems.

Answer 212

* Dequeue on empty queue must define behavior: throw exception, return sentinel, or block ## Footnote Proper handling of underflow is crucial to prevent errors in queue operations.

Answer 213

* Enqueue when full must have well-defined behavior: block, drop, or return error ## Footnote This ensures that the system behaves predictably under load.

Answer 214

* Treat them as queues, not pseudo-lists * Be explicit about bounded vs unbounded * Document thread-safety and ordering guarantees ## Footnote Following these practices helps in creating robust queue implementations.

Answer 215

* Explain the queue ADT * Implement a queue using ring buffer or linked list * Use queues for BFS, producer-consumer, and event loops * Choose between queue types * Reason about performance * Identify and fix queue-related bugs ## Footnote Mastery of these skills indicates a strong understanding of queues in software engineering.

Answer 216

A finite, ordered collection of elements where *position* matters and duplicates are allowed ## Footnote Key points include: Order matters, duplicates allowed, indexed, and elements can be inserted/removed at any position.

Answer 217

* `get(i)` – element at index `i` * `set(i, x)` – replace element at `i` * `insert(i, x)` – shift elements [i..end) right * `remove(i)` – remove element at `i` and shift elements left * `push_back(x)` / `append(x)` – add at end * `pop_back()` – remove last element * iteration: `for each element in order` ## Footnote Everything else is variations on top of these.

Answer 218

* `get(i)` / `set(i,x)` → **O(1)** * `push_back(x)` → **amortized O(1)** * `pop_back()` → **O(1)** * `insert/remove` near the middle → **O(n)** ## Footnote These expectations apply to implementations like `std::vector`, Java `ArrayList`, and Python `list`.

Answer 219

* Contiguous memory block (array) * Random access O(1) via pointer arithmetic * Good cache locality for iteration ## Footnote Examples include C++ `std::vector`, Java `ArrayList`, and Python `list`.

Answer 220

* Singly linked (`next`) * Doubly linked (`prev` + `next`) * Circular variants ## Footnote Examples include C++ `std::list` (doubly linked) and Java `LinkedList`.

Answer 221

* You care about **order** and **position** * You want to iterate in a consistent sequence * You frequently append at the end * You need random access by index ## Footnote Lists are not ideal for presence checks, key-value lookups, or priority semantics.

Answer 222

* Great spatial locality * Fewer allocations (one big block) * Reallocation only on growth/shrink events ## Footnote This leads to better performance for large data and hot loops.

Answer 223

* Forward iteration * Reverse iteration * Safe removal while iterating ## Footnote Especially important with linked lists, using pointers/iterators carefully.

Answer 224

* Implement singly and doubly linked lists * Recognize and handle empty lists, single-element lists * Insert/remove at head and tail * Removing the node you’re currently at during traversal ## Footnote Classic bugs include losing part of the list and memory leaks.

Answer 225

* Expose the right abstraction * Consider ownership and mutability * Avoid leaking implementation details * Document complexity expectations ## Footnote This ensures clarity and usability for API consumers.

Answer 226

* Define the list ADT * Implement dynamic array and linked lists * Know the complexity of operations * Use lists correctly in algorithms * Understand memory/cache behavior * Choose the right structure * Handle corner cases * Reason about API design ## Footnote Mastery of these areas indicates a strong generalist/systems-minded engineer.

Answer 227

A connected, acyclic graph with a distinguished root ## Footnote Key concepts include nodes, edges, root, parent/child relationships, leaves, internal nodes, subtrees, height, and depth.

Answer 228

* Nodes (vertices) * Edges (links) * Root * Parent / child * Leaf * Internal node * Subtree * Height * Depth ## Footnote These concepts help define the structure and properties of trees.

Answer 229

TRUE ## Footnote However, not every graph is a tree.

Answer 230

* File systems * Org charts * UI widgets * DOM * Binary search trees * B-trees * Heaps * Tries * Expression trees * Quadtrees ## Footnote Trees are prevalent in many structured data representations.

Answer 231

* O(log n) ## Footnote This applies to structures like AVL trees, Red-Black trees, and B-trees.

Answer 232

O(n) ## Footnote Operations are often defined in terms of traversals (DFS/BFS).

Answer 233

Each node has at most 2 children ## Footnote This is a fundamental tree structure.

Answer 234

Each node has 0 or 2 children ## Footnote This structure is distinct from other types of binary trees.

Answer 235

Filled level by level, left to right, no gaps except possibly last level ## Footnote This structure ensures efficient use of space.

Answer 236

For each node, all keys in left subtree < node’s key, all keys in right subtree > node’s key ## Footnote This property allows for efficient searching.

Answer 237

* Depth-First Search (DFS) * Breadth-First Search (BFS) * Level-order traversal ## Footnote Each traversal method has different applications and use cases.

Answer 238

Implement priority queues ## Footnote Heaps maintain a specific order among elements.

Answer 239

* O(log n) ## Footnote The `peekMin` operation is O(1).

Answer 240

A tree structure where nodes correspond to prefixes of strings or bit sequences ## Footnote Tries are used for efficient string operations.

Answer 241

Efficient disk-based search trees ## Footnote They are optimized for minimizing I/O operations.

Answer 242

* Flexible * Often used for general trees, BSTs, tries * Pointer-heavy; not cache-optimal ## Footnote Each node typically contains pointers to its children.

Answer 243

* No pointer overhead * Great cache locality * Works best for complete or near-complete trees ## Footnote This representation computes child indices based on parent indices.

Answer 244

* Efficient search, insert, delete by key * Hierarchical or branching structure ## Footnote Trees provide advantages in structured data scenarios.

Answer 245

* Filesystems * UI / DOM trees * Abstract Syntax Trees (ASTs) * Scene graphs / game entities ## Footnote These domains utilize tree structures for organization and representation.

Answer 246

Inserting sorted keys can lead to a linked list shape ## Footnote This results in degraded performance (O(n)).

Answer 247

Use iterative traversals with an explicit stack ## Footnote This approach avoids deep recursion issues.

Answer 248

* What a tree is * How it differs from a graph * Basic terminology (root, leaf, height, depth, subtree) ## Footnote Understanding these concepts is fundamental for working with trees.

Answer 249

* File/DOM/AST hierarchies * Decision trees * Organizational hierarchies ## Footnote These problems often require tree-based data structures for efficient representation and manipulation.

Answer 250

Balanced trees provide better performance with O(log n) operations, while unbalanced trees can degrade to O(n) ## Footnote Understanding this difference is crucial for optimizing tree operations.

Answer 251

tasks, dependencies, UI components ## Footnote This helps in visualizing and managing relationships within the data.

Answer 252

* Spot stack overflows from deep recursion * Reason about incorrect tree invariants (e.g., BST property broken) ## Footnote Debugging tree structures often involves checking for recursion depth and maintaining properties of the tree.

Answer 253

FALSE ## Footnote Comfort with tree structures is important for various software engineering tasks.

Answer 254

* Show concrete C++ examples of BSTs / tree traversals / heaps * Walk through a real-world case (e.g., flattening a tree, implementing a simple file tree, or building a tiny AST and interpreter) ## Footnote These options provide practical applications of tree structures in programming.

Answer 255

A tree-based data structure that organizes elements by **priority** and guarantees that the **extremal** element is always at the top ## Footnote Supports efficient operations like inserting a new element and getting/removing the min or max element.

Answer 256

* **Min-heap**: smallest key is at the root * **Max-heap**: largest key is at the root ## Footnote The **heap property** ensures that for every node, the key is less than or equal to its children's keys.

Answer 257

FALSE ## Footnote Only the root is guaranteed to be min/max; siblings have no particular order.

Answer 258

* **Heap**: specific data structure implementation * **Priority queue**: abstract data type with operations like insert, findMin, extractMin ## Footnote Heaps are often used to implement priority queues.

Answer 259

* `insert(x)` / `push` → **O(log n)** worst-case * `findMin` / `top` → **O(1)** * `extractMin` / `pop` → **O(log n)** worst-case * `heapify` → **O(n)** total * `decreaseKey` → **O(log n)** ## Footnote These complexities highlight the efficiency of heaps for dynamic sets.

Answer 260

As an **array-backed tree** ## Footnote Most production heaps are complete binary trees stored in an array, with implicit tree shape determined by index math.

Answer 261

**O(n)** ## Footnote This is more efficient than repeated insertions, which would take O(n log n).

Answer 262

* Task scheduling / job priority * Graph algorithms (e.g., Dijkstra’s shortest path) * Top-k queries / streaming ## Footnote Heaps are useful for scenarios where you need to repeatedly extract the next best element.

Answer 263

* **Heap**: `insert` = O(log n), `findMin` = O(1) * **Sorted array**: `insert` = O(n), `findMin` = O(1) ## Footnote Heaps are more efficient for many inserts intermixed with finds.

Answer 264

* **Binary heap**: standard, array-based * **d-ary heap**: each node has `d` children * **Fibonacci heap**: amortized O(1) `insert` ## Footnote These variants have different trade-offs and use cases.

Answer 265

Marking an element as 'invalid' instead of removing it ## Footnote This is useful in algorithms like Dijkstra's when using heaps without decreaseKey.

Answer 266

* **Heap (data structure)**: used to implement priority queues * **Heap (memory)**: general-purpose memory area for allocation ## Footnote They are unrelated concepts despite sharing the name.

Answer 267

* Explain what a heap is and its properties * Know the complexities of heap operations * Use standard library heaps (e.g., C++ `std::priority_queue`) ## Footnote Additional skills include implementing a binary heap and applying heaps to algorithms.

Answer 268

key(u) ≤ key(child) for all children ## Footnote This ensures that the root is the minimum element.

Answer 269

**O(log n)** worst-case ## Footnote This operation involves bubbling down the root element to maintain the heap property.

Answer 270

TRUE ## Footnote It allows each node to have `d` children, which can optimize certain patterns.

Answer 271

* Dijkstra * A* * Prim ## Footnote These algorithms are commonly used in graph-related problems.

Answer 272

* Maintain a k-sized heap * Extract extremal values from a changing set * Manage priority tasks ## Footnote Heaps are particularly useful for efficiently handling priority queues.

Answer 273

FALSE ## Footnote A heap is not fully sorted; it maintains a partial order.

Answer 274

Heap (data structure) is a binary tree structure; heap (memory) refers to dynamic memory allocation ## Footnote Understanding this distinction is crucial for programming and data structure management.

Answer 275

O(n) ## Footnote This is a common misconception; building a heap is more efficient than one might expect.

Answer 276

* Show C++ semantics examples * Sketch a small priority scheduler ## Footnote These steps can deepen understanding of heaps in practical applications.

Answer 277

vertices (nodes), edges (links) ## Footnote Formally: G = (V, E) where V = set of vertices and E = set of edges.

Answer 278

Edge `{u, v}` has no direction ## Footnote “u is connected to v” is symmetric.

Answer 279

Edge `(u → v)` has direction ## Footnote Think “u can reach v” but not necessarily vice versa.

Answer 280

Edges have weights/costs/capacities ## Footnote This allows for more complex relationships between nodes.

Answer 281

All edges considered equal (weight 1) ## Footnote Simplifies calculations and relationships.

Answer 282

* Undirected graph * Directed graph (digraph) * Weighted graph * Unweighted graph ## Footnote Combination examples include directed weighted and undirected unweighted graphs.

Answer 283

Individual item in the graph ## Footnote Each vertex can represent an entity or point of interest.

Answer 284

Connection between nodes ## Footnote Edges can be directed or undirected.

Answer 285

Number of edges incident to a node ## Footnote Indicates the connectivity of a vertex.

Answer 286

# of edges *entering* a node ## Footnote Reflects how many nodes point to this node.

Answer 287

# of edges *leaving* a node ## Footnote Indicates how many nodes this node points to.

Answer 288

Sequence of vertices connected by edges ## Footnote Paths can vary in length and complexity.

Answer 289

Path with no repeated vertices ## Footnote Ensures unique traversal of nodes.

Answer 290

Path starting and ending at the same vertex with at least one edge and no repeats in between ## Footnote Cycles can indicate redundancy or loops in processes.

Answer 291

There is a path between every pair of nodes ## Footnote Ensures all nodes are reachable from one another.

Answer 292

Maximal set of nodes where each pair is mutually reachable ## Footnote Relevant in undirected graphs.

Answer 293

u and v are mutually reachable via directed paths ## Footnote Indicates a robust interconnection between nodes.

Answer 294

Maximal set where every node can reach every other via directed paths ## Footnote Important for analyzing directed graphs.

Answer 295

Directed graph with **no directed cycles** ## Footnote Crucial for scheduling and dependency management.

Answer 296

For each vertex `u`, store a list of its neighbors ## Footnote Typically represented as `vector> adj;`.

Answer 297

O(V + E) ## Footnote Efficient for sparse graphs.

Answer 298

A 2D array `M` where `M[u][v]` indicates if edge `u → v` exists ## Footnote Useful for dense graphs.

Answer 299

O(V²) ## Footnote Can be inefficient for large sparse graphs.

Answer 300

Just a list/array of edges `(u, v, w)` ## Footnote Space complexity is O(E).

Answer 301

O(V + E) ## Footnote Explores as far as possible along each branch before backtracking.

Answer 302

O(V + E) ## Footnote Explores neighbors by layers based on distance from the start node.

Answer 303

A connected graph with no cycles ## Footnote Trees have unique properties and traversal algorithms.

Answer 304

Vertices can be partitioned into 2 sets (U, V) such that all edges go between U and V ## Footnote Equivalent condition: graph has **no odd-length cycles**.

Answer 305

Produces an ordering of vertices such that for every edge `u → v`, `u` comes before `v` ## Footnote Applicable only to **DAGs**.

Answer 306

BFS ## Footnote Efficiently finds the shortest path in terms of edge count.

Answer 307

Dijkstra’s algorithm ## Footnote Utilizes a min-heap for efficiency.

Answer 308

A spanning tree that connects all vertices with no cycles and minimum total edge weight ## Footnote Algorithms include **Kruskal’s** and **Prim’s**.

Answer 309

To find strongly connected components (SCC) in directed graphs ## Footnote Useful in compilers and static analysis.

Answer 310

How many vertices (V) and how many edges (E) ## Footnote Determines if the graph is sparse or dense.

Answer 311

Using lists/maps where a graph would help ## Footnote Recognizing graphs allows for standard algorithms instead of brittle solutions.

Answer 312

* What a graph is (directed/undirected, weighted/unweighted) * Key terms: path, cycle, connected component, DAG, SCC, degree ## Footnote Fundamental knowledge for graph-related tasks.

Data Structures Flashcards

(336 cards)