Amazon Interview Question SDE-3s
0of 0 votesFind a subarray with a give sum
Country: India
Interview Type: In-Person
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;
}
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);
}
}
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”);
}
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);
}
}
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);
}
}
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); } }
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;
}
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)
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}}
});
}
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");
}
}
private int[] findSubSum(int[] a, int s) {
- Vu Kien April 12, 2019List<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;
}