interesting algorithmic problems and puzzles

THESE QUESTIONS ARE TAKEN FROM INTERVIEWS OF GOOGLE,YAHOO,MSFT AND ADOBE.
THE QUESTIONS ARE LITTLE BIT ALTERED INORDER NOT TO BREAK THE NDA.

TRY SOLVING THESE WITH A PEN AND PAPER.

1.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].

Solve it without division operator and in O(n).

2.Classical josephus problem-there are N numbers numbered from 1 to N and there is game to b played tht startin from 1 every second num wud b eliminated .... perform ths untill thr wud b only single num remained ...
e.g.
thr r 5 nums
1 2 3 4 5
thn aftr 1st iteration 1 3 5 wud remained
thn .... thn 1 will b elliminated and thn 5
3 will remain alone...

give sum efficient algo to calculate which num will remain at the end

3.the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.Write some good code to find this maximum sum.

4.Consider a String with N (say 1000k) words in it.Write a function which takes two parameters i,j<=N which swaps the position of i th and the j th words present in the string.
Ex. This blog is really rocking courtesy citians.
if input if 2,5 thn o/p is
This rocking is really blog courtesy citians.

5.A convex polygon hull is given . How would you search a point ( whether a vertex or not)
in O( log n). n = number of vertices in polygon.

6.Write some efficient pseudocode to find the 6th maximum element from an array of numbers.

7.Try designing a moore/mealy machine to output the exor of the input bits supplied.