What is the best way to implement a map (storing a key, value) with fixed number of key,...
IBM technical mcq question, verified with a worked answer. Free to practise - no sign-up.
What is the best way to implement a map (storing a key, value) with fixed number of key, value pairs in a C program, where key is a contiguous number and value can contain any number?
Example: {1,0xABCD}, {2,0x1234}, {3,0x5678}
Pick ONE option
Show answer & explanation
Arrays are the optimal choice for a fixed-size map with contiguous numeric keys because they provide O(1) direct index-based access. Since keys are contiguous (1, 2, 3...), you can directly map key to array index, eliminating traversal overhead. Linked lists and stacks require sequential traversal, resulting in O(n) lookup time and unnecessary memory overhead for pointers.
Step-by-step Derivation:
Analysis of each option:
Arrays (A): With contiguous keys starting from 1, create an array where array[key] = value. Access is O(1) direct indexing. Memory-efficient for fixed-size maps.
- Example: arr[1] = 0xABCD, arr[2] = 0x1234, arr[3] = 0x5678
Circular Linked List (B): Requires traversing nodes to find a key. O(n) lookup. Unnecessary pointer overhead for a fixed-size collection.
Doubly Linked List (C): Similar to circular linked list. O(n) lookup even though bidirectional traversal is possible. Overkill for fixed-size data with contiguous keys.
Stack (D): LIFO structure doesn't support arbitrary key lookup. Would need to pop elements to access middle keys. Not suitable for map semantics.
Conclusion: Arrays directly leverage the contiguous key property for optimal O(1) access and minimal memory overhead.