Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

3 sequential numbers

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.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List