Coding Puzzle

Supposedly this is one of the Google Interview Questions:

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].

When I first looked at it I didn't know what to do with it. I think a lot of it had to do with the fact that I was busy with work and didn't take the time to think about it. So today I was driving and came across an answer. Here is my proposed answer written in ruby (the machine I'm doing this on didn't have a C complier but it did have a ruby interpreter). Pardon my ruby style, I'm still new at it.

Also, it has a bit of unnecessary code to print out the multiplications that are happening (proof to me that it worked)

#Total O(2n) = O(n)
def SecondArray(orig)
 arr2 = Array.new(orig.length,1)
 strArr = Array.new(orig.length,"")
 #First Loop O(n)
 arr2.each_index do |x| 
      if(x != 0) 
       arr2[x] = arr2[x-1]*orig[x-1]
       char = ""
       if( strArr[x-1].length > 0 )
        char = "*"
       end
       strArr[x] = strArr[x-1]+char+orig[x-1].to_s
       end 
     end

 temp = 1
 i = orig.size - 1 
 tempStr = ""

 #Second Loop O(n)
 while (i >= 0 )
  arr2[i] = arr2[i]*temp
  temp = temp*orig[i]
  char = ""
  if( strArr[i].length > 0 && tempStr.length > 0)
   char = "*"
  end
  strArr[i] = strArr[i]+char+tempStr

  tempStr = orig[i].to_s+char+tempStr
  i = i-1
 end

 i = 0
 strArr.each do |x|
     print i,":",x,"\n"
     i = i+1
     end
 print "\n"

 arr2
end


arrSize = 10
arr = Array.new(arrSize){|idx| idx+1}
#print arr
arr.each{|x| print x-1,":",x,"\n"}
print "\n"
arr2 = SecondArray(arr)

#Print the resulting Array
i = 0
arr2.each do |x|
    print i,":",x,"\n"
    i = i+1
    end
print "\n"

Labor Day

Finally. For the first time in quite a few years I get Labor Day off. As a student of RIT we were regularly exposed to the joys of a first day of school on Labor Day. Most schools have the decency to make it a vacation day, but we were not so lucky. Beside the point, this year my current employer has decided to make Labor Day a vacation day, and with that my wife and I are planning a trip to Salem, MA. She's been there before, but not in quite a while and I've never been. We're planning on camping just outside the city on the ocean. In fact, here's a map of our trip (I just wanted an excuse to use the new embedded map feature of google maps)

The Sky

Today Google Earth was updated to allow the viewing of the sky. This is a nice update to a favorite application that now allows one to view the beauties of the night sky, and also learn more / get more detailed images of heavenly bodies.

This is an example shot of the new appication:



I think it's nice, but my current favorite night time sky application is Stellarium which gives a nice perspective of the sky from anywhere on earth (it was really helpful in my astronomy class to help identify stars, constellations, etc..).

Also worth mentioning is Celestia however, I have never found it to be quite as useful.