What is a data structure?
A data structure is a specialized format for organizing, processing, retrieving, and storing data. Examples include arrays, linked lists, stacks, queues, trees, and graphs.
---------------------------What is an array?
An array is a collection of elements identified by index or key, where each element is of the same data type. It supports random access and has a fixed size.
---------------------------What is a linked list?
A linked list is a linear data structure where elements are stored in nodes. Each node contains a value and a reference (or link) to the next node. Types include singly linked lists and doubly linked lists.
---------------------------
What are the advantages of a linked list over an array?
Linked lists allow for dynamic memory allocation and easier insertions/deletions compared to arrays, which require resizing and shifting elements.
---------------------------What is a stack?
A stack is a collection of elements that follows the Last In, First Out (LIFO) principle. Operations are performed at one end called the top. Key operations are push (add an element) and pop (remove an element).
---------------------------What is a queue?
A queue is a collection of elements that follows the First In, First Out (FIFO) principle. Elements are added at the rear and removed from the front.
---------------------------What is a hash table?
A hash table maps keys to values using a hash function to compute an index into an array of buckets or slots, providing average-case constant time complexity for lookups, insertions, and deletions.
---------------------------What is a binary tree?
A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left and right child.
---------------------------What is a binary search tree (BST)?
A binary search tree is a binary tree where each node’s left subtree contains nodes with values less than the node’s value, and the right subtree contains nodes with values greater, facilitating efficient searching, insertion, and deletion.
---------------------------What is a balanced tree?
A balanced tree is a binary tree where the height difference between the left and right subtrees of any node is at most one, ensuring operations like search, insert, and delete are efficient.
---------------------------What is an AVL tree?
An AVL tree is a self-balancing binary search tree where the heights of the two child subtrees of any node differ by no more than one, ensuring O(log n) time complexity for insertions, deletions, and lookups.
---------------------------What is a red-black tree?
A red-black tree is a self-balancing binary search tree with an additional property of node colors (red or black) that helps maintain balance during insertions and deletions, ensuring O(log n) time complexity for operations.
---------------------------What is a heap?
A heap is a specialized tree-based data structure that satisfies the heap property. In a max-heap, the value of each node is greater than or equal to the values of its children, while in a min-heap, it is less than or equal to its children.
---------------------------What is the difference between a min-heap and a max-heap?
In a min-heap, the root node has the smallest value, while in a max-heap, the root node has the largest value.
---------------------------What is a graph?
A graph is a collection of nodes (vertices) and edges (connections) where edges can be directed or undirected, and it is used to represent relationships between objects.
---------------------------What is the difference between a directed and an undirected graph?
In a directed graph, edges have a direction (from one vertex to another), while in an undirected graph, edges do not have a direction and represent a bidirectional relationship.
---------------------------What is a cyclic graph?
A cyclic graph contains at least one cycle, which is a path that starts and ends at the same vertex.
---------------------------What is an acyclic graph?
An acyclic graph is a graph that does not contain any cycles.
---------------------------What is a tree?
A tree is a special type of graph that is connected and acyclic, meaning there is exactly one path between any two nodes.
---------------------------What is a subtree?
A subtree is a portion of a tree that includes a node and all of its descendants.
---------------------------What is a depth-first search (DFS)?
Depth-first search is an algorithm for traversing or searching tree or graph data structures by starting at the root (or an arbitrary node) and exploring as far as possible along each branch before backtracking.
---------------------------What is a breadth-first search (BFS)?
Breadth-first search is an algorithm for traversing or searching tree or graph data structures by starting at the root (or an arbitrary node) and exploring all of its neighbors at the present depth before moving on to nodes at the next depth level.
---------------------------What is the time complexity of accessing an element in an array?
The time complexity of accessing an element in an array is O(1), as it allows for constant-time access using the index.
---------------------------What is the time complexity of inserting an element in a linked list?
The time complexity of inserting an element in a linked list is O(1) if the location for insertion is known; otherwise, it can be O(n) if you need to traverse the list to find the insertion point.
---------------------------What is the time complexity of deleting an element from a stack?
The time complexity of deleting an element from a stack is O(1), as it only involves removing the top element.
---------------------------What is the time complexity of searching for an element in a binary search tree?
The time complexity of searching for an element in a binary search tree is O(log n) in the average case, and O(n) in the worst case if the tree is unbalanced.
---------------------------What is a doubly linked list?
A doubly linked list is a type of linked list where each node contains a reference to both the next node and the previous node, allowing traversal in both directions.
---------------------------What is a circular linked list?
A circular linked list is a linked list where the last node points back to the first node, forming a circle.
---------------------------What is a priority queue?
A priority queue is an abstract data type that supports inserting elements with an associated priority and retrieving the element with the highest (or lowest) priority.
---------------------------What is the time complexity of insertions and deletions in a hash table?
The average time complexity for insertions and deletions in a hash table is O(1), but it can be O(n) in the worst case due to collisions.
---------------------------What is the time complexity of performing a level-order traversal on a binary tree?
The time complexity of a level-order traversal (BFS) on a binary tree is O(n), where n is the number of nodes in the tree.
---------------------------What is a depth of a binary tree?
The depth of a binary tree is the length of the longest path from the root to a leaf node.
---------------------------What is the height of a binary tree?
The height of a binary tree is the length of the longest path from the root to any leaf node.
---------------------------What is the time complexity of balancing an AVL tree?
The time complexity of balancing an AVL tree is O(log n), as rotations and updates are required to maintain the balance after insertions or deletions.
---------------------------What is the purpose of a hash function in a hash table?
A hash function computes an index into an array of buckets or slots, helping to distribute keys evenly and minimize collisions in a hash table.
---------------------------What is a linked list used for?
Linked lists are used for dynamic memory allocation, implementing stacks and queues, and efficiently inserting and deleting elements.
---------------------------What is the difference between an array and a linked list?
Arrays provide fast access and fixed size, while linked lists offer dynamic size and efficient insertions/deletions but slower access time.
---------------------------What is a sparse matrix?
A sparse matrix is a matrix in which most of the elements are zero. It can be represented efficiently using data structures like linked lists or arrays.
---------------------------What is a bloom filter?
A bloom filter is a probabilistic data structure used to test whether an element is a member of a set, with a possibility of false positives but no false negatives.
---------------------------What is the difference between a stack and a queue?
A stack follows the Last In, First Out (LIFO) principle, while a queue follows the First In, First Out (FIFO) principle.
---------------------------What is the time complexity of enqueue and dequeue operations in a queue implemented using a linked list?
The time complexity of both enqueue and dequeue operations in a queue implemented using a linked list is O(1).
---------------------------What is the space complexity of a binary tree?
The space complexity of a binary tree is O(n), where n is the number of nodes, as each node requires space for its value and pointers.
---------------------------What is a trie?
A trie, or prefix tree, is a tree-like data structure used to store associative data structures, often used for fast retrieval of strings or prefixes.
---------------------------What is the worst-case time complexity of binary search in a sorted array?
The worst-case time complexity of binary search in a sorted array is O(log n), as it repeatedly divides the search interval in half.
---------------------------What is a skip list?
A skip list is a data structure that allows for fast search, insertion, and deletion operations by maintaining multiple levels of linked lists with increasing skip factors.
---------------------------What is a disjoint set (union-find) data structure?
A disjoint set is a data structure that keeps track of a partition of a set into disjoint subsets and supports union and find operations efficiently.
---------------------------What is the time complexity of inserting an element in a balanced binary search tree?
The time complexity of inserting an element in a balanced binary search tree is O(log n), where n is the number of nodes in the tree.
---------------------------What is a hash collision, and how is it handled?
A hash collision occurs when two keys hash to the same index. It is handled using techniques like chaining (linked lists at each index) or open addressing (probing).
---------------------------What is an adjacency matrix?
An adjacency matrix is a 2D array used to represent a graph, where the element at row i and column j indicates the presence or absence of an edge between vertices i and j.
---------------------------What is an adjacency list?
An adjacency list is a data structure used to represent a graph where each vertex has a list of adjacent vertices.
---------------------------What is a recursive algorithm?
A recursive algorithm is one that solves a problem by solving smaller instances of the same problem, typically using a base case to terminate the recursion.
---------------------------What is the time complexity of accessing an element in a hash table?
The average time complexity of accessing an element in a hash table is O(1), though it can be O(n) in the worst case due to collisions.
---------------------------What is the space complexity of a graph represented by an adjacency list?
The space complexity of a graph represented by an adjacency list is O(V + E), where V is the number of vertices and E is the number of edges.
---------------------------What is a topological sort?
Topological sort is an ordering of the vertices in a directed acyclic graph (DAG) such that for every directed edge u → v, vertex u comes before v in the ordering.
---------------------------What is the purpose of a stack in function call management?
A stack is used to manage function calls and local variables in a program, where each function call creates a new stack frame with its own local variables and return address.
---------------------------What is the difference between an iterative and a recursive algorithm?
An iterative algorithm uses loops to repeat operations, while a recursive algorithm calls itself with modified parameters to achieve repetition.
---------------------------What is the time complexity of inserting an element in a hash table with separate chaining?
The average time complexity of inserting an element in a hash table with separate chaining is O(1), but can be O(n) in the worst case if all elements hash to the same bucket.
No comments:
Post a Comment