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-04 17:31

>>15
Isn't that like, O(n3)?

Here's mine, which should be O(n):
import random

def findthree(array): # returns [i, j, k] or None
  solution = []
  minimum = None

  for i, n in enumerate(array):
    # Keep looking for an array element larger than the last one.
    if minimum is None or n > minimum:
      minimum = n
      solution.append(i)
      if len(solution) >= 3:
        return solution

for i in range(10):
  array = [random.randrange(1, 100) for i in range(10)]
  print array, '==>', findthree(array)

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