Skip to content

Instantly share code, notes, and snippets.

@tail-call
Created December 19, 2022 10:25
Show Gist options
  • Save tail-call/d936bbf9f610af41e9fde421ad05b8a2 to your computer and use it in GitHub Desktop.
Save tail-call/d936bbf9f610af41e9fde421ad05b8a2 to your computer and use it in GitHub Desktop.
(require math/flonum)
(define (sorted-lists->stream list-1 list-2)
(cond ((empty? list-1) list-2)
((empty? list-2) list-1)
((< (car list-1)
(car list-2))
(stream-cons (car list-1)
(sorted-lists->stream (cdr list-1) list-2)))
(else
(stream-cons (car list-2)
(sorted-lists->stream list-1 (cdr list-2))))))
(define (middle-of-a-stream stream)
(let loop ([scanner stream]
[middle #f]
[is-odd #f])
(cond ((stream-empty? scanner)
(values middle is-odd))
((not middle)
(loop (stream-rest scanner)
scanner
(not is-odd)))
((not is-odd)
(loop (stream-rest scanner)
(stream-rest middle)
(not is-odd)))
(else
(loop (stream-rest scanner)
middle
(not is-odd))))))
(define (average a b)
(/ (+ a b) 2))
(define (stream-second stream)
(stream-first (stream-rest stream)))
(define/contract (find-median-sorted-arrays nums1 nums2)
(-> (listof exact-integer?) (listof exact-integer?) flonum?)
(let-values ([(middle is-odd)
(middle-of-a-stream (sorted-lists->stream nums1 nums2))])
(fl (if is-odd
(stream-first middle)
(average (stream-first middle)
(stream-second middle))))))
@tail-call
Copy link
Author

This is a solution to the Leetcode problem #4. I wanted to make it Racket because I felt like it.

Earlier versions of the program didn't use streams, so data was stored in lists — I mean Lisp lists, the cons cells — and those lists allocated too much memory. Some of the tests were failing, so I decided to give streams a shot (never used them before).

I like the algorithm I came up with for searching for the middle of the stream (middle-of-a-stream). We can't compute the middle of a stream directly unless we reached the end of the list.

So basically I'm merging two sorted lists into a stream and then I look for the median value which is in the middle of the stream.

I like my solution a lot.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment