## Adobe Interview Question

Member Technical Staffs**Country:**India

**Interview Type:**In-Person

```
Scanner scanner = new Scanner(System.in);
try {
System.out.println("Please enter number of machine: ");
int n = scanner.nextInt();
System.out.println("Please enter defected number of machine: ");
int m = scanner.nextInt();
System.out
.println("Please enter standard ouput of a non-defective machine: ");
int x = scanner.nextInt();
int[][] machines = new int[n][2];
for (int i = 1; i <= n; i++) {
System.out.println("Enter machine number: ");
int machine = scanner.nextInt();
System.out.println("Enter machine output: ");
int output = scanner.nextInt();
machines[i - 1][0] = machine;
machines[i - 1][1] = output;
}
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
for (int i = 0; i < machines.length; i++) {
int[] arr = machines[i];
if (map.containsKey(arr[1])) {
List<Integer> list = map.get(arr[1]);
list.add(arr[0]);
map.put(arr[1], list);
} else {
List<Integer> list = new ArrayList<Integer>();
list.add(arr[0]);
map.put(arr[1], list);
}
}
System.out.println("Defective machines are " + map.get(x - 1));
} catch (Exception e) {
e.printStackTrace();
} finally {
scanner.close();
}
```

If there are n machines and m of them are defective, we can do following procedure:

1.Label machines from #1 to #n

2.Divide them in sets with each set having m+1 machines.

If n = k*(m+1) + r then there will be k+1 sets with k having exactly m+1 machines and 1 last set having r machines. Remember that r can be at max m (max value of n%(m+1))

3.For each of the k+1 sets, get a coin from each machine from the set. Now, take a coin and do its weight comparison with all other coins. (total m comparisons).

4.If all coins are of same weight, we move to next set. If not, we may get a few coins less heavy and therefore the corresponding machines are defective. If the number of defective machines found in a set is already equal to m, we are done else move to the next set.

=>So, in the above method, we are doing in worst scenario doing max comparisons possible which equals: k*(m) + (r-1). Since, k = n/(m+1) and r = n%(m+1), we can write this in terms of n and m as follows: (n/(m+1))*m + n/(m+1) - 1

Its about choosing the right number for identifying the machines. Lets say machines are numbered from 1....to...10.

Start picking Fibonacci numbers of coins from each machine. For example

Machine1 : 1

Machine2 : 2

Machine3 : 3

Machine4 : 5

Machine5 : 8

Machine6 : 13

......And so on.

Total weight of coins will tell you the combination of Fibonacci numbers.

lets say number increased or decreased by

5 then defective coins belongs to 3,2

similarly diff 8 (5,3) ,13(8,5) and so on.

public static void main(String[] args) {

int n = 10; // Number of machines

int actualWeight = 354; // Actual weight of all coins

int temp, diff, totalWeight = 0;

List<Integer> lst = new ArrayList<Integer>();

lst.add(1);

lst.add(2);

for (int i = 2; i <= n; i++) {

temp = lst.get(i - 2) + lst.get(i - 1);

lst.add(temp);

}

for (int j = 0; j < lst.size(); j++) {

totalWeight = totalWeight + lst.get(j);

}

diff = totalWeight - actualWeight;

diff = diff * 2;

System.out.println(diff);

loop: for (int i = 0; i < lst.size(); i++) {

for (int j = lst.size() - 1; j >= 0; j--) {

if (diff == (lst.get(j) + lst.get(i)) && j != i) {

System.out.println("Defective machines are: " + i + " & "+ j);

break loop;

}

}

}

}

int n = 10; // Number of machines

int actualWeight = 354; // Actual weight of all coins

int temp, diff, totalWeight = 0;

List<Integer> lst = new ArrayList<Integer>();

lst.add(1);

lst.add(2);

for (int i = 2; i <= n; i++) {

temp = lst.get(i - 2) + lst.get(i - 1);

lst.add(temp);

}

for (int j = 0; j < lst.size(); j++) {

totalWeight = totalWeight + lst.get(j);

}

diff = totalWeight - actualWeight;

diff = diff * 2;

System.out.println(diff);

loop: for (int i = 0; i < lst.size(); i++) {

for (int j = lst.size() - 1; j >= 0; j--) {

if (diff == (lst.get(j) + lst.get(i)) && j != i) {

System.out.println("Defective machines are: " + i + " & "+ j);

break loop;

}

}

}

```
int n = 10; // Number of machines
int actualWeight = 354; // Actual weight of all coins
int temp, diff, totalWeight = 0;
List<Integer> lst = new ArrayList<Integer>();
lst.add(1);
lst.add(2);
for (int i = 2; i <= n; i++) {
temp = lst.get(i - 2) + lst.get(i - 1);
lst.add(temp);
}
for (int j = 0; j < lst.size(); j++) {
totalWeight = totalWeight + lst.get(j);
}
diff = totalWeight - actualWeight;
diff = diff * 2;
System.out.println(diff);
loop: for (int i = 0; i < lst.size(); i++) {
for (int j = lst.size() - 1; j >= 0; j--) {
if (diff == (lst.get(j) + lst.get(i)) && j != i) {
System.out.println("Defective machines are: " + i + " & "+ j);
break loop;
```

```
public static void main(String[] args) {
int n = 10; // Number of machines
int actualWeight = 354; // Actual weight of all coins
int temp, diff, totalWeight = 0;
List<Integer> lst = new ArrayList<Integer>();
lst.add(1);
lst.add(2);
for (int i = 2; i <= n; i++) {
temp = lst.get(i - 2) + lst.get(i - 1);
lst.add(temp);
}
for (int j = 0; j < lst.size(); j++) {
totalWeight = totalWeight + lst.get(j);
}
diff = totalWeight - actualWeight;
diff = diff * 2;
System.out.println(diff);
loop: for (int i = 0; i < lst.size(); i++) {
for (int j = lst.size() - 1; j >= 0; j--) {
if (diff == (lst.get(j) + lst.get(i)) && j != i) {
System.out.println("Defective machines are: " + i + " & "+ j);
break loop;
}
}
}
}
```

```
public static void main(String[] args) {
int n = 10; // Number of machines
int actualWeight = 354; // Actual weight of all coins
int temp, diff, totalWeight = 0;
List<Integer> lst = new ArrayList<Integer>();
lst.add(1);
lst.add(2);
for (int i = 2; i <= n; i++) {
temp = lst.get(i - 2) + lst.get(i - 1);
lst.add(temp);
}
for (int j = 0; j < lst.size(); j++) {
totalWeight = totalWeight + lst.get(j);
}
diff = totalWeight - actualWeight;
diff = diff * 2;
System.out.println(diff);
loop: for (int i = 0; i < lst.size(); i++) {
for (int j = lst.size() - 1; j >= 0; j--) {
if (diff == (lst.get(j) + lst.get(i)) && j != i) {
System.out.println("Defective machines are: " + i + " & "+ j);
break loop;
}
}
}
}
```

Note that there is a simpler version

- Sidharth Ghoshal September 11, 2015We have 10 machines and 1 machine is defective with known defect X-1 vs. The rest have X

We then label them 1, 2, 3.... 10

Then take 1 coin from 1, 2 coins from 2 etc...

If they are all fine then we will see 55X as the weight

But if the weight is 55X - M.

Then find Max J s.t. ((55X - M)-55X)/J = -1

That is the machine #.

Now suppose instead you are dealing with m machines with n defective ones whereas X here no indicates the maximum possible weight of an individual coin, including defects.

Take 1 of machine 1, X+1 of machine 2, (X+1)^2 of machine 3 .... (X+1)^(m-1) of machine m.

Call the weight of this combination T. Then the weight expressed in base X+1 can have each coefficient read off to determine exactly what weight of coin is being generated by that machine.