Amazon Interview Question Dev Leads
Country: United States
I think that the idea here is to do this in O(N) as the brute force algorithm take O(N^2). We can achieve an O(N) solution by have 1 loop which runs over the array and looks over a window of the array. This will use the fact that the array contains non negative numbers.
def find_continued_sub_arr(A, S):
i, j, sum = 0, 0, 0
while i < len(A) and j < len(A) and sum != S:
sum += A[j]
if sum < S:
j += 1
elif sum > S:
if i < j:
sum -= A[i]
i += 1
else:
i = j = i + 1
return None if sum != S else (i,j)
/******************************************************************************
Online C Compiler.
Code, Compile, Run and Debug C program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <stdio.h>
int main()
{
int temp,idx,i,start,end;
idx =0;
start = 0;
end = 0;
int a[]={2,0,1,2,4,4};
for (i=0;i<sizeof(a);i++)
{
temp += a[i];
if(temp > 7)
{
i = ++start;
temp = a[i];
}
if (temp == 7)
{
end =i;
++idx;
break;
}
}
if(idx == 0)
printf("xxx");
else
printf("%d %d",start, end);
return 0;
}
/******************************************************************************
Online C Compiler.
Code, Compile, Run and Debug C program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <stdio.h>
int main()
{
int temp,idx,i,start,end;
idx =0;
start = 0;
end = 0;
int a[]={2,0,1,2,4,4};
for (i=0;i<sizeof(a);i++)
{
temp += a[i];
if(temp > 7)
{
i = ++start;
temp = a[i];
}
if (temp == 7)
{
end =i;
++idx;
break;
}
}
if(idx == 0)
printf("xxx");
else
printf("%d %d",start, end);
return 0;
}
Since it says continuous sub array so i think it is asking for sonsecutive elements which gives the target.
def cont(array, s):
i, j, su = 0,0,0
while i<len(array) and j<len(array):
su += array[j]
if su==s:
if i!=j:
return i,j
else:
return i
if su < s:
j += 1
if su > s:
su -= array[i]
i += 1
j += 1
return
array = [7,8,3,2,1,5,4]
print(cont(array, 24))
private static int[] findSubArray(int[] array, int sum) {
int start = 0, end = 0;
int sum_temp = array[start];
for (;end<array.length;end++) {
if (end > 0) {
sum_temp += array[end];
}
if (sum_temp > sum) {
while (sum_temp > sum) {
sum_temp -= array[start];
start++;
}
}
if (sum_temp == sum) {
return Arrays.copyOfRange(array, start, end+1);
}
}
return new int[0];
}
Time complexity O(N)
private static int[] findSubArray(int[] array, int sum) {
int start = 0, end = 0;
int sum_temp = array[start];
for (;end<array.length;end++) {
if (end > 0) {
sum_temp += array[end];
}
if (sum_temp > sum) {
while (sum_temp > sum) {
sum_temp -= array[start];
start++;
}
}
if (sum_temp == sum) {
return Arrays.copyOfRange(array, start, end+1);
}
}
return new int[0];
}
Sliding window - O(n)
def sub_array_with_sum(arr: [int], sum: int) -> [int]:
window_sum = arr[0]
window_range = (0, 0)
if window_sum == sum:
return [0]
start = 1
for i in range(start, len(arr)):
window_sum += arr[i]
window_range[1] = i
while window_sum > sum:
window_sum -= arr[window_range[0]]
window_range[0] += 1
if window_sum == sum:
res = []
for j in range(window_range[0], window_range[1] + 1):
res.append(j)
return res
return [-1]
public class ContiguousSubarrayWithSum {
public static void main(String[] args) {
int[] array = {2,6,1,2,4,4};
int k = 7;
findSubArray(array,k);
}
public static void findSubArray(int[] array, int k){
int start = 0;
int sum = 0;
for (int i =0; i < array.length ; i++){
while (start < i && sum > k ){
sum -= array[start++];
}
if(sum == k){
int end = i-1;
System.out.println("Subarray found at : "+ start+ " "+ end);
}
if (i < array.length){
sum+= array[i];
}
}
}
}
private static int[] continuousSub(int[] arr, int i, int j, int csum, int sum){
if(arr==null||arr.length==0){
return new int[]{-1,-1};
}else if(sum==csum){
return new int[]{i,j};
}else if(csum>sum){
csum = csum - arr[i];
if(i==j){
if(++j==arr.length){
return new int[]{-1,-1};
}else{
csum+=arr[j];
}
}
++i;
}else{
if(++j==arr.length){
return new int[]{-1,-1};
}else{
csum = csum + arr[j];
}
}
return continuousSub(arr, i, j, csum, sum);
}
#Efficient Python Solution: Time complexity O(N), Space complexity O(1)
def subarray_sum(input, target_sum):
sub_start = 0
cur_sum = 0
for i, element in enumerate(input):
if cur_sum < target_sum:
cur_sum += element
while cur_sum > target_sum:
cur_sum -= input[sub_start]
sub_start += 1
if cur_sum == target_sum:
if sub_start != i:
return sub_start, i #must be two elements, not one equating sum
else:
sub_start += 1
#Efficient Python, Time O(N) and Space O(1)
def subarray_sum(input, target_sum):
sub_start = 0
cur_sum = 0
for i, element in enumerate(input):
if cur_sum < target_sum:
cur_sum += element
while cur_sum > target_sum:
cur_sum -= input[sub_start]
sub_start += 1
if cur_sum == target_sum:
if sub_start != i:
return sub_start, i #must be two elements, not one equating sum
else:
sub_start += 1
def find_sub_array(a, s):
- ash February 06, 2020for i in range(len(a)):
for j in range(len(a), i, -1):
sub = a[i:j]
total = sum(sub)
if total == s:
return sub
return None