Question 10 Two data structures, Array and LinkedList are having a fight.
Palo Alto Networks technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Question 10
Two data structures, Array and LinkedList are having a fight. LinkedList says that it's the most suitable data structure for any situation. The Array comes up with an algorithm for which the LinkedList is not a suitable one for use. Which of the following is the algorithm that the Array came up with?
**Select any one of the following
Show answer & explanation
Binary search requires O(1) random access to find the middle element. Arrays support O(1) random access, whereas LinkedList requires O(n) sequential traversal, making binary search inefficient on linked lists.
Step-by-step Derivation:
Step 1: Binary search repeatedly divides the search range in half by jumping to the middle index: mid = (low + high) / 2.
Step 2: In an array, accessing element at index 'mid' takes O(1) time.
Step 3: In a linked list, accessing node at index 'mid' requires sequential traversal taking O(k) steps, leading to an overall O(n) time rather than O(log n). Hence binary search is unsuitable for linked lists.