Hash Map vs Array vs Linked List for Lookup in DSA C - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare an array of integers with size 5.

DSA C

int arr[[1]];

Drag options to blanks, or click blank then click option'

A5

B10

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 as size which creates an empty array.

Using size 1 or 10 which does not match the requirement.

The array size must be 5 to hold 5 integers.

2fill in blank

medium

Complete the code to access the third element of the array.

DSA C

int value = arr[[1]];

Drag options to blanks, or click blank then click option'

A3

B0

C1

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Using index 3 which is the fourth element.

Using index 1 which is the second element.

Array indexing starts at 0, so the third element is at index 2.

3fill in blank

hard

Fix the error in the linked list node definition by completing the pointer declaration.

DSA C

struct Node {
    int data;
    struct Node[1] next;
};

Drag options to blanks, or click blank then click option'

A*

B&

C[]

D.

Attempts:

3 left

💡 Hint

Common Mistakes

Using '&' which is address-of operator, not pointer declaration.

Using '.' which accesses members, not declares pointers.

The next pointer must be declared as a pointer to struct Node using '*'.

4fill in blank

hard

Fill both blanks to complete the hash map lookup function header and return type.

DSA C

[1] [2](HashMap* map, int key);

Drag options to blanks, or click blank then click option'

Aint

Blookup

Cvoid

Dinsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using void as return type which means no value returned.

Using insert as function name which is for adding, not lookup.

The function returns an int and is named lookup to find a value by key.

5fill in blank

hard

Fill all three blanks to complete the array search function that returns index or -1 if not found.

DSA C

int search(int arr[], int size, int target) {
    for (int [1] = 0; [2] < size; [3]++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

Drag options to blanks, or click blank then click option'

Ai

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names causing compilation errors.

Using 'j' which is not declared in the loop.

The loop variable is 'i' used consistently for initialization, condition, and increment.

Practice

1. Which data structure provides the fastest average lookup time for finding an element by key?

easy

A. Stack

B. Hash Map

C. Linked List

D. Array

Solution

1. Step 1: Understand lookup times for each data structure

   Hash Map uses hashing to find keys quickly, usually in constant time O(1). Arrays require scanning or index access, O(1) if index known but O(n) if searching by value. Linked Lists require scanning all nodes, O(n).

2. Step 2: Compare average lookup times

   Hash Map is fastest on average for key lookup due to direct hashing. Arrays and Linked Lists are slower for key-based search.

3. Final Answer:

   Hash Map -> Option B

4. Quick Check:

   Fastest lookup by key = Hash Map [OK]

Hint: Hash Map lookup is usually O(1), faster than arrays or lists [OK]

Common Mistakes:

• Confusing array index access with key lookup
• Thinking linked list lookup is fast
• Assuming stack is good for key lookup

2. Which of the following is the correct way to declare an array of 5 integers in C?

easy

A. int arr(5);

B. int arr = new int[5];

C. array<int> arr(5);

D. int arr[5];

Solution

1. Step 1: Recall C array declaration syntax

   In C, arrays are declared with type, name, and size in square brackets, e.g., int arr[5];

2. Step 2: Check each option

   int arr[5]; matches correct C syntax. int arr = new int[5]; uses C++ style new keyword. int arr(5); is invalid syntax. array<int> arr(5); is C++ template syntax, not C.

3. Final Answer:

   int arr[5]; -> Option D

4. Quick Check:

   C array declaration = int arr[5]; [OK]

Hint: C arrays use square brackets for size, no new keyword [OK]

Common Mistakes:

• Using C++ new keyword in C
• Using parentheses instead of brackets
• Confusing C++ templates with C arrays

3. Consider the following C code snippet using a linked list for lookup:

typedef struct Node {
  int key;
  int value;
  struct Node* next;
} Node;

int lookup(Node* head, int key) {
  Node* current = head;
  while (current != NULL) {
    if (current->key == key) {
      return current->value;
    }
    current = current->next;
  }
  return -1;
}

// List: (1,10) -> (2,20) -> (3,30) -> NULL
// Call: lookup(head, 2);

What is the output of lookup(head, 2);?

medium

A. 20

B. 10

C. 30

D. -1

Solution

1. Step 1: Trace the linked list nodes

   The list nodes have keys and values: (1,10), (2,20), (3,30). The function searches for key 2.

2. Step 2: Follow lookup function logic

   Starting at head (key=1), key != 2, move next. Next node key=2 matches, return value 20.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Found key 2 with value 20 [OK]

Hint: Linked list lookup scans nodes until key found [OK]

Common Mistakes:

• Returning value of first node always
• Confusing key and value fields
• Returning -1 when key exists

4. The following C code attempts to find a value in an array but has a bug:

int find(int arr[], int size, int target) {
  for (int i = 0; i <= size; i++) {
    if (arr[i] == target) {
      return i;
    }
  }
  return -1;
}

What is the bug in this code?

medium

A. Return value should be arr[i], not i

B. Function should return void

C. Loop condition should be i < size, not i <= size

D. Array parameter should be int* arr

Solution

1. Step 1: Analyze loop boundary

   The loop runs from i = 0 to i <= size, which means i can be equal to size. Array indices go from 0 to size-1, so arr[size] is out of bounds.

2. Step 2: Correct loop condition

   Change condition to i < size to avoid accessing out of bounds memory.

3. Final Answer:

   Loop condition should be i < size, not i <= size -> Option C

4. Quick Check:

   Array index must be less than size [OK]

Hint: Array indices go 0 to size-1, use i < size in loops [OK]

Common Mistakes:

• Using <= size causes out-of-bounds access
• Returning arr[i] instead of index
• Changing return type unnecessarily

5. You need to store a large number of unique integer keys with associated values and perform frequent lookups. Which data structure is best and why?

hard

A. Hash Map - because it provides average constant time lookup

B. Linked List - because it allows easy insertion

C. Array - because it uses contiguous memory

D. Binary Search Tree - because it keeps keys sorted

Solution

1. Step 1: Understand requirements

   We need to store many unique keys with values and do frequent lookups efficiently.

2. Step 2: Evaluate data structures

   Array is inefficient for key lookup unless keys are indices. Linked List has slow O(n) lookup. Binary Search Tree has O(log n) lookup but more complex. Hash Map offers average O(1) lookup, ideal for fast access.

3. Final Answer:

   Hash Map - because it provides average constant time lookup -> Option A

4. Quick Check:

   Fast lookup with many keys = Hash Map [OK]

Hint: For fast key lookup, choose Hash Map over arrays or lists [OK]

Common Mistakes:

• Choosing array for non-index keys
• Ignoring lookup speed in linked lists
• Preferring BST without sorting need