Data Structures and Algorithms

Cards (24)

• 1
  Front

  What is the time complexity of accessing an element by index in an array?

  Back

  O(1) — arrays support constant-time random access because elements are stored in contiguous memory.

• 2
  Front

  What is the worst-case time complexity of inserting an element at the beginning of an array?

  Back

  O(n) — all existing elements must be shifted one position to make room.

• 3
  Front

  What is the key structural difference between a singly linked list and a doubly linked list?

  Back

  A singly linked list node has one pointer (to the next node); a doubly linked list node has two pointers (to the next and previous nodes).

• 4
  Front

  What is the time complexity of searching for an element in an unsorted linked list?

  Back

  O(n) — the list must be traversed from the head until the element is found or the end is reached.

• 5
  Front

  What abstract data type follows the Last-In, First-Out (LIFO) principle?

  Back

  A stack. The most recently added element is the first to be removed.

• 6
  Front

  What are the two primary operations of a stack and what do they do?

  Back

  Push — adds an element to the top of the stack. Pop — removes and returns the top element.

• 7
  Front

  What abstract data type follows the First-In, First-Out (FIFO) principle?

  Back

  A queue. Elements are added at the rear (enqueue) and removed from the front (dequeue).

• 8
  Front

  What is the average-case time complexity of search, insert, and delete in a hash table?

  Back

  O(1) for all three operations on average, assuming a good hash function and low load factor.

• 9
  Front

  What is a hash collision and how does chaining resolve it?

  Back

  A collision occurs when two keys hash to the same index. Chaining resolves this by storing a linked list (or similar structure) of all entries at that index.

• 10
  Front

  In a binary search tree (BST), what property must hold for every node?

  Back

  All values in the left subtree are less than the node's value, and all values in the right subtree are greater.

• 11
  Front

  What is the worst-case time complexity of search in a binary search tree?

  Back

  O(n) — occurs when the BST is completely unbalanced (degenerated into a linked list).

• 12
  Front

  What is the height of a complete binary tree with n nodes?

  Back

  O(log n) — the height grows logarithmically with the number of nodes.

• 13
  Front

  What traversal order does in-order traversal of a BST produce?

  Back

  Ascending (sorted) order — it visits the left subtree, then the root, then the right subtree.

• 14
  Front

  What is the difference between a graph's adjacency list and adjacency matrix representations?

  Back

  An adjacency list stores neighbors per vertex (space-efficient for sparse graphs); an adjacency matrix is a 2D array marking edges (O(V²) space, O(1) edge lookup).

• 15
  Front

  What algorithm is used to find the shortest path in an unweighted graph?

  Back

  Breadth-First Search (BFS) — it explores nodes level by level, guaranteeing the shortest path in terms of number of edges.

• 16
  Front

  What is the time complexity of BFS and DFS on a graph with V vertices and E edges?

  Back

  O(V + E) for both BFS and DFS.

• 17
  Front

  What is the average and worst-case time complexity of quicksort?

  Back

  Average: O(n log n). Worst case: O(n²), which occurs when the pivot is consistently the smallest or largest element.

• 18
  Front

  What sorting algorithm has a guaranteed worst-case time complexity of O(n log n)?

  Back

  Merge sort — it always divides the array in half and merges, regardless of input order.

• 19
  Front

  What is the space complexity of merge sort?

  Back

  O(n) — it requires auxiliary space proportional to the input size for the temporary arrays used during merging.

• 20
  Front

  What is the time complexity of binary search, and what precondition must the data satisfy?

  Back

  O(log n). The data must be sorted before binary search can be applied.

• 21
  Front

  What does Big-O notation describe about an algorithm?

  Back

  It describes the upper bound on the algorithm's growth rate — the worst-case time or space complexity as input size n grows.

• 22
  Front

  What is the difference between time complexity and space complexity?

  Back

  Time complexity measures how the number of operations grows with input size; space complexity measures how the memory usage grows with input size.

• 23
  Front

  What sorting algorithm is most efficient for nearly sorted data due to its adaptive nature?

  Back

  Insertion sort — it runs in O(n) time on nearly sorted data because few elements need to be shifted.

• 24
  Front

  What is a heap, and what time complexity does it provide for extracting the minimum (or maximum) element?

  Back

  A heap is a complete binary tree satisfying the heap property (min-heap: parent ≤ children). Extracting the min/max takes O(log n) after reheapification.