Choosing data structures for interview problems in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main reason to choose the right data structure in an interview problem?

Choosing the right data structure helps solve problems efficiently by optimizing speed, memory use, and code simplicity.

beginner

When should you use a hash table (dictionary) in an interview problem?

Use a hash table when you need fast lookups, insertions, or deletions, usually in average constant time.

intermediate

Why might a linked list be chosen over an array?

A linked list is better when you need frequent insertions or deletions in the middle of the list without shifting elements.

intermediate

What data structure is best for implementing a priority queue?

A heap is best because it allows quick access to the highest or lowest priority element and efficient insertions.

beginner

How does understanding problem constraints help in choosing data structures?

Knowing constraints like input size and operation frequency guides you to pick data structures that balance speed and memory well.

Which data structure provides the fastest average lookup time?

A Hash table

B Array

C Linked list

D Binary tree

Hash tables provide average constant time lookup, faster than arrays (linear search) or linked lists.

If you need to maintain elements in sorted order with fast insertion, which data structure is best?

A Array

B Heap

C Balanced binary search tree

D Stack

Balanced binary search trees keep elements sorted and allow fast insertions and lookups.

Which data structure is ideal for implementing undo functionality?

A Queue

B Stack

C Hash table

D Graph

Stacks follow last-in, first-out order, perfect for undo operations.

What data structure should you use if you want to quickly find the minimum element repeatedly?

A Heap

B Queue

C Linked list

D Array

A min-heap allows quick access to the smallest element.

Why is it important to consider memory usage when choosing a data structure?

A Memory usage does not affect performance

B Memory usage only matters for graphics

C Memory usage is irrelevant in interviews

D Some data structures use more memory which can slow down the program

Data structures that use more memory can cause slower performance due to cache misses or memory limits.

Explain how you decide which data structure to use when solving an interview problem.

Think about what operations are most frequent and what performance matters most.

Describe scenarios where a linked list is better than an array and vice versa.

Consider how elements are stored and accessed.

Practice

1. Which data structure is best suited for implementing a phone book where you need to quickly find a person's phone number by their name?

easy

A. Linked List

B. Queue

C. Stack

D. Hash Table

Solution

1. Step 1: Understand the problem requirement

   The problem requires fast lookup of phone numbers by name, which means quick access based on a key.

2. Step 2: Choose data structure with fast key-based access

   Hash Tables provide average constant time O(1) lookup by key, making them ideal for this use case.

3. Final Answer:

   Hash Table -> Option D

4. Quick Check:

   Fast key lookup = Hash Table [OK]

Hint: Use hash tables for fast key-value lookups [OK]

Common Mistakes:

• Choosing linked list which has slow search
• Using stack or queue which are not for key-based lookup

2. Which of the following is the correct syntax to declare an empty stack using a list in Python?

easy

A. stack = {}

B. stack = []

C. stack = ()

D. stack = set()

Solution

1. Step 1: Recall Python data types for stack implementation

   Stacks are commonly implemented using lists in Python because lists support append() and pop() methods.

2. Step 2: Identify correct syntax for empty list

   An empty list is declared with square brackets []. Curly braces {} create a dictionary, () a tuple, and set() a set.

3. Final Answer:

   stack = [] -> Option B

4. Quick Check:

   Empty list syntax = stack = [] [OK]

Hint: Use [] to create an empty list for stack in Python [OK]

Common Mistakes:

• Using {} which creates a dictionary, not a list
• Using () which creates a tuple, not a list

3. Consider the following Python code snippet:

queue = []
queue.append(10)
queue.append(20)
queue.pop(0)
print(queue)

What will be the output?

medium

A. [20]

B. Error

C. [10]

D. [10, 20]

Solution

1. Step 1: Trace the queue operations

   Initially queue is empty []. After append(10), queue = [10]. After append(20), queue = [10, 20].

2. Step 2: Understand pop(0) effect

   pop(0) removes the first element (10), so queue becomes [20].

3. Final Answer:

   [20] -> Option A

4. Quick Check:

   pop(0) removes first element = [20] [OK]

Hint: pop(0) removes first item in list acting as queue [OK]

Common Mistakes:

• Thinking pop() removes last element by default
• Expecting no change after pop(0)
• Confusing list with stack behavior

4. You wrote this code to implement a stack using a list in Python:

stack = []
stack.push(5)
stack.push(10)
print(stack.pop())

What is the error in this code?

medium

A. Stack cannot be implemented with list

B. 'pop' method does not exist for list

C. 'push' method does not exist for list

D. Syntax error in print statement

Solution

1. Step 1: Check list methods for stack operations

   Python lists use append() to add elements, not push().

2. Step 2: Identify the error

   Calling stack.push(5) causes AttributeError because 'push' is not a list method.

3. Final Answer:

   'push' method does not exist for list -> Option C

4. Quick Check:

   Use append() for stack push in list [OK]

Hint: Use append() to push on list, not push() [OK]

Common Mistakes:

• Assuming push() is a list method
• Thinking pop() is missing
• Believing stack can't be made with list

5. You need to design a system that keeps track of the top 3 highest scores in a game, updating efficiently as new scores arrive. Which data structure is the best choice?

hard

A. Min-Heap of size 3

B. Max-Heap of all scores

C. Linked List sorted ascending

D. Queue storing last 3 scores

Solution

1. Step 1: Understand the requirement for top 3 scores

   We want to keep only the highest 3 scores updated efficiently as new scores come in.

2. Step 2: Choose data structure for efficient top-k tracking

   A min-heap of size 3 keeps the smallest of the top scores at the root. When a new score arrives, compare with root; if higher, replace root and heapify. This keeps top 3 efficiently.

3. Final Answer:

   Min-Heap of size 3 -> Option A

4. Quick Check:

   Top-k tracking = Min-Heap size k [OK]

Hint: Use min-heap of size k to track top k items efficiently [OK]

Common Mistakes:

• Using max-heap of all scores wastes memory
• Using linked list is slow for updates
• Queue stores last scores, not top scores