Name:
eye
2012-04-04 16:06
Alright geniuses, if you think your programming ability is up to par, lets see you solve this:
Write an algorithm which in O(n) time finds 3 indices i, j, and k such that i < j < k and array[i] < array[j] < array[k].
Name:
Anonymous
2012-04-07 10:33
(define (blah array)
(define min 999999999999)
(define max 0)
(define min+1 999999999999)
(define i #f)
(define j #f)
(define k #f)
(for ([x (in-range 0 (vector-length array))])
(define current (vector-ref array x))
(cond
((current . < . min)
(set! min current)
(set! i x))
((and (current . > . min) (current . < . min+1))
(set! min+1 current)
(set! j x))
((current . > . max)
(set! max current)
(set! k x))))
(values i j k))
Example:
> (blah (vector 999 1 998 1 7 2 8 3 8 2 9 3 4 10 4 5 6))
1
5
13
[m]
999 1 998 1 7 2 8 3 8 2 9 3 4 10 4 5 6
^ ^ ^
i j k
i < j < k satisfied: 1 < 5 < 13
array[i] < array[j] < array[k] satisfied: 1 < 2 < 10
[/m]
Next time do your own homework though.