grep

grep.py

# print common area of sorted [(a_i, b_i)]
a = [1, 4, 5, 9]
b = [3, 6, 7, 9]
lines = "0 1 2 3 4 5 6 7 8 9 10".split()


def f(i, no):
    if i == len(a):
        return
    if a[i] > no:
        f(i, no + 1)
    elif a[i] <= no < b[i]:
        print(lines[no])
        f(i, no + 1)
    else:
        print(lines[no])
        k = i + 1
        while k < len(a):
            if b[i] < b[k]:
                break
            k += 1
        f(k, no+1)
f(0, 0)

grep.rb

# Memory spece O(n)

if ARGV.length != 2
  print "you need pattern and N"
  exit!
end

pattern = ARGV[0]
n = ARGV[1].to_i

if n < 0
    print "N must be not less than 0"
    exit!
end

queue = []  # assume that complexity of push and shfit are O(1)
i = 0
while s = STDIN.gets
    if s.match(pattern)
      while not queue.empty?
        puts queue.shift
      end
      puts s
      i = n
    elsif i > 0
      puts s
      i -= 1
    else
      queue.push s
    end
    if queue.length > n
      queue.shift
    end
end