DSA

Question 1

What is a data structure?

Answer 1

A data structure is a way to organize and store data for efficient access and modification, like arrays, linked lists, or trees.

Question 2

What is an algorithm?

Answer 2

An algorithm is a step-by-step procedure to solve a problem, like sorting an array or searching for an item.

Question 3

What is the difference between an array and a linked list?

Answer 3

An array stores elements in contiguous memory with fast access (O(1)) but fixed size; a linked list uses nodes with pointers, allowing dynamic size but slower access (O(n)).

Question 4

What is a stack, and how does it work?

Answer 4

A stack is a LIFO (Last In, First Out) data structure. Elements are added (push) and removed (pop) from the top. Example: push(1), push(2), pop() → 2.

Question 5

What is a queue, and how does it differ from a stack?

Answer 5

A queue is a FIFO (First In, First Out) data structure where elements are added at the rear and removed from the front.

Question 6

What is time complexity in algorithms?

Answer 6

Time complexity measures how an algorithm’s runtime grows with input size, expressed in Big O notation (e.g., O(n) for linear time).

Question 7

What does O(1) time complexity mean?

Answer 7

O(1) means constant time, where the algorithm’s runtime doesn’t depend on input size.

Question 8

What is a binary search, and when can it be used?

Answer 8

Binary search finds an element in a sorted array by halving the search space each step (O(log n)). It requires a sorted input.

Question 9

What is a binary tree?

Answer 9

A binary tree is a hierarchical structure where each node has at most two children (left and right).

Question 10

What is the difference between BFS and DFS?

Answer 10

Breadth-First Search (BFS) explores nodes level by level using a queue; Depth-First Search (DFS) explores as far as possible along a branch using a stack or recursion.

Question 11

What is a hash table, and how does it work?

Answer 11

A hash table stores key-value pairs using a hash function to compute an index for fast lookup (average O(1)).

Question 12

What is a linked list, and how do you reverse one?

Answer 12

A linked list is a chain of nodes, each with data and a next pointer. To reverse, iterate and update pointers.

Question 13

What is recursion, and when should you use it?

Answer 13

Recursion is when a function calls itself to solve smaller subproblems. Use it for problems like tree traversal.

Question 14

What is a heap, and what are its types?

Answer 14

A heap is a tree-based structure where the parent is greater (max-heap) or smaller (min-heap) than its children.

Question 15

What is the difference between a graph and a tree?

Answer 15

A graph is a collection of nodes and edges, possibly with cycles; a tree is a graph with no cycles and a single root.

Question 16

What is bubble sort, and what is its time complexity?

Answer 16

Bubble sort repeatedly swaps adjacent elements if out of order. Time complexity is O(n²).

Question 17

What is quicksort, and how does it work?

Answer 17

Quicksort picks a pivot, partitions the array around it, and recursively sorts subarrays. Average time complexity is O(n log n).

Question 18

What is a trie, and what is it used for?

Answer 18

A trie is a tree where each node represents a character in a string, used for efficient string searches.

Question 19

What is dynamic programming, and when is it used?

Answer 19

Dynamic programming solves problems by breaking them into overlapping subproblems, storing results to avoid recomputation.

Question 20

What is a graph cycle, and how do you detect it?

Answer 20

A cycle is a path in a graph that returns to the starting node. Detect using DFS.

Question 21

What is the Sliding Window pattern?

Answer 21

Sliding Window optimizes problems with subarrays/substrings by maintaining a dynamic window. Example: Find max sum of k consecutive elements in an array (O(n)).

Question 22

How does the Two Pointers pattern work?

Answer 22

Two Pointers uses two indices to traverse an array or list, often from opposite ends or same direction. Example: Find two numbers summing to a target in a sorted array (O(n)).

Question 23

What is the Fast and Slow Pointers pattern?

Answer 23

Fast and Slow Pointers uses two pointers moving at different speeds, often in linked lists. Example: Detect a cycle in a linked list (Floyd’s algorithm, O(n)).

Question 24

What is the Binary Search pattern?

Answer 24

Binary Search halves the search space each step in a sorted dataset. Example: Find an element in a sorted array (O(log n)).

Question 25

What is the Depth-First Search (DFS) pattern?

Answer 25

DFS explores as far as possible along each branch in a graph or tree before backtracking. Example: Find all paths in a tree (O(V + E)).

Question 26

What is the Breadth-First Search (BFS) pattern?

Answer 26

BFS explores nodes level by level using a queue. Example: Find shortest path in an unweighted graph (O(V + E)).

Question 27

What is the Two Heaps pattern?

Answer 27

Two Heaps uses two priority queues (min/max) to solve problems like median finding. Example: Find median in a data stream (O(log n) per insert).

Question 28

What is the Backtracking pattern?

Answer 28

Backtracking explores all possible solutions, pruning invalid paths. Example: Solve N-Queens by trying all placements (O(n!)).

Question 29

What is the Dynamic Programming (DP) pattern?

Answer 29

DP breaks problems into overlapping subproblems, storing results to avoid recomputation. Example: Fibonacci with memoization (O(n)).

Question 30

What is the Topological Sort pattern?

Answer 30

Topological Sort orders nodes in a directed acyclic graph (DAG) so that dependencies come first. Example: Course scheduling (O(V + E)).

Question 31

What is the Greedy pattern?

Answer 31

Greedy makes locally optimal choices to achieve a global solution. Example: Minimum coins for change (may not always work, O(n)).

Question 32

What is the Merge Intervals pattern?

Answer 32

Merge Intervals combines overlapping intervals in a sorted list. Example: Merge time intervals like [[1,3], [2,4]] → [[1,4]] (O(n log n)).

Question 33

What is the Subsets pattern?

Answer 33

Subsets generates all possible combinations of a set, often using backtracking. Example: Find all subsets of [1,2] → [[], [1], [2], [1,2]] (O(2ⁿ)).

Question 34

What is the Monotonic Stack pattern?

Answer 34

Monotonic Stack maintains elements in increasing/decreasing order to solve problems like next greater element. Example: Find next larger number in array (O(n)).

Question 35

What is the Prefix Sum pattern?

Answer 35

Prefix Sum precomputes cumulative sums for efficient range queries. Example: Calculate sum of array range [i,j] in O(1) after O(n) preprocessing.

Question 36

What is the Kadane’s Algorithm pattern?

Answer 36

Kadane’s finds the maximum subarray sum by tracking local and global maxima. Example: Max sum subarray of [-2,1,-3,4,-1] → 4 (O(n)).

Question 37

What is the Divide and Conquer pattern?

Answer 37

Divide and Conquer splits a problem into smaller subproblems, solves them, and combines results. Example: Mergesort (O(n log n)).

Question 38

What is the K-way Merge pattern?

Answer 38

K-way Merge combines k sorted lists using a min-heap or merging pairs. Example: Merge k sorted arrays (O(n log k), n total elements).

Question 39

What is the Trie pattern?

Answer 39

Trie stores strings as a tree for efficient prefix-based searches. Example: Implement autocomplete (O(m) lookup, m is string length).

Question 40

What is the Bit Manipulation pattern?

Answer 40

Bit Manipulation uses bitwise operations to solve problems efficiently. Example: Check if a number is a power of 2 (x & (x-1) == 0, O(1)).