Amazon Interview Question
SDE1sCountry: -
Interview Type: In-Person
I read the problem as being one where the number of holes are greater than or equal to the number of mice. In that regard, this would align well with a bipartite graph of mice to holes. To solve:
1. sort the array of mice based on position
2. sort the array of holes based on position
3. create graph. The edges should be relative to the size difference between the mice and hole arrays. (if |mice| == |holes|, then it would only be m1 -> h1. But if |holes| - |mice| = 1, then there would be 2 edges for each mouse, m1 -> h1, h2; m2 -> h2, h3; etc)
4. solve using a bipartite graph matching algorithm.
Solution complexity would be O( mice * (|holes| - |mice| + 1) ).
Yes, this is the correct answer. But we can optimize it. if |holes| - |mice| = 1,
and if mn stick to hn, but not hn+1, mn-i would stick to the original one
public int getMin(int[] mouse, int[] holes) {
if (mouse == null || holes == null) {
return -1;
}
int lenM = mouse.length;
int lenH = holes.length;
if (lenM == 0 || lenH == 0 || lenM > lenH) {
return -1;
}
int result = 0;
int[] position = new int[lenM];
for (int i = 0; i < lenM; i++) {
position[i] = i;
}
for (int i = lenM; i < lenH; i++) {
if (!adjust(mouse, holes, position, i, lenM - 1)) {
break;
}
}
for (int i = 0; i < lenM; i++) {
result = Math.max(result, Math.abs(mouse[i] - holes[position[i]]));
}
return result;
}
private boolean adjust(int[] mouse, int[] holes, int[] position,
int holeIndex, int lastMouse) {
if (lastMouse < 0) {
return false;
}
if (Math.abs(mouse[lastMouse] - holes[position[lastMouse]]) > Math
.abs(mouse[lastMouse] - holes[holeIndex])) {
position[lastMouse] = holeIndex;
adjust(mouse, holes, position, holeIndex - 1, lastMouse - 1);
return true;
}
return false;
}
##python##
print('mice')
mice=input().split(' ')
mice1=[]
for m in mice:mice1.append(int(m))
mice1.sort()
print('hole')
hole=input().split(' ')
hole1=[]
for h in hole:hole1.append(int(h))
hole1.sort()
temp=0
for a in range(len(mice1)):
k=abs(mice1[a]-hole1[a])
if temp<k:
temp=k
print(temp)
I will explain xlshi's solution.
Let the arrays be M and H for mice and hole respectively. Sort the arrays in ascending order
M : -4 2 4
H : 0 4 5
For any mice at position i all holes with position <i (in the array) will be further away when compared to hole at i (because the array is sorted in ascending order). Thus applying this logic recursively from the bottom of the array you will be able to get the final hole for each mouse and max time taken.
My solutions:
1) sort holes and mice
2) get the max difference between holes[i] and mice[i] 0<=i<holes.length
public int mouseAssignment(int[] holes, int[] mice){
if(holes==null || mice==null || holes.length==0 || mice.length==0 || holes.length!=mice.length){
return 0;
}
Arrays.sort(holes);
Arrays.sort(mice);
int maxTime = 0;
for(int i=0; i<holes.length; i++){
maxTime = Math.max(Math.abs(holes[i]-mice[i]), maxTime);
}
return maxTime;
}
I read the question as having a number of holes equal to or greater than the number of mice. If this were the case, then your approach would not be optimal.
Zortlord its right... lets say we have 3 mouses: -1 2 3
and these positions: -40 -20 0 1 4 5
His algorithm would return 39; the answer should be 2
@Fernando
If there are 3 mouse : -1 2 3
and holes are : -40 -20 0 1 4 5
Then the answer should be 1 not 2 as
(-1, 0) = 1
(2, 1) = 1
(3, 4) = 1
So ans = 1
Please correct if I am wrong.
Also we can approach like -
1) sort both the mouse and holes array
2) pick the first mouse and find the point where the absolute diff between mouse and hole is minimum
3) Now perform the diff operation from this point in holes array.
int HolesMice(vector<int> &mice, vector<int> &holes, map<int,int> &assignment)
{
//DO pre-checks.
const int invalidInput = -1;
if(mice.size() == 0 || holes.size() != mice.size())
return invalidInput;
int maxTime = INT_MIN;
sort(mice.begin(), mice.end());
sort(holes.begin(), holes.end());
transform(mice.begin(), mice.end(), holes.begin(), inserter(assignment,assignment.end()), [&](int a,int b)
{
maxTime=max(maxTime,abs(abs(a)-abs(b)));
return make_pair(a,b);
}
);
return maxTime;
}
BOOST_AUTO_TEST_CASE(TestHolesMice)
{
int _mice[] = {2,3,5,7,10};
int _holes[] = {7,11,14,12,15};
vector<int> mice;
mice.assign(_mice,_mice+5);
vector<int> holes;
holes.assign(_holes,_holes+5);
map<int,int> assignment;
BOOST_CHECK(HolesMice(mice, holes, assignment) == 8);
BOOST_CHECK(assignment[_mice[0]] == 7);
BOOST_CHECK(assignment[_mice[4]] == 15);
}
import java.util.Arrays;
public class MouseHole {
public static void main(String[] args) {
int[] Mouse = {4,-4,2};
int[] Hole = {4,0,5};
getMax(Hole,Mouse);
}
static void getMax(int[] Hole , int[] Mouse) {
Arrays.sort(Hole);
Arrays.sort(Mouse);
int max = Integer.MIN_VALUE;
for(int i=0;i<Hole.length;i++) {
max = Math.max(Math.abs(Hole[i]-Mouse[i]), max);
}
System.out.println(max);
}
}
1) store mice & holes positions in two different array
2)sort both arrays
3)Remove common elements
4)now iterate through each index,subtract elements on same index and store the sum.
Ex :
sorted array will be :
0 4 5
-4 2 4
after removing common elements arrays will be
0 5
-4 2
so sum would be
|(-4-0) |+ |(2-5)| = 7
This will not provide the optimal answer. If the holes are {1, 2, 3} and the mice are {2, 3, 4}, then it will report the best time as 3 minutes when the best time could be 1 minute.
- Anonymous September 14, 2014