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

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

I guess the subarray should be consequent...

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.

### 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.