DSA interview question

Find Pairs with a Given Sum in a Sorted Doubly Linked List

Medium · Data structures · Topics: linkedlist, doubly linkedlist, two pointer

The problem

A price-matching tool keeps a store's product prices in a sorted doubly linked list of distinct values and needs every pair of products whose prices add up to a gift card's value. Checking all pairs is O(n²); a hash set works but ignores the sorting. Because the list is doubly linked, the classic two-pointer technique applies directly: one pointer starts at the head (smallest), one at the tail (largest), and they walk toward each other depending on whether the current sum is too small or too large.

Example: 1 <-> 2 <-> 4 <-> 5 <-> 6 <-> 8 <-> 9, target 7 → (1, 6), (2, 5).

Function signature

vector<pair<int, int>> findPairsWithSum(DNode* head, int target);  // pairs (smaller, larger), ascending by first value

Test cases

Input `(list, target)`	Output	Explanation
`(1 <-> 2 <-> 4 <-> 5 <-> 6 <-> 8 <-> 9, 7)`	`(1, 6) (2, 5)`
`(1 <-> 5 <-> 6, 6)`	`(1, 5)`
`(2 <-> 4 <-> 6 <-> 8, 10)`	`(2, 8) (4, 6)`
`(1 <-> 2 <-> 3, 10)`	(none)
`(5, 10)`	(none)	One node can't pair with itself

(Confirm: the list is sorted with distinct values; each pair uses two different nodes.)

How interviewers phrase it

"Find pairs with a given sum in a sorted doubly linked list" (GeeksforGeeks).
The array version is two-sum on a sorted array; the doubly linked list simply provides the backward pointer.

Clarifying questions to ask

Is the list sorted? Are values distinct?
In what order should pairs be reported?
Can extra space be used? (A hash set would also work.)

Follow-ups to expect

"How do you find the tail?"
"Why move the left pointer when the sum is too small?"
"When do you stop?"
"How would a singly linked list change this?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview