Amazon Interview Question
SDE1sCountry: India
Interview Type: Phone Interview
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();
}
}
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);
}
}
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);
}
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))
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))
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;
}
}
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();
}
}
}
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;
}
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;
}
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;
}
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;
}
Concise Backtracking Solution (Depth First Search)
Return -1 if there is no such subset.
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
- aonecoding February 22, 2017We 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.