Interview Prep: DSA Questions, thesarfo

What is a data structure? A data structure is a way of organizing and storing data in a computer’s memory or storage system. It provides a systematic approach to managing and manipulating data efficiently. Examples include arrays, linked lists, stacks, queues, trees, and graphs.
What is an array? An array is a data structure that stores a fixed-size sequence of elements of the same type. It provides random access to its elements using an index. Arrays are commonly used for storing and manipulating collections of data.
What is a linked list? A linked list is a data structure in which each element, called a node, contains a value and a reference to the next node in the sequence. Unlike arrays, linked lists don’t require contiguous memory allocation, allowing for efficient insertion and deletion. However, accessing elements requires traversing the list from the beginning.
What is a stack? A stack is an abstract data type that follows the Last-In-First-Out (LIFO) principle. It supports two main operations: push (inserting onto the top) and pop (removing the topmost element). Stacks are often used for managing function calls, expression evaluation, and undo mechanisms.
What is a queue? A queue is an abstract data type that follows the First-In-First-Out (FIFO) principle. It supports enqueue (adding to the end) and dequeue (removing from the front). Queues are commonly used when data needs to be processed in arrival order, such as scheduling tasks or handling requests.
What is a tree? A tree is a hierarchical data structure consisting of nodes connected by edges, with a root node at the top and child nodes below it, forming a branching structure. Trees represent hierarchical relationships, such as file systems or organization structures.
What is a graph? A graph is a non-linear data structure consisting of nodes (vertices) and edges connecting them — a powerful tool for representing relationships between objects. Graphs can be directed (edges have a specific direction) or undirected. Widely used in network analysis, social networks, and pathfinding algorithms.
What is the difference between an array and a linked list? Arrays have contiguous memory allocation and provide direct access to elements using an index, allowing fast random access. Linked lists use nodes with references to the next element, providing efficient insertion and deletion at any position, but slower access time.
What is the difference between a stack and a queue? A stack follows LIFO — the last element inserted is the first removed. A queue follows FIFO — the first element inserted is the first removed. Stacks are like a pile of plates; queues resemble a line of people waiting.
What is the difference between a tree and a graph? A tree is a type of graph that doesn’t contain cycles — no loops or circular dependencies among nodes. A general graph can have cycles and arbitrary connections, allowing for more complex relationships.
What is the difference between breadth-first search (BFS) and depth-first search (DFS)? Both are graph traversal algorithms. BFS visits all the neighbors of a node before moving to the next level, like a wave expanding from the starting point. DFS explores as far as possible along each branch before backtracking, going deeper into the graph.
What is the time complexity of inserting an element into an array? Depends on the position: inserting at the beginning requires shifting all existing elements, O(n). Inserting at the end is O(1).
What is the time complexity of searching for an element in an array? Linear search is O(n). Binary search, if the array is sorted, is O(log n), since it repeatedly halves the search space.
What is the time complexity of inserting an element into a linked list? Inserting at the beginning or end is O(1) — updating only a few references. Inserting in the middle requires traversing to the position first, O(n).
What is the time complexity of searching for an element in a linked list? O(n) — linked lists don’t provide random access, so you traverse from the beginning until you find the element or reach the end.
What is a binary search tree (BST)? A binary tree where each node’s key satisfies: the key of any node in the left subtree is less than the node’s own key, and the key of any node in the right subtree is greater. This allows efficient searching, insertion, and deletion, with average time complexity O(log n).
What is a heap data structure? A complete binary tree satisfying the heap property: for a max heap, each node’s key is greater than or equal to its children’s; for a min heap, smaller than or equal to. Commonly used to implement priority queues and efficient sorting (heap sort).
What is a hash table? A data structure that uses a hash function to map keys to values, providing efficient insertion, deletion, and retrieval with average time complexity O(1). Widely used for fast data lookup — dictionaries, symbol tables.
What is the difference between an array and a hash table? Arrays provide direct, index-based access for fast random access. Hash tables use a hash function to map keys to values, providing efficient insertion/deletion/retrieval but without direct index-based access.
What is dynamic programming? A problem-solving technique that breaks down complex problems into smaller overlapping subproblems, solving each only once and storing results for reuse. Used when subproblems exhibit optimal substructure. Significantly improves efficiency by avoiding redundant computation.
What is a greedy algorithm? An algorithmic paradigm that makes the locally optimal choice at each stage, hoping to find a global optimum. Simple to design and efficient, but doesn’t guarantee the optimal solution for all problems.
What is a divide-and-conquer algorithm? Breaks a problem into smaller, more manageable subproblems, solves them independently, and combines the solutions. Follows the recursive structure of dividing, solving, and merging. Common in sorting (merge sort, quicksort) and searching (binary search).
What is a dynamic array? A resizable array — starts with a fixed initial capacity and dynamically allocates more memory when needed, combining constant-time random access with the ability to grow or shrink as necessary.
What is the time complexity of inserting an element at the beginning of a linked list? O(1) — the new element becomes the head, requiring only a head-pointer update.
What is the time complexity of inserting an element at the end of a linked list? O(n) — requires traversing the entire list to reach the last node.
What is the time complexity of removing an element from a linked list? Depends on position: O(1) at the beginning (update the head pointer); O(n) in the middle or at the end (requires traversal).