Amazon Interview Question for SDE-3s


Country: India
Interview Type: In-Person




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

private int[] findSubSum(int[] a, int s) {
List<Integer> resIds = new ArrayList<>();
int t = 0;
int b = 0;
int c = 0;
for (int i = 0; i < a.length; i++) {
t += a[i]; c++;
if (t == s) {
return new int []{b,c};
} else if (t > s) {
t = c = 0;
i = b; // next loop will advance i
b = b + 1;
}
}
return null;
}

- Vu Kien April 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private int[] findSubSum(int[] a, int s) {
        List<Integer> resIds = new ArrayList<>();
        int t = 0;
        int b = 0;
        int c = 0;
        for (int i = 0; i < a.length; i++) {
            t += a[i]; c++;
            if (t == s) {
                return new int []{b,c};
            } else if (t > s) {
                t = c = 0;
                i = b; // next loop will advance i
                b = b + 1;
            }
        }
        return null;
    }

- Vu Kien April 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void subarraySumFind(int[] nums, int k) {
	        
		  int count =0, sum =0;
		  int start=0, end =-1;
		  
		  Map<Integer, Integer> map = new HashMap();
		  map.put(0, 1);
		  
		  for(int i=0; i< nums.length; i++){
			  
			  sum += nums[i];
			 
			  if(map.containsKey(sum-k)){
				  start = map.get(sum-k)-1;
				  end = i;
				  
				  System.out.println(start + " " + end);
			  }
			  
			  map.put(sum, i);
		  }
		  
		  
	    }

- him4211 April 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] FindSumSubArray(int[] arr, int expectedSum)
{
    int start = 0;
    int end = 0;
    int sum = arr[0];
    while(start < arr.Length && end < arr.Length)
    {
     if (sum == expectedSum)
          return arr.Skip(start).Take(end - start).ToArray();
    
     if(sum > expectedSum)
     {
          sum -= arr[start];
          start++;
      }

      if(sum < expectedSum)
      {
          end++;
          sum += arr[end];
       }
       throw new ArgumentException(“Cannot find subarray with given sum”);
}

- Denys April 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int[] GetSumArray(int[] ar, int sum, int end, int[] sub)
{
if (sum == 0)
return sub;
if (sum < 0 || end < 0)
return new int[0];
if (sum < ar[end])
{
return GetSumArray(ar, sum, end - 1,sub);
}
else
{
sub[end] = ar[end];
return GetSumArray(ar, sum - ar[end], end - 1, sub);

}
}

- laxman April 30, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int[] GetSumArray(int[] ar, int sum, int end, int[] sub)
        {
            if (sum == 0)
                return sub;
            if (sum < 0 || end < 0)
                return new int[0];
            if (sum < ar[end])
            {
                return GetSumArray(ar, sum, end - 1,sub);
            }
            else
            {
                sub[end] = ar[end];
                return GetSumArray(ar, sum - ar[end], end - 1, sub);
                    //+ GetSumCount(ar, sum, end - 1);
            }
        }

- laxman April 30, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int[] GetSumArray(int[] ar, int sum, int end, int[] sub)
        {
            if (sum == 0)
                return sub;
            if (sum < 0 || end < 0)
                return new int[0];
            if (sum < ar[end])
            {
                return GetSumArray(ar, sum, end - 1,sub);
            }
            else
            {
                sub[end] = ar[end];
                return GetSumArray(ar, sum - ar[end], end - 1, sub);
                    //+ GetSumCount(ar, sum, end - 1);
            }

}

- laxman April 30, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int[] GetSumArray(int[] ar, int sum, int end, int[] sub)    {             if (sum == 0)                 return sub;            if (sum < 0 || end < 0)                return new int[0];            if (sum < ar[end])            {                return GetSumArray(ar, sum, end - 1,sub);            }            else            {                sub[end] = ar[end];                return GetSumArray(ar, sum - ar[end], end - 1, sub);                    //+ GetSumCount(ar, sum, end - 1);            }        }

- laxman April 30, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We start from 0 and keeping track of the current sum of the current subarray (of len 1)
* If the cursum < sum => add next element to the end of the subarray (while updating the cursum)
* If the cursim > sum => start removing elements from the start of the subarry (while updating the cursum)
* If the cursum matches sum - return true

O(N) solution.
Here is the C++ implementation:

#include <vector>

using namespace std;
bool findSubArraySum(const vector<int>& arr, vector<int> &subarr, int sum)
{
    if(arr.empty()) { return false; }

    subarr.push_back(arr[0]);
    int subarrSum = arr[0];
    for(size_t i = 1; i < arr.size(); ++i) {
        if(subarrSum == sum) { return true; }
        while((subarrSum > sum) && !subarr.empty()) {
            // remove the first element from  subarr
            subarrSum -= subarr[0];
            subarr.erase(subarr.begin());
        }
        subarr.push_back(arr[i]);
        subarrSum += arr[i];
    }
    return false;
}

- PenChief May 01, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Runs in O(n)

csharp
private static int[] FindSubArrayForSum(int[] arr, int sum)
{
    // keeps running total/sum for array iteration
    var runningTotal = 0;

    // advances the first position to start iterating from
    var offset = 0;

    // keeps track of the sub array
    var subArray = new int[arr.Length];

    // iterate through the entire array starting from index = 0;
    for (var index = offset; index < arr.Length;)
    {
        // update sub array
        subArray[index - offset] = arr[index];

        // update running total and increment index
        runningTotal += arr[index++];

        // if we have the sum then return sub array containing
        // the sequence totaling to the specified sum
        if (runningTotal == sum)
        {
            return subArray;
        }

        // if running total is greater than sum then reset everything
        // and advance offset by 1. This will cause another array iteration
        // but instead of starting from 0, it will start at offset
        if (runningTotal > sum)
        {
            index = ++offset;
            runningTotal = 0;
            subArray = new int[arr.Length];
        }
    }

    return null;
}

Calling code

var arr = new int[6] { 1, 4, 20, 3, 10, 5 };
var sum = 33;

var subArray = FindSubArrayForSum(arr, sum);

Runs in O(n)

- avenoir May 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I didn't notice that someone is considering a negative sum as an input parameters, in that case an additional logic should be applied...
So, here is my solution:

public class SubarrayWithGivenSum {

  int[] isSubarrayExist(int[] array, int sum) {
    int f = 0; // from pointer
    int t = 0; // to pointer
    int currentSum = array[f];

    boolean reverseComparision = sum >= 0;

    while (t < array.length - 1 && f < array.length - 1) {
      if (currentSum == sum) {
        return new int[]{f, t};
      }

      if (reverseComparision) {
        if (currentSum < sum) {
          currentSum += array[++t];
        } else {
          currentSum -= array[f++];
        }
      } else {
        if (currentSum > sum) {
          currentSum += array[++t];
        } else {
          currentSum -= array[f++];
        }
      }
    }

    if (currentSum == sum) {
      return new int[]{f, t};
    }
    return new int[]{-1, -1};
  }
}

and set of parameterised test cases:

@Parameters
  public static Iterable<Object[]> data() {
    return Arrays.asList(new Object[][]{
        {new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 55, new int[]{0, 9}},
        {new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 56, new int[]{-1, -1}},
        {new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 16, new int[]{-1, -1}},
        {new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 15, new int[]{0, 4}},
        {new int[]{10, 10, 10, 10, 10, 10, 10, 10, 10}, 5, new int[]{-1, -1}},
        {new int[]{-10, -5, -6, -10, -10, 10, -10, 5, -10, -5, -10, -10, -1}, -50, new int[]{3, 11}}
    });
  }

- Mike L May 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def get_array(arrary,sum):

    subarray = []
    sub_sum = 0

    for elem in array:
        subarray.append(elem)
        sub_sum += elem

        if sub_sum == sum:
            return subarray

        if sub_sum > sum:
            sub_sum -= subarray[0]
            subarray = subarray[1:] # Remove first element


    return subarray

- Zeeshan May 16, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

typedef struct
{
int len;
int *arr;
}subarry;

subarry res;

subarry* find_sub_sum(int arr[],int sum,int len)
{
    int temp=0;
    int *r_arr,r_i=0;
    quick_sort(arr,0,len-1);
    r_arr = (int *) malloc(sizeof(int)*len);
    for(int i=len-1;i>=0;i--)
    {
        if(arr[i] > sum)
                continue;
        if(arr[i]+temp <= sum)
        {
                temp = arr[i]+temp;
                *(r_arr+r_i)=arr[i];
                r_i++;
        }
    }
    if(temp == sum)
    {
        res.len = r_i;
        res.arr = r_arr;
        return &res;
        }
    return NULL;
}

void main()
{
int arr[6] = {1,2,3,4,5,6},len = 6;
int sum = 22;
subarry *val;
val = find_sub_sum(&arr,sum,len);
if(val == NULL)
{
        printf("subarray not found \n");
        return;
}
else
{
        for(int i = 0;i<val->len;i++)
        {
                printf("%d ",*(val->arr+i));
        }
        printf("\n");
}
}

- Anonymous April 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess the subarray should be consequent...

- Mike L May 04, 2019 | 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