Amazon Interview Question for SDE1s


Country: India
Interview Type: Phone Interview




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

Concise Backtracking Solution (Depth First Search)
Return -1 if there is no such subset.

public int lengthOfNSum(int[] array, int n) {
        return lengthOfNSumRec(array, n, 0);
    }

    private int lengthOfNSumRec(int[] array, int n, int start) {
        if(n < 0) {
            return -1;
        }
        if(n == 0) {
            return 0;
        }
        for(int i = start; i < array.length; i++) {
            int len = lengthOfNSumRec(array, n - array[i], i + 1);
            if(len >= 0) {
                return len + 1;
            }
        }
        return -1;
    }

Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews. All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions.

- aonecoding February 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The dp approach to find the length of subset whose sum is equals to the given sum

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    TreeMap<Integer,Integer> tmap=new TreeMap<Integer,Integer>();
	int k=6;
	void calSum(int b,int e,int a[]){
		
		int tempSum=0;
		for(int i=b;i<=e;i++){
			tempSum=tempSum+a[i];
			}
			if(tempSum==k){
				
		tmap.put(e-b+1,e-b+1);
			}
		
	}
	
	int  function(int beg,int end ,int arr[]){
		if(beg<=end){
		calSum(beg,end,arr);
		function(beg+1,end-1,arr);
		function(beg+1,end,arr);
		function(beg,end-1,arr);}
		else{
			
		return 0;	
			
		}
		
	return 0;	
		
	}
	
	void seeResult(){
		System.out.println(tmap.lastKey().toString());
		
	}
	
	
	public static void main (String[] args) throws java.lang.Exception
	{
		int array[]={-2,1,-3,4,-1,2,1,-5,4};
		
		Ideone id=new Ideone();
		id.function(0,array.length-1,array);
		id.seeResult();
		
	}
}

- Harsh Bhardwaj February 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package problems;

import java.util.HashMap;
import java.util.Map;

public class problem5 {

	static int[] A={1,2,1,2,3,7,1,3,2,1};
	int M=5;
	static Map map1;
	int total=0;
	public  int getSum(int []A,int start , int end ){
		
	 total =total+A[end];
	   if(total==M){
		   System.out.println(" start "+start+" end "+end);
	        return total;
	}else if (total<M){		
		return getSum(A, start ,  ++end );
	}else if (total>M){
		start++;
		total=A[start];
		end=start+1;
	  return  getSum(A, start ,  end );
	}

      return total;
	}
	
	

	public static void main (String argsv []){
		
	problem5 p = new problem5();
	p.getSum(A,0,0);
	
	}
}

- Ayman Elgharabawy February 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void FindSubset(int[] arr, int number)
        {
            int ctr = 0;
            bool hasSubset;
            for (int i=0; i<arr.Length; i++)
            {
                hasSubset = false;
                int sum = arr[i];
                ctr++;
                if (sum == number) // the element value = number 
                {
                    hasSubset = true;
                    break;
                }
                for (int j=i+1; j<arr.Length; j++)
                {
                    sum += arr[j];
                    ctr++;
                    if (sum == number)
                    {
                        hasSubset = true;
                        break;
                    }
                    else if (sum > number)
                    {
                        ctr = 0;
                        break;
                    }
                }
                if (hasSubset)
                    break;
                else
                    ctr = 0;
            }
            Console.WriteLine(ctr);
        }

- ChihHo.Chou February 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* Sounds like cheating - it is not 
   The problem of iterating over power set 
   is done by sequences() function */
a = [1,2,3,20,4,9,89,54,21]
k = 16 
v = find( sequences( [0:size(a)] ) ) :: {
  sum( $.o ) -> { a[$.o] } == k 
}
printf( 'Indices are: %s, size: %d\n', v.value, size(v.value) )

- NoOne February 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python 3 DP solution

arr_input = [1, 5, 7, 78, 88, 9, 4, 6, 89, 54, 21, 345, 12, 145]
n_input = 152


def find_subset(arr, n):
    return find(arr, n, 0, len(arr))


def find(arr, n, si, ei):
    if n < 0:
        return None

    if n == 0:
        return []

    for i in reversed(range(si, ei)):
        if arr[i] <= n:
            result = find(arr, n - arr[i], si, i)
            if result is not None:
                result.append(arr[i])
                return result

    return None


print('Input array: ', arr_input)
print('N: ', n_input)
print('Solution: ', find_subset(sorted(arr_input), n_input))

- Anonymous February 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python 3 DP solution

arr_input = [1, 5, 7, 78, 88, 9, 4, 6, 89, 54, 21, 345, 12, 145]
n_input = 152


def find_subset(arr, n):
    return find(arr, n, 0, len(arr))


def find(arr, n, si, ei):
    if n < 0:
        return None

    if n == 0:
        return []

    for i in reversed(range(si, ei)):
        if arr[i] <= n:
            result = find(arr, n - arr[i], si, i)
            if result is not None:
                result.append(arr[i])
                return result

    return None


print('Input array: ', arr_input)
print('N: ', n_input)
print('Solution: ', find_subset(sorted(arr_input), n_input))

- Toxaxaxa February 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java version of solution

public class SubArrayFindAlg {

	static int[] givenNumbers = { 1, 3, 5, 7, 11, 13, 17, 19, 1, 1, 23, 29 };

	static int expSum = 30;

	public static void main(String[] args) {
		findIt(0, 0);
	}

	private static void findIt(int start, int end) {
		long sum = sum(start, end);
		if (sum < expSum) {
			findIt(start, nextIndex(end));
		} else if (sum > expSum) {
			findIt(nextIndex(start), end);
		} else {
			for (int i = start; i <= end; i++) {
				System.out.print(" " + givenNumbers[i]);
			}
		}
	}

	private static int nextIndex(int index) {
		if (index + 1 > givenNumbers.length) {
			System.out.println("can't locate subarray for sum " + expSum);
			System.exit(0);
		}
		return ++index;
	}

	private static long sum(int start, int end) {
		long sum = 0;
		for (int i = start; i <= end; i++) {
			sum += givenNumbers[i];
		}
		return sum;
	}

}

- ricoto February 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ArraynNumber {

public void subsetsCheckSum(int[] arr, int num) {
int n = arr.length;
int sum;
List<Integer> listel = new ArrayList<Integer>();

if (arr.length >= 1) {
// Run a loop for printing all 2^n
// subsets one by one
for (int i = 0; i < (1 << n); i++) {
listel.clear();
sum = 0;
// Print current subset
for (int j = 0; j < n; j++) {
// (1<<j) is a number with jth bit 1
// so when we 'and' them with the
// subset number we get which numbers
// are present in the subset and which
// are not
if ((i & (1 << j)) > 0)
listel.add(arr[j]);
}
for (int k = 0; k < listel.size(); k++) {
sum = sum + listel.get(k);
}
if (num == sum) {
System.out.println(listel.toString());
Collections.reverse(listel);
System.out.println(listel.toString());
}
}
}
}

public static void main(String[] args) {
int number;
ArraynNumber anr = new ArraynNumber();
List<Integer> list = new ArrayList<Integer>();

Scanner scr = new Scanner(System.in);

try {
number = Integer.parseInt(scr.nextLine());

while (list.isEmpty()) {
String str = scr.nextLine();
String[] strArray;

strArray = str.split(" ");
for (int i = 0; i < strArray.length; i++) {
list.add(Integer.parseInt(strArray[i]));
}
}

int[] myArray = new int[list.size()];

for (int j = 0; j < list.size(); j++) {
myArray[j] = list.get(j);
}
anr.subsetsCheckSum(myArray, number);
} catch (Exception e) {
e.printStackTrace();
} finally {
scr.close();
}
}
}

- rohit.emmadishetty February 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private int lengthOfSubset(int[] a, int sum) {
int[][] dp = new int[a.length+1][sum+1];
for(int i=0; i<=a.length; i++) {
dp[i][0] = 1;
}

for(int i=1; i<=a.length; i++) {
for(int j=1; j<=sum; j++) {
dp[i][j] = dp[i-1][j];
if(j >= a[i-1] && dp[i][j] < dp[i-1][j-a[i-1]]) {
dp[i][j] = dp[i-1][j-a[i-1]]+1;
}
}
}
return dp[a.length][sum]-1;
}

- Anonymous March 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private int lengthOfSubset(int[] a, int sum) {
int[][] dp = new int[a.length+1][sum+1];
for(int i=0; i<=a.length; i++) {
dp[i][0] = 1;
}

for(int i=1; i<=a.length; i++) {
for(int j=1; j<=sum; j++) {
dp[i][j] = dp[i-1][j];
if(j >= a[i-1] && dp[i][j] < dp[i-1][j-a[i-1]]) {
dp[i][j] = dp[i-1][j-a[i-1]]+1;
}
}
}
return dp[a.length][sum]-1;
}

- Anonymous March 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private int lengthOfSubset(int[] a, int s) {
int[][] dp = new int[a.length+1][s+1];
for(int i=0; i<=a.length; i++) {
dp[i][0] = 1;
}

for(int i=1; i<=a.length; i++) {
for(int j=1; j<=s; j++) {
dp[i][j] = dp[i-1][j];
if(j >= a[i-1] && dp[i][j] < dp[i-1][j-a[i-1]]) {
dp[i][j] = dp[i-1][j-a[i-1]]+1;
}
}
}
return dp[a.length][s]-1;
}

- pankaj kumar March 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private int lengthOfSubset(int[] a, int s) {
int[][] dp = new int[a.length+1][s+1];
for(int i=0; i<=a.length; i++) {
dp[i][0] = 1;
}
for(int i=1; i<=a.length; i++) {
for(int j=1; j<=s; j++) {
dp[i][j] = dp[i-1][j];
if(j >= a[i-1] && dp[i][j] < dp[i-1][j-a[i-1]]) {
dp[i][j] = dp[i-1][j-a[i-1]]+1;
}
}
}
return dp[a.length][s]-1;
}

- pankaj kumar March 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static boolean hasSub(int[] arr , int desired){
		int sum=0,s=0,e=0,l = arr.length;	
		while (s<=l && e<=l){
			if (sum<desired && e<l){
				sum+=arr[e];
				e++; // index outofbounds
			}else if (sum>desired && s<l){
				sum-=arr[s];
				s++;
			}else break;			
		}
		if (sum == desired) return true;		
		return false;

}

- EE66 July 01, 2017 | Flag Reply


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