Data Structures and Algorithms Flashcards

What is the best-case time complexity of bubble sort?

Answer: O(n)

With an optimized implementation, bubble sort detects an already-sorted array in O(n) by checking for zero swaps in a pass.

Which data structure is used to implement Dijkstra's algorithm efficiently?

Answer: Priority queue (min-heap)

A min-heap priority queue allows Dijkstra's algorithm to extract the minimum-distance unvisited node in O(log n).

What is the time complexity of searching for an element in a balanced BST?

Answer: O(log n)

A balanced BST halves the search space at each step, yielding O(log n) search time.

Which technique resolves hash table collisions by storing multiple entries in a linked list at each bucket?

Answer: Separate chaining

Separate chaining stores colliding elements in a linked list at the same bucket, allowing multiple values per index.

What is a deque (double-ended queue)?

Answer: A data structure allowing insertion and deletion at both ends

A deque supports efficient push and pop operations at both the front and the rear.

In the context of graphs, what does DFS stand for and what data structure does it implicitly use?

Answer: Depth-First Search, uses a stack

Depth-First Search explores as far as possible along each branch using a stack (or recursion's call stack).

What is the primary purpose of the two-pointer technique in algorithm design?

Answer: To reduce time complexity from O(n²) to O(n) for certain array/string problems

The two-pointer technique uses two indices moving toward or away from each other to solve problems like pair-sum or palindrome checks in O(n).