## Amazon Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
3
of 5 vote

Here is my method.
{{
import java.util.*;
public class Generate {
//start and end are inclusive
private static Set<Integer> eval(int[] values, int start, int end) {

if(start == end) {
return Collections.singleton(values[start]);
}

Set<Integer> results = new HashSet<Integer>();
//now break the array
// first array is from [start to i] and second array if from (i, end]
for (int i = start; i < end; i++) {
Set<Integer> lefts = eval(values, start, i);
Set<Integer> rights = eval(values, i + 1, end);

for(int left : lefts) {
for(int right: rights) {

if(right != 0) {
}

}

}
}

return results;
}

public static void main(String[] args) {
Set<Integer> a = eval(new int[]{6,6, 4, 4}, 0, 3);
int i=1;
while (a.contains(i)) {
i++;
}
System.out.println("number is:" + i);
}
}
}}

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

+1
Good solution! The complexity here is n*(4^n) I think. The following lines:

``````Set<Integer> lefts = eval(values, start, i);
Set<Integer> rights = eval(values, i + 1, end);``````

in your code you calculate multiple times same values. So keeping the previously calculated values will be a good optimization (memoization using for example start and end as keys) - this is only if you have very very much memory or very short array :)

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

``6 * (6 + 4) * 4``

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

I see. Looks like the recursion handles it automatically

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

Actually the recursive solution to solve left and right parts separately won't work if the condition of braces is not included in the problem statement because of precedence of operators.

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

suppose ther is an empty list.

void find(int A[ ], int size , int index, int sum)
{
if(index >size)
{
return;
}
else
{
for(int i =0; i<4; i++)
{
if(i==0)
{
sum = sum + A[index];
find(A, size, ++index, sum);
}
if(i==1)
{
sum = sum - A[index];
find(A, size, ++index, sum);
}
if(i==2)
{
sum = sum * A[index];
find(A, size, ++index, sum);
}
if(i==3)
{
sum = sum / A[index];
find(A, size, ++index, sum);
}
}
}
}

List contain all the number that can be generated by given numbers
so find the smallest no. not present in list in O(nlogn) time using sorting.

note brackets can be there means all possible combination means brackets are making it easy.
the program will take O(4^n).

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

I believe your algorithm won't work or I misunderstood it, can you prove how your algorithm will generate a value 15?

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

package amazon;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

public class Get_All_Possible_Results {

public static ArrayList<Integer> compute(int[] test,int begin,int end, ArrayList<Integer> deal){
if(begin==end){
return deal;
}
HashMap<Integer,Boolean> keep=new HashMap<Integer,Boolean>();
if(begin==end-1){
keep.put(test[begin]+test[end], true);

if(!keep.containsKey(test[begin]-test[end])){
keep.put(test[begin]-test[end], true);
}

if(!keep.containsKey(test[begin]*test[end])){
keep.put(test[begin]*test[end], true);
}

if(test[end]!=0){

if(!keep.containsKey(test[begin]/test[end])){
keep.put(test[begin]/test[end], true);
}
}
return deal;
}

for(int let=begin;let!=end;let++){
ArrayList<Integer> left=compute(test,begin,let,new ArrayList<Integer>());
ArrayList<Integer> right=compute(test,let+1,end,new ArrayList<Integer>());
for(int i=0;i!=left.size();i++){
for(int j=0;j!=right.size();j++){
if(!keep.containsKey(left.get(i)+right.get(j))){
keep.put(left.get(i)+right.get(j), true);
}

if(!keep.containsKey(left.get(i)-right.get(j))){
keep.put(left.get(i)-right.get(j), true);
}
if(!keep.containsKey(left.get(i)*right.get(j))){
keep.put(left.get(i)*right.get(j), true);
}
if(right.get(j)!=0){
if(!keep.containsKey(left.get(i)/right.get(j))){
keep.put(left.get(i)/right.get(j), true);
}
}
}
}
}

return deal;
}
public static void main(String[] args) {
int [] test=new int[]{6,6,4,4};
ArrayList<Integer> results=compute(test,0,test.length-1,new ArrayList<Integer>());
Collections.sort(results);
for(int i=0;i!=results.size();i++){
System.out.println(results.get(i));
}

}

}

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

Can you explain your code? Also, I'm wondering how to handle the case where you can repeat the operators. The way I think about this question is that given an array of ints. I will have length - 1 place to put operators (e.g., 6_6_4_4). With total of 5 operators (Because you cannot have a bracket alone) we can find a permutation solution. So far that's all I got...I can't think of any efficient way to do this.

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

If you run my code, you will know I am correct.

Comment hidden because of low score. Click to expand.

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.