[zyzzy]

If someone had some experience with pascal triangle, they could come up with a very efficient solution, that might put them at a advantage. If the interviewer valued efficient solutions.

So far dspeyer, has one of the most efficient algorithms.

  def pascal(i):
        o=[1]
        for j in xrange(1,i):
           o.append(o[-1] * (i - j) / j)
        return o

in ruby this could be

  def pascal2(i)
    o=[1]
    i += 1
    for j in 1.upto(i - 1 )
       o << o[-1] * (i - j)/j
    end
    o
   end

we could make it even more efficient if we remember a there is symmetry in a pascal triangle. So that we don't have to calculate all the values in a row, maybe just half of the values. We have to calculate the row a little different if it is even or odd in number.

  def pascal(i)
   o=[1]
   i += 1
   if i == 1 then
    return o 
   end
   i.even? ? d = i / 2  - 1 : d = i / 2 
   for j in 1.upto(d )
            o << o[-1] * (i - j)/j
   end
   o[0..i/2] + o[0..i/2 - 1].reverse
   end

So far it up to 2x as fast. I wrote this method in Ruby to time the different methods, pascal, pascal2.

  def timeA(m,n)
    begin_time = Time.now
    send(m,n)
    end_time = Time.now
    p "Time elapased #{(end_time - begin_time)*1000}    milliseconds"
    end

these are the times I get

  ruby-1.9.2-p290 :037 > timeA('pascal2',40000)
  "Time elapased 949.9490000000001 milliseconds"
   => "Time elapased 949.9490000000001 milliseconds" 
  ruby-1.9.2-p290 :038 > timeA('pascal',40000)
  "Time elapased 470.48699999999997 milliseconds"
   => "Time elapased 470.48699999999997 milliseconds" 
  ruby-1.9.2-p290 :039 > timeA('pascal',80000)
  "Time elapased 1776.224 milliseconds"
   => "Time elapased 1776.224 milliseconds" 
  ruby-1.9.2-p290 :040 > timeA('pascal2',80000)
  "Time elapased 5722.419000000001 milliseconds"
   => "Time elapased 5722.419000000001 milliseconds" 
  ruby-1.9.2-p290 :041 > timeA('pascal',200000)
  "Time elapased 160416.34199999998 milliseconds"
   => "Time elapased 160416.34199999998 milliseconds" 
  ruby-1.9.2-p290 :042 > timeA('pascal2',200000)
  "Time elapased 235113.38 milliseconds"
  => "Time elapased 235113.38 milliseconds"