## Amazon Interview Question for Dev Leads

Country: United States

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

def find_sub_array(a, s):
for 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

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

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

Comment hidden because of low score. Click to expand.
0
of 0 vote
I think that the idea is to use a solution that runs in O(N) which uses the fact that the array contains non-negative numbers. So if we run over the array in one loop which modifies a start and end indices it will do the magic. {{{ 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) }}
Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def find_sub_arr(arr, S):
for i1, e1 in enumerate(arr):
sub_sum = e1
if sub_sum == S:
return arr[i1:i1+1]
elif sub_sum > S:
continue

for i2, e2 in enumerate(arr[i1+1:], i1+1):
sub_sum += e2
if sub_sum == S:
return arr[i1:i2+1]
elif sub_sum > S:
break

return []``````

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

``````#include <stdio.h>

int main()
{
int temp,idx,i,start,end;
start = 0;
end = 0;
int a[]={2,6,2,1,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;
break;
}
}
printf("%d %d",start, end);
return 0;
}``````

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

#include <stdio.h>

int main()
{
int temp,idx,i,start,end;
start = 0;
end = 0;
int a[]={2,6,2,1,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;
break;
}
}
printf("%d %d",start, end);
return 0;
}

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

/******************************************************************************

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

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

``````/******************************************************************************

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

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

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

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

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

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

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

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

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

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

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

}
}``````

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

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

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

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

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````def find_sub_array(a, s):
for 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``````

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.