Data Structures Answers

Basic Data Structures Answers

#	Question	Answer	Examples
1	What is a Data Structure?	A way of organizing, managing, and storing data in a computer	Arrays, Linked Lists, Stacks, Queues, Trees, Graphs
2	What is an Array?	A collection of elements of the same data type stored in contiguous memory locations	[1, 2, 3, 4, 5]
3	What is a Linked List?	A sequence of elements (nodes) where each node contains data and a pointer to the next	Node1 -> Node2 -> Node3 -> null
4	What is a Stack?	A linear data structure following the Last-In, First-Out (LIFO) principle	push(), pop(), peek() operations
5	What is a Queue?	A linear data structure following the First-In, First-Out (FIFO) principle	enqueue(), dequeue(), peek() operations
6	What is a Tree?	A hierarchical data structure with nodes connected by edges	Binary Tree, Binary Search Tree (BST), AVL Tree
7	What is a Binary Tree?	A tree where each node has at most two children (left and right)	Root node, left child, right child
8	What is a Binary Search Tree (BST)?	A binary tree where all nodes in the left subtree are smaller than the root, and all nodes in the right subtree are larger	Efficient searching, insertion, and deletion operations.
9	What is a Hash Table (Hash Map)?	A data structure that uses a hash function to map keys to indices in an array	Stores key-value pairs; provides fast lookups, insertions, and deletions.
10	What is a Graph?	A collection of nodes (vertices) connected by edges	Represents networks, relationships, or connections between entities
11	What is Time Complexity?	A measure of how the runtime of an algorithm grows with the input size	Big O notation (O(1), O(log n), O(n), O(n log n), O(n^2))
12	What is Space Complexity?	A measure of how the memory usage of an algorithm grows with the input size	Big O notation (O(1), O(n), O(n^2))
13	What is O(1) complexity?	Constant time; execution time does not depend on input size	Accessing an array element by its index
14	What is O(n) complexity?	Linear time; execution time grows proportionally to input size	Traversing an array once
15	What is O(log n) complexity?	Logarithmic time; execution time grows slowly as input size increases	Binary search

Intermediate Data Structures Answers

#	Question	Answer	Examples
1	What is the difference between an Array and a Linked List?	Array uses contiguous memory, random access; Linked List uses non-contiguous memory, sequential access	Arrays offer faster random access; Linked Lists are better for insertions/deletions in the middle.
2	What is a Doubly Linked List?	A linked list where each node has pointers to both the previous and next nodes	Allows traversal in both directions.
3	What is a Circular Linked List?	A linked list where the last node's pointer points back to the first node	Useful for implementing circular buffers or queues.
4	What is a Priority Queue?	A queue where elements are served based on their priority (not just FIFO)	Often implemented using a Heap (Min-Heap or Max-Heap).
5	What is a Heap?	A specialized tree-based data structure that satisfies the heap property (parent-child relationship)	Min-Heap (parent <= children), Max-Heap (parent >= children).
6	What is a Hash Collision?	When two different keys map to the same index in a hash table	Solutions include Separate Chaining or Open Adressing (Linear Probing, Quadratic Probing).
7	What is Separate Chaining?	A collision resolution technique where each bucket in the hash table holds a linked list (or tree)	Stores multiple key-value pairs at the same index.
8	What is Binary Search?	An efficient search algorithm that repeatedly divides the search interval in half	Requires sorted data; O(log n) time complexity.
9	What is Breadth-First Search (BFS)?	A graph/tree traversal algorithm that explores neighbor nodes at the present depth prior to moving to nodes at the next depth level	Uses a queue; explores all nodes at one level before moving to the next.
10	What is Depth-First Search (DFS)?	A graph/tree traversal algorithm that explores as far as possible along each branch before backtracking	Uses a stack (or recursion); explores one branch fully before trying another.
11	What is a Trie (Prefix Tree)?	A tree-like data structure used for efficient retrieval of keys in a dataset	Used for autocomplete, spell checking, dictionary implementations.
12	What is a Balanced BST (e.g., AVL, Red-Black)?	A BST that automatically adjusts itself to maintain balance, ensuring efficient operations	Prevents skewed trees, guaranteeing O(log n) time complexity for operations.
13	What is a LRU Cache (Least Recently Used)?	A cache that evicts the least recently used item when a capacity limit is reached	Often implemented using a Hash Map and a Doubly Linked List.
14	What is a Sliding Window Technique?	An algorithmic technique for solving problems involving a "window" of a fixed size that slides over data	Finding the maximum sum of a subarray of size k.
15	What is the Two Pointers Technique?	An algorithmic technique using two pointers (indices) to traverse a data structure	Finding pairs in a sorted array that sum to a target value.

Advanced Data Structures Answers

#	Question	Answer	Examples
1	What is Dynamic Programming?	Solving problems by breaking them down into smaller, overlapping subproblems and storing the results	Fibonacci sequence, Knapsack problem, Longest Common Subsequence.
2	What is Memoization?	Storing the results of expensive function calls and returning the cached result when encountered again	Storing computed Fibonacci numbers in a cache/map.
3	What is Tabulation (Bottom-Up DP)?	Building up the solution from smaller subproblems to larger ones	Filling a table with results of subproblems, starting from base cases.
4	What is a Greedy Algorithm?	Making locally optimal choices at each step with the hope of finding a globally optimal solution	Dijkstra's algorithm, Prim's algorithm, Kruskal's algorithm.
5	What is Backtracking?	Exploring all possible solutions by building candidates incrementally, abandoning branches that don't lead to a solution	N-Queens problem, Sudoku solver.
6	What is a Segment Tree?	A tree data structure used for efficiently querying ranges (e.g., sum, min, max) in an array	Supports range queries and point updates.
7	What is a Fenwick Tree (Binary Indexed Tree)?	A data structure that efficiently supports prefix sum queries and point updates	Often used in competitive programming for range sums.
8	What is a Disjoint Set Union (Union-Find)?	A data structure that keeps track of a partition of a set of elements	Used for finding minimum spanning trees (Kruskal's algorithm), detecting cycles in graphs.
9	What is a Trie (Prefix Tree) in more detail?	Efficiently stores and retrieves strings based on prefixes	Often used for autocomplete, spell checking, IP routing.
10	What is a Skip List?	A probabilistic data structure that allows efficient search, insertion, and deletion operations	Uses multiple levels of linked lists with probabilistic level assignment.
11	What is the difference between Adjacency Matrix and Adjacency List?	Adjacency Matrix uses a 2D array for connections; Adjacency List uses lists of neighbors for each node	Adjacency List is generally more space-efficient for sparse graphs; Adjacency Matrix is good for dense graphs.
12	What is Dijkstra's Algorithm?	Finds the shortest paths from a source node to all other nodes in a graph with non-negative edge weights	Uses a priority queue to explore nodes in increasing order of distance from the source.
13	What is the Floyd-Warshall Algorithm?	Finds the shortest paths between all pairs of vertices in a graph	Uses dynamic programming; works with negative edge weights (but no negative cycles).
14	What is Prim's Algorithm?	Finds a Minimum Spanning Tree (MST) for a connected, undirected, weighted graph	Uses a greedy approach with a priority queue.
15	What is Kruskal's Algorithm?	Finds a Minimum Spanning Tree (MST) for a connected, undirected, weighted graph	Uses a greedy approach, sorting edges by weight and adding them if they don't form a cycle (often with Union-Find).