Amazon Interview Question for SDE1s


Country: United States




Comment hidden because of low score. Click to expand.
9
of 9 vote

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)
2. ANSWER : return sum(x2) - sum(x1-1) - o(1)

- Naor October 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

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;
}

- kyduke October 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

preCalSum is O(n) so finally it is O(n) not O(1).

- SIVA R October 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

It can't be solved in O(1). It is because in order to find that sub sum at least we need to traverse from x1 to x2. If array elements holds the some of all previous elements then it is possible in O(1).

- SIVA R October 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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)

- mnicpt October 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1 for writing it in swift :p

- shobhit657 November 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n) complexity.

- Anonymous January 02, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- mostaqur October 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

k is running from min to max i.e O(n) in worst case.

- SIVA R October 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution. But it is not O(1) complexity.

def sum(arr,x1,x2):
    sum = 0
    for i in range(x1,x2+1):
        sum = sum+ arr[i]
    return sum
print sum([1,6,5,4], 1, 3)

- revanthpobala October 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

JavaScript - Not O(1), but O(n)

function sum(x1, x2, arr) {
    return arr.splice(x1, x2).reduce(function(prev, curr) {
		return prev += curr
    });
}

console.log(sum(1, 3, [1, 2, 3, 4, 5, 6, 7, 8]));

- jooka October 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N) worst case solution for unsorted array.

int Sum(int x1, int x2)
{
int sum = 0 ;
int start = -1 ;
int end = -1 ;

if(x1 < x2)
{
start = x1 ;
end = x2 ;
}
else if( x2 < x1)
{
start = x2 ;
end = x1 ;

}
else
return x1 ;

for( int i=start; i<=end ; i++)
{
sum += arr[i] ;
}

return sum ;
}

- Anonymous October 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N) worst case solution for unsorted array

int Sum(int x1, int x2)
{
	int sum = 0 ;
	int start = -1 ;
	int end = -1 ;
	
	if(x1 < x2)
	{
		start = x1 ;
		end = x2 ;
	}
	else if( x2 < x1)
	{
		start = x2 ;
		end = x1 ;
		
	}
	else
		return x1 ;
	
	for( int i=start; i<=end ; i++)
	{
		sum += arr[i] ;
	}
			
	return sum ;
}

- Tushar October 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- castro October 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Seems like we need to use concept similar to Fenwick Tree Data structure(Binary Indexed Tree).

- Ashwath November 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Looks like we need to use concept similar to Fenwick tree or Binary Indexed Tree.

- ashwath10110 November 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Build a "Segment Tree". Best data structure for range queries

- gameOfCode November 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * 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));


    }
}

- akkhil2012 December 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
}

- Mostaqur Rahamn October 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(max-min+1)...!!

- Shuboy October 27, 2015 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More