Question 1 |
What is the time complexities of finding median element from a sorted singly linked list?
Note: The median of a finite list of numbers is the "middle" number, when those numbers are listed in order from smallest to greatest.
Note: The median of a finite list of numbers is the "middle" number, when those numbers are listed in order from smallest to greatest.
O(\log n) | |
O(n) | |
O(1) | |
O(n^2) |
Question 1 Explanation:
Median element is present at middle of the sorted link list. Hence, it require the traversal of n/2 nodes from the starting of link list.
Hence, it takes O(n).
Click to Join Our Telegram Group for Latest Update of MOCK TEST 
Click Here to Practice ALL Previous MOCK TEST FREE
Hence, it takes O(n).
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Question 2 |
What is the time complexity to search an element from a sorted single link list?
NOTE/HINT : Binary search concept with sorted array.
NOTE/HINT : Binary search concept with sorted array.
O(\log n) | |
O(n) | |
O(1) | |
O(n^2) |
Question 2 Explanation:
Binary search technique can be used in sorted array but not in link list. As binary search requires the middle element in O(1) time which is not possible in link list while it is possible in array. Hence, only sequential search is possible to search an element from sorted link list which require O(n).
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Question 3 |
What are the time complexities of finding 7th smallest element from beginning and 7th largest element from end in a sorted singly linked list?
Let n be the number of nodes in linked list, you may assume that n > 7
Let n be the number of nodes in linked list, you may assume that n > 7
O(1) O(1) | |
O(1) O(n) | |
O(n) O(1) | |
O(n) O(n) |
Question 3 Explanation:
In sorted single link list, 7th smallest element is present as 7th node from the starting. Hence, only we have to traverse 7 node from the starting node irrespective of number of node in link list n. Hence, it can be found on O(1).
In sorted single link list, 7th largest element is present as 7th node from the end of link list. To find that element, we have to traverse the link list starting to end. Hence, it will take O(n).
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
In sorted single link list, 7th largest element is present as 7th node from the end of link list. To find that element, we have to traverse the link list starting to end. Hence, it will take O(n).
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Question 4 |
What is the time complexity to delete a node pointed by pointer P from a single link list?
O(n^2) | |
O(n) | |
O(1) | |
O(\log n) |
Question 4 Explanation:
As shown in the above figure, to delete node pointed by P we requires the pointer of previous node of P. To get the pointer of previous node of P, we have to start traversal from starting to that node. Hence, it will depends on number of node in link list. Hence, it will take O(n).
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Question 5 |
What is the time complexity to delete a node pointed by pointer P from a double link list?
O(n^2) | |
O(n) | |
O(1) | |
O(\log n) |
Question 5 Explanation:
As shown in the above figure, to delete node pointed by P we requires the pointer of previous node of P. It can be found in O(1) as P -> prev.
So, total two pointer need to be change as shown on above figure. That can be done in O(1).
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
There are 5 questions to complete.
Helpful to revise my deta structure knowledge.