## Nearest Pair

### March 13, 2018

Our solution first stores each value in the list with its position, then iterates through the input list, looking up the position of the conjugate and saving the pair if it is nearer than the current best solution:

(define (nearest-pair xs target) (let ((pos (list))) (do ((i 0 (+ i 1)) (ys xs (cdr ys))) ((null? ys)) (set! pos (cons (cons (car ys) i) pos))) (let loop ((i 0) (xs xs) (np #f) (dist #e1e9)) (if (null? xs) np (let ((j (assoc (- target (car xs)) pos))) (cond ((not j) (loop (+ i 1) (cdr xs) np dist)) ((= i (cdr j)) (loop (+ i 1) (cdr xs) np dist)) ((< (abs (- i (cdr j))) dist) (loop (+ i 1) (cdr xs) (cons (car xs) (car j)) (abs (- i (cdr j))))) (else (loop (+ i 1) (cdr xs) np dist))))))))

For no particular reason, we use association lists rather than hash tables to store the `pos`

dictionary. There are several important quantities with similar definitions: `(- target (car xs))`

is the number that must be added to the current item to make the desired total, `(car j)`

is that number, and `(cdr j)`

is the position of that number, if it exists in the input list. `(abs (- i (cdr j)))`

is the distance between the current item and its conjugate. It’s easy to get those confused; I did while writing this program.

You car run the program at https://ideone.com/5t2k65.

Pages: 1 2

var a = [1, 5, 3, 6, 4, 2];

var p = [];

var q = [];

for(i=0;i<a.length;i++){

for(j=i+1;j<a.length;j++){

if(a[i] + a[j] === 7){

var k = j – i;

p.push([k]);

q.push([k,[a[i],a[j]]]);

}

This being an interview question, you’d definitely want to ask if you can assume the numbers in the list are unique.

is second iteration necessary ” for(s=0;s<item.length;s++){

A Haskell version.

it can be done in O(N) using hash tables

Here’s a solution in Python.

Output:

Line 13 can be removed from my prior solution, as the defaultdict will return an empty list.

O(n) solution: