fork download
copy 
  1. ; google interview question
  2.  
  3. (define (fold-right op base xs)
  4.   (if (null? xs)
  5.       base
  6.       (op (car xs) (fold-right op base (cdr xs)))))
  7.  
  8. (define (cross . xss)
  9.   (define (f xs yss)
  10.     (define (g x zss)
  11.       (define (h ys uss)
  12.         (cons (cons x ys) uss))
  13.       (fold-right h zss yss))
  14.     (fold-right g '() xs))
  15.   (fold-right f (list '()) xss))
  16.  
  17. (define (intersect xs ys)
  18.   (cond ((null? xs) (list))
  19.         ((member (car xs) ys)
  20.           (cons (car xs) (intersect (cdr xs) ys)))
  21.         (else (intersect (cdr xs) ys))))
  22.  
  23. (define sort #f)
  24. (define merge #f)
  25. (let ()
  26.   (define dosort
  27.     (lambda (pred? ls n)
  28.       (if (= n 1)
  29.           (list (car ls))
  30.           (let ((i (quotient n 2)))
  31.             (domerge pred?
  32.                      (dosort pred? ls i)
  33.                      (dosort pred? (list-tail ls i) (- n i)))))))
  34.   (define domerge
  35.     (lambda (pred? l1 l2)
  36.       (cond
  37.         ((null? l1) l2)
  38.         ((null? l2) l1)
  39.         ((pred? (car l2) (car l1))
  40.          (cons (car l2) (domerge pred? l1 (cdr l2))))
  41.         (else (cons (car l1) (domerge pred? (cdr l1) l2))))))
  42.   (set! sort
  43.     (lambda (pred? l)
  44.       (if (null? l) l (dosort pred? l (length l)))))
  45.   (set! merge
  46.     (lambda (pred? l1 l2)
  47.       (domerge pred? l1 l2))))
  48.  
  49. (define (g xs)
  50.   (car
  51.     (sort
  52.       (lambda (xs ys) (> (car xs) (car ys)))
  53.       (map
  54.         (lambda (xs)
  55.           (cons (* (string-length (car xs))
  56.                    (string-length (cadr xs)))
  57.                 xs))
  58.         (filter
  59.           (lambda (xs)
  60.             (null?
  61.               (intersect
  62.                 (string->list (car xs))
  63.                 (string->list (cadr xs)))))
  64.           (cross xs xs))))))
  65.  
  66. (display (g '("ABCW" "BAZ" "FOO" "BAR" "XTFN" "ABCDEF")))
Success #stdin #stdout 0.04s 8792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(16 ABCW XTFN)
https://ideone.com/1WgN56
language:
Scheme (guile 2.2.4)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!