codepad

Language:

; find two added integers

(define sort #f)
(define merge #f)
(let ()
  (define dosort
    (lambda (pred? ls n)
      (if (= n 1)
          (list (car ls))
          (let ((i (quotient n 2)))
            (domerge pred?
                     (dosort pred? ls i)
                     (dosort pred? (list-tail ls i) (- n i)))))))
  (define domerge
    (lambda (pred? l1 l2)
      (cond
        ((null? l1) l2)
        ((null? l2) l1)
        ((pred? (car l2) (car l1))
         (cons (car l2) (domerge pred? l1 (cdr l2))))
        (else (cons (car l1) (domerge pred? (cdr l1) l2))))))
  (set! sort
    (lambda (pred? l)
      (if (null? l) l (dosort pred? l (length l)))))
  (set! merge
    (lambda (pred? l1 l2)
      (domerge pred? l1 l2))))

(define (diffs lt? xs ys)
  (let loop ((xs (sort lt? xs)) (ys (sort lt? ys)) (adds (list)) (subs (list)))
    (cond ((and (null? xs) (null? ys)) (values adds subs))
          ((null? xs) (loop xs (cdr ys) (cons (car ys) adds) subs))
          ((null? ys) (loop (cdr xs) ys adds (cons (car xs) subs)))
          ((lt? (car xs) (car ys)) (loop (cdr xs) ys adds (cons (car xs) subs)))
          ((lt? (car ys) (car xs)) (loop xs (cdr ys) (cons (car ys) adds) subs))
          (else (loop (cdr xs) (cdr ys) adds subs)))))

(define (interview a b)
  (call-with-values
    (lambda () (diffs < a b))
    (lambda (adds subs) subs)))

(display (interview '(1 4 9 2 7 3) '(9 7 4 1)))

Private [?]

Run code