InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
Given a value x and a sorted doubly linked list of different nodes (no two nodes have the same data). Count the number of triplets in the list that add up to x. The expected time complexity is O(n^2) and the expected space complexity is O(1). |
|
Answer» Following the approach os using two POINTERS: From left to right, traverse the doubly linked list. Initialize two pointers for each current node during the traversal: first = pointer to the node next to the current node, and LAST = pointer to the list's last node. Count the NUMBER of PAIRS in the list that add up to the VALUE (x – the current node's data) from the first to the last pointer (algorithm described in Q8). This number should be added to the total count of triplets. Pointer to the last node can be retrieved only once at the beginning. Implementation: int pairCount(struct Node* num1, struct Node* num2, int val){ int cnt = 0; // The loop terminates when either of two the pointers // become NULL, or they cross each other or they become equal while (num1 != NULL && num2 != NULL && num1 != num2 && num2->next != num1) { // pair found if ((num1->value + num2->value) == val) { cnt++; // second is moved in backward direction num2 = num2->prev; // first is moved in forward direction num1 = num1->next; } // else first is moved in forward direction else if ((num1->value + num2->value) < val) num1 = num1->next; // if sum is greater than 'value' // second is moved in backward direction else num2 = num2->prev; } // required number of pairs return cnt;}// function to count triplets in a sorted DLL// whose sum equals a given value 'x'int tripletCount(struct Node* head, int x){ // check if the list is empty if (!head) return 0; int cnt = 0; struct Node* current = head; struct Node* last = head; struct Node* first; // get pointer to the last node of the doubly linked list while (last->next) last = last->next; // traverse the doubly linked list while (current) { // for every current node first = current->next; // count the number of pairs with sum(x - current->data) in the range // first to last and add it to the 'cnt' of triplets cnt += pairCount(first, last, x - current->value); current = current->next; } // required number of triplets return cnt;} |
|