Amazon Interview Question
0of 0 votesGiven 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
Country: United States
+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 :)
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).
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));
}
}
}
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.
Here is my method.
- Anonymous on August 05, 2012 Edit | Flag Reply{{
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);
}
}
}}