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

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

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

}``````

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

You should do

``start = map.get(sum-k) + 1``

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”);
}``````

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

}
}

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

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

}

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

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

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)

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

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``````

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");
}
}``````

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

I guess the subarray should be consequent...

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