moar

1 files changed, 65 insertions, 0 deletions

diff --git a/coding-exercises/2/65.rkt b/coding-exercises/2/65.rkt
new file mode 100644
index 0000000..ca26639
--- /dev/null
+++ b/coding-exercises/2/65.rkt
@@ -0,0 +1,65 @@
+#lang racket
+(require "../../shared/sets.rkt")
+
+;; 2*O(n) + O(n) + O(n)
+(define (union-set s1 s2)
+  (define (ordered-list-union-set set1 set2)
+      (cond
+        ((and (null? set1) (null? set2)) '())
+        ((null? set1) (cons (car set2) (ordered-list-union-set set1 (cdr set2))))
+        ((null? set2) (cons (car set1) (ordered-list-union-set (cdr set1) set2)))
+        ((= (car set1) (car set2)) (cons (car set2) (ordered-list-union-set (cdr set1) (cdr set2))))
+        ((> (car set1) (car set2)) (cons (car set2) (ordered-list-union-set set1 (cdr set2))))
+        ((< (car set1) (car set2)) (cons (car set1) (ordered-list-union-set (cdr set1) set2)))))
+  (list->tree
+    (ordered-list-union-set (tree->list s1) (tree->list s2))))
+
+;; 2*O(n) + O(n) + O(n)
+(define (intersection-set set1 set2)
+  (define (ordered-list-intersection-set s1 s2)
+    (if (or (null? s1) (null? s2))
+      '()
+      (let ((x1 (car s1)) (x2 (car s2)))
+        (cond ((= x1 x2)
+               (cons x1
+                     (ordered-list-intersection-set
+                       (cdr s1)
+                       (cdr s2))))
+              ((< x1 x2)
+               (ordered-list-intersection-set
+                 (cdr s1)
+                 s2))
+              ((> x1 x2)
+               (ordered-list-intersection-set
+                 s1
+                 (cdr s2)))))))
+  (list->tree
+    (ordered-list-intersection-set
+        (tree->list set1) (tree->list set2))))
+
+((lambda ()
+  (println "tree -- UNION")
+  (define test216a (make-entry
+                     7
+                     '()
+                     '()))
+  (define test216b (make-entry
+                     4
+                     (make-entry 1 '() '())
+                     (make-entry
+                       8
+                       (make-entry 6 '() '())
+                       (make-entry
+                         10
+                         '()
+                         (make-entry
+                           12
+                           '()
+                           '())))))
+  (println (union-set
+             (list->tree (tree->list test216a))
+             (list->tree (tree->list test216b))))
+  (println (intersection-set
+             (list->tree (tree->list test216a))
+             (list->tree (tree->list test216b))))
+  (newline)))