Data Structures & Algorithms Flashcards
(14 cards)
What is Big O notation and why is it important?
Big O notation describes the upper bound of algorithm complexity in terms of time or space as input size grows. It helps compare algorithm efficiency and predict performance scalability. Common complexities: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic, O(2ⁿ) exponential. It’s crucial for choosing appropriate algorithms for large datasets.
Compare different sorting algorithms.
Bubble Sort: O(n²) time, O(1) space, stable, simple but inefficient. Quick Sort: O(n log n) average, O(n²) worst case, O(log n) space, not stable, divide-and-conquer. Merge Sort: O(n log n) time, O(n) space, stable, consistent performance. Heap Sort: O(n log n) time, O(1) space, not stable, good for memory-constrained environments.
Explain hash tables and collision resolution.
Hash tables use hash functions to map keys to array indices for O(1) average-case lookup. Collision resolution methods include: Chaining: Store colliding elements in linked lists at each index. Open Addressing: Find alternative positions using probing (linear, quadratic, double hashing). Load factor affects performance; rehashing may be needed when table becomes too full.
What are binary search trees and their properties?
BSTs are hierarchical data structures where each node has at most two children. Left subtree contains values less than the node, right subtree contains values greater. This enables O(log n) search, insertion, and deletion in balanced trees. However, unbalanced trees can degrade to O(n) performance. Self-balancing variants like AVL trees and Red-Black trees maintain balance automatically.
Explain graph data structures and common algorithms.
Graphs consist of vertices (nodes) connected by edges, representing relationships between entities. Types include directed/undirected, weighted/unweighted, cyclic/acyclic. Common algorithms: Traversal: Depth-First Search (DFS), Breadth-First Search (BFS). Shortest Path: Dijkstra’s algorithm, Bellman-Ford. Minimum Spanning Tree: Kruskal’s, Prim’s algorithms. Topological Sort: For directed acyclic graphs. Applications include social networks, GPS navigation, and dependency resolution.
What is dynamic programming and when do you use it?
Dynamic programming solves complex problems by breaking them into overlapping subproblems and storing results to avoid redundant calculations. Key characteristics: optimal substructure and overlapping subproblems. Approaches include memoization (top-down) and tabulation (bottom-up). Classic examples: Fibonacci sequence, knapsack problem, longest common subsequence. More efficient than naive recursion for problems with repeated subproblems.
Explain different tree traversal methods.
Tree traversal methods for binary trees: In-order: Left subtree, root, right subtree (gives sorted order in BST). Pre-order: Root, left subtree, right subtree (useful for copying tree). Post-order: Left subtree, right subtree, root (useful for deletion). Level-order: Breadth-first traversal using queue. Each method serves different purposes and can be implemented recursively or iteratively.
What are heaps and priority queues?
Heaps are complete binary trees satisfying heap property: parent nodes are greater (max-heap) or smaller (min-heap) than children. Implemented as arrays for space efficiency. Priority queues are abstract data types where elements have priorities; heaps provide efficient implementation with O(log n) insertion/deletion and O(1) peek operations. Applications include Dijkstra’s algorithm, scheduling systems, and sorting algorithms.
Compare arrays, linked lists, and dynamic arrays.
Arrays: Fixed size, O(1) random access, cache-friendly, but inflexible size. Linked Lists: Dynamic size, O(n) access, efficient insertion/deletion at known positions, extra memory overhead for pointers. Dynamic Arrays: Resizable, O(1) amortized append, combine benefits of arrays and flexibility, but occasional O(n) resize operations. Choice depends on access patterns, memory constraints, and modification frequency.
Explain string algorithms and pattern matching.
String algorithms solve text processing problems: Naive Pattern Matching: O(nm) time complexity, simple but inefficient. KMP Algorithm: O(n+m) using failure function to avoid redundant comparisons. Boyer-Moore: Efficient for large alphabets, skips characters intelligently. Rabin-Karp: Uses hashing for pattern matching, good for multiple pattern search. Applications include text editors, search engines, DNA sequence analysis, and compiler design.
What are tries and their applications?
Tries (prefix trees) are tree structures for storing strings efficiently, where each path from root to leaf represents a word. Benefits include: Efficient prefix-based searches, O(m) lookup time where m is string length, Space sharing for common prefixes, Fast auto-complete and spell-check functionality. Applications include dictionaries, IP routing tables, and text prediction systems.
Explain the concept of algorithmic complexity classes.
Complexity classes categorize problems by computational resources required: P: Problems solvable in polynomial time, NP: Problems verifiable in polynomial time, NP-Complete: Hardest problems in NP; if any has polynomial solution, all do, NP-Hard: At least as hard as NP-complete problems, PSPACE: Problems using polynomial space. Understanding these classes helps identify problem difficulty and solution approaches.
What are greedy algorithms and their characteristics?
Greedy algorithms make locally optimal choices at each step, hoping to find global optimum. Characteristics: Make the best choice at current step, Never reconsider previous choices, Often simpler than dynamic programming, Don’t always produce optimal solutions. Examples: Dijkstra’s algorithm, Huffman coding, fractional knapsack. Success requires proving greedy choice property and optimal substructure.
Describe divide-and-conquer algorithms.
Divide-and-conquer breaks problems into smaller subproblems, solves them recursively, then combines results. Three steps: 1. Divide: Break problem into subproblems, 2. Conquer: Solve subproblems recursively, 3. Combine: Merge solutions. Examples: merge sort, quick sort, binary search, Strassen’s matrix multiplication. Often leads to efficient O(n log n) algorithms and natural parallelization opportunities.
