Interview Question
Country: United States
Interview Type: Written Test
Algo
1.take 2 arrays X and Y
where X[i]={A[1]+A[2]+ _ _ _ _ +A[i]}
AND Y[i}={A[i]+A[i+1]+A[i+2]+_ _ _ _ +A[n]}
THE ABOVE can be calculated in O(n) time
Now s[i]=x[i-1]+y[i+1]
Boundry conditions needs to be handled for i=0 and i=n
@blackfever: On a close inspection this really works.I was too rigid to notice that.
1 2 3 4
x[1] = 1 , x[2] = 1+2
y[1] = 1+ 2+3+4 y[2] = 2+ 3+4 y[3] = 3+4
s[1] = y[2] s[2] = x[1] + y[3]
This is the correct answer. After a day of thinking, I came up with the same algorithm. It'll take two additional arrays and 3n time = O(n).
Good job, Blackfever!
@Denjar: Assuming you already have two arrays A (input), and S (output) this can be done without any additional array! Simply reuse S.
And it can be done in 2 passes, not 3.
Something like this:
sum = 0
s[0] = 0
// Arrays are 0 indexed.
for i in 0 to n-2
sum += A[i]
S[i+1] = sum
sum = 0
for i = n-1 downto 1
sum += A[i]
S[i-1] = sum
Traverse the array from index 1 to n, and calculate the sum. This step can be done in O(n). Let s be that sum.
Now for each index, do S[i] = s + (~A[i] +1)
~ operator inverts each bit of the value in A[i], converting it to it's 1's complement form. Adding 1 to ~A[i], evaluates the 2's complement of A[i]. We know (~A[i] +1) + A[i] = 0.
Hence (~A[i] +1) = -A[i]
Thus each S[i] = s - A[i]
@Anonymous: is not the question only asking us to use + operations only however I don't think it can ever become o(n) with that.
class Exercise1
{
int[] A = { 1, 2, 3 };
int[] S = new int[3];
public int calc(int sumOfNumbersBeforeI, int sumOfNumbersAfterI, int i)
{
int response = 0;
if (i == A.Length - 1)
{
S[i] = sumOfNumbersBeforeI;
sumOfNumbersAfterI = A[i];
response = A[i];
}
else
{
sumOfNumbersAfterI = calc(sumOfNumbersBeforeI + A[i], sumOfNumbersAfterI, i+1);
S[i] = sumOfNumbersBeforeI + sumOfNumbersAfterI;
response = sumOfNumbersAfterI + A[i];
}
return response;
}
public void runme()
{
calc(0, 0, 0);
foreach (int i in S)
Console.Write(i+",");
Console.ReadKey();
}
}
@aka u forced me to write the complete code :)
int sumUptoi=a[0];
int x[]=new int[a.length];
x[0]=sumUptoi
i=1;
while(i<a.length)
{
x[i]=a[i]+=sumUptoi;
i++;
} //(o(n) asu can see)
int y[]=new int[a.length];
int sumfromi=a[a.length-1];
y[a.length-1]=a[a.length-1];
j=a.length-2;
while(j>=0)
{
y[j]=sumfromi+a[j]
j--;
}//(o(n) asu can see)
for(int i=0;i<a.length;i++)
{
if(i==0)
s[i]=y[i+1];
else if (i==a.length-1)
s[i]=x[i-1]
s[i]=x[i-1]+y[i+1]
}//this is also o(N)
This can be done easily in O(n) following the method explained below:
- Manohar Singh June 01, 20131. take a variable say, Sum, initialize it as Sum = 0.
2. For index i=1 to N do :
S[i] = Sum;
Sum+=A[i];
3. Sum = 0;
4. For index i=N down to 1 do:
S[i]+=Sum;
Sum+=A[i];
5. Done.