Amazon Interview Question
SDE1sCountry: United States
c++, implementation, O(1)
preCalcSum: O(n)
typedef long long INT64;
vector<INT64> sums;
void preCalcSum(vector<int>& arr) {
int i;
if (arr.size() == 0) return;
sums.clear();
sums.assign(arr.size() + 1, 0);
for (i = 0; i < arr.size(); i++) {
sums[i + 1] = sums[i] + arr[i];
}
}
int subSum(vector<int>& arr, int x1, int x2) {
if (x1 > x2 || x1 < 0 || x2 >= arr.size()) return 0;
return sums[x2 + 1] - sums[x1];
}
int main() {
int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<int> arr(data, data + 10);
preCalcSum(arr);
cout << subSum(arr, 0, 9) << "\n"; // 55
cout << subSum(arr, 0, 0) << "\n"; // 1
cout << subSum(arr, 9, 9) << "\n"; // 10
cout << subSum(arr, 2, 7) << "\n"; // 33
cout << subSum(arr, -1, 9) << "\n"; // 0
cout << subSum(arr, 0, 10) << "\n"; // 0
cout << subSum(arr, 9, 0) << "\n"; // 0
return 0;
}
Swift:
var arr = [1, 5, 4, 9, 75, 23]
func sum(arr: [Int], x1: Int, x2: Int) -> Int {
var total = 0
for i in x1...x2 {
total += arr[i]
}
return total
}
sum(arr, x1: 1, x2: 3)
private static int sum(int[] array, int i, int j) {
int min = (i <= j) ? i : j;
int max = (i >= j) ? i : j;
if(max+1 > array.length) {
return 0;
}
int sum = 0;
for (int k = min; k < max + 1 ; k++) {
sum += array[k];
}
return sum;
}
Let say x1 is zero and x2 is length of array, is there any way to get the sum without going through all elements? Probaby not, hence it cannot be O(n).
However if x1 and x2 are fixed within range of the array, we can achieve x2-x1 which is a constant irrespective of the size of the array. This only work if preprocessing is done as suggested by Naor
/**
* Created by akhil on 12/13/2015.
*/
public class DiffBetweenIndices {
public static int difBetween(int[] arr, int a, int b) {
int sum = 0;
for (int i = 0; i < arr.length; i++) {
arr[i] = sum + arr[i];
sum = arr[i];
}
for (int i : arr) {
System.out.print(" " + i + " ");
}
return arr[b] - arr[a];
}
public static void main(String args[]) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// difBetween(arr,0,4);
System.out.print(" Diff is " + difBetween(arr, 0, 4));
}
}
private static int sum(int[] array, int i, int j) {
int min = (i <= j) ? i : j;
int max = (i >= j) ? i : j;
if(max+1 > array.length) {
return 0;
}
int sum = 0;
for (int k = min; k < max + 1 ; k++) {
sum += array[k];
}
return sum;
}
1.PREPROCCESS : Every element saves the sum of all the integers from left include itself (sum 0...i). We can do it by passing the array from left to right o(n)
- Naor October 27, 20152. ANSWER : return sum(x2) - sum(x1-1) - o(1)