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.