Amazon Interview Question
SDE1sCountry: India
for ex:
[Initial List: 2 3 4 6 8 5 3 ]
first itr will give
1 1 2 2 -3 -2
second
0 1 0 -5 1
and equation looks like
for last element in second itr = 1
[Initial List: 2 3 4 6 8 5 3 ]
3-(5*2)+8 = 1
after 3rd itr
1 -1 -5 6 and equation looks like
for last element in 3rd itr = 6
[Initial List: 2 3 4 6 8 5 3 ]
3-(5*3)+(8*3)-6 = 6
after 4th itr
-2 -4 11 and equation looks like
for last element in 4th itr = 11
[Initial List: 2 3 4 6 8 5 3 ]
3-(5*4)+(8*6)-(6*4)+4
after 5th itr
-2 15 and equation looks like
for last element in 4th itr = 15
[Initial List: 2 3 4 6 8 5 3 ]
3-(5*5)+(8*10)-(6*10)+(4*5)-3
aaaaah not able to figure out in wt order this series is moving.....
@PKT: The multipliers: 1 -2 1, 1 -3 3 -1, 1 -4 6 -4 1, 1 -5 10 -10 5 -1 are all rows of the pascal's triangle (with a - sign thrown in alternately), and are binomial coefficients as I mentioned in Observation 2.
What part are you having difficulty with? (if any...)
@Arun, you don't seem to have read the whole sentence. I repeat here:
r choose 0, r choose 1, r choose 2, ... r choose r, can be computed in O(r) time, by computing r choose t in O(1) time after already having computed r choose (t-1)
Note the part about computing r choose t in O(1) time _after_ having computed r choose (t-1).
@Loler : I understood the above logic ..
but I didn't get how u come to know it is "r choose t" ? By just looking at, I couldn't get the idea of "r choose t" .. Can u pls explain ?
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SumAfterIterations
{
class Program
{
//A = {5, 3, 8, 9, 16}
//After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7}
//After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9
//Given an array, return sum after n iterations
static void Main(string[] args)
{
int[] A = new int[] { 5, 3, 8, 9, 16 };
int iterations = 12;
int ans = SumAfterNIterations(A, iterations);
Console.WriteLine("answer is {0}", ans);
}
static int SumAfterNIterations(int[] array, int iterations)
{
int sum = 0;
if (array == null) return 0;
if (array.Length == 1) return array[0];
if (iterations < 1)
{
foreach (int i in array)
sum += i;
return sum;
}
int len = array.Length;
int round = 0;
while (len > 1 && round++ < iterations)
{
sum = 0;
for (int i = 0; i < len - 1; i++)
{
array[i] = array[i + 1] - array[i];
sum += array[i];
}
len--;
}
return sum;
}
}
}
Dupe of question?id=16390676.
There is an O(n) solution there, which uses Pascal's triangle.
void GetSum(array<int> input, int N)
{
if(N == 0)
{
int sum = 0;
for(int i = 1; i < input.length; i++)
{
sum += input[i] ;
}
return sum;
}
if(input.length == 1)
{
return 0;//error
}
int temp[input.length -1];
for(int i = 1; i < input.length; i++)
{
temp[i-1] = input[i];
}
for(int j = 0; j < temp.length; j++)
{
temp[j] = temp[j] - input[j];
}
GetSum(temp, N--);
}
Obviously it's recursion.
public class ArraySum {
public static int getSum(int[] a, int n) {
if (a.length < n || n == 1) {
int sum = 0;
for (int e : a) {
sum += e;
}
return sum;
}
int[] b = new int[a.length - 1];
for (int i = 0; i < b.length; i++) {
b[i] = a[i + 1] - a[i];
}
return getSum(b, n - 1);
}
public static void main(String[] args) {
int[] a = {5, 3, 8, 9, 16};
System.out.println(getSum(a, 3));
}
}
public long sumFromArray(int iNoOfIterations, int [] arrValues) {
long lSum = 0;
if(iNoOfIterations >= arrValues.length || iNoOfIterations < 0) return -1L;
if(iNoOfIterations == 0) for(int i = 0; i < arrValues.length; i++) lSum += arrValues[i];
else {
int iToCalc = 1;
while (iToCalc <= iNoOfIterations) {
int [] newArray = new int[arrValues.length - 1];
for(int i = 0; i < arrValues.length; i++) {
newArray[i] = (arrValues[i + 1] - arrValues[i]);
if(iToCalc == iNoOfIterations) lSum += newArray[i];
if( (i + 1) == arrValues.length - 1 ) break;
}
arrValues = newArray;
iToCalc++;
}
}
return lSum;
}
Here is the solution in C#
int[] array = {5,3,8,9,16};
int length = array.Length;
int[] inner = new int[4];
for(int k = 0;k<2;k++)
{
for(int i=1,j=0;i<length;i++,j++)
{
inner[j]=array[i]-array[i-1];
}
length = length - 1;
for(int l = 0;l< length;l++)
array[l] = inner[l];
}
inner.Take(length).Sum().Dump();
inner.Dump();
1) Here the sum is always first number in array - last number in array for the subsequent array.
2) So we have to find the first number and last number in the previous array.
3) For that we have to find a magic number which is as follows:
Iteration1: 1
which means 1st number = 1*a[0] ;second number = 1*a[n-1]
Iteration2: 10 +1 =11
which means 1st number = 1*a[0] -1*a[1] ; 2nd Number = 1*a[n-1] -1 *a[n-2];
Iteration3: 110 +11 =121
which means 1st number = 1*a[0] -2*a[1]+1*a[2] ; 2nd Number =1*a[n-1] -2 *a[n-2]+1*a[n-3]
Iteration4: 1210+121 =1331
Return firstnumber - secondnumber;
I'm not big on pasting links of previous solutions. Here is the solution I worked out, and checked against the previous link. It appears to have the same outcome, with some minor syntactical differences. The solution in the pasted link actually runs a sum on all elements at each new grouping. My algorithm takes advantage of the fact that each rows sum is equal to the previous rows firstElement - previous rows lastElement to save on computational power.
public static int operation(int[] a, int c){
int first = 0;
int last = 0;
int sum = 0;
int count = 0;
int length = a.length;
if(length == 1) {return a[0];}
if(c == 0){
for(int i = 0; i < a.length; i++){
sum += a[i];
}
return sum;
}
while(length > 1 && count < c){
first = a[0];
last = a[length-1];
for(int i = 0; i < length-1; i++){
a[i] = a[i] - a[i+1];
System.out.println(a[i] + " loop");
}
length--;
count++;
}
sum = first - last;
return sum;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args){
int[] main = {4,6,8,3,6};
int it = 6;
int result;
result = operation(main, it);
System.out.println(result);
}
Which solution are you talking about?
Loler's solution in the pasted link is much more efficient than yours.
If the array is of size N, and you do K iterations, Loler's solution will run very fast O(k) (independent of N), while your solution is O(N(K-1)), which is highly inefficient: consider the case N = 100 billion but k = 100.
class SumArray {
public static int sumOfArray(int[] A) {
if ( (A.length <= 0) || (A.length == 1) ) {
return(A[0]);
}
else if (A.length == 2) {
return(A[1] - A[0]);
}
else {
int[] B = new int[A.length - 1];
for(int i=1; i<A.length; i++) {
B[i-1] = A[i] - A[i-1];
}
return(sumOfArray(B));
}
}
public static void main(String[] args) {
int[] items = {4, 24, 68, 112};
System.out.println(sumOfArray(items));
}
}
If the array is of size N, and we are required to do k (>= 1) iterations, then it is possible to do this in O(k) time (yes, independent of N!), using the following observations:
- Loler March 27, 2013Observation 1)
If at some intermediate step the array was x_1, x_2, ..., x_M and we then performed one iteration on it, to get x_2 - x_1, ..., x_M - x_{M-1}, the sum of the elements is x_M - x_1.
Thus if you want to find the sum after k iterations, you need to find the first and last element after k-1 iterations and subtract.
Observation 2)
After r iterations, x_1, x_2, ..., x_M, the first element becomes
x_{r+1} - r x_r + (r choose 2) x_{r-1} - (r choose 3) x_{r-2} + ...
Similar formula can be given for the last term.
(Yes, those are binomial coefficients).
Observation 3)
r choose 0, r choose 1, r choose 2, ... r choose r, can be computed in O(r) time, by computing r choose t in O(1) time after already having computed r choose (t-1).