Find Pairs
We are given a sorted doubly-linked list which contains distinct positive integers, and an integer ‘X’. Print all such unique pairs from the given list so that their sum is equal to ‘X’.

Input format :

The first line of the input contains the elements of the doubly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element. The second line contains a single integer ‘X’.

Output format :

Print pair elements separated by a single pace where the first element of the pair should be less than the second element of the pair. The order of pairs does not matter. Print each unique pair in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the function and return the answer.

Follow Up:

Try to solve this problem in linear time complexity without using any other data structures.

Constraints :

1

Question

Find Pairs

We are given a sorted doubly-linked list which contains distinct positive integers, and an integer ‘X’. Print all such unique pairs from the given list so that their sum is equal to ‘X’.

Input format :

The first line of the input contains the elements of the doubly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

The second line contains a single integer ‘X’.

Output format :

Print pair elements separated by a single pace where the first element of the pair should be less than the second element of the pair. The order of pairs does not matter.

Print each unique pair in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the function and return the answer.

Follow Up:

Try to solve this problem in linear time complexity without using any other data structures.

Constraints :

1 <= N <= 5*10^5
-2*10^9 <= X <= 2*10^9
-10^9 <= data <= 10^9 and data != -1

Where ‘N’ is the length of the linked list and ‘X’ is the required pair sum value.

Time Limit: 1 sec

Accepted Answer

Used a hashmap for O(n) appproach

Accepted Answer

Brute Force Approach

A simple approach for this problem is to explore all the pairs and print those pairs which have the sum equal to ‘X’.

Pick one by one each node and pivot that node.
Find all nodes in the remaining list by traversing in the forward direction such that whose sum with the pivoted node is equal to the ‘X’.

Space Complexity: O(n)Explanation:

O(1)

we are not using any extra space here.

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ is the number of nodes in the doubly linked list.

For each pivoted node, we are exploring all other nodes thus there are total N*(N+1)/2 nodes. So Overall Time complexity is O(N^2)

Accepted Answer

HashSet Based Approach

To improve our run time complexity, we need a more efficient way to check if the complement exists in the doubly linked list or not. If the complement exists, then print the complement and the data of the current node.

Steps:

While iterating and inserting elements into HashSet, we first look back to check if the current element’s complement already exists in the table. If it exists, We found a pair.
Insert the data of the current node in HashSet.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the doubly linked list.

We are using a HashSet to store ‘N’ elements. So overall space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the doubly linked list.

We are traversing the list while doing insert and lookup operation in HashSet, So there will be ‘N’ insert and ‘N’ lookup operation. On average a HashSet takes O(1) time in both lookup and insert operation. So overall time complexity is O(N).

Accepted Answer

Two Pointer Approach

Since the given doubly linked list is sorted, so here we can use two-pointer techniques.

The algorithm looks like:

Initialise two pointers to find the paired element in the sorted doubly linked list. Let’s say the first pointer is “start” and the second pointer is “end”.
Make “start” as the first node of the doubly linked list and “end” as the last node of the doubly linked list. Here we don’t have random access property, so we need to find the last node of the doubly linked list by traversing the entire list.
If the sum of data at the “start” node and “end” node is less than ‘X’, then we want to increase the sum so we will move the “start” pointer forward to get a larger value node.
If the sum of data at the “start” node and “end” node is greater than ‘X’, then we want to decrease the sum so we will move the “end” pointer backwards to get a smaller value node.
Loop will terminate when either of “start” or “end” become NULL, or when they cross each other, i.e. (end->next==start).

Space Complexity: O(n)Explanation:

O(1), we are not using any extra space here.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the doubly linked list.

We are traversing the whole linked-list to get the last node of the linked-list. Then in each operation either we are moving start in the forward direction or moving end in the backward direction, so at max, we can have O(N) operations.

We are given a sorted doubly-linked list which contains distinct positive integers, and an integer ‘X’. Print all such unique pairs from the given list so that their sum is equal to ‘X’.

Input format :

Output format :

Note :

Follow Up:

Constraints :

Top Bank of America Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Bank of America Software Developer