Amazon Interview Question

  • amazon-interview-questions
    0
    of 0 votes
    11
    Answers

    Given the array of digits, you have to calculate the least positive integer value of the expression that could NOT have been received by you.
    The binary operators possible are *, +, -, / and brackets possible are ( and ). Note that / is an integer division i.e. 9/5 = 1.
    For ex- 6 6 4 4 the answer is 18
    1 = 6 /6 + 4-4

    2 = 6/6 + 4/4

    3 = 6 +( 6/4) -4

    4 = (6+6+4) / 4

    ……..

    18 cannot be formed

    - Barney on August 05, 2012 in United States Report Duplicate | Flag
    Amazon Algorithm

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) {
results.add(left + right);
results.add(left - right);

results.add(left * right);
if(right != 0) {
results.add(left / right);
}

}

}
}

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

- Anonymous on August 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

+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 :)

- GKalchev on August 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What about the braces?

6 * (6 + 4) * 4

- dc360 on August 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I see. Looks like the recursion handles it automatically

- dc360 on August 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- dc360 on August 11, 2012 | Flag
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)
{
list.add(sum);
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).

- Roopam Saxena on August 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- hari@hbiz.in on August 11, 2012 | Flag
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){
deal.add(test[begin]);
return deal;
}
HashMap<Integer,Boolean> keep=new HashMap<Integer,Boolean>();
if(begin==end-1){
deal.add(test[begin]+test[end]);
keep.put(test[begin]+test[end], true);

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

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

if(test[end]!=0){

if(!keep.containsKey(test[begin]/test[end])){
deal.add(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))){
deal.add(left.get(i)+right.get(j));
keep.put(left.get(i)+right.get(j), true);
}

if(!keep.containsKey(left.get(i)-right.get(j))){
deal.add(left.get(i)-right.get(j));
keep.put(left.get(i)-right.get(j), true);
}
if(!keep.containsKey(left.get(i)*right.get(j))){
deal.add(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))){
deal.add(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));
}

}

}

- Chengyun Zuo on August 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Malluce on August 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Chengyun Zuo on August 16, 2012 | Flag
Comment hidden because of low score. Click to expand.


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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